跳到主要内容

DocumentDB and Bw-Tree

DocumentDB​

DocumentDB是Microsoft實作的JSON document DB，後來加入更多功能以後，現在變成Cosmos DB的一部分。

DocumentDB想解決幾個問題:

  • Scaling: RMDBS處理scaling和頻繁write的情境處理的不好
  • High write performance: 要支援Microsoft內部的app(Xbox、Skype等等)，需要能處理頻繁的寫入
  • Consistency level: 一般的document db(ex: Mongo)不支援RMDBS等級的consistency level，而transaction對開發來說更直覺更容易設計，因此希望DocumentDB也支援transaction。

Replication​

每次write，primary都會send 此訊息給secondaries，如果有quorum的secondaries完成，就視為此write被accept。

Bw-Tree​

Bw-Tree architecture Bw-Tree 是為了滿足需求特別設計的資料結構，總共分為三層，最上層用B+ B^+-TreeTree來做index，tree的leaf存的是一個pointer，指向真正的page。

中間層是cache layer，用來cache page，或是如果hit miss就從disk把page swap進來。

底層是physical storage，資料結構是log based，基本上跟SSTable大同小異。

B+-Tree​

CAS​

在B+ B^+-TreeTree的leaf存的不是record或是page而是一個pointer，這個pointer指向真正資料存放的位置，因為是pointer，所以在資料做更新的時候，可以在產生一個新的pointer指向當前的pointer，因此存在CPU L1/L2 cache的資料不會被cache invalid(因為舊的pointer記憶體位置不受影響)，而新的transaction還是可以新的pointer。

要達到上面的做法，需要一個atomic的操作來確保pointer變換的時候，不會有transaction讀到空值，這個compare-and-swap操作由OS提供，並且是atomic。

Latch-free (Lock-free)​

如上面說的，因為每次的write(insert/update)都是對leaf的pointer做CAS，而當需要做compact的時候，也是做完以後，在對pointer做CAS，所以不需要lock。

B+ B^+-TreeTree的調整也是follow這套CAS的做法，因此在write不會block read，而read也不會block write。至於consistency level則由更上層的transaction manager來處理，Bw-Tree負責的是storage engine。

LSS​

沒有提到很詳細，但看起來是log-based的做法，然後到一定threshold就compact。

References​