CephのCRUSHデータ分布アルゴリズムの紹介
4587 ワード
CephのCRUSHデータ分布アルゴリズムの紹介
概要
CRUSHはcephのモジュールであり、主に制御可能、拡張可能、中心化されたデータコピー分布の問題を解決する.CephはCRUSH(拡張可能な擬似ランダムデータ分布アルゴリズム)を設計し、分散オブジェクトストレージシステム上でデータオブジェクトをストレージデバイス上に効率的にマッピングすることができる(センタデバイスを必要としない).大規模なシステムの構造が動的に変化するため、CRUSHはストレージデバイスの追加と削除を処理し、ストレージデバイスの追加と移動によるデータ移行を最小限に抑えることができる.オブジェクトストレージデバイス(object-based storage devices)は、ディスク・データ・ブロックの割り当てを管理し、オブジェクトの読み書きインタフェースを提供する.一部のオブジェクトストレージシステムでは、各ファイルのデータは、ストレージクラスタ全体に分布する複数のオブジェクトに分割される.オブジェクトストレージシステムは、データ層を簡略化する(データブロックリストをオブジェクトリストに変換し、低レベルのデータブロック割り当て問題を各デバイスに渡す).オブジェクトストレージシステムの基本的な問題は、数千のストレージデバイスにデータをどのように分散するかです.1つのrobustソリューションは、データをランダムにストレージデバイスに分散することです.この方法は、負荷の均衡を保証し、新しいデータと古いデータの混合を保証します.しかし,単純HASH分布ではデバイス数の変化を効率的に処理できず,大量のデータ移行を招く.CephはCRUSH(Controoled Replication Under Scale Hashing)を開発し,階層構造のストレージクラスタにおいてオブジェクトのコピーを効率的に分散できる擬似ランダムデータ分布アルゴリズムを開発した.CRUSHは、object idまたはobject group idのパラメータを持つ擬似ランダム(決定的)関数を実現し、objectコピーを保存するためのストレージデバイスのセットを返します.CRUSHにはcluster map(ストレージクラスタの階層構造を記述する)、レプリカ分散ポリシー(rule)が必要です.CRUSHには2つの重要な利点があります.追加デバイスを削除する場合にのみ、これらのメタデータを変更する必要がある限り、わずかなメタデータ(cluster map)しか必要ありません.
CRUSHアルゴリズム
CRUSHアルゴリズムは,各デバイスの重みによりデータオブジェクトの分布を計算する.オブジェクト分布はcluster mapとdata distribution policyによって決定される.cluster mapでは、使用可能なストレージリソースと階層構造(ラック数、ラック数、サーバ数、ディスク数など)について説明します.Data distribution policyはplacement rulesからなる.ruleは、各データ・オブジェクトにどれだけのコピーがあるかを決定します.これらのコピーは、3つのコピーが異なるラックに配置されるなど、制限されています.CRUSH算出xから一組のOSD集合(OSDは対象記憶装置):
CRUSHはマルチパラメータHASH関数を利用し,HASH関数中のパラメータはxを含み,xからOSDの集合が確定的で独立であるようにした.CRUSHはcluster map、placement rules、xのみを使用しています.CRUSHは擬似ランダムアルゴリズムであり,類似入力の結果間に相関はない.
レベルのCluster map
Cluster mapはdeviceとbucketからなり、idと重み値があります.Bucketには任意の数のitemを含めることができます.itemはすべてdevicesでもbucketsでもいいです.管理者はストレージデバイスの重みを制御します.重みはストレージデバイスの容量に関係します.Bucketの重みは、すべてのitemの重みの和を含むように定義されます.CRUSHは4つの異なるbucket typeに基づいており,それぞれ異なる選択アルゴリズムがある.
レプリカの分散
レプリカのストレージデバイスへの分散は、データのセキュリティに影響します.cluster mapはストレージシステムの物理構造を反映している.CRUSH placement policiesは、オブジェクトのコピーを異なる領域に分散することを決定します(ある領域に障害が発生した場合、他の領域には影響しません).各ruleには、階層構造で使用される一連の操作が含まれています.次のような操作があります. tack(a):通常bucketであるitemを選択し、bucketに含まれるすべてのitemを返します.これらのitemは、ベクトルiを構成する後続の動作のパラメータである. select(n,t):各item(ベクトルiのitem)を反復操作し、各item(ベクトルiのitem)に対して下へ遍歴(このitemに含まれるitemを遍歴)し、n個の異なるitem(typeがtのitem)を返し、これらのitemをベクトルiに配置する.select関数はc(r,x)関数を呼び出し、この関数はbucketごとに擬似ランダムにitemを選択します. emit:ベクトルiをresultに配置します.ストレージデバイスには、特定のタイプがあります.各bucketにはtype属性値があり、「row」、「rack」、「host」など、異なるbucketタイプを区別するために使用され、typeはカスタマイズできます.rulesは、複数のtakeおよびemit文ブロックを含むことができ、これにより、異なるストレージプールからレプリカのstorage targetを選択できます.
衝突、故障、オーバーロード
select(n,t)操作では、r=1,...,n個目のコピー、rを選択パラメータとしてループします.この過程で、選択したitemが3つの状況(競合、障害、オーバーロード)に遭遇した場合、CRUSHはこのitemの選択を拒否し、r’(r’とr、エラー回数、firstnパラメータに関連)を選択パラメータとしてitemを再選択します.競合:このitemはベクトルiで選択されています. 障害:デバイスに障害が発生し、選択できません. 過負荷:設備使用容量が警戒線を超え、データオブジェクトを保存する余裕がない.
障害デバイスとオーバーロードデバイスはcluster mapにマークされ(システムに残っています)、不要なデータ移行を回避します.
MAP変更とデータ移行
ストレージデバイスの削除を追加したり、ストレージデバイスに障害が発生した場合(cluster mapが変更された場合)、ストレージシステム内のデータが移行します.良いデータ分散アルゴリズムは、データ移行サイズを最小限に抑えることができます.
Bucketのタイプ
CRUSHマッピングアルゴリズムは効率と拡張性という二つの矛盾した目標を解決した.また、ストレージクラスタが変化すると、データの移行を最小限に抑え、バランス分布を再復元できます.CRUSHは4つの異なるアルゴリズムを持つbucketsを定義した.各bucketは異なるデータ構造に基づいており,異なるc(r,x)擬似ランダム選択関数を有する.bucketによってパフォーマンスと特性が異なります. Uniform Buckets:同じ重みを持つitemに適用され、bucketが削除itemを追加することはめったにありません.検索速度が一番速いです. List Buckets:チェーンテーブル構造であり、含まれるitemは任意の重みを有することができる.CRUSHは、ヘッダからレプリカの位置を検索し、ヘッダitemの重みWh、残りのチェーンテーブルのすべてのitemの重みの和Wsを先に取得し、hash(x,r,item)に基づいて[0~1]の値vを取得し、この値vが[0~Wh/Ws)の場合、レプリカはヘッダitemにあり、ヘッダitemのidを返す.No者は残りのチェーンテーブルを遍歴し続ける. Tree Buckets:チェーンテーブルの検索複雑度はO(n)であり、決定ツリーの検索複雑度はO(log n)である.itemは決定ツリーのリーフノードであり,決定ツリーの他のノードはその左右のサブツリーの重みを知っており,ノードの重みは左右のサブツリーの重みの和に等しい.CRUSHはrootノードからレプリカの位置を検索し、ノードの左サブツリーの重みWlを先に取得し、ノードの重みWnを取得し、hash(x,r,node_id)に基づいて[0~1]の値vを得る.この値vが[0~Wl/Wn]の場合、コピーは左サブツリーにあり、NOは右サブツリーにある.リーフノードに到達するまでノードを巡回し続ける.Tree Bucketの鍵は、削除リーフノードを追加すると、決定ツリー内の他のノードのnode_idは変わらないことである.決定ツリー内のノードのnode_idの識別は、二叉木の中順に従来から決定されている(node_idはitemのidに等しくなく、ノードの重みにも等しくない). Straw Buckets:このタイプはbucketに含まれるすべてのitemを公平に競争させる(listやtreeのように遍歴する必要はありません).このアルゴリズムは抽選のように、すべてのitemが抽選される機会がある(最長のくじだけが抽選される).各くじの長さはlength=f(Wi)*hash(x,r,i)で決定され,f(Wi)はitemの重みに関係し,iはitemのid番号である.c(r, x) = MAXi(f(Wi) * hash(x, r, i)).
図1 Tree Bucketsの構造図2の異なるBucketのアルゴリズムの複雑さとデータ移行サイズの結論は、ストレージシステム内のデバイスの状況と予想される拡張計画に基づいて異なるbucketを選択することである.
概要
CRUSHはcephのモジュールであり、主に制御可能、拡張可能、中心化されたデータコピー分布の問題を解決する.CephはCRUSH(拡張可能な擬似ランダムデータ分布アルゴリズム)を設計し、分散オブジェクトストレージシステム上でデータオブジェクトをストレージデバイス上に効率的にマッピングすることができる(センタデバイスを必要としない).大規模なシステムの構造が動的に変化するため、CRUSHはストレージデバイスの追加と削除を処理し、ストレージデバイスの追加と移動によるデータ移行を最小限に抑えることができる.オブジェクトストレージデバイス(object-based storage devices)は、ディスク・データ・ブロックの割り当てを管理し、オブジェクトの読み書きインタフェースを提供する.一部のオブジェクトストレージシステムでは、各ファイルのデータは、ストレージクラスタ全体に分布する複数のオブジェクトに分割される.オブジェクトストレージシステムは、データ層を簡略化する(データブロックリストをオブジェクトリストに変換し、低レベルのデータブロック割り当て問題を各デバイスに渡す).オブジェクトストレージシステムの基本的な問題は、数千のストレージデバイスにデータをどのように分散するかです.1つのrobustソリューションは、データをランダムにストレージデバイスに分散することです.この方法は、負荷の均衡を保証し、新しいデータと古いデータの混合を保証します.しかし,単純HASH分布ではデバイス数の変化を効率的に処理できず,大量のデータ移行を招く.CephはCRUSH(Controoled Replication Under Scale Hashing)を開発し,階層構造のストレージクラスタにおいてオブジェクトのコピーを効率的に分散できる擬似ランダムデータ分布アルゴリズムを開発した.CRUSHは、object idまたはobject group idのパラメータを持つ擬似ランダム(決定的)関数を実現し、objectコピーを保存するためのストレージデバイスのセットを返します.CRUSHにはcluster map(ストレージクラスタの階層構造を記述する)、レプリカ分散ポリシー(rule)が必要です.CRUSHには2つの重要な利点があります.追加デバイスを削除する場合にのみ、これらのメタデータを変更する必要がある限り、わずかなメタデータ(cluster map)しか必要ありません.
CRUSHアルゴリズム
CRUSHアルゴリズムは,各デバイスの重みによりデータオブジェクトの分布を計算する.オブジェクト分布はcluster mapとdata distribution policyによって決定される.cluster mapでは、使用可能なストレージリソースと階層構造(ラック数、ラック数、サーバ数、ディスク数など)について説明します.Data distribution policyはplacement rulesからなる.ruleは、各データ・オブジェクトにどれだけのコピーがあるかを決定します.これらのコピーは、3つのコピーが異なるラックに配置されるなど、制限されています.CRUSH算出xから一組のOSD集合(OSDは対象記憶装置):
(osd0, osd1, osd2 … osdn) = CRUSH(x)CRUSHはマルチパラメータHASH関数を利用し,HASH関数中のパラメータはxを含み,xからOSDの集合が確定的で独立であるようにした.CRUSHはcluster map、placement rules、xのみを使用しています.CRUSHは擬似ランダムアルゴリズムであり,類似入力の結果間に相関はない.
レベルのCluster map
Cluster mapはdeviceとbucketからなり、idと重み値があります.Bucketには任意の数のitemを含めることができます.itemはすべてdevicesでもbucketsでもいいです.管理者はストレージデバイスの重みを制御します.重みはストレージデバイスの容量に関係します.Bucketの重みは、すべてのitemの重みの和を含むように定義されます.CRUSHは4つの異なるbucket typeに基づいており,それぞれ異なる選択アルゴリズムがある.
レプリカの分散
レプリカのストレージデバイスへの分散は、データのセキュリティに影響します.cluster mapはストレージシステムの物理構造を反映している.CRUSH placement policiesは、オブジェクトのコピーを異なる領域に分散することを決定します(ある領域に障害が発生した場合、他の領域には影響しません).各ruleには、階層構造で使用される一連の操作が含まれています.次のような操作があります.
衝突、故障、オーバーロード
select(n,t)操作では、r=1,...,n個目のコピー、rを選択パラメータとしてループします.この過程で、選択したitemが3つの状況(競合、障害、オーバーロード)に遭遇した場合、CRUSHはこのitemの選択を拒否し、r’(r’とr、エラー回数、firstnパラメータに関連)を選択パラメータとしてitemを再選択します.
障害デバイスとオーバーロードデバイスはcluster mapにマークされ(システムに残っています)、不要なデータ移行を回避します.
MAP変更とデータ移行
ストレージデバイスの削除を追加したり、ストレージデバイスに障害が発生した場合(cluster mapが変更された場合)、ストレージシステム内のデータが移行します.良いデータ分散アルゴリズムは、データ移行サイズを最小限に抑えることができます.
Bucketのタイプ
CRUSHマッピングアルゴリズムは効率と拡張性という二つの矛盾した目標を解決した.また、ストレージクラスタが変化すると、データの移行を最小限に抑え、バランス分布を再復元できます.CRUSHは4つの異なるアルゴリズムを持つbucketsを定義した.各bucketは異なるデータ構造に基づいており,異なるc(r,x)擬似ランダム選択関数を有する.bucketによってパフォーマンスと特性が異なります.
図1 Tree Bucketsの構造図2の異なるBucketのアルゴリズムの複雑さとデータ移行サイズの結論は、ストレージシステム内のデバイスの状況と予想される拡張計画に基づいて異なるbucketを選択することである.