cephcrush算法介紹課件

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