閱讀本文之前，最好已經(jīng)閱讀過Spanner官方文檔。
本文適合以下兩類人：
A. 如果你讀完官方文檔完全沒能舉一反三，還是一頭霧水，不知道使用Spanner的正確姿勢是什么，以及為什么這些姿勢比較正確。那你就可以讀一下這篇文章，一定會(huì)對你有幫助。
B. 如果你對數(shù)據(jù)庫原理及其實(shí)現(xiàn)有一定理解，你讀完官方文檔已經(jīng)舉一反三大概猜測到了它的實(shí)現(xiàn)原理，大神，還是請你讀一下這篇文章，交流一下我們理解不一致的地方。

重要的話再說一遍：閱讀本文之前，最好已經(jīng)閱讀過Spanner官方文檔，帶著問題來讀這篇文章，收獲會(huì)更多一些。

（如果你想對Spanner的基本架構(gòu)有一個(gè)概覽，可以讀一讀上一篇：理解Google Spanner(1)：數(shù)據(jù)復(fù)制與分片）

本文會(huì)講什么

要理解Spanner中的數(shù)據(jù)是如何被存儲、組織的，只有三個(gè)關(guān)鍵詞：

• Key-Value數(shù)據(jù)庫
• LSM-Tree
• PAX 行列混存

一、存儲形式：Key-Value數(shù)據(jù)庫

Key-Value數(shù)據(jù)庫怎么組織數(shù)據(jù)

首先，Spanner不是關(guān)系型數(shù)據(jù)庫，也不是NoSQL，它被稱為NewSQL。Spanner的本質(zhì)是Key-Value數(shù)據(jù)庫，在Spanner底層，是沒有Schema的，任何一行數(shù)據(jù)都會(huì)被轉(zhuǎn)換為一個(gè)或多個(gè)Key-Value對存儲。
對于基于Key-Value的NewSQL數(shù)據(jù)庫，面向用戶這一層是可以定義Schema的，它怎么將Schema轉(zhuǎn)換為底層的Key-Value存呢？也就是說，怎么為數(shù)據(jù)構(gòu)建一個(gè)key呢？
首先，我們得保證每一個(gè)Key在數(shù)據(jù)庫中全局唯一，如果不唯一，可能會(huì)出現(xiàn)X表的某條數(shù)據(jù)覆蓋了Y表的某條數(shù)據(jù)這種情況。
以下圖中的Singers表為例，我們可以為每個(gè)表都分配一個(gè)唯一id，比如Singer表的id為singers，在表中，主鍵(Primary Key)一定是唯一的，那么將他們拼起來就是singers_primarykey1，那么這行數(shù)據(jù)是這樣存的：
singers_1 : (1, "Jay", "Zhou", "臺灣歌手")

Schema

等等，上面這樣設(shè)計(jì)數(shù)據(jù)表(Table)和索引(Index)的Key，好像不能保證唯一性了，萬一有一個(gè)數(shù)據(jù)表也叫firstname呢？有道理，所以我們需要一個(gè)前綴區(qū)分?jǐn)?shù)據(jù)表和索引，我們可以使數(shù)據(jù)表的前綴為table，索引的前綴為index。
那么數(shù)據(jù)表的結(jié)構(gòu)應(yīng)該如下：
table_singers_1 : (1, "Jay", "Zhou", "臺灣歌手")
唯一索引的結(jié)構(gòu)如下：
index_firstname_Jay ： (1)
非唯一索引的結(jié)構(gòu)如下：
index_fristname_Jay_1 : null
Perfect Done.

數(shù)據(jù)如何排序

理解了如何使用Key-Value的形式組織數(shù)據(jù)，就理解了Spanner是如何組織數(shù)據(jù)，不論是表還是索引，都是表，那么下一個(gè)問題：表中的數(shù)據(jù)如何排序呢？
首先，數(shù)據(jù)是根據(jù)Key排序的，從小到大升序排列。
Key是如何排序的？
首先，對于同一個(gè)表的數(shù)據(jù)，前綴(Prefix)應(yīng)該是相同的，那么它們會(huì)根據(jù)接在后面的主鍵排序，如果是數(shù)字，則按數(shù)字從小到大排列，如果是字符串，則使用字典序(Lexicographical Order)，字典序是依次對比字符的，先對比左邊第一個(gè)字符，如果相同，再對比第二個(gè)字符，直到分出大小為止。因此，排序結(jié)果和字符串長短沒有關(guān)系，沒有關(guān)系，沒有關(guān)系！
For example，對于下面三個(gè)字符串，正確排序應(yīng)該如下：

1. "aaa"
2. "b"
3. "cc"

看到這里你可能有一個(gè)問題：主鍵是數(shù)字也會(huì)被拼接到Key中，不就變成了一個(gè)字符串嗎，不也應(yīng)該按照字符串的字典順序排列嗎？
答：前面講的將Primary Key拼接到Key，并不是說一定會(huì)拼接成一個(gè)字符串，實(shí)際上在底層，都是一個(gè)個(gè)二進(jìn)制位，一個(gè)個(gè)Bit，上面說的將Key拼成字符串只是為了好理解。

從數(shù)據(jù)的組織理解Interleave

利用預(yù)讀

由于是根據(jù)Key排序，所以前綴相同的Key，一定會(huì)排列在一起，這里就和Spanner中有Interleave結(jié)構(gòu)有關(guān)系了。
父表的Primary Key是子表的Primary Key的前綴，因此子表的rows會(huì)緊跟著排在父表后面。那么重點(diǎn)來了：
子表行會(huì)緊跟父表行存儲，也就是會(huì)存在同一頁或者相鄰頁（這在白皮書中也有說到），因此如果訪問父表行的同時(shí)要訪問相應(yīng)的子表行，效率會(huì)有提升，因?yàn)槊看蜸panner會(huì)從硬盤讀出一頁或多頁數(shù)據(jù)（預(yù)讀），你要訪問的子表行已經(jīng)在內(nèi)存中，這種情況下，速度會(huì)比不使用Interleave更快。
但是由于它是利用預(yù)讀，如果你要訪問的子表行離父表行太遠(yuǎn)，預(yù)讀也會(huì)失效，比如父表行對應(yīng)的子表行有1萬行，100MB，而你要訪問的子表行距離對應(yīng)的父表行有8000行，也就是大概距離80MB的數(shù)據(jù)，那么Spanner可能不會(huì)進(jìn)行這么遠(yuǎn)的預(yù)讀…也就是說，對于子表行太多的情況，Interleave的優(yōu)勢也被削弱了，反而使數(shù)據(jù)分片變得困難，增加了熱點(diǎn)(HotSpot)的可能，因此這種情況下是否應(yīng)該使用Interleave值得考慮。

避免多節(jié)點(diǎn)數(shù)據(jù)傳輸

Spanner是計(jì)算靠近存儲的，也就是每個(gè)節(jié)點(diǎn)不止存儲著數(shù)據(jù)，還分配有計(jì)算資源，Spanner對Interleave提供了父表行與對應(yīng)子表行一定存儲在同一個(gè)節(jié)點(diǎn)的保證，因此有的計(jì)算可以在相同的node完成，而不需要將數(shù)據(jù)傳輸?shù)狡渌鹡ode完成計(jì)算。比如對于一個(gè)Join語句，如果需要被Join的數(shù)據(jù)就存儲在本節(jié)點(diǎn)，那么就可以直接在節(jié)點(diǎn)中完成join，而不需要進(jìn)行distributed join，減少網(wǎng)絡(luò)傳輸，提高Join效率。
但是如果父表和子表很少甚至完全不會(huì)涉及到一起參與計(jì)算，那么Interleave的這個(gè)優(yōu)勢就利用不上，此時(shí)是否還堅(jiān)持使用Interleave也值得考慮了。

二、組織方式：LSM-Tree

對于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫，一般使用B+ Tree的結(jié)構(gòu)組織表，查詢非常高效。（如果你還不理解傳統(tǒng)的索引結(jié)構(gòu)，可以先看看理解數(shù)據(jù)庫（1）：數(shù)據(jù)組織方式與索引，請一定先對B+ Tree有一定了解，否則不容易理解下面的LSM-Tree）
但是B+ Tree對于寫入則不那么友好，因此每次寫入都需要插入到合適的位置，那么就可能涉及到頁分裂，且每次寫入時(shí)插入的位置不同，那么寫入打在磁盤上都是隨機(jī)的，而隨機(jī)寫比順序?qū)懸藥讉€(gè)數(shù)量級。于是出現(xiàn)了一種新的數(shù)據(jù)組織方式：LSM-Tree，全稱為Log Structured Merge Tree。

寫

LSM-Tree是一種追加寫(Append only)的數(shù)據(jù)組織方式，LSM-Tree分為多個(gè)數(shù)據(jù)段，每個(gè)更新的數(shù)據(jù)段相對于更舊的數(shù)據(jù)段，都是追加的，不會(huì)修改舊數(shù)據(jù)段，這些數(shù)據(jù)段稱為SSTable(Sorted String Table)。
SSTable是內(nèi)部有序的，并且Key唯一，也就是說同一個(gè)SSTable中不是追加寫，是in-place update。剛剛不是說希望能將隨機(jī)寫都變?yōu)轫樞驅(qū)憜?，為什么SSTable可以隨機(jī)寫？
因?yàn)閷懭胧侵苯拥絻?nèi)存的，LSM-Tree在內(nèi)存中劃分了兩塊區(qū)域，一塊是MemTable，新寫入的數(shù)據(jù)都存在這里，在內(nèi)存中進(jìn)行隨機(jī)寫與排序的速度都是非常快的，另一塊區(qū)域是Immutable Table，當(dāng)MemTable中的數(shù)據(jù)量達(dá)到一定閾值后，將會(huì)把MemTable轉(zhuǎn)化為Immutable Table，Immutable Table是不可被修改的，它將在稍后被刷入磁盤。
Immutable Table被刷入磁盤后成為一個(gè)獨(dú)立的SSTable，磁盤中的SSTable分為多個(gè)層級，新鮮數(shù)據(jù)都被刷到Level 0層，每一層可能有多個(gè)SSTable，當(dāng)本層的數(shù)據(jù)達(dá)到一定閾值后，將會(huì)被合并刷入Level 1層，以此類推。由于SSTable本身有序，因此在合并時(shí)只需要使用歸并排序，那么合并后的下層SSTable也是能夠保證順序的。合并SSTable有助于減少冗余數(shù)據(jù)、增加讀寫效率。

LSM-Tree

Spanner會(huì)周期性地對SSTable進(jìn)行壓縮合并，可以從后臺CPU utilization監(jiān)控看到，紅色為Low Priority System Task，也就是對數(shù)據(jù)進(jìn)行壓縮所消耗的CPU，對數(shù)據(jù)進(jìn)行壓縮是低優(yōu)先級的任務(wù)，如果有讀寫進(jìn)來，壓縮會(huì)讓出它們所需要的CPU，但是如果讀寫一直搶占CPU，導(dǎo)致數(shù)據(jù)的壓縮無限推遲，就會(huì)造成讀性能下降，因?yàn)槿哂鄶?shù)據(jù)太多，由于讀性能下降，就會(huì)導(dǎo)致寫性能也下降，因?yàn)閿?shù)據(jù)寫入前也需要進(jìn)行讀取，比如修改了Singer的FirstName，則需要將數(shù)據(jù)重新寫一份到MemTable，需要先查找到修改前的版本，然后將它的值復(fù)制到MemTable寫入。

紅色為System Low Priority Task

讀

雖然LSM-Tree的順序?qū)懭敕绞教岣吡藬?shù)據(jù)庫的寫吞吐量，但是相比B+ Tree，在讀的性能上卻有一些損耗，因?yàn)槊看尾檎抑付↘ey，都需要從內(nèi)存開始，然后依次往下查找，直到找到為止，因此相比B+ Tree，就可能有更多的讀損耗。
為了盡量避免讀取不必要的數(shù)據(jù)，每個(gè)（或者每層）SSTable都有一個(gè)布隆過濾器(Bloom Filter)，對每個(gè)要查找的Key，進(jìn)行hash后，如果未命中布隆過濾器，則說明這個(gè)Key在這個(gè)SSTable中絕對不存在，則避免了無效的讀取，節(jié)省了IO。如果命中了布隆過濾器，則說明這個(gè)Key可能存在在這個(gè)SSTable中，開始對這個(gè)SSTable進(jìn)行查找。
下圖為Level DB中的SSTable結(jié)構(gòu)，每個(gè)Table有多個(gè)Data Block，每個(gè)Block有固定大小，可能是64KB，Index Block是對Data Block的索引，保存著每個(gè)DataBlock的最后一個(gè)Key，因此先根據(jù)Index Block確定key處于哪個(gè)Data Block，再讀取對應(yīng)的Data Block，查找Key的值。

Level DB SSTable 結(jié)構(gòu)

三、塊(Block)結(jié)構(gòu)：PAX 行列混存

每個(gè)SSTable中都有數(shù)個(gè)數(shù)據(jù)塊(Data Block)，每個(gè)數(shù)據(jù)塊都會(huì)被一起刷入磁盤，為一頁(Page)，在Spanner之前，頁中的數(shù)據(jù)組織一般有兩種方式：行存(NSM)和列存(DSM)。
行存是將每一行的數(shù)據(jù)依次寫入Block中，如果我們SELECT *一次性查出所有列，或者一次查出大多數(shù)列，則行存非常高效，因?yàn)閺拇疟P的一次讀取，就能把這個(gè)record的所有列都查出來。但是如果我們每次只查一列或者少數(shù)列，就會(huì)讀入大量無用的數(shù)據(jù)，無用的數(shù)據(jù)比有用的數(shù)據(jù)多很多倍，因此容易造成內(nèi)存中Cache命中率較低，等于間接減少了可用內(nèi)存。

行存

Spanner即非原始的行存，又非列存，它使用一種名為PAX的結(jié)構(gòu)，行列混存：

PAX

PAX將每一頁分為多個(gè)mini page，每個(gè)mini page存儲特定的列，因此只需要查詢特定的列時(shí)，只需要讀取少數(shù)的mini page，而不需要將整個(gè)Page都讀入內(nèi)存，如果需要查詢整條數(shù)據(jù)，也可以直接將整個(gè)Page讀入內(nèi)存。

總結(jié)

Spanner本質(zhì)上是一個(gè)Key-Value數(shù)據(jù)庫，使用LSM-Tree提升寫入吞吐量，數(shù)據(jù)在頁(Page)中為PAX行列混存結(jié)構(gòu)，因此能夠進(jìn)行OLTP還適合進(jìn)行輕量OLAP。

參考資料

TiKV是如何存取數(shù)據(jù)的
Titan的設(shè)計(jì)與實(shí)現(xiàn)
PAX：一個(gè) Cache 友好高效的行列混存方案
Data Page Layouts for Relational Databases on Deep Memory Hierarchies