cephcrush算法介紹課件

CephCRUSH算法介紹Agenda數(shù)據(jù)分布算法的解決的問題CRUSH算法介紹Ceph數(shù)據(jù)尋址ClushmapPlacementRuleBucket隨機(jī)選擇算法CRUSH算法的評價數(shù)據(jù)分布算法解決的問題數(shù)據(jù)如何分布到存儲設(shè)備上數(shù)據(jù)均衡靈活應(yīng)對集群伸縮存儲設(shè)備的增加刪除導(dǎo)致數(shù)據(jù)遷移量小支持大規(guī)模集群較少的元數(shù)據(jù)維護(hù)合適的計算量CRUSH算法的核心：多層迭代偽隨機(jī)選擇算法Ceph數(shù)據(jù)的尋址兩層映射Object-->PGPG-->(OSD1,OSD2,OSD3)CRUSH做什么用？PG如何分布到osd上CRHUSH(X)-->(OSD1,OSD2,OSD3)參數(shù)inputx（pgid)HierachicalClustermapPlacementrules輸出一組OSDHierarchicalClustermap層級化的Clustermapdevice基本的存儲設(shè)備OSDbucket:容器，包含device和子類型item：容器的組成成員，可以是基本的device，也可以是低層的bucketbucket的類型root，region，datacenter，row，rack，host，可以自己定義bucket類型和層級關(guān)系層級化Clustermap編寫hosttest1{id-2##weight6.000algstraw#隨機(jī)選擇的算法hash0#rjenkins1itemosd.1weight1.000itemosd.2weight1.000itemosd.3weight1.000}hosttest2{id-3##weight6.000algstraw#隨機(jī)選擇的算法hash0#rjenkins1itemosd.4weight1.000itemosd.5weight1.000itemosd.6weight1.000}rootdefault{id-1#bucket的id，一般為負(fù)數(shù)#weight6.000#權(quán)重，為item的權(quán)重之和algstraw#bucket類型，決定隨機(jī)選擇的算法hash0#rjenkins1#hash函數(shù)的類型itemtest1weight3.000#itemitemtest2weight3.000}Clustermap示例缺省提供了root，datacenter，room，row，rack，host。8.12.00.82.02.12.01.31.01.0PlacementRulesClustermap反應(yīng)了存儲系統(tǒng)的物理結(jié)構(gòu)CRUSHplacementpolicies（Placementrule）決定對象副本如何分布的規(guī)則由三個基本的操作步（step）構(gòu)成基本操作步steptack(a)：選擇一個bucket（一般是rootbucket）做為后續(xù)step操作的輸入choose：對于上一個操作的每個item，都要做相應(yīng)的操作choosefirstn{num}type{bucket-type}選擇一個bucket-type類型的itemchooseleaffirstn{num}type{bucket-type}先選擇bucket-type類型的item，再遞歸選擇葉子節(jié)點(diǎn)的OSDNUM參數(shù)的意義If{num}==0,choosepool-num-replicasbuckets(allavailable).If{num}>0&&<pool-num-replicas,choosethatmanybuckets.If{num}<0,itmeanspool-num-replicas-{num}.firstn和indepn的分別是一個是深度優(yōu)先和廣度優(yōu)先選擇emit示例1ruleset編寫rulereplicated_ruleset{ruleset0#ruleset的編號idtypereplicated#類型repliated或者erasurecodemin_size1#副本數(shù)最小值max_size10#副本數(shù)最大值steptakeroot#選擇一個rootbucket，做下一步的輸入stepchoosefirstn1typerow#選擇一個row，同一排stepchoosefirstn3typecabinet#選擇三個cabinet,三副本分別在不同的cabinetstepchoosefirstn1typeosd#在上一步輸出的三個cabinet中，分別選擇一個osdstepemit}示例1圖示例1的ruleset對于的圖ruleset示例2pg主osd為ssd，從osd為hdd的rulesetrulessd-primary{ruleset5typereplicatedmin_size5max_size10steptakessd#選擇ssd這個rootbucket為輸入stepchooseleaffirstn1typehost#選擇一個host，并遞歸選擇葉子節(jié)點(diǎn)osdstepemit#輸出結(jié)果steptakehdd#選擇hdd這個rootbucket為輸入stepchooseleaffirstn-1typehost#選擇總副本數(shù)減一個host，并遞歸選擇一個葉子節(jié)點(diǎn)osdstepemit#輸出結(jié)果}Agenda數(shù)據(jù)分布算法的解決的問題CRUSH算法介紹Ceph數(shù)據(jù)尋址ClushmapPlacementRuleBucket類型和對應(yīng)的隨機(jī)選擇算法CRUSH算法的評價Bucket隨機(jī)選擇算法目標(biāo)從Bucket中隨機(jī)選擇一個item出來根據(jù)Buckent的類型不同，對應(yīng)同的隨機(jī)選擇算法Bucket：不同的數(shù)據(jù)結(jié)構(gòu)，并有不同的c(r,x)偽隨機(jī)選擇函數(shù)uniformlisttreestrawUniformBuckets適用于具有相同權(quán)重的item，而且bucket很少添加刪除item。它的查找速度是最快的。本質(zhì)上就是定長hash算法ListBuckets鏈表結(jié)構(gòu)，所包含的item可以具有任意的權(quán)重。具體查找方法：CRUSH從表頭開始查找副本的位置，它先得到表頭item的權(quán)重Wh、剩余鏈表中所有item的權(quán)重之和Ws，然后根據(jù)hash(x,r,item)得到一個[0~1]的值v，假如這個值v在[0~Wh/Ws)之中，則副本在表頭item中，并返回表頭item的id。否者繼續(xù)遍歷剩余的鏈表。鏈表的查找復(fù)雜度是O(n)TreeBucketsitem是決策樹的葉子節(jié)點(diǎn)，節(jié)點(diǎn)的權(quán)重等于左右子樹的權(quán)重之和。CRUSH從root節(jié)點(diǎn)開始查找副本的位置，它先得到節(jié)點(diǎn)的左子樹的權(quán)重Wl，得到節(jié)點(diǎn)的權(quán)重Wn，然后根據(jù)hash(x,r,node_id)得到一個[0~1]的值v，假如這個值v在[0~Wl/Wn)中，則副本在左子樹中，否者在右子樹中。繼續(xù)遍歷節(jié)點(diǎn)，直到到達(dá)葉子節(jié)點(diǎn)。決策樹的查找復(fù)雜度是O(logn)StrawBuckets這種類型讓bucket所包含的所有item公平的競爭(不像list和tree一樣需要遍歷)。這種算法就像抽簽一樣，所有的item都有機(jī)會被抽中(只有最長的簽才能被抽中)。每個簽的長度是由length=f(Wi)*hash(x,r,i)決定的，f(Wi)和item的權(quán)重有關(guān)，i是item的id號。c(r,x)=MAXi(f(Wi)*hash(x,r,i))。沖突、故障、超載處理沖突、故障、超載沖突：這個item已經(jīng)在向量i中，已被選擇。故障：設(shè)備發(fā)生故障，不能被選擇。超載：設(shè)備使用容量超過警戒線，沒有剩余空間保存數(shù)據(jù)對象選擇到的item遇到三種情況(沖突，故障，超載)時，CRUSH會拒絕選擇這個item，并使用r’(r’和r、出錯次數(shù)、firstn參數(shù)有關(guān))作為選擇參數(shù)重新選擇itemCrush算法評價多層確定性偽隨機(jī)選擇算法優(yōu)點(diǎn)：輸入元數(shù)據(jù)較少（clustermap，placementrule)，可以應(yīng)對大規(guī)模集群數(shù)據(jù)均衡為以概率為基礎(chǔ)的統(tǒng)計上的均衡，在大規(guī)模集群中可以實(shí)現(xiàn)數(shù)據(jù)均衡能夠靈活應(yīng)對集群伸縮缺點(diǎn)：在小規(guī)模集群中