Indexed Shared Log

01-29

用途

Indexed Shared Log 作為分散式系統的基礎數據結構，可以用於以下三個用途

低成本的日誌檢索

state of art 的日誌檢索系統是把日誌集中化到中央節點進行排序，建立倒排索引來實現的。無論是往中央節點匯聚，還是log segment的合併排序都需要大量的移動位元組，有巨大的成本。

中央化排序的目的是讓查詢的時候更快，只需要讀取很少的位元組就可以掃過大量的日誌。但是這個日誌檢索的需求和面向消費者的搜索引擎是有很大不同的。面向定位調錯的日誌檢索系統並不需要搜索引擎那麼低的檢索延遲。用搜索引擎的倒排架構是一種over kill。如果能夠犧牲一定的檢索速度，就可以節省大量的建立索引的成本。bitfunnel的基於樹狀bloom filter的索引結構是更經濟的做法。

低寫入延遲的高可用隊列

現在的kafka單partition的可用性模型是CP的。大部分的消息隊列的使用場景可以接受AP的。通過把多個indexed shared log進行組合使用，我們可以組裝出一個AP模型的消息隊列：應用 RAID 6 於消息隊列

強一致的存儲

在多個indexed shared log上使用paxos演算法進行分散式一致性演算法的寫入，可以組合成CP模型的日誌存儲。在這個CP的日誌上，可以構建單隊列或者多隊列的存儲系統，不管是KV的還是文檔的還是關係型的或者文件系統。一致性演算法的說明：不要騙我了，這能有多難嘛！

corfu

Indexed Shared Log 就是對在 corfu 模型上的幾點擴展

Shared Log 已經很有用了。Indexed Shared Log會更有用的。

Indexed Shared Log 的索引模型

Indexed Shared Log 從概念上可以理解為一個immutable append only 的 mysql 表。有多列，以及一個主鍵。主鍵是uint64類型，全局增長非連續的整數。如果index shared log只有一個物理文件的時候，這個主鍵就是記錄在文件里的offset。如果分解為了多個物理文件，這個主鍵就是一個虛擬的全局的offset。

整串log分多個segment來保存。每個segment上記錄這個segment里包含日誌的摘要信息。摘要分成兩種格式：

bloomfilter 摘要：用於支持 string 和 int 類型。用於快速實現 == 查找
min/max 摘要：用於支持 int 類型。用於快速實現範圍查找

segment之間構成樹狀多級的結構，用於加速查找。

每個列可以選擇三種模式

只保存值：比如用於保存blob，任意內容
建立bloomfilter或者min/max摘要：可檢索的列
unique約束：在這個列上施加unique約束。用於實現write once register的語義。也可以用於實現RPC冪等性。