前言

? ? ? 本文主要介紹 Cassandra 中數據的存儲格式，包括在內存中的數據和磁盤中數據。Cassandra 的寫的性能表現(xiàn)非常好，為什么寫的性能這么好？和它的數據結構有沒有關系，以及和它的寫的機制又有多大的關系。同時也將分析哪些因素會影響讀的性能 Cassandra 又做了哪些改進。

Cassandra 的數據存儲結構主要分為三種：

1、CommitLog：主要記錄下客戶端提交過來的數據以及操作。這個數據將被持久化到磁盤中，以便數據沒有被持久化到磁盤時可以用來恢復。

2、Memtable：用戶寫的數據在內存中的形式，它的對象結構在后面詳細介紹。其實還有另外一種形式是 BinaryMemtable 這個格式目前 Cassandra 并沒有使用，這里不再介紹了。

3、SSTable：數據被持久化到磁盤，這又分為 Data、Index 和 Filter 三種數據格式。

CommitLog 數據格式

CommitLog 的數據只有一種，那就是按照一定格式組成 byte 組數，寫到 IO 緩沖區(qū)中定時的被刷到磁盤中持久化，在上一篇的配置文件詳解中已經有說到 CommitLog 的持久化方式有兩種，一個是 Periodic 一個是 Batch，它們的數據格式都是一樣的，只是前者是異步的，后者是同步的，數據被刷到磁盤的頻繁度不一樣。關于 CommitLog 的相關的類結構圖如下：

圖 1. CommitLog 的相關的類結構圖

它持久化的策略也很簡單，就是首先將用戶提交的數據所在的對象 RowMutation 序列化成 byte 數組，然后把這個對象和 byte 數組傳給 LogRecordAdder 對象，由 LogRecordAdder 對象調用 CommitLogSegment 的 write 方法去完成寫操作，這個 write 方法的代碼如下：

清單 1. CommitLogSegment. write

public CommitLogSegment.CommitLogContext write（RowMutation rowMutation，

Object serializedRow）{

long currentPosition = -1L;

...

Checksum checkum = new CRC32（）;

if （serializedRow instanceof DataOutputBuffer）{

DataOutputBuffer buffer = （DataOutputBuffer） serializedRow;

logWriter.writeLong（buffer.getLength（））;

logWriter.write（buffer.getData（）， 0， buffer.getLength（））;

checkum.update（buffer.getData（）， 0， buffer.getLength（））;

}

else{

assert serializedRow instanceof byte［］;

byte［］ bytes = （byte［］） serializedRow;

logWriter.writeLong（bytes.length）;

logWriter.write（bytes）;

checkum.update（bytes， 0， bytes.length）;

}

logWriter.writeLong（checkum.getValue（））;

...

}

這個代碼的主要作用就是如果當前這個根據 columnFamily 的 id 還沒有被序列化過，將會根據這個 id 生成一個 CommitLogHeader 對象，記錄下在當前的 CommitLog 文件中的位置，并將這個 header 序列化，覆蓋以前的 header。這個 header 中可能包含多個沒有被序列化到磁盤中的 RowMutation 對應的 columnFamily 的 id。如果已經存在，直接把 RowMutation 對象的序列化結果寫到 CommitLog 的文件緩存區(qū)中后面再加一個 CRC32 校驗碼。Byte 數組的格式如下：

圖 2. CommitLog 文件數組結構

上圖中每個不同的 columnFamily 的 id 都包含在 header 中，這樣做的目的是更容易的判斷那些數據沒有被序列化。

CommitLog 的作用是為恢復沒有被寫到磁盤中的數據，那如何根據 CommitLog 文件中存儲的數據恢復呢？這段代碼在 recover 方法中：

清單 2. CommitLog.recover

public static void recover（File［］ clogs） throws IOException{

...

final CommitLogHeader clHeader = CommitLogHeader.readCommitLogHeader（reader）;

int lowPos = CommitLogHeader.getLowestPosition（clHeader）;

if （lowPos == 0） break;

reader.seek（lowPos）;

while （！reader.isEOF（））{

try{

bytes = new byte［（int） reader.readLong（）］;

reader.readFully（bytes）;

claimedCRC32 = reader.readLong（）;

}

...

ByteArrayInputStream bufIn = new ByteArrayInputStream（bytes）;

Checksum checksum = new CRC32（）;

checksum.update（bytes， 0， bytes.length）;

if （claimedCRC32 ！= checksum.getValue（））{continue;}

final RowMutation rm =

RowMutation.serializer（）.deserialize（new DataInputStream（bufIn））;

}

...

}

這段代碼的思路是：反序列化 CommitLog 文件的 header 為 CommitLogHeader 對象，尋找 header 對象中沒有被回寫的最小 RowMutation 位置，然后根據這個位置取出這個 RowMutation 對象的序列化數據，然后反序列化為 RowMutation 對象，然后取出 RowMutation 對象中的數據重新保存到 Memtable 中，而不是直接寫到磁盤中。CommitLog 的操作過程可以用下圖來清楚的表示：

圖 3. CommitLog 數據格式的變化過程

Memtable 內存中數據結構

Memtable 內存中數據結構比較簡單，一個 ColumnFamily 對應一個唯一的 Memtable 對象，所以 Memtable 主要就是維護一個 ConcurrentSkipListMap《decoratedkey， columnfamily=“” style=“box-sizing： border-box;”》 類型的數據結構，當一個新的 RowMutation 對象加進來時，Memtable 只要看看這個結構是否 《decoratedkey， columnfamily=“” style=“box-sizing： border-box;”》集合已經存在，沒有的話就加進來，有的話取出這個 Key 對應的 ColumnFamily，再把它們的 Column 合并。Memtable 相關的類結構圖如下：

圖 4. Memtable 相關的類結構圖

Memtable 中的數據會根據配置文件中的相應配置參數刷到本地磁盤中。這些參數在上一篇中已經做了詳細說明。

前面已經多處提到了 Cassandra 的寫的性能很好，好的原因就是因為 Cassandra 寫到數據首先被寫到 Memtable 中，而 Memtable 是內存中的數據結構，所以 Cassandra 的寫是寫內存的，下圖基本上描述了一個 key/value 數據是怎么樣寫到 Cassandra 中的 Memtable 數據結構中的。

圖 5. 數據被寫到 Memtable

SSTable 數據格式

每添加一條數據到 Memtable 中，程序都會檢查一下這個 Memtable 是否已經滿足被寫到磁盤的條件，如果條件滿足這個 Memtable 就會寫到磁盤中。先看一下這個過程涉及到的類。相關類圖如圖 6 所示：

圖 6. SSTable 持久化類結構圖

Memtable 的條件滿足后，它會創(chuàng)建一個 SSTableWriter 對象，然后取出 Memtable 中所有的 《decoratedkey， columnfamily=“” style=“box-sizing： border-box;”》集合，將 ColumnFamily 對象的序列化結構寫到 DataOutputBuffer 中。接下去 SSTableWriter 根據 DecoratedKey 和 DataOutputBuffer 分別寫到 Date、Index 和 Filter 三個文件中。

Data 文件格式如下：

圖 7. SSTable 的 Data 文件結構

Data 文件就是按照上述 byte 數組來組織文件的，數據被寫到 Data 文件中是接著就會往 Index 文件中寫，Index 中到底寫什么數據呢？

其實 Index 文件就是記錄下所有 Key 和這個 Key 對應在 Data 文件中的啟示地址，如圖 8 所示：

圖 8. Index 文件結構

?

Index 文件實際上就是 Key 的一個索引文件，目前只對 Key 做索引，對 super column 和 column 都沒有建索引，所以要匹配 column 相對來說要比 Key 更慢。

Index 文件寫完后接著寫 Filter 文件，F(xiàn)ilter 文件存的內容就是 BloomFilter 對象的序列化結果。它的文件結構如圖 9 所示：

圖 9. Filter 文件結構

BloomFilter 對象實際上對應一個 Hash 算法，這個算法能夠快速的判斷給定的某個 Key 在不在當前這個 SSTable 中，而且每個 SSTable 對應的 BloomFilter 對象都在內存中，F(xiàn)ilter 文件指示 BloomFilter 持久化的一個副本。三個文件對應的數據格式可以用下圖來清楚的表示：

圖 10. SSTable 數據格式轉化

這個三個文件寫完后，還要做的一件事件就是更新前面提到的 CommitLog 文件，告訴 CommitLog 的 header 所存的當前 ColumnFamily 的沒有寫到磁盤的最小位置。

在 Memtable 往磁盤中寫的過程中，這個 Memtable 被放到 memtablesPendingFlush 容器中，以保證在讀時候它里面存的數據能被正確讀到，這個在后面數據讀取時還會介紹。

數據的寫入

數據要寫到 Cassandra 中有兩個步驟：

1.找到應該保存這個數據的節(jié)點

2.往這個節(jié)點寫數據。客戶端寫一條數據必須指定 Keyspace、ColumnFamily、Key、Column Name 和 Value，還可以指定 Timestamp，以及數據的安全等級。

數據寫入涉及的主要相關類如下圖所示：

圖 11. Insert 相關類圖

大慨的寫入邏輯是這樣的：

CassandraServer 接收到要寫入的數據時，首先創(chuàng)建一個 RowMutation 對象，再創(chuàng)建一個 QueryPath 對象，這個對象中保存了 ColumnFamily、Column Name 或者 Super Column Name。接著把用戶提交的所有數據保存在 RowMutation 對象的 Map《string， columnfamily=“” style=“box-sizing： border-box;”》 結構中。接下去就是根據提交的 Key 計算集群中那個節(jié)點應該保存這條數據。這個計算的規(guī)則是：將 Key 轉化成 Token，然后在整個集群的 Token 環(huán)中根據二分查找算法找到與給定的 Token 最接近的一個節(jié)點。如果用戶指定了數據要保存多個備份，那么將會順序在 Token 環(huán)中返回與備份數相等的節(jié)點。這是一個基本的節(jié)點列表，后面 Cassandra 會判斷這些節(jié)點是否正常工作，如果不正常尋找替換節(jié)點。還有還要檢查是否有節(jié)點正在啟動，這種節(jié)點也是要在考慮的范圍內，最終會形成一個目標節(jié)點列表。最 后把數據發(fā)送到這些節(jié)點。

接下去就是將數據保存到 Memtable 中和 CommitLog 中，關于結果的返回根據用戶指定的安全等級不同，可以是異步的，也可以是同步的。如果某個節(jié)點返回失敗，將會再次發(fā)送數據。下圖是當 Cassandra 接收到一條數據時到將數據寫到 Memtable 中的時序圖。

圖 12. Insert 操作的時序圖

#e#

數據的讀取

Cassandra 的寫的性能要好于讀的性能，為何寫的性能要比讀好很多呢？原因是，Cassandra 的設計原則就是充分讓寫的速度更快、更方便而犧牲了讀的性能。事實也的確如此，僅僅看 Cassandra 的數據的存儲形式就能發(fā)現(xiàn)，首先是寫到 Memtable 中，然后將 Memtable 中數據刷到磁盤中，而且都是順序保存的不檢查數據的唯一性，而且是只寫不刪（刪除規(guī)則在后面介紹），最后才將順序結構的多個 SSTable 文件合并。這每一步難道不是讓 Cassandra 寫的更快。這個設計想想對讀會有什么影響。首先，數據結構的復雜性，Memtable 中和 SSTable 中數據結構肯定不同，但是返回給用戶的肯定是一樣的，這必然會要轉化。其次，數據在多個文件中，要找的數據可能在 Memtable 中，也可能在某個 SSTable 中，如果有 10 個 SSTable，那么就要在到 10 個 SSTable 中每個找一遍，雖然使用了 BloomFilter 算法可以很快判斷到底哪個 SSTable 中含有指定的 key。還有可能在 Memtable 到 SSTable 的轉化過程中，這也是要檢查一遍的，也就是數據有可能存在什么地方，就要到哪里去找一遍。還有找出來的數據可能是已經被刪除的，但也沒辦法還是要取。

下面是讀取數據的相關類圖：

圖 13. 讀取相關類圖

根據上面的類圖讀取的邏輯是，CassandraServer 創(chuàng)建 ReadCommand 對象，這個對象保存了用戶要獲取記錄的所有必須指定的條件。然后交給 weakReadLocalCallable 這個線程去到 ColumnFamilyStore 對象中去搜索數據，包括 Memtable 和 SSTable。將找到的數據組裝成 Row 返回，這樣一個查詢過程就結束了。這個查詢邏輯可以用下面的時序圖來表示：

圖 14. 查詢數據時序圖

在上圖中還一個地方要說明的是，取得 key 對應的 ColumnFamily 要至少在三個地方查詢，第一個就是 Memtable 中，第二個是 MemtablesPendingFlush，這個是將 Memtable 轉化為 SSTable 之前的一個臨時 Memtable。第三個是 SSTable。在 SSTable 中查詢最為復雜，它首先將要查詢的 key 與每個 SSTable 所對應的 Filter 做比較，這個 Filter 保存了所有這個 SSTable 文件中含有的所有 key 的 Hash 值，這個 Hsah 算法能快速判斷指定的 key 在不在這個 SSTable 中，這個 Filter 的值在全部保存在內存中，這樣能快速判斷要查詢的 key 在那個 SSTable 中。接下去就要在 SSTable 所對應的 Index 中查詢 key 所對應的位置，從前面的 Index 文件的存儲結構知道，Index 中保存了具體數據在 Data 文件中的 Offset。，拿到這個 Offset 后就可以直接到 Data 文件中取出相應的長度的字節(jié)數據，反序列化就可以達到目標的 ColumnFamily。由于 Cassandra 的存儲方式，同一個 key 所對應的值可能存在于多個 SSTable 中，所以直到查找完所有的 SSTable 文件后再與前面的兩個 Memtable 查找出來的結果合并，最終才是要查詢的值。

另外，前面所描述的是最壞的情況，也就是查詢在完全沒有緩存的情況下，當然 Cassandra 在對查詢操作也提供了多級緩存。第一級直接針對查詢結果做緩存，這個緩存的設置的配置項是 Keyspace 下面的 RowsCached。查詢的時候首先會在這個 Cache 中找。第二級 Cache 對應 SSTable 的 Index 文件，它可以直接緩存要查詢 key 所對應的索引。這個配置項同樣在 Keyspace 下面的 KeysCached 中，如果這個 Cache 能命中，將會省去 Index 文件的一次 IO 查詢。最后一級 Cache 是做磁盤文件與內存文件的 mmap，這種方式可以提高磁盤 IO 的操作效率，鑒于索引大小的限制，如果 Data 文件太大只能在 64 位機器上使用這個技術。

數據的刪除

從前面的數據寫入規(guī)則可以想象，Cassandra 要想刪除數據是一件麻煩的事，為何這樣說？理由如下：

1.數據有多處 同時還可能在多個節(jié)點都有保存。

2.數據的結構有多種 數據會寫在 CommitLog 中、Memtable 中、SSTable 中，它們的數據結構都不一樣。

4.數據時效性不一致 由于是集群，所以數據在節(jié)點之間傳輸必然有延時。

6.除了這三點之外還有其它一些難點如 SSTable 持久化數據是順序存儲的，如果刪除中間一段，那數據有如何移動，這些問題都非常棘手，如果設計不合理，性能將會非常之差。

本部分將討論 Cassandra 是如何解決這些問題的。

CassandraServer 中刪除數據的接口只有一個 remove，下面是 remove 方法的源碼：

清單 3. CassandraServer.remove

public void remove（String table， String key， ColumnPath column_path，

long timestamp， ConsistencyLevel consistency_level）{

checkLoginDone（）;

ThriftValidation.validateKey（key）;

ThriftValidation.validateColumnPathOrParent（table， column_path）;

RowMutation rm = new RowMutation（table， key）;

rm.delete（new QueryPath（column_path）， timestamp）;

doInsert（consistency_level， rm）;

}

仔細和 insert 方法比較，發(fā)現(xiàn)只有一行不同：insert 方法調用的是 rm.add 而這里是 rm.delete。那么這個 rm.delete 又做了什么事情呢？下面是 delete 方法的源碼：

清單 4. RowMutation. Delete

public void delete（QueryPath path， long timestamp）{
....

if （columnFamily == null）

columnFamily = ColumnFamily.create（table_， cfName）;

if （path.superColumnName == null && path.columnName == null）{

columnFamily.delete（localDeleteTime， timestamp）;

}else if （path.columnName == null）{

SuperColumn sc = new SuperColumn（path.superColumnName，

DatabaseDescriptor.getSubComparator（table_， cfName））;

sc.markForDeleteAt（localDeleteTime， timestamp）;

columnFamily.addColumn（sc）;

}else{

ByteBuffer bytes = ByteBuffer.allocate（4）;

bytes.putInt（localDeleteTime）;

columnFamily.addColumn（path， bytes.array（）， timestamp， true）;

}

}

這段代碼的主要邏輯就是，如果是刪除指定 Key 下的某個 Column，那么將這個 Key 所對應的 Column 的 vlaue 設置為當前系統(tǒng)時間，并將 Column 的 isMarkedForDelete 屬性設置為 TRUE，如果是要刪除這個 Key 下的所有 Column 則設置這個 ColumnFamily 的刪除時間期限屬性。然后將這個新增的一條數據按照 Insert 方法執(zhí)行下去。

這個思路現(xiàn)在已經很明顯了，它就是通過設置同一個 Key 下對應不同的數據來更新已經在 ConcurrentSkipListMap 集合中存在的數據。這種方法的確很好，它能夠達到如下目的：

1.簡化了數據的操作邏輯。將添加、修改和刪除邏輯都統(tǒng)一起來。

2.解決了前面提到的三個難點。因為它就是按照數據產生的方式，來修改數據。有點以其人之道還治其人之身的意思。

4.但是這仍然有兩個問題：這個只是修改了指定的數據，它并沒有刪除這條數據；還有就是 SSTable 是根據 Memtable 中的數據保存的，很可能會出現(xiàn)不同的 SSTable 中保存相同的數據，這個又怎么解決？的確如此，Cassandra 并沒有刪除你要刪除的數據，Cassandra 只是在你查詢數據返回之前，過濾掉 isMarkedForDelete 為 TRUE 的記錄。它能夠保證你刪除的數據你不能再查到，至于什么時候真正刪除，你就不需要關心了。Cassandra 刪除數據的過程很復雜，真正刪除數據是在 SSTable 被壓縮的過程中，SSTable 壓縮的目的就是把同一個 Key 下對應的數據都統(tǒng)一到一個 SSTable 文件中，這樣就解決了同一條數據在多處的問題。壓縮的過程中 Cassandra 會根據判斷規(guī)則判定哪些數據應該被刪除。

SSTable 的壓縮

數據的壓縮實際上是數據寫入 Cassandra 的一個延伸，前面描述的數據寫入和數據的讀取都有一些限制，如：在寫的過程中，數據會不停的將一定大小的 Memtable 刷到磁盤中，這樣不停的刷，勢必會產生很多的同樣大小的 SSTable 文件，不可能這樣無限下去。同樣在讀的過程中，如果太多的 SSTable 文件必然會影響讀的效率，SSTable 越多就會越影響查詢。還有一個 Key 對應的 Column 分散在多個 SSTable 同樣也會是問題。還有我們知道 Cassandra 的刪除同樣也是一個寫操作，同樣要處理這些無效的數據。

鑒于以上問題，必然要對 SSTable 文件進行合并，合并的最終目的就是要將一個 Key 對應的所有 value 合并在一起。該組合的組合、該修改的修改，該刪除的刪除。然后將這個 Key 所對應的數據寫在 SSTable 所對應的 Data 文件的一段連續(xù)的空間上。

何時壓縮 SSTable 文件由 Cassandra 來控制，理想的 SSTable 文件個數在 4~32 個。當新增一個 SSTable 文件后 Cassandra 會計算當期的平均 SSTable 文件的大小當新增的 SSTable 大小在平均 SSTable 大小的 0.5~1.5 倍時 Cassandra 就會調用壓縮程序壓縮 SSTable 文件，導致的結果就是重新建立 Key 的索引。這個過程可以用下圖描述：

圖 15 數據壓縮

?