第一部分-資料系統基礎

1 可靠、可拓展與可維護的應用系統

2 資料模型與查詢語言

3 資料存儲與檢索

3.1 日志結構存儲

• 代表：Bitcask，LSM-Tree（Log Structed Merge Tree）
• 使用哈希索引實作
• 隻允許追加更新的資料檔案，以最後一次鍵值對為準
• 在記憶體存放key，以及value在硬碟中的偏移量，讀取時隻需一次磁盤尋址
• 如何防止耗盡磁盤空間？
  • 将日志分解為小段，以檔案大小限制，查找時依次向前查找
  • 在多個段上實行壓縮，隻保留最新的鍵值對，對于相同的key
• 崩潰恢複：Bitcask将hashmap快照存放于磁盤，來加快恢複速度
• 删除記錄: 墓碑機制，壓縮時直接忽略
• 并發控制：單個線程負責追加，允許多個線程讀取
• 缺點
  • 哈希表必須全部放入記憶體
  • 區間查詢效率不高
• 改進：SSTables
  • 名稱：排序字元串表
  • 記憶體中存放的叫稀疏索引，因為是間隔存放key及偏移的
  • 要求段檔案内按照key排序，且每個key在每個段檔案隻出現一次
  • 優點：
    • 合并更加簡單高效
    • 不必在記憶體存儲所有key及索引，可以根據已有key進行推測。eg：根據handbag和handsome，區間内查找handiword對應的value
  • 整體流程：
    • 寫入時，在記憶體維護一個類似平衡樹的資料結構（紅黑樹/AVL）
    • 當記憶體表超過門檻值，作為SSTables寫入磁盤
    • 背景周期性的執行段合并和壓縮過程，丢棄已經被覆寫或者删除的值
    • 在磁盤單獨保留日志，先寫日志，再寫記憶體表，崩潰後恢複記憶體表
    • 查詢多個段檔案可能會比較慢，可以使用布隆過濾器提前判斷
    • LevelDB和RocksDB使用分層壓縮（根據key範圍分裂成更小的SSTables，舊資料移動到單獨的層級），HBase使用大小分級（較新和較小的SSTables合并大較久和較大的SSTables），Cassandra同時支援兩種方案

3.2 B-trees

• 與SSTable相似：保留按key排序的kv對，實作高效kv查找，以及區間查詢
• 将資料庫分解成固定大小的頁（通常4KB），更接近底層硬體（硬碟）
• 一個頁包含的子頁引用，稱為分支因子
• 分支因子為500的4KB頁的四級樹，存儲高達256TB
• 具有n個鍵的btree，深度為O(logn)
• 缺點：
  • 寫入時直接覆寫頁，對ssd不友好
  • 如果需要覆寫多個頁，比如插入導緻頁溢出，會進行分裂，如果寫入部分頁後崩潰，可能會出現索引損壞，以及孤兒頁
  • WAL(Write Ahead Log)支援崩潰恢複，寫入時先寫WAL，再修改頁
  • 多線程通路B-tree，需要使用鎖存器（輕量級鎖）保護樹的資料結構
• 改進：
  • 儲存鍵的縮略資訊，而不是完整的鍵，節省頁空間（b+樹）
  • 使用寫時複制技術，替代覆寫頁+WAL的方案，同時對并發控制也有幫助（如LMDB）
  • 嘗試對樹進行布局，使相鄰葉子節點在磁盤相鄰，資料量變大之後，這個過程會變得困難

3.3 對比B-tree和LSM-tree

LSM-tree優點：

• LSM-tree能夠承受比B-tree更高的寫入吞吐量，部分因為有時寫放大（由于反複壓縮和SSTables和合并，一次資料寫入，會導緻多次磁盤寫，對ssd影響較大），部分因為以順序方式寫入緊湊的SSTables檔案，而不必重寫樹的多個頁
• LSM-tree不是面向頁，并且定期重寫SSTables以消除碎片化，故具有較低的存儲開銷，尤其是在使用分層壓縮時；由于碎片，B-tree當頁被分裂獲當一行的内容不能适合現有頁，頁中的空間可能會無法使用。
• 部分ssd的内部會使用日志結構化算法，将随機寫入轉換為順序寫入，一定程度上能減輕寫放大的危害

LSM-tree缺點：

• 硬碟并發的讀寫資源有限，有時壓縮過程會幹擾正在進行的讀寫操作
• 高寫入吞吐量時，磁盤的有限寫入帶寬，需要在初始寫入（記錄并重新整理記憶體表到硬碟）和背景運作的壓縮線程之間共享
• B-tree每個鍵都唯一對應索引某個位置，對事務語義的實作有幫助，可以直接将鎖定義到樹中；而LSM-tree一個鍵則可能存在多個副本，對事務支援不好

3.4 其他索引結構

二級索引

• 基于kv索引來建構，對于高效的聯結操作至關重要（我了解就是對外鍵建立索引）
• 鍵不唯一，兩種方式解決
  • 使索引每個值成為比對行辨別符的清單
  • 追加行辨別符來使鍵變得唯一

在索引中存儲值

• 索引中的值可以是實際行（聚集索引），也可以是指向行的引用（非聚集索引，存儲行的位置被稱為堆檔案）
• 當更新值不更改鍵時，堆檔案實作會非常高效
• 覆寫和聚集索引可以加快讀取速度，但是需要額外存儲，會增加寫入的開銷

多列索引

• 将幾個字段組合成一個鍵
• 建立方法：
  • 可以使用空格填充曲線将二維位置轉換為單個數字，然後使用B-tree索引（聯合索引）
  • 使用專門的空間索引，如R樹（HyperDex也使用了二級索引這種技術）

全文搜尋和模糊索引

• 支援對單詞的同義詞查詢
• Lecene支援在某個編輯距離内搜尋文本
• Lecene對詞典使用類似SSTables的結構，需要小記憶體結構來告訴查詢，為了找到一個鍵，需要排序檔案的那個偏移量。在LevelDB中，這個記憶體索引是一些鍵的稀疏集合（未存儲所有鍵），在Lecene中，這個記憶體索引是建中字元序列的有限狀态自動機，類似于字典樹

在記憶體中儲存所有内容

• 用于緩存，資料丢失可接受
• 提供了一些基于磁盤索引難以實作的資料模型，比如redis的幾種資料類型

3.5 事務處理與分析處理

OLTP

• Online Transaction Processing，線上事務處理
• 讀資料基于鍵，每次查詢傳回很少資料量
• 寫資料随機通路，低延遲寫入
• 使用場景為終端使用者，通過網絡應用程式
• 規模為GB-TB

OLAP

• • Online Analytic Processing，線上分析處理
• 讀資料特征，對大量資料進行彙總
• 寫資料批量導入（ETL）或者事件流
• 使用場景為分析師，為決策提供支援
• 規模為TB-PB

資料倉庫

• 包含公司所有OLTP系統的隻讀副本
• 在不影響OLTP的前提下盡情使用
• 可以針對分析通路模式進行優化

星型與雪花分析模式

• 當表關系可視化時，事實表位于中間，被一系列次元表包圍，表之間連接配接像星星的光芒

  雪花模式：

• 次元進一步細分為子空間

列式存儲

• 将每一列所有的值存儲在一起
• 每一行在所有列檔案中的偏移量相同（重要）
• 查詢時隻需要讀取和解析在該查詢中使用的列，節省大量工作

• 通常，列中不同值的數量小于行數
• 使用單獨位圖表示列值出現的情況
• 排序之後進行壓縮，a個1，b個0...可以極大減少空間占用
• Cassandra和HBase（內建自BigTable）有一個列族的概念，将一行所有列和行主鍵一起儲存，且不進行列壓縮，仍然是面向行存儲的

列存儲的排序

• 幫助進一步壓縮列
• 對前幾列壓縮會取得不錯的收益
• 為了防止寫入更加困難，借鑒了LSM-tree，寫入首先進入記憶體存儲區，添加到已排序結構中，然後準備寫入磁盤。當積累了足夠寫入時，他們與磁盤上的列檔案合并，并批量寫入新檔案（Vertica做了這個事兒）

聚合：資料立方體與物化視圖

• 物化聚合（COUNT/SUM/AVG等操作），重複查詢浪費性能
• 物化視圖：查詢結果的十幾副本，被寫入到磁盤
• 虛拟試圖：編寫查詢的快捷方式（mysql視圖，是一個虛表）
• 缺點：資料立方體缺乏像查詢原始資料的靈活性
• 僅當資料立方體可以對特性查詢顯著提升性能時，才會采用多為資料聚合