nutsdb的研究以及一些心得體會分享

背景

有一天nutsdb學(xué)習(xí)交流群中有一位老哥說nutsdb重新恢復(fù)的速度太慢了，他那邊大概有一個G左右的數(shù)據(jù)。我對這個問題還是比較感興趣的，當(dāng)場就接下了這個任務(wù)。開啟了這段時間的優(yōu)化之路，歷時還蠻長時間的，因?yàn)槠綍r上班，還有其他的一些興趣愛好什么，所以開源上面的投入倒是有細(xì)水長流的感覺。好了，閑話不多說了，下面把這段時間在這個問題上面的研究以及一些心得體會分享給大家。

分析問題

俗語有云，能復(fù)現(xiàn)的問題都不是什么大問題。根據(jù)學(xué)習(xí)老哥的描述，我首先要做的就是準(zhǔn)備1G的數(shù)據(jù)，然后benchmark+pprof測試重啟恢復(fù)db的cpu和內(nèi)存情況。最終問題定位到了這段代碼上面：

// ReadAt returns entry at the given off(offset).
func (df *DataFile) ReadAt(off int) (e *Entry, err error) {

   // 讀取header
   buf := make([]byte, DataEntryHeaderSize)


   if _, err := df.rwManager.ReadAt(buf, int64(off)); err != nil {
      return nil, err
   }


   meta := readMetaData(buf)


   e = &Entry{
      crc:  binary.LittleEndian.Uint32(buf[0:4]),
      Meta: meta,
   }


   if e.IsZero() {
      return nil, nil
   }


   // read bucket
   off += DataEntryHeaderSize
   bucketBuf := make([]byte, meta.BucketSize)
   _, err = df.rwManager.ReadAt(bucketBuf, int64(off))
   if err != nil {
      return nil, err
   }


   e.Meta.Bucket = bucketBuf


   // read key
   off += int(meta.BucketSize)
   keyBuf := make([]byte, meta.KeySize)


   _, err = df.rwManager.ReadAt(keyBuf, int64(off))
   if err != nil {
      return nil, err
   }
   e.Key = keyBuf


   // read value
   off += int(meta.KeySize)
   valBuf := make([]byte, meta.ValueSize)
   _, err = df.rwManager.ReadAt(valBuf, int64(off))
   if err != nil {
      return nil, err
   }
   e.Value = valBuf


   crc := e.GetCrc(buf)
   if crc != e.crc {
      return nil, ErrCrc
   }


   return
}

這段代碼的作用是給定一個文件的偏移位置，從這個位置開始往后讀取一條數(shù)據(jù)。在db重啟恢復(fù)的過程中這個函數(shù)會被頻繁的調(diào)用，為什么呢？我們知道nutsdb是基于bitcask模型實(shí)現(xiàn)的，本質(zhì)上來說是hash索引。在重啟恢復(fù)的過程中會加載所有db的數(shù)據(jù)來重新構(gòu)建索引。所以理論上來說，重啟的時候當(dāng)前db有多少數(shù)據(jù)，這個函數(shù)就會被調(diào)用多少次，由于這個函數(shù)性能不大行，所以這里成為了瓶頸。為什么說這個函數(shù)性能不太行呢？且看我娓娓道來。

一條nutsdb中的數(shù)據(jù)是以這樣的形式被存儲在磁盤中的：

首先我們需要獲取這條數(shù)據(jù)的元數(shù)據(jù)(header)，也就是描述真實(shí)數(shù)據(jù)的數(shù)據(jù)，這里會記錄bucket，key，value的長度，我們拿到這些信息之后會再次發(fā)起系統(tǒng)調(diào)用去獲取真實(shí)bucket，key，value。由這段代碼我們可以看到，這個函數(shù)沒執(zhí)行一次，就會發(fā)起四次系統(tǒng)調(diào)用，分別在磁盤中獲取meta，bucket，key，value。而且每次都需要申請與數(shù)據(jù)長度匹配字節(jié)數(shù)組去承接這些數(shù)據(jù)。這個現(xiàn)狀有兩個問題，其一是過多的系統(tǒng)調(diào)用會是性能的瓶頸，其次是過多的申請內(nèi)存，在這些對象被使用完之后會在內(nèi)存中堆積起來，觸發(fā)gc之后才會被清除回收。但是如果db數(shù)據(jù)過多，在這個時候也會觸發(fā)gc造成卡頓。

如何解決？

在定位到問題之后，就開始了解決問題的旅程，這段旅程異常的漫長，這段過程翻閱了很多資料，嘗試了很多方法。且看我一一道來。

1. 減少系統(tǒng)調(diào)用

在上面的分析中，我們知道讀一條數(shù)據(jù)需要發(fā)起四次系統(tǒng)調(diào)用。我覺得這里其實(shí)大可不必，兩次就足夠了。因?yàn)榈谝淮巫x取meta之后，我們就知道bucket，key，value這些數(shù)據(jù)的長度和位置了加上這些數(shù)據(jù)都是連續(xù)存儲的，直接一次全部拿出來然后分別解析就好。

所以在第一次優(yōu)化中，將上面的四次系統(tǒng)調(diào)用優(yōu)化成了2次，帶來了一倍速度上的提升。不僅僅是重啟速度上的，因?yàn)樵谶\(yùn)行中讀取數(shù)據(jù)用的也是這個函數(shù)。所以在數(shù)據(jù)的讀取上同樣也是優(yōu)化了一倍的讀取速度。下圖是我提交的pr的截圖，我構(gòu)造了大小分別是50B， 256B，1024B的數(shù)據(jù)，db總數(shù)據(jù)1G，做并發(fā)讀取性能測試，實(shí)驗(yàn)結(jié)果表明此次優(yōu)化在讀取速度上提升了接近一倍，但是在內(nèi)存的使用上并沒有減少。

2. 批量讀取，然后解析數(shù)據(jù)

在做完系統(tǒng)調(diào)用的優(yōu)化之后的一個星期的時間里，這項(xiàng)優(yōu)化工作其實(shí)陷入了沉寂，有時候會腦爆一下這個該怎么做，翻越了bitcask論文和DDIA對hash索引恢復(fù)操作的描述，書中所說都是要將數(shù)據(jù)一條條的拿出來，沒有可參考的資料感覺有點(diǎn)寸步難行。不過天無絕人之路，有一天打游戲的時候突然想到了，為什么不一次性讀取文件的一部分，比如4KB，然后在這4KB中解析出里面的數(shù)據(jù)，解析到解析不下去的時候再拿下一個，直到文件解析完畢。下面讓我們展開一下這個思路。

我們知道磁盤底層會把自己存儲空間劃分成一個個扇區(qū)，在磁盤之上的文件系統(tǒng)會把磁盤的扇區(qū)組成一個個的block，我們的應(yīng)用程序每次去讀取數(shù)據(jù)都是按照block去讀取的。打個比方，一個block是4KB，如果我要讀1KB的數(shù)據(jù)，那么會加載4KB的數(shù)據(jù)到pagecache，然后返回1KB給我們的應(yīng)用程序。所以當(dāng)我們一次次發(fā)起系統(tǒng)調(diào)用的去磁盤回去數(shù)據(jù)的時候，實(shí)際上數(shù)據(jù)已經(jīng)從磁盤里拿出來并且放到pagecache中了。所以我們直接把整個block拿出來就完事了。

一開始想的是批量獲取一批完整的數(shù)據(jù)。這個時候其實(shí)不太好控制，因?yàn)槲覀儾恢酪粭l數(shù)據(jù)有多大，所以如果要要批量獲取數(shù)據(jù)還需要額外的數(shù)據(jù)結(jié)構(gòu)去描述，我把這個東西叫做斷點(diǎn)，也就是說一個文件分成若干個斷點(diǎn)，斷點(diǎn)之間存儲的是一批數(shù)據(jù)。如果朝這個方向改會衍生出很多問題，其一是在什么樣的標(biāo)準(zhǔn)下面去寫這個斷點(diǎn)，比如按照數(shù)據(jù)量來記呢，還是按照一個固定的空間大小來記錄。其二是再增加這個邏輯去額外記錄還需要在數(shù)據(jù)寫入過程中做添加。一來二去感覺太復(fù)雜了。

那么我們按照一個個固定的塊來搞。由于我們不知道數(shù)據(jù)的大小是怎么樣的，所以按照固定塊讀取會出現(xiàn)以下的情況。

我們看上圖，上圖中的e1和e2代表著在一個存儲文件中一條條連續(xù)著存儲的數(shù)據(jù)，header是元數(shù)據(jù)，payload是對bucket，key，value這三個數(shù)據(jù)的整體描述，即有效數(shù)據(jù)部分。圖中的箭頭代表按塊讀取數(shù)據(jù)的時候有可能讀到的塊的邊界。其實(shí)也很好理解，在讀一個塊的時候可能會出現(xiàn)的情況是：

這個塊就包含了若干條完完整整的數(shù)據(jù)。這個時候不需要額外的處理。

這個塊前面包含了若干條完整的數(shù)據(jù)，但是最后的一條是殘缺的，缺失了header。這個時候我們需要讀入header殘余的數(shù)據(jù)，解析出一整個header。為什么不讀一整個block然后在在block中獲取解析header所需的剩余數(shù)據(jù)呢？因?yàn)槲覀儾恢肋@條數(shù)據(jù)長什么樣子，如果他的大小超過了一個block的size，那么還需要在后續(xù)做額外的處理。

最后一種情況是缺失了payload，那么我們需要根據(jù)缺失數(shù)據(jù)的大小來判斷要讀多少個block進(jìn)來。

經(jīng)過這一分析之后，其實(shí)一整個解析數(shù)據(jù)的流程就是在這三個狀態(tài)之間來回轉(zhuǎn)換。解析的流程就是一個狀態(tài)機(jī)的算法。等到文件讀完，那么也就解析完了。

激動的心顫抖的手，代碼寫完之后做了一版benchmark。

BenchmarkRecovery-10           1 2288482750 ns/op 1156858488 B/op 14041579 allocs/op
BenchmarkRecovery-10           2 701933396 ns/op 600666340 B/op 3947879 allocs/op

我們分析一下這個思路下的優(yōu)化，理論上來說db中一條數(shù)據(jù)越小，優(yōu)化效果越明顯，因?yàn)檫@就意味著單次獲取的block中蘊(yùn)含著更多的數(shù)據(jù)，就可以減少更多的系統(tǒng)調(diào)用。但是我們可以看到的是，雖然啟動的時間變短了，申請內(nèi)存的次數(shù)變少了，但是申請的內(nèi)存還是不少。

執(zhí)行兩次啟動恢復(fù)1G左右的數(shù)據(jù)大概花了4G的內(nèi)存。也就是說一次啟動花了2G，里面有1G消耗不知道是在哪里來的。一開始我以為是讀取數(shù)據(jù)的時候會在用戶空間往內(nèi)核空間拷貝，會存在讀取放大的情況。不過轉(zhuǎn)念一想覺得不大可能，因?yàn)閜agecache是類似LRU的緩存機(jī)制，不會緩存你所有的數(shù)據(jù)，他也有數(shù)據(jù)的淘汰策略，不太可能1比1放大的。

所以問題出在哪里呢？我百思不得其解。不過源碼之下無秘密，我反復(fù)一次又一次看我寫下的代碼，終于讓我在一個地方發(fā)現(xiàn)了貓膩。一個我意想不到的地方，那就是append操作。

我的文件數(shù)據(jù)恢復(fù)恢復(fù)操作所代表的結(jié)構(gòu)體是這樣的：

FileRecovery struct {
   fd    *os.File
   rest      []byte
   state     state
   blockSize uint32
   finish    bool
   entry     *handlingEntry
   entries   []*Entry
   off       int64
}

我的解析流程是把文件讀完，把里面的數(shù)據(jù)一個個append進(jìn)entries字段里面，文件解析完了再把entries返回。要是在平時我不會覺得這個操作是有什么問題的，不過我準(zhǔn)備的數(shù)據(jù)量太大了（兩百萬條），append應(yīng)該會觸發(fā)多次擴(kuò)容操作，然后反復(fù)申請內(nèi)存。去翻看了一下append操作的擴(kuò)容機(jī)制，當(dāng)數(shù)據(jù)量小于1024的時候，會擴(kuò)成原來的2倍，數(shù)據(jù)量大于1024時，會變成原來的1.25倍?？吹竭@里其實(shí)基本驗(yàn)證了我的猜想，不過謹(jǐn)慎起見還是計算了一下, nutsdb數(shù)據(jù)有segment設(shè)置，當(dāng)一個文件大于這個參數(shù)的大小的時候會保存成只讀文件。兩百萬條數(shù)據(jù)寫了兩個文件，這個結(jié)構(gòu)體是解析單個文件的，我們按照每個文件100萬條數(shù)據(jù)算。100萬條數(shù)據(jù)大概要擴(kuò)容幾次呢：

1024前面的過程就忽略不計了，直接從1024開始，掏出計算器，這里x的值是30次，那么擴(kuò)容30次總共需要多少內(nèi)存呢？

為什么是乘8呢，因?yàn)槲沂?4位機(jī)器，entries里面的元素是指針，那么指針的長度和字長是一樣的，也就是8個byte。這里的結(jié)果大概是3000萬，3000萬個比特大概是220MB的內(nèi)存，兩個文件加起來大概就是440MB的內(nèi)存了。驚不驚喜，意不意外？

那么如何優(yōu)化這里呢，其實(shí)一個個往外傳就可以了，不要等到解析完了堆在數(shù)組里再往外丟。如果要在原來的基礎(chǔ)上改的話，我需要每次處理完一條數(shù)據(jù)的時候記錄下當(dāng)前這個block處理到哪里，也就是要把block改成ring buffer的形式，這個時候我隱隱約約想到了go的標(biāo)準(zhǔn)庫里有一個東西做了類似的事情，沒錯，就是bufio.Reader.他不僅僅會幫我們看到記錄ringbuffer的位置，還會預(yù)讀block。整體上看是完美契合這個需求的。

3. bufio.Reader

bufio.Reader會維護(hù)一個默認(rèn)大小4KB的ring buffer，當(dāng)讀取的內(nèi)容大于它所能承載的緩存時，他會直接在讀取而不使用緩存，如果讀取的是比較小的數(shù)據(jù)，會在他的緩存中copy出來一份返回。這個就完美的契合了我們多次讀取的場景?？匆幌赂某蛇@樣子的性能提升吧：

這下無論是速度上，還是內(nèi)存的使用上，都達(dá)到了一個比較理想的狀態(tài)。這次優(yōu)化歷程就到此結(jié)束了。

總結(jié)

做性能優(yōu)化的感覺就像和計算機(jī)對話，依照自己現(xiàn)有的知識去想方案， 然后寫出來之后做實(shí)驗(yàn)求證。做這個的思路是讓他慢慢的變好，而不是上來就追求完美主義，完美主義是不靠譜的，反而會讓你陷入到糾結(jié)之中，能優(yōu)化一點(diǎn)是一點(diǎn)，我們要看到一個變好的趨勢，然后在這個趨勢上面不斷的基于上一次的結(jié)果去猜想下一次怎么優(yōu)化，也就是所謂的“小步快跑”。在做這個的過程中會往各個方向去腦爆，一些背景知識不是很清楚的時候需要翻越各種資料。整體來說是一次很不錯的成長體驗(yàn)。

審核編輯：劉清