互聯⽹做得太棒了，以⾄于⼤多數⼈将它看作像太平洋這樣的⾃然資源，⽽不是什麼⼈⼯産物。
上⼀次出現這種⼤規模且⽆差錯的技術， 你還記得是什麼時候嗎？ -- 阿蘭·凱
本文将會介紹資料系統底層的基礎概念，⽆論是在單台機器上運⾏的單點資料系統，還是分布在多台機器上的分布式資料系統都适⽤。
第⼀部分将介紹本書使⽤的術語和⽅法。可靠性，可擴充性和可維護性 ，這些詞彙到底意味着什麼？如何實作這些⽬标？
第⼆部分将對⼏種不同的資料模型和查詢語⾔進⾏⽐較。從程式員的⻆度看，這是資料庫之間最明顯的差別。不同的資料模型适⽤于不同的應⽤場景。
第三部分将深⼊存儲引擎内部，研究資料庫如何在磁盤上擺放資料。不同的存儲引擎針對不同的負載進⾏優化，選擇合适的存儲引擎對系統性能有巨⼤影響。
第四部分将對⼏種不同的 資料編碼進⾏⽐較。特别研究了這些格式在應⽤需求經常變化、模式需要随時間演變的環境中表現如何。
目标與意義
現今很多應⽤程式都是 資料密集型（data-intensive） 的，⽽⾮ 計算密集型（compute-intensive）
的。是以CPU很少成為這類應⽤的瓶頸，更⼤的問題通常來⾃資料量、資料複雜性、以及資料的變更速
度。
資料密集型應⽤通常由标準元件建構⽽成，标準元件提供了很多通⽤的功能；例如，許多應⽤程式都需
要：
存儲資料，以便⾃⼰或其他應⽤程式之後能再次找到 （（資料庫（database））） ;
記住開銷昂貴操作的結果，加快讀取速度（緩存（cache）） ;
允許⽤戶按關鍵字搜尋資料，或以各種⽅式對資料進⾏過濾（搜尋索引（search indexes）） ;
向其他程序發送消息，進⾏異步處理（流處理（stream processing））;
定期處理累積的⼤批量資料（批處理（batch processing））;
如果這些功能聽上去平淡⽆奇，那是因為這些 資料系統（data system） 是⾮常成功的抽象：我們⼀直不假思索地使⽤它們并習以為常。絕⼤多數⼯程師不會幻想從零開始編寫存儲引擎，因為在開發應⽤時，資料庫已經是⾜夠完美的⼯具了。
但現實沒有這麼簡單。不同的應⽤有着不同的需求，因⽽資料庫系統也是百花⻬放，有着各式各樣的特性。實作緩存有很多種⼿段，建立搜尋索引也有好⼏種⽅法，諸如此類。是以在開發應⽤前，我們依然有必要先弄清楚最适合⼿頭⼯作的⼯具和⽅法。⽽且當單個⼯具解決不了你的問題時，組合使⽤這些⼯具可能還是有些難度的。
本部分将從我們所要實作的基礎⽬标開始：可靠、可擴充、可維護的資料系統，以及探讨考量這些⽬标的⽅法。
可靠性（Reliability）
可靠性意味着即使發⽣故障，系統也能正常⼯作。故障可能發⽣在硬體（通常是随機的
和不相關的），軟體（通常是系統性的Bug，很難處理），和⼈類（不可避免地時不時出錯）。容錯技術可以對終端⽤戶隐藏某些類型的故障。
容錯
造成錯誤的原因叫做故障（fault），能預料并應對故障的系統特性可稱為容錯（fault tolerant）或韌性（resilient）。
“容錯”⼀詞可能會産⽣誤導，因為它暗示着系統可以容忍所有可能的錯誤，但在實際中這是不可能的時，隻有談論特定類型的錯誤才有意義。
注意，故障（fault）不同于失效（failure）。故障通常定義為系統的⼀部分狀态偏離其标準，⽽失 效則是系統作為⼀個整體停⽌向⽤戶提供服務。故障的機率不可能降到零，是以最好設計容錯機制以防因故障⽽導緻失效。而我們的目的就是要利⽤不可靠的部件建構可靠系統的技術。
可擴充性（Scalability）
可擴充性意味着即使在負載增加（資料量、流量、複雜性）的情況下也有保持性能的政策。為了讨論可擴充性，我們⾸先需要定量描述負載和性能的⽅法。
描述負載
負載可以⽤⼀些稱為負載參數（load parameters）的數字來描述。參數的最佳選擇取決于系統架構，它可能是每秒向Web伺服器發出的請求、資料庫中的讀寫⽐率、聊天室中同時活躍的⽤戶數量、緩存命中率或其他東⻄。
除此之外，也許平均情況對你很重要，也許你的瓶頸是少數極端場景。
描述性能
⼀旦系統的負載被描述好，就可以研究當負載增加會發⽣什麼。我們可以從兩種⻆度來看：
a。增加負載參數并保持系統資源（CPU、記憶體、⽹絡帶寬等）不變時，系統性能将受到什麼影響？
b。增加負載參數并希望保持性能不變時，需要增加多少系統資源？
這兩個問題都需要性能資料，是以讓我們簡單地看⼀下如何描述系統性能。
吞吐量（throughput）：即每秒可以處理的記錄數量，或者在特定規模資料集上運⾏作業的總時間。
響應時間（response time）：即用戶端發送請求到接收響應之間的時間。
測量的數值分布（distribution）名額
算術平均值（arithmetic mean）：平均值并不是⼀個⾮常好的名額，
百分位點（percentiles）法：如果你想知道“典
型（typical）”響應時間，通常使⽤百分位點會更好。如果将響應時間清單按最快到最慢排序，那麼中位數（median）就在正中間。中位數也被稱為第50百分位點，有時縮寫為p50。
百分位點通常⽤于服務級别⽬标（SLO, service level objectives）和服務級别協定（SLA, service level agreements），即定義服務預期性能和可⽤性的合同。 SLA可能會聲明，如果服務響應時間的中位數⼩于200毫秒，且99.9百分位點低于1秒，則認為服務⼯作正常；如果響應時間更⻓，就認為服務不達标。
響應時間的⾼百分位點（也稱為尾部延遲（tail latencies））⾮常重要，因為它們直接影響⽤戶的服務體驗。
應對負載的⽅法
⼈們經常讨論縱向擴充（scaling up）（垂直擴充（vertical scaling），轉向更強⼤的機器）和橫向擴充（scaling out）（⽔平擴充（horizontal scaling），将負載分布到多台⼩機器上）之間的對⽴。
跨多台機器配置設定負載也稱為“⽆共享（shared-nothing）”架構。可以在單台機器上運⾏的系統通常更簡單，但⾼端機器可能⾮常貴，是以⾮常密集的負載通常⽆法避免地需要橫向擴充。現實世界中的優秀架構需要将這兩種⽅法務實地結合，因為使⽤⼏台⾜夠強⼤的機器可能⽐使⽤⼤量的⼩型虛拟機更簡單也更便宜。
有些系統是彈性（elastic）的，這意味着可以在檢測到負載增加時⾃動增加計算資源，⽽其他系統則是⼿動擴充（⼈⼯分析容量并決定向系統添加更多的機器）。如果負載極難預測（highly
unpredictable），則彈性系統可能很有⽤，但⼿動擴充系統更簡單，并且意外操作可能會更少（參閱“重新平衡分區”）。
可維護性（Maintainability）
可維護性有許多⽅⾯，但實質上是關于⼯程師和運維團隊的⽣活品質的。良好的抽象可以幫助降低複雜度，并使系統易于修改和适應新的應⽤場景。良好的可操作性意味着對系統的健康狀态具有良好的可⻅性，并擁有有效的管理⼿段。
我們應該以這樣⼀種⽅式來設計軟體：在設計之初就盡量考慮盡可能減少維護期間的痛苦，從⽽避免⾃⼰的軟體系統變成遺留系統。為此，我們将特别關注軟體系統的三個設計原則：
可操作性（Operability）：便于運維團隊保持系統平穩運⾏。
簡單性（Simplicity）：從系統中消除盡可能多的複雜度（complexity），使新⼯程師也能輕松了解系統。
可演化性（evolability）：使⼯程師在未來能輕松地對系統進⾏更改，當需求變化時為新應⽤場景做适配。也稱為可擴充性（extensibility），可修改性（modifiability）或可塑性（plasticity）。
目标與意義：資料模型可能是軟體開發中最重要的部分了，因為它們的影響如此深遠：不僅僅影響着軟體的編寫⽅式，⽽且影響着我們的解題思路。
多數應⽤使⽤層層疊加的資料模型建構。每個層都通過提供⼀個明确的資料模型來隐藏更低層次中的複雜性。這些抽象允許不同的⼈群有效地協作，例如資料庫⼚商的⼯程師和使⽤資料庫的應⽤程式開發⼈員。
因為資料模型對上層軟體的功能（能做什
麼，不能做什麼）有着⾄深的影響，是以選擇⼀個适合的資料模型是⾮常重要的。
常見資料模型
關系模型
現在最著名的資料模型可能是SQL。它基于Edgar Codd在1970年提出的關系模型【1】：資料被組織成關系（SQL中稱作表），其中每個關系是元組（SQL中稱作⾏)的⽆序集合。
特點
事務處理
批處理
阻抗不比對：資料存儲在關系表中，那麼需要⼀個笨拙的轉換層，處于應⽤程式代碼中的對象和表，⾏，列的資料庫模型之間。模型之間的不連貫有時被稱為阻抗不比對（impedance mismatch）。
多對⼀和多對多的關系
查詢資料簡單：在關系資料庫中，“通路路徑”是由查詢優化器⾃動⽣成的，⽽不是由程式員⽣成。
文檔模型
Nosql
“NoSQL”這個名字讓⼈遺憾，因為實際上它并沒有涉及到任何特定的技術。最初它隻是作為⼀個醒⽬的Twitter标簽，⽤在2009年⼀個關于分布式，⾮關系資料庫上的開源聚會上。後被追溯性地重新解釋為不僅是SQL（Not Only SQL）。
驅動Nosql資料庫的幾個因素：
i. 需要⽐關系資料庫更好的可擴充性，包括⾮常⼤的資料集或⾮常⾼的寫⼊吞吐量。
ii. 相⽐商業資料庫産品，免費和開源軟體更受偏愛。
iii. 關系模型不能很好地⽀持⼀些特殊的查詢操作。
iv. 受挫于關系模型的限制性，渴望⼀種更具多動态性與表現⼒的資料模型。
資料通常是⾃我包含的，⽽且⽂檔之間的關系⾮常稀少。
在表示多對⼀和多對多的關系時，關系資料庫和⽂檔資料庫并沒有根本的不同：在這兩種情況
下，相關項⽬都被⼀個唯⼀的辨別符引⽤，這個辨別符在關系模型中被稱為外鍵，在⽂檔模型中稱為⽂檔引⽤【9】。該辨別符在讀取時通過連接配接或後續查詢來解析。
通路記錄的唯⼀⽅法是跟随從根記錄起沿這些鍊路所形成的路徑。這被稱為通路路徑（access path）。
對比關系模型和文檔模型
使應用程式代碼更簡單方面
如果應⽤程式中的資料具有類似⽂檔的結構（即，⼀對多關系樹，通常⼀次性加載整個樹），那麼使⽤⽂檔模型可能是⼀個好主意。
關系模型可能導緻繁瑣的模式和不必要的複雜的應⽤程式代碼。
⽂檔資料庫對連接配接的糟糕⽀持有可能會是⼀個問題，這取決于應⽤程式。如果你的應⽤程式确實使⽤多對多關系，文檔模型通過反規範化可以減少對連接配接的需求，但是應⽤程式代碼需要做額外的⼯作來保持資料的⼀緻性。這也将複雜性轉移到應⽤程式中，并且通常⽐由資料庫内的專⽤代碼執⾏的連接配接慢。在這種情況下，使⽤⽂檔模型會導緻更複雜的應⽤程式代碼和更差的性能。
靈活性方面
⽂檔資料庫有時稱為⽆模式（schemaless），但這具有誤導性，因為讀取資料的代碼通常假定某種結構，即存在隐式模式，但不由資料庫強制執⾏。⼀個更精确的術語是讀時模式schema-onread：資料的結構是隐含的，隻有在資料被讀取時才被解釋，相應的是寫時模式schema-onwrite：傳統的關系資料庫⽅法中，模式明确，且資料庫確定所有的資料都符合其模式。
當由于某種原因（例如，資料是異構的）集合中的項⽬并不都具有相同的結構時,讀時模式更具優勢。但是，當所有記錄都具有相同的結構，那麼寫時模式是記錄并強制這種結構的有效機制。
查詢資料的局部性方面
⽂檔通常以單個連續字元串形式進⾏存儲，編碼為JSON，XML或其⼆進制變體（如MongoDB的BSON）。如果應⽤程式經常需要通路整個⽂檔（例如，将其渲染⾄⽹⻚），那麼存儲局部性會帶來性能優勢。如果将資料分割到多個表中，則需要進⾏多次索引查找才能将其全部檢索出
來，這可能需要更多的磁盤查找并花費更多的時間。
局部性僅僅适⽤于同時需要⽂檔絕⼤部分内容的情況。資料庫通常需要加載整個⽂檔，即使隻通路其中的⼀⼩部分，這對于⼤型⽂檔來說是很浪費的。更新⽂檔時，通常需要整個重寫。且隻有不改變⽂檔⼤⼩的修改才可以容易地原地執⾏。這些性能限制⼤⼤減少了⽂檔資料庫的實⽤場景。
圖資料模型
如果你的應⽤程式⼤多數的關系是⼀對多關系（樹狀結構化資料），或者⼤多數記錄之間不存在關系，那麼使⽤⽂檔模型是合适的。
但是，要是多對多關系在你的資料中很常⻅，随着資料之間的連接配接變得更加複雜，使用圖資料模型更加⾃然。
⼀個圖由兩種對象組成：頂點（vertices）（也稱為節點（nodes） 或實體（entities）），和邊 （edges）（ 也稱為關系（relationships）或弧 （arcs） ）。
有⼏種不同但相關的⽅法⽤來建構和查詢圖中的資料。如屬性圖模型和三元組存儲模型（triple-store）。
屬性圖模型
在屬性圖模型中，每個頂點（vertex）包括：
唯⼀的辨別符
⼀組出邊（outgoing edges）
⼀組⼊邊（ingoing edges）
⼀組屬性（鍵值對）
每條邊（edge）包括：
唯⼀辨別符
邊的起點/尾部頂點（tail vertex）
邊的終點/頭部頂點（head vertex）
描述兩個頂點之間關系類型的标簽
可以将圖存儲看作由兩個關系表組成：⼀個存儲頂點，另⼀個存儲邊。可以用頭部和尾部頂點⽤來存儲每條邊；頂點的輸⼊或輸出邊也同理。
- 關于這個模型的⼀些重要特性，這些特性為資料模組化提供了很⼤的靈活性：
任何頂點都可以有⼀條邊連接配接到任何其他頂點。沒有模式限制哪種事物可不可以關聯。
給定任何頂點，可以⾼效地找到它的⼊邊和出邊，從⽽周遊圖，即沿着⼀系列頂點的路徑前後移動。
通過對不同類型的關系使⽤不同的标簽，可以在⼀個圖中存儲⼏種不同的資訊，同時仍然保持⼀個清晰的資料模型。
4.在可演化性方面富有優勢：當向應⽤程式添加功能時，可以輕松擴充圖以适應應⽤程式資料結構的變化。
- Cypher查詢語⾔
通常對于聲明式查詢語⾔來說，在編寫查詢語句時，不需要指定執⾏細節：查詢優化程式會⾃動選擇預測效率最⾼的政策，是以你可以繼續編寫應⽤程式的其他部分。
原始資料類型中的值，例如字元串或數字。在這種情況下，三元組的謂語和賓語相當于主語頂點上的屬性的鍵和值。例如， (lucy, age, 33) 就像屬性 {“age”：33} 的頂點lucy。
圖中的另⼀個頂點。在這種情況下，謂語是圖中的⼀條邊，主語是其尾部頂點，⽽賓語是其頭部頂點。例如，在 (lucy, marriedTo, alain) 中主語和賓語 lucy 和 alain 都是頂點，并且謂語
marriedTo 是連接配接他們的邊的标簽。
- SPARQL查詢語⾔
SPARQL，這使得它們看起來⾮常相似【37】。
查詢語言
當引⼊關系模型時，關系模型包含了⼀種查詢資料的新⽅法：SQL是⼀種【聲明式】查詢語⾔，⽽IMS和CODASYL使⽤【指令式】代碼來查詢資料庫。
聲明式查詢語言
聲明式查詢語言緊密地遵循關系代數的結構。
關注結果不關注過程：在聲明式查詢語⾔（如SQL或關系代數）中，你隻需指定所需資料的模式 - 結果必須符合哪些條件，以及如何将資料轉換（例如，排序，分組和集合） - 但不是如何實作這⼀⽬标。資料庫系統的查詢優化器決定使⽤哪些索引和哪些連接配接⽅法，以及以何種順序執⾏查詢的各個部分。
簡潔易懂：聲明式查詢語⾔是迷⼈的，因為它通常⽐指令式API更加簡潔和容易。但更重要的是，它還隐藏了資料庫引擎的實作細節，這使得資料庫系統可以在⽆需對查詢做任何更改的情況下進⾏性能提升。
适合并⾏執⾏：聲明式語⾔往往适合并⾏執⾏。現在，CPU的速度通過核心的增加變得更快，⽽不是以⽐以前更⾼的時脈速度運⾏。指令代碼很難在多個核心和多個機器之間并⾏化，因為它指定了指令必須以特定順序執⾏。
圖的聲明式查詢語⾔
Cypher，SPARQL和Datalog。
指令式查詢語言
指令式語⾔告訴計算機以特定順序執⾏某些操作。
在資料庫中，使⽤像SQL這樣的聲明式查詢語⾔⽐使⽤指令式查詢API要好得多 6 。
聲明式查詢語⾔的優勢不僅限于資料庫。
MapReduce既不是⼀個聲明式的查詢語⾔，也不是⼀個完全指令式的查詢API，⽽是處于兩者之間：查詢的邏輯⽤代碼⽚斷來表示，這些代碼⽚段會被處理架構重複性調⽤。
其他(專業)資料模型
使⽤基因組資料的研究⼈員通常需要執⾏序列相似性搜尋，這意味着需要⼀個很⻓的字元串（代表⼀個DNA分⼦），并在⼀個擁有類似但不完全相同的字元串的⼤型資料庫中尋找比對。這⾥所描述的資料庫都不能處理這種⽤法，這就是為什麼研究⼈員編寫了像GenBank這樣的專⻔的基因組資料庫軟體的原因【48】。
粒⼦實體學家數⼗年來⼀直在進⾏⼤資料類型的⼤規模資料分析，像⼤型強⼦對撞機（LHC）這樣的項⽬現在可以⼯作在數百億兆位元組的範圍内！在這樣的規模下，需要定制解決⽅案來阻住硬體成本的失控【49】。
全⽂搜尋可以說是⼀種經常與資料庫⼀起使⽤的資料模型。資訊檢索是⼀個很⼤的專業課題，我們不會在本書中詳細介紹，但是我們将在第三章和第三章中介紹搜尋索引。
目标&意義
本章主題：在第2章中，我們讨論了資料模型和查詢語⾔，即程式員将資料錄⼊資料庫的格式，以及再次找回需要的資料的機制。在本章中我們會從資料庫的視⻆來讨論同樣的問題：資料庫如何存儲我們提供的資料，以及如何在我們需要時重新找到資料。
資料庫的根本功能：⼀個資料庫在最基礎的層次上需要完成兩件事情：當你把資料交給資料庫時，它應當把資料存儲起來；⽽後當你向資料庫要資料時，它應當把資料傳回給你。
目标：作為⼀名應⽤程式開發⼈員，如果您掌握了有關存儲引擎内部的知識，那麼您就能更好地了解哪種⼯具最适合您的特定應⽤程式。以及需要調整資料庫的什麼參數，以達到期望的效果。
驅動資料庫的資料結構
哈希索引
索引（index）為了⾼效查找資料庫中特定鍵的值的一種資料結構。添加與删除索引，不會影響資料的内容，隻影響查詢的性能。維護額外的結構會産⽣開銷，特别是在寫⼊時。
存儲系統中⼀個重要的權衡：精⼼選擇的索引加快了讀查詢的速度，但是每個索引都會拖慢寫⼊速度。
記憶體中的哈希映射，其中每個鍵都映射到⼀個資料⽂件中的位元組偏移量，指明可以找到對應值的位置。當你想查找⼀個值時，使⽤哈希映射來查找資料⽂件中的偏移量，尋找（seek）該位置并讀取該值。
如果隻是追加寫⼊⼀個⽂件，如何避免最終⽤完磁盤空間？⼀種好的解決⽅案是：分段壓縮和合并算法
i。将⽇志分為特定⼤⼩的段，當⽇志增⻓到特定尺⼨時關閉目前段⽂件，并開始寫⼊⼀個新的段⽂件。然後，我們就可以對這些段進⾏壓縮（compaction）。壓縮意味着在⽇志中丢棄重複的鍵，隻保留每個鍵的最近更新。
ii。由于壓縮經常會使得段變得很⼩（假設在⼀個段内鍵被平均重寫了好⼏次），我們也可以在執⾏壓縮的同時将多個段合并在⼀起。
iii。段被寫⼊後永遠不會被修改，是以合并的段被寫⼊⼀個新的⽂件。當機段的合并和壓縮可以在背景線程中完成，在進⾏時，我們仍然可以繼續使⽤舊的段⽂件來正常提供讀寫請求。合并過程完成後，我們将讀取請求轉換為使⽤新的合并段⽽不是舊段 —— 然後可以簡單地删除舊的段⽂件。
為什麼不更新⽂件，隻能追加設計的原因
有⼏個：
i。追加和分段合并是順序寫⼊操作，通常⽐随機寫⼊快得多，尤其是在磁盤旋轉硬碟上。
ii。如果段⽂件是附加的或不可變的，并發和崩潰恢複就簡單多了。例如，您不必擔⼼在更新值時發⽣崩潰的情況，⽽将包含舊值和新值的⼀部分的⽂件保留在⼀起。
iii。合并舊段可以避免資料⽂件随着時間的推移⽽分散的問題。
哈希表索引的局限性：
i。散清單必須能放進記憶體。磁盤哈希映射表現較差。它需要⼤量的随機通路I/O，當它變滿時增⻓是很昂貴的，并且散列沖突需要很多的邏輯。
ii。範圍查詢效率不⾼。
SSTable和LSM樹
SSTable：在普通⽇志結構存儲段都是⼀系列鍵值對，鍵值對的順序為寫⼊的順序出現，⽇志中稍後的值優先于⽇志中較早的相同鍵的值。此時，如果我們要求鍵值對的序列按鍵排序。則這種格式就是【排序字元串表（Sorted String Table）】，簡稱SSTable。
SSTable的優勢：
1.合并段是簡單⽽⾼效的，即使⽂件⼤于可⽤記憶體。
2.因為鍵是有序的，是以在⽂件中找到⼀個特定的鍵，不再需要儲存記憶體中所有鍵的索引。
3.可以将記錄分組到塊中，并在寫⼊磁盤之前進⾏壓縮 ，稀疏記憶體中索引的每個條⽬。不僅節省了磁盤空間，壓縮還可以減少IO帶寬的使⽤。
建構和維護SSTables
a。寫⼊時，将其添加到記憶體中的平衡樹資料結構（例如，紅⿊樹）。這個記憶體樹有時被稱為【記憶體表（memtable）】。
b。當記憶體表⼤于某個門檻值（通常為⼏兆位元組）時，将其作為SSTable⽂件寫⼊磁盤。這可以⾼效地完成，因為樹已經維護了按鍵排序的鍵值對。新的SSTable⽂件成為資料庫的最新部分。當SSTable被寫⼊磁盤時，寫⼊可以繼續到⼀個新的記憶體表執行個體。
c。為了提供讀取請求，⾸先嘗試在記憶體表中找到關鍵字，然後在最近的磁盤段中，然後在下⼀個較舊的段中找到該關鍵字。
d。有時會在背景運⾏合并和壓縮過程以組合段⽂件并丢棄覆寫或删除的值。
e。這個⽅案效果很好。它隻會遇到⼀個問題：如果資料庫崩潰，則最近的寫⼊（在記憶體表中，但尚未寫⼊磁盤）将丢失。為了避免這個問題，我們可以在磁盤上儲存⼀個單獨的⽇志，每個寫⼊都會⽴即被附加到磁盤上。每當記憶體表寫出到SSTable時，相應的⽇志都可以被丢棄。該⽇志的唯⼀⽬的是在崩潰後恢複記憶體表。
SSTables的應用
以上描述的算法本質上正是LevelDB和RocksDB所使用的，主要用于嵌入到其他應用程式的key-value存儲引擎庫。類似的引擎還被用于Cassandra和HBase。
LSM存儲引擎
基于SSTable和記憶體表memTable的這種索引結構最初被成為基于日志的合并樹，即LSM（Log-Structure Merge Tree）。這種基于合并和壓縮排序檔案原理的存儲引擎通常都被成為LSM存儲引擎，
Lucene索引引擎
Lucene是Elasticsearch和Solr使⽤的⼀種全⽂搜尋的索引引擎，它使⽤類似的⽅法來存儲它的詞典。全⽂索引⽐鍵值索引複雜得多，但是基于類似的想法：在搜尋查詢中給出⼀個單詞，找到
提及單詞的所有⽂檔（⽹⻚，産品描述等）。這是通過鍵值結構實作的，其中鍵是單詞（關鍵詞
（term）），值是包含單詞（⽂章清單）的所有⽂檔的ID的清單。在Lucene中，從術語到釋出清單的這種映射儲存在SSTable類的有序⽂件中，根據需要在背景合并。
性能優化：
LSM樹算法在大多數情況向性能表現良好，但當查找資料庫中不存在的鍵時，LSM樹算法可能會很慢：您必須檢查記憶體表，然後将這些段⼀直回到最⽼的（可能必須從磁盤讀取每⼀個），然後才能确定鍵不存在。為了優化這種通路，存儲引擎通常使⽤額外的Bloom過濾器。
不同的政策來也會影響SSTables被壓縮和合并順序和時機。最常⻅的選擇是⼤⼩分級壓縮和分層壓縮。
大小分級壓縮
HBase使⽤⼤⼩分級壓縮，Cassandra同時⽀持。
在大小分級壓縮中，較新的和較小的SSTable被連續合并到較舊和較大的SSTables。
分層壓縮
LevelDB和RocksDB使⽤分層壓縮（LevelDB是以得名），Cassandra同時⽀持。
在分層壓縮中，鍵的範圍分裂成多個更小的SSTable，舊資料被移動到單獨的“層級”，這樣壓縮可以逐漸進行并節省磁盤空間。
LSM樹的基本思想簡單⽽有效：儲存⼀系列在背景合并的SSTables。
即使資料集⽐可⽤記憶體⼤得多，它仍能繼續正常⼯作。由于資料按排序順序存儲，是以可以⾼效地執⾏範圍查詢（掃描所有⾼于某些最⼩值和最⾼值的所有鍵），并且因為磁盤寫⼊是連續的，是以LSM樹可以⽀持⾮常⾼的寫⼊吞吐量。
B樹
以上讨論的⽇志結構索引正處在逐漸被接受，而應用最廣泛的索引結構是B樹。
像SSTables⼀樣，B樹保持按鍵排序的鍵值對，這允許⾼效的鍵值查找和範圍查詢。
⽇志結構索引将資料庫分解為可變⼤⼩的段，通常是⼏兆位元組或更⼤的⼤⼩，并且總是按順序編寫段。而B樹将資料庫分解成固定⼤⼩的塊或⻚⾯，傳統上⼤⼩為4KB（有時會更⼤），并且⼀次隻能讀取或寫⼊⼀個⻚⾯。這種設計更接近于底層硬體，因為磁盤也被安排在固定⼤⼩的塊中。
每個⻚⾯都可以使⽤位址或位置來辨別，這允許⼀個⻚⾯引⽤另⼀個⻚⾯，類似于指針。我們可以在磁盤中使⽤這些⻚⾯引⽤來建構⼀個⻚⾯樹，⽽不是在記憶體中。
讓B樹更可靠
B樹的基本底層寫操作是⽤新資料覆寫磁盤上的⻚⾯。假定覆寫不改變⻚⾯的位置; 即當⻚⾯被覆寫時，對該⻚⾯的所有引⽤保持完整。這與⽇志結構索引（如LSM樹）形成鮮明對⽐，後者隻附加到⽂件（并最終删除過時的⽂件），但從不修改⽂件。但此過程是一個複雜的操作，會産生各種問題，如下：
問題1: 頁分裂過程中，如果此時資料庫崩潰，可能導緻損壞的索引，如産生孤兒頁面，既不是任何父頁的子頁。
解決方案：預寫式⽇志（WAL,write-ahead-log），也稱為重做⽇志（redo log）。該磁盤資料結構是⼀個僅追加的⽂件，每個B樹修改都可以應⽤到樹本身的⻚⾯上。當資料庫在崩潰後恢複時，這個⽇志被⽤來使B樹恢複到⼀緻的狀态。
問題2: 并發問題：更新⻚⾯的⼀個額外的複雜情況是，如果多個線程要同時通路B樹，則需要仔細的并發控制，否則線程可能會看到樹處于不⼀緻的狀态。
解決方案：這種情況通常通過使⽤【鎖存器（latches）】（輕量級鎖）保護樹的資料結構來完成。⽇志結構化的⽅法在這⽅⾯更簡單，因為它們在背景進⾏所有的合并，⽽不會⼲擾傳⼊的查詢，并且不時地将舊的分段原⼦交換為新的分段。
B樹優化
a。寫時複制技術：⼀些資料庫（如LMDB）使⽤寫時複制⽅案【21】，⽽不是覆寫⻚⾯并維護WAL進⾏崩潰恢複。修改的⻚⾯被寫⼊到不同的位置，并且樹中的⽗⻚⾯的新版本被建立，指向新的位置。這種⽅法對于并發控制也很有⽤，資料庫“快照隔離和可重複讀”中也有類似用法。
b。壓縮鍵的⼤⼩：可以通過壓縮鍵，不存儲整個鍵來節省⻚⾯空間，特别是在樹内部的⻚⾯上，鍵需要提供⾜夠的資訊來充當鍵範圍之間的邊界。在⻚⾯中包含更多的鍵允許樹具有更⾼的分⽀因⼦，是以更少的層次。
c。布局樹：通常，⻚⾯可以放置在磁盤上的任何位置，如果查詢需要按照順序掃描⼤部分關鍵字範圍，每個讀取的⻚⾯都可能需要磁盤查找，性能不太好。是以，許多B樹實作嘗試布局樹，使得葉⼦⻚⾯按順序出現在磁盤上。但是，随着樹的增⻓，維持這個順序是很困難的。相⽐之下，由于LSM樹在合并過程中⼀次⼜⼀次地重寫存儲的⼤部分，是以它們更容易使順序鍵在磁盤上彼此靠近。
d。樹中添加額外的指針。例如，每個葉⼦⻚⾯可以在左邊和右邊具有對其兄弟⻚⾯的引⽤，這允許不跳回⽗⻚⾯就能順序掃描。
e。B樹的變體如分形樹借⽤⼀些⽇志結構的思想來減少磁盤尋道（⽽且它們與分形⽆關）。
比較B樹與LSM樹
我們将簡要讨論⼀些在衡量存儲引擎性能時值得考慮的事情
寫放⼤（write amplification）：在資料庫的⽣命周期中寫⼊資料庫導緻對磁盤的多次寫⼊，被稱為寫放⼤。
在寫⼊繁重的應⽤程式中，性能瓶頸可能是資料庫可以寫⼊磁盤的速度。在這種情況下，寫放⼤會導緻直接的性能代價，降低每秒的寫入次數。
LSM樹
優點
通常LSM樹的寫⼊速度更快。順序寫⼊⽐随機寫⼊快得多。
資料在磁盤上更靠近，減少磁盤查找。由于LSM樹在合并過程中⼀次⼜⼀次地重寫存儲的⼤部分，是以它們更容易使順序鍵在磁盤上彼此靠近。
沒有并發問題。⽇志結構化的⽅法在背景進⾏所有的合并，⽽不會⼲擾傳⼊的查詢，并且不時地将舊的分段原⼦交換為新的分段。
更⾼的寫⼊吞吐量：LSM樹通常能夠⽐B樹⽀持更⾼的寫⼊吞吐量，部分原因是它們有時具有【較低的寫放⼤】（這取決于存儲引擎配置和⼯作負載），部分是因為它們順序地寫⼊緊湊的SSTable⽂件⽽不是必須覆寫樹中的⼏個⻚⾯。這種差異在磁性硬碟驅動器上尤其重要，【順序寫⼊⽐随機寫⼊快得多】。
LSM樹可以被壓縮得更好，碎片更少。LSM樹不是⾯向⻚⾯的，并且定期重寫SSTables以【去除碎⽚】，是以它們具有較低的存儲開銷，特别是當使⽤平坦壓縮時。
B樹存儲引擎會由于頁分裂，⽽留下⼀些不能使用的磁盤空間，進而産生磁盤碎片。
缺點
LSM樹上的讀取通常⽐較慢。因為它們必須在壓縮的不同階段檢查⼏個不同的資料結構和SSTables。
讀寫操作與壓縮公用磁盤資源，進而影響讀寫操作速度。⽇志結構存儲的缺點是壓縮過程有時會⼲擾正在進⾏的讀寫操作。盡管存儲引擎嘗試逐漸執⾏壓縮⽽不影響并發通路，但是磁盤資源有限，是以很容易發⽣請求需要等待⽽磁盤完成昂貴的壓縮操作。
在更⾼百分⽐的情況下（參閱“描述性能”），⽇志結構化存儲引擎的查詢響應時間有時會相當⻓，⽽B樹的⾏為則相對更具可預測性。
寫入與壓縮公用磁盤帶寬，進而影響寫入吞吐量。壓縮的另⼀個問題出現在⾼寫⼊吞吐量：磁盤的有限寫⼊帶寬需要在初始寫⼊（記錄和重新整理記憶體表到磁盤）和在背景運⾏的壓縮線程之間共享。
壓縮速率影響讀取速度。如果寫⼊吞吐量很⾼，并且壓縮沒有仔細配置，壓縮跟不上寫⼊速率。在這種情況下，磁盤上未合并段的數量不斷增加，直到磁盤空間⽤完，讀取速度也會減慢，因為它們需要檢查更多段⽂件。通常情況下，即使壓縮⽆法跟上，基于SSTable的存儲引擎也不會限制傳⼊寫⼊的速率，此時需要進⾏明确的監控來檢測這種情況。
不支援事務。⽇志結構化的存儲引擎可能在不同的段中有相同鍵的多個副本，不利于實作事務。B樹的⼀個優點是每個鍵隻存在于索引中的⼀個位置，⽽這使得B樹在想要提供強⼤的事務語義的資料庫中很有吸引⼒：在許多關系資料庫中，事務隔離是通過在鍵範圍上使⽤鎖來實作的。
通常B樹的讀取速度更快。LSM樹的寫⼊速度更快。
強大的事務支援。
維持資料的順序較難。随着樹的增⻓，維持葉⼦⻚⾯按順序出現在磁盤上是很困難的，即使B樹實作使用布局樹。
并發問題。需要通過使⽤鎖存器（latches）（輕量級鎖）保護樹的資料結構來完成。
B樹的寫入速度較慢。B樹索引必須⾄少兩次寫⼊每⼀段資料：⼀次寫⼊預先寫⼊⽇志，⼀次寫⼊樹⻚⾯本身（也許再次分⻚）。即使在該⻚⾯中隻有⼏個位元組發⽣了變化，也需要⼀次編寫整個⻚⾯的開銷。
B樹索引必須⾄少兩次寫⼊每⼀段資料：⼀次寫⼊預先寫⼊⽇志，⼀次寫⼊樹⻚⾯本身（也許再次分⻚）。即使在該⻚⾯中隻有⼏個位元組發⽣了變化，也需要⼀次編寫整個⻚⾯的開銷。
其他結構
主鍵索引primary index：
主鍵唯⼀辨別關系表中的⼀⾏，或⽂檔資料庫中的⼀個⽂檔或圖形資料庫中的⼀個頂點。資料庫中的其他記錄可以通過其主鍵（或ID）引⽤該⾏/⽂檔/頂點，并且索引⽤于解析這樣的引⽤。
二級索引：
⼀個⼆級索引可以很容易地從⼀個鍵值索引建構。⼆級索引的鍵不是唯⼀的，可能有許多⾏（⽂檔，頂點）具有相同的鍵。
聚簇索引clustered index：
在索引中存儲所有⾏資料。在某些情況下，從索引到堆⽂件的額外跳躍對讀取來說性能損失太⼤，是以可能希望将索引⾏直接存儲在索引中，這被稱為聚集索引。例如，在MySQL的InnoDB存儲引擎中，表的主鍵總是⼀個聚簇索引，⼆級索引⽤主鍵⽽不是堆⽂件中的位置。
非聚簇索引nonclustered index：
僅在索引中存儲對資料的引⽤。
覆寫索引covering index：
在聚集索引和⾮聚集索引之間的折衷被稱為包含列的索引（index with included columns） 或覆寫索引，其存儲表的⼀部分在索引内。這允許通過單獨使⽤索引來回答⼀些查詢，這種情況叫做：索引覆寫（cover）了查詢。
記憶體資料庫
Memcached
Redis
VoltDB，MemSQL和Oracle TimesTen等
事務處理還是分析處理？
存儲引擎分類
a.線上事務處理（OLTP, OnLine
Transaction Processing）
通常⾯向⽤戶
可能會接受處理⼤量的請求；每個查詢僅接受少量記錄，要求較低。
磁盤尋道時間往往是這⾥的瓶頸。
存儲引擎使⽤索引來提高查詢效率。
b.線上分析處理（OLAP, OnLine Analytice
Processing）
主要由業務分析⼈員使⽤
處理⽐OLTP系統少得多的查詢量；但是每個查詢通常要求很⾼，需要在短時間内掃描數百萬條記錄。
磁盤帶寬（不是查找時間）往往是瓶頸。
列式存儲是這種⼯作負載較為流⾏的解決
⽅案。
c.OLTP對比OLAP
OLTP兩大主流存儲引擎
a。日志結構學派
特點：隻允許追加寫⽂件(append only)和删除過時的⽂件，但不會更新已經寫⼊的⽂件。主要想法是，他們系統地将随機通路寫⼊順序寫⼊磁盤，由于硬碟驅動器和固态硬碟的性能特點，可以實作更⾼的寫⼊吞吐量。
案例： Bitcask，SSTables，LSM樹，
LevelDB，Cassandra，HBase，Lucene等。
b。就地更新學派
特點：将磁盤視為⼀組可以覆寫的固定⼤⼩的⻚⾯。
案例：基于B樹實作資料庫。
列式存儲
OLAP⼯作負載比OLTP高的原因：當您的查詢需要在⼤量⾏中順序掃描時，索引的相關性就會降低很多。相反，⾮常緊湊地編碼資料變得⾮常重要，以最⼤限度地減少查詢需要從磁盤讀取的資料量。
可演化性：應⽤程式不可避免地随時間⽽變化。新産品的推出，對需求的深⼊了解，或者商業環境的變化，總會伴随着功能（feature）的增增改改。第⼀章介紹了可演化性(evolvability)的概念：應該盡⼒建構能靈活适應變化的系統（參閱“可演化性：擁抱變化”）。
在⼤多數情況下，修改應⽤程式的功能也意味着其存儲的資料格式的更改，當資料格式（format）或模式（schema）發⽣變化時，通常需要對應⽤程式代碼進⾏相應的更改。但在⼤型應⽤程式中，一般需要執行滾動更新。
滾動更新：新版本的服務逐漸部署到少數節點，⽽不是同時部署到所有節點。滾動更新允許在不停機的情況下釋出新版本的服務，并使部署⻛險降低。從⽽⿎勵在罕⻅的⼤型版本上頻繁釋出⼩型版本，同時允許在影響⼤量⽤戶之前檢測并復原有故障的版本。這些屬性對于可演化性，以及對應⽤程式進⾏更改的容易性都是⾮常有利的。
相容性：滾動更新意味着新舊版本的代碼，以及新舊資料格式可能會在系統中同時共處。系統想要繼續順利運⾏，就需要保持雙向相容性：
i。向後相容 (backward compatibility)：新代碼可以讀舊資料。
ii。向前相容 (forward compatibility)：舊代碼可以讀新資料。
編碼影響點
1.效率
2.應用程式的體系結構和部署選項
編碼格式及其相容性
概念
程式通常（⾄少）使⽤兩種形式的資料：
在記憶體中，資料儲存在對象，結構體，清單，數組，哈希表，樹等中。 這些資料結構針對CPU的⾼效通路和操作進⾏了優化（通常使⽤指針）。
如果要将資料寫⼊⽂件，或通過⽹絡發送，則必須将其編碼（encode）為某種⾃包含的位元組序列（例如，JSON⽂檔）。 由于每個程序都有⾃⼰獨⽴的位址空間，⼀個程序中的指針對任何其他程序都沒有意義，是以這個位元組序清單示會與通常在記憶體中使⽤的資料結構完全不同 1 。
- 是以，需要在兩種表示之間進⾏某種類型的翻譯。 從記憶體中表示到位元組序列的轉換稱為編碼
（Encoding）也稱為序列化（serialization）或編組（marshalling），反過來稱為解碼
（Decoding） 解析（Parsing），反序列化（deserialization），反編組(unmarshalling） 。
1.程式設計語⾔特定的編碼
僅限于單⼀程式設計語⾔，并且往往⽆法提供前向和後向相容性。
2.JSON、XML和CSV等文本結構
⾮常普遍，其相容性取決于您如何使⽤它們。讓不同的組織達成⼀緻的難度較大。
對于資料類型有些模糊，是以你必須⼩⼼數字和⼆進制字元串。
JSON雖然區分字元串和數字，但不區分整數和浮點數，⽽且不能指定精度。
CSV沒有任何模式，是以應⽤程式需要定義每⾏和每列的含義。
3.Thrift、Protocol Buffers和Avro等二進制模式驅動的格式
緊湊，⾼效
允許使⽤清晰定義的前向和後向相容性語意，以提供較好的相容性。
這些模式可以用于靜态類型語言的文檔和代碼生成，但是資料在解碼前不可讀
資料流的類型
1.資料庫中的資料流
資料寫入者對資料編碼，資料讀取者對資料解碼。
2.服務中的資料流：RPC和Rest API
具象狀态傳輸（REST）和遠端過程調⽤（RPC）
用戶端對請求編碼，服務端接受請求并解碼，并對響應編碼，用戶端對響應解碼。
3.消息中的資料流：異步消息傳遞
節點之間通過發送消息進行通信，消息有發送者編碼，由接受者解碼。