存儲與索引------《Designing Data-Intensive Applications》讀書筆記3

在上一篇的筆記之中，我們討論了數據模型和查詢語言。在第三章之中我們來聊一聊不同的數據引擎內部是如何實現存儲和檢索的，以及不同設計之間的折中與妥協。

1.鍵值對資料庫

鍵值對資料庫是資料庫形式之中最簡單的一種模式，我們可以把它簡化的實現為下麵兩個函數：

底層存儲格式也十分簡單：一個文本文件，其中每行包含一個鍵值對，用逗號分隔（類似於CSV文件，忽略轉義問題）。每一次調用 db_set 會追加鍵值對到文件的末尾，如果你更新的一個鍵值對的舊版本不會覆蓋之前的鍵值對，但是 db_get會利用 tail -n 1 in 語句讀取最新的鍵值對。但是真正的資料庫需要處理更多的問題（例如併發控制、回收磁碟空間、使日誌不能永久增長、處理錯誤和部分寫的問題），但基本設計思路和原則是相同的。

但是，db_get 在性能上表現的很糟糕，每一次需要查找一個key，db_get 會掃描整個資料庫文件來查找Key。在演算法定義之中，查找的時間複雜度是O（n）。為了有效地查找資料庫中某個特定鍵的值，我們需要一個不同的數據結構：索引。

2.索引

索引是從原始數據派生出來的附加結構。在添加和刪除索引時，不會影響數據存儲的內容，它只會影響查詢的性能。但是維護額外的結構會導致開銷，尤其是寫操作。任何類型的索引都會減慢寫速度，因為每次寫入數據時也需要更新索引。
在存儲系統的有一個重要的權衡：精心挑選的索引加快了讀取的速度，但是每個索引都會減慢寫入速度。由於這個原因，資料庫通常不會預設索引所有內容，但要求應用程式開發人員或資料庫管理員手動地選擇索引，可以選擇使應用程式受益最大的索引，而不需要引入更多的開銷。

• 哈希索引
  這裡我們通過哈希索引來分析一下上文提及的那個簡易的鍵值資料庫。最簡單的索引策略是：保持一個記憶體的哈希映射，其中每一個鍵都映射到數據文件中的位元組偏移量，通過偏移量可以找到該值的位置，如下圖所示：
  
  每當向文件追加一個新的鍵值對時，也會同時更新哈希映射以反映剛纔寫入的數據的偏移量（這既可以用於插入新的鍵值對，也可以用於更新現有的鍵值對）。在查找值時，使用哈希映射查找數據文件中的偏移量，查找該位置並讀取該值。
  那麼我們如何避免最終耗盡磁碟空間呢？一個好的解決方案是，我們可以對這些文件執行壓縮，如下圖所示。壓縮意味著在文件中扔掉重覆的鍵，並且只保留每個鍵的最新更新。
  
  合併和壓縮可以由後臺線程完成，並且在進行合併和壓縮操作時，我們仍然可以使用舊的文件繼續正常地服務讀寫請求。在合併過程完成後，我們將讀取請求轉換為使用新合併的文件，然後舊的文件可以簡單地刪除。
  缺點：
  （1）哈希索引嚴重依賴於記憶體，所以如果Key的數量龐大，需要匹配足夠的記憶體空間。
  （2）範圍查詢效率不高，每查找一個值都需要一次鍵值對映射。
• SSTable
  由哈希索引我們可以引申出更加高效的索引結構:SSTable(Sorted String Table)，SSTable要求鍵值對序列按照鍵來排序。乍一看，這個要求似乎破壞了順序寫的性能，但是它大大提高了維護數據以及索引結構的效率。
  • 合併文件既簡單又高效，使用簡單的歸併排序演算法。
    
    • 不再需要保留所有鍵在記憶體中的索引，只需要保留部分鍵的索引，利用鍵在SSTable之中有序的特點。
      
    • 可以進行分組壓縮，每個索引可以指向壓縮塊的起始點，來節省存儲空間與減少I/O帶寬的使用。

但是，如何讓我們寫入的鍵值對有序呢？這個問題在記憶體之中並不是什麼難事，如紅黑樹或AVL樹這些數據結構，可以按任何順序插入鍵，並按排序順序讀取它們。所以我們在使用SSTable時，會維護一個MemTable的數據結構在記憶體之中，當MemTable達到閥值時，我們將MemTable作為一個新的SSTable序列化到磁碟之上。同時利用後臺線程，不斷壓縮刪除舊的SSTable，來維護一個可迴圈運行的存儲系統。由於兩次寫入一次是在記憶體，一次磁碟寫入是連續的（append日誌），因此SSTable可以支持非常高的寫入吞吐量。

許多資料庫都是採用這樣的思路來高效的處理數據，如Cassandra，HBase，LevelDB，Bitcask等。Lucene的全文搜索的使用Elasticsearch和Solr索引引擎，也採用了類似的方法來存儲它的詞典，當然，全文索引比鍵值索引複雜得多，但基於一個類似的想法：給定搜索查詢中的一個詞，查找提及該詞的所有文檔（Web頁面、產品描述等）。這同樣是一個鍵值結構實現的，其中鍵是一個詞，而這個值是包含該詞的所有文檔的ID列表。

• B樹索引
  這個索引結構大家應該非常熟悉了，在關係型資料庫（如：MySQL，Oracle）與非關係型資料庫（如：MongoDB）之中都大量應用。B樹也把鍵值對進行了排序，它既允許高效的值查詢也允許高效的範圍查詢。
  哈希索引結構將數據分解成可變大小的段，通常是幾個兆位元組或更多的大小。而相比之下，樹型索引將數據分成固定大小的塊或頁，通常為4KB大小（有時更大），每次讀或寫都基於頁的大小。這種設計更接近於底層硬體，因為磁碟也是按固定大小的頁來排列的。B樹索引保證了：N個鍵總是有深度的O（log n）樹，大多數數據都可以放入到一個三或四層的B樹之中，（一個4頁的四級樹，分支繫數為500，可以存儲256TB）。下圖展示了我們怎麼樣使用B樹來查找“251”這個鍵:
  
  基本寫的操作是覆蓋舊數據的數據頁，重寫不會改變頁的位置；即，當頁被覆蓋時，對該頁的所有引用都保持不變。這與SSTable這樣的哈希索引結構形成鮮明對比，它有附加操作，但從不修改文件。
  而B樹索引的併發控制相對複雜，當多個線程會對樹進行訪問時，需要通過用鎖存器（輕量級鎖）保護樹的數據結構來完成。（這裡也可以用Copy on Write來快照隔離）而哈希索引結構的壓縮，合併則不會影響查詢，寫入等操作。

• 一些優缺點的探討

  （1）順序寫入通常比隨機寫入快得多，所以SSTable通常的寫入性能是相對優秀的。
  （2）由於SSTable壓縮與清理的線程存在，通常會有較低的存儲開銷。但是壓縮和清理磁碟的過程之中會與正常的請求服務產生磁碟競爭，導致吞吐量的下降。
  （3）由於SSTable會存在同一個鍵值的多個副本，對於實現事務等對於一致性要求更高的場景，樹型索引會表現的更加出色。

3.小結

樹型索引在資料庫架構是非常根深蒂固的，對於很多的工作負載提供始終如一的良好性能。而以SSTable為代表的哈希索引也越來越受歡迎。確定哪種類型的存儲引擎更適合應用場景，並沒有一個簡單易用的規則，因此需要我們對業務邏輯有更深層次的理解。