ceph的存儲是無主結構，數據分布依賴client來計算，有兩個條主要路徑。

1、數據到PG

2、PG 到OSD

有兩個假設： 第一，pg的數量穩定，可以認為保持不變； 第二， OSD的數量可以增減，OSD的存儲空間權重不等；

由于 PG的數量保持不變，由數據來找PGID的環節可以簡單處理，對數據的key來取hash值再對pg的總數取模即可唯一確認pgid，pgid=hash(data_key)/pg_num。

難點在于從PG到OSD，如果直接用 hash(pgid)/osd_num的模式，則OSD有增減的時候數據就有無規律的遷移，并且也無法體現OSD的不同權重。

Crush算法就是來解決這個問題的，Crush目的是隨機跳出一個OSD，并且要滿足權重越大的OSD，挑中的概率越大。

每個OSD有不同的容量，比如是4T還是12T的容量，可以根據每個OSD的容量定義它的權重，以T為單位， 比如4T權重設為4，12T則設為12。

如何將PG映射到不同權重的OSD上面？這里可以直接采用CRUSH里面的Straw抽簽算法。

核心步驟：

1）計算HASH

draw = CRUSH＿HASH（ PG＿ID， OSD＿ID， r )，其中把r當做一個常數，將PG＿ID， OSD＿ID一起作為輸入，得到一個HASH值。

2）增加OSD權重

osd＿straw =（ draw ＆0xffff ） ＊ osd＿weight

draw &0xffff 得到一個0-65535的數字，再與OSD的權重相乘，以這個作為每個OSD的簽長， 權重越大的，數值越大。

3）遍歷選取最高的權重

high_draw

Crush所計算出的隨機數，是通過HASH得出來，可以保障相同的輸入會得出同樣的輸出結果。

這里只是計算得出了一個OSD，在Ceph集群中是會存在多個副本，如何解決一個PG映射到多個OSD的問題？

將常量r加1， 再去計算一遍，如果和之前的OSD編號不一樣， 那么就選取它；如果一樣的話，那么再把r+2，再重新計算，直到選出三個不一樣的OSD編號。

如果樣本容量足夠大， 隨機數對選中的結果影響逐漸變小， 起決定性的是OSD的權重，OSD的權重越大， 被挑選的概率也就越大。

樣本容量足夠大，到底是多大？ 到底多大才能按照盡可能按照權重來分布，當然是盡量小的樣本才好。

樣本容量主要由PG和OSD的數量多少來決定，其中最關鍵的還是OSD數量，如果OSD很少（比如5塊盤）也能盡量按照權重分布才好。

PG的數量主要是根據數據預估和OSD的數量來定，有個理論參考數，PG數量 =（OSD數量* 100）/副本數，但是PG數量少影響后面的擴容，太多又占用過多資源，需要有一個平衡。

基于上述考慮，寫了一個很簡單的程序來驗證下數據分布平衡性。

假定OSD數量為5并且權重隨機，PG的數量為5000。

結果1:

1.隨機生成5個OSDID和對應權重

OSDID=I0N@6nt5pOhjY$g;權重=32.0

OSDID=.nIjl%3zs3aoE7K;權重=16.0

OSDID=S5O9bSS4NMo%qDN;權重=1.0

OSDID=t$lZF91ofuvOKcn;權重=24.0

OSDID=!E2Ia8XE^Jzb5Dz;權重=12.0

2.在pg數量為5000的時候，PG的分布結果：

OSDID=!E2Ia8XE^Jzb5Dz;權重=12.0;擁有的PG數量=625

OSDID=I0N@6nt5pOhjY$g;權重=32.0;擁有的PG數量=2682

OSDID=t$lZF91ofuvOKcn;權重=24.0;擁有的PG數量=1554

OSDID=.nIjl%3zs3aoE7K;權重=16.0;擁有的PG數量=139

結果2:

1.隨機生成5個OSDID和對應權重

OSDID=C%EN$UM!e8nZy.R;權重=1.0

OSDID=1iTDBnZeeQ6^Uos;權重=32.0

OSDID=%EMc6a4V5cWi%7D;權重=2.0

OSDID=M7WKDUjLrQaV42D;權重=64.0

OSDID=7OVTO@l$XLE$OV$;權重=8.0

2.在pg數量為5000的時候，PG的分布結果：

OSDID=1iTDBnZeeQ6^Uos;權重=32.0;擁有的PG數量=1201

OSDID=7OVTO@l$XLE$OV$;權重=8.0;擁有的PG數量=18

OSDID=M7WKDUjLrQaV42D;權重=64.0;擁有的PG數量=3781

結果3:

1.隨機生成5個OSDID和對應權重

OSDID=TSvabIIG#9IssWW;權重=12.0

OSDID=XglajmN2q3f5qRI;權重=0.8

OSDID=ZEeeX^Wp9tHaxuA;權重=0.5

OSDID=PSiiRAwddyc^ThW;權重=32.0

OSDID=nPI^YbDr0ttVzGa;權重=8.0

2.在pg數量為5000的時候，PG的分布結果：

OSDID=nPI^YbDr0ttVzGa;權重=8.0;擁有的PG數量=319

OSDID=PSiiRAwddyc^ThW;權重=32.0;擁有的PG數量=3816

OSDID=TSvabIIG#9IssWW;權重=12.0;擁有的PG數量=865

package com.test.zhangzk.crush;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;public class TestCephCrush {static String str = "abcdefghijklmnopqrstuvwxyzABCDEDFGHIJKLMNOPQRSTUVWXYZ0123456789.@!#$%^&*";static Float[] factories =new Float[] {0.25f,0.5F,0.8f,1f,2f,4f,8f,12f,16f,20f,24f,32f,64f};static int pgidCount = 5000;static int osdCount = 5;public static void main(String[] args) {List<String> pgidList = getRandomPgIdList(pgidCount);List<OSDBean> osdList = getRandomOSDIdList(osdCount);HashMap<String,Integer> keyCount = new HashMap<String,Integer>();for(int i=0;i<pgidCount;i++) {float maxStraw = 0.0f;float osdFactor = 0.0f;String osdId = "";for( int j=0;j<osdCount;j++) {String key = pgidList.get(i) + osdList.get(j);int hashCode = key.hashCode() & 0xffff;float straw = hashCode * osdList.get(j).getFactor();if( maxStraw < straw) {maxStraw = straw;osdFactor = osdList.get(j).getFactor();osdId = osdList.get(j).getId();}}String key =  "OSDID="+osdId  + ";權重=" + osdFactor;Integer v = keyCount.get(key);if( v == null ) {keyCount.put(key, 1);}else {keyCount.put(key, v+1);}	}System.out.println("2.在pg數量為" + pgidCount +"的時候，PG的分布結果：");for(String k:keyCount.keySet()){System.out.println(k + ";擁有的PG數量=" +keyCount.get(k));}}private static List<String> getRandomPgIdList(int pgidCount){// TODO Auto-generated method stubList<String> pgidList = new ArrayList<String>();java.util.Random r = new Random(System.currentTimeMillis());for( int i=0;i<pgidCount;i++) {StringBuilder sb = new StringBuilder();for( int j=0;j<10;j++) {sb.append(str.charAt(r.nextInt(str.length()-1)));}pgidList.add(sb.toString());}return pgidList;}private static List<OSDBean> getRandomOSDIdList(int osdCount){System.out.println("1.隨機生成"+ osdCount + "個OSDID和對應權重");// TODO Auto-generated method stubList<OSDBean> osdList = new ArrayList<OSDBean>();java.util.Random r = new Random(System.currentTimeMillis());for( int i=0;i<osdCount;i++) {StringBuilder sb = new StringBuilder();for( int j=0;j<15;j++) {sb.append(str.charAt(r.nextInt(str.length()-1)));}OSDBean osd = new OSDBean();osd.setId(sb.toString());osd.setFactor(factories[r.nextInt(factories.length)]);System.out.println( "OSDID=" + sb.toString()+ ";權重="+ osd.getFactor() );osdList.add(osd);}return osdList;}
}class OSDBean {private String id;private float factor;public String getId() {return id;}public void setId(String id) {this.id = id;}public float getFactor() {return factor;}public void setFactor(float factor) {this.factor = factor;}
}