深入Ceph原理包含核心算法Crush說明和通信機制原理（五）【與云原生的故事】

一、Crush算法與作用

CRUSH 算法，全稱 Controlled Replication Under Scalable Hashing （可擴展哈希下的受控復制），它是一個可控的、可擴展的、分布式的副本數據放置算法， 通過CRUSH 算法來計算數據存儲位置來確定如何存儲和檢索數據。

保障數據分布的均衡性

集群的靈活伸縮性

支持更大規模的集群

二、Crush算法說明

PG 到 OSD 的映射的過程算法稱為 CRUSH 算法，它是一個偽隨機的過程，可以從所有的 OSD 中，隨機性選擇一個OSD 集合。

Crush Map 將系統的所有硬件資源描述成一個樹狀結構，然后再基于這個結構按照一定的容錯規則生成一個邏輯上的樹形結構，樹的末級葉子節點device 也就是 OSD ，其他節點稱為 bucket 節點，根據物理結構抽象的虛擬節點，包含數據中心抽象、機房抽象、機架抽象、主機抽象。

三、Crush算法原理

1、Ceph的存儲結構

Ceph 為了保存對象，會先構建一個池（ pool ），把 pool 可以比喻成一個倉庫，一個新對象的保存就類似于把一個包裹放到倉庫里面。

2、PG的分配存儲

對象是如何保存至哪個 PG 上？假設 Pool 名稱為 rbd ，共有 256 個 PG ，每個 PG 編個號分別叫做 0x0， 0x1， 0x2 ，．．． 0xFF 。 具體該如何分配？這里可以采用 Hash 方式計算。假設有兩個對象名， 分別為bar 和 foo 的，根據對象名做 Hash 計算：

HASH （ ‘bar’ ） ＝ 0x3E0A4162

HASH （ ‘foo’ ） ＝ 0x7FE391A0

通過 Hash 得到一串隨機的十六進制的值， 對于同樣的對象名，計算出的結果能夠永遠保持一致，但我們預分配的是256 個 PG ，這就需要再進行取模處理， 所得的結果會落在【 0x0 ， 0xFF 】區間：

0x3E0A4162 ％ 0xFF ＝＝＝＞ 0x62

0x7FE391A0 ％ 0xFF ＝＝＝＞ 0xA0

實際在Ceph中， 存在很多個Pool，每個Pool里面存在若干個PG，如果兩個Pool里面的PG編號相同，該如何標識區分？Ceph會對每個pool再進行編號，一個PG的實際編號是由pool_id + . + pg_id組成。

3、OSD的分配存儲

Ceph 的物理層，對應的是服務器上的磁盤， Ceph 將一個磁盤或分區作為 OSD ，在邏輯層面，對象是保存至PG 內，現在需要打通 PG 與 OSD 之間的聯系， Ceph 當中會存在較多的 PG 數量，如何將 PG平均分布各個OSD 上面，這就是 Crush 算法主要做的事情： 計算 PG -> OSD 的映射關系。

上述所知， 主要兩個計算步驟：

POOL_ID （對象池） ＋ HASH （‘對象名稱 ’ ） ％ pg ＿ num （歸置組）＝＝＞ PG ＿ ID （完整的歸置組編號）

CRUSH （ PG ＿ ID ）＝＝＞ OSD （對象存儲設備位置）

4、為什么需要采用Crush算法

如果把 CRUSH （ PG ＿ ID ）改成 HASH （ PG_ID ） % OSD_NUM 能否適用？ 是會存在一些問題。

1 ）如果掛掉一個 OSD ，所有的 OSD_NUM 余數就會發生變化，之前的數據就可能需要重新打亂整理， 一個優秀的存儲架構應當在出現故障時， 能夠將數據遷移成本降到最低，

CRUSH 則可以做到。

2 ）如果增加一個 OSD, OSD_NUM 數量增大， 同樣會導致數據重新打亂整理，但是通過CRUSH可以保障數據向新增機器均勻的擴散， 且不需要重新打亂整理。

3 ）如果保存多個副本，就需要能夠獲取多個 OSD 結果的輸出， 但是 HASH 方式只能獲取一個， 但是通過CEPH 的 CRUSH 算法可以做到獲取多個結果。

5、Crush算法如何實現

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

那么如何將 PG 映射到不同權重的 OSD 上面？這里可以直接采用 CRUSH 里面的 Straw 抽簽算法，這里面的抽簽是指挑取一個最長的簽，而這個簽值就是OSD 的權重。

主要步驟：

計算HASH: CRUSH＿HASH（ PG＿ID， OSD＿ID， r ） ＝＝＞ draw把r當做一個常數，將PG＿ID， OSD＿ID一起作為輸入，得到一個HASH值。

增加OSD權重： （ draw ＆0xffff ） ＊ osd＿weight ＝＝＞ osd＿straw 將計算出的HASH值與OSD的權重放置一起，這樣就能夠得到每個OSD的簽長， 權重越大的，數值越大。

遍歷選取最高的權重：high_draw

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

Crush 所計算出的隨機數，是通過 HASH 得出來，可以保障相同的輸入會得出同樣的輸出結果。 所以Crush 并不是真正的隨機算法， 而是一個偽隨機算法。

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

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

假設常數 r=0 ，根據算法 (CRUSH_HASH & 0xFFFF) * weight 計算最大的一個 OSD ，結果為 osd.1 的0x39A00，也就是選出的第一個 OSD ，然后再讓 r=1 ， 生成新的 CRUSH_HASH 隨機值，取得第二個OSD，依次得到第三個 OSD 。

四、IO流程圖

步驟：

1. client 連接 monitor 獲取集群 map 信息。

2. 同時新主 osd1 由于沒有 pg 數據會主動上報 monitor 告知讓 osd2 臨時接替為主。

3. 臨時主 osd2 會把數據全量同步給新主 osd1 。

4. client IO 讀寫直接連接臨時主 osd2 進行讀寫。

5. osd2 收到讀寫 io ，同時寫入另外兩副本節點。

6. 等待 osd2 以及另外兩副本寫入成功。

7. osd2 三份數據都寫入成功返回給 client, 此時 client io 讀寫完畢。

8. 如果 osd1 數據同步完畢，臨時主 osd2 會交出主角色。

9. osd1 成為主節點， osd2 變成副本。

五、Ceph 通信機制

網絡通信框架三種不同的實現方式：

Simple線程模式

特點：每一個網絡鏈接，都會創建兩個線程，一個用于接收，一個用于發送。

缺點：大量的鏈接會產生大量的線程，會消耗CPU資源，影響性能。

Async事件的I/O多路復用模式

特點：這種是目前網絡通信中廣泛采用的方式。新版默認已經使用Asnyc異步方式了。

XIO方式使用了開源的網絡通信庫accelio來實現

特點：這種方式需要依賴第三方的庫accelio穩定性，目前處于試驗階段。

消息的內容主要分為三部分：

header //消息頭類型消息的信封

user data //需要發送的實際數據

payload //操作保存元數據

middle //預留字段

data //讀寫數據

footer //消息的結束標記

步驟：

Accepter監聽peer的請求, 調用 SimpleMessenger::add_accept_pipe() 創建新的 Pipe, 給SimpleMessenger::pipes 來處理該請求。

Pipe用于消息的讀取和發送。該類主要有兩個組件，Pipe::Reader，Pipe::Writer用來處理消息讀取和發送。

Messenger作為消息的發布者, 各個 Dispatcher 子類作為消息的訂閱者, Messenger 收到消息之后， 通過 Pipe 讀取消息，然后轉給 Dispatcher 處理。

Dispatcher是訂閱者的基類，具體的訂閱后端繼承該類,初始化的時候通過Messenger::add_dispatcher_tail/head 注冊到 Messenger::dispatchers. 收到消息后，通處理。

DispatchQueue該類用來緩存收到的消息, 然后喚醒 DispatchQueue::dispatch_thread 線程找到后端的 Dispatch 處理消息。

六、Ceph RBD 塊存儲 IO流程圖

osd寫入過程：

采用的是librbd的形式，使用librbd創建一個塊設備，向這個塊設備中寫入數據。

在客戶端本地通過調用librados接口，然后經過pool，rbd，object、pg進行層層映射,在PG這一層中，可以知道數據是保存在哪三個OSD上，這三個OSD分別為主從的關系。

客戶端與primary OSD建立SOCKET 通信，將要寫入的數據傳給primary OSD，由primary OSD再將數據發送給其他replica OSD數據節點。

七、Ceph 心跳和故障檢測機制

問題：

故障檢測時間和心跳報文帶來的負載 , 如何權衡降低壓力 ?

心跳頻率太高則過多的心跳報文會影響系統性能。

心跳頻率過低則會延長發現故障節點的時間，從而影響系統的可用性。

故障檢測策略應該能夠做到：

及時性：節點發生異常如宕機或網絡中斷時，集群可以在可接受的時間范圍內感知。

適當的壓力：包括對節點的壓力，和對網絡的壓力。

容忍網絡抖動：網絡偶爾延遲。

擴散機制：節點存活狀態改變導致的元信息變化需要通過某種機制擴散到整個集群。

OSD節點會監聽public、cluster、front和back四個端口

public端口：監聽來自Monitor和Client的連接。

cluster端口：監聽來自OSD Peer的連接。

front端口：客戶端連接集群使用的網卡, 這里臨時給集群內部之間進行心跳。

back端口：在集群內部使用的網卡。集群內部之間進行心跳。

hbclient：發送ping心跳的messenger(送信者)。

【與云原生的故事】有獎征文火熱進行中：https://bbs.huaweicloud.com/blogs/345260

分布式

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。