lsm-tree vs B-tree

直覺來看，LSM-tree的優(yōu)勢在于寫性能， B-tree的優(yōu)勢在于讀性能， 而LSM-tree可能需要檢查不同的data structure及SST才能得到.
但是, 你不該這么武斷的得出這個結(jié)論， 而是應(yīng)該通過你的具體場景做比較， 在衡量存儲引擎性能時， 這里有幾個值得思考的東西

• LSM-tree的優(yōu)勢

  B-tree

  寫數(shù)據(jù)時， 每條數(shù)據(jù)至少要寫兩次： 一次是WAL， 一次是page 自身， 這里有額外開銷得注意： 即使一個page 只改了一個字節(jié)，寫入時候，也要寫入整個page， 在一些基于B-tree引擎中，為了避免在斷電情況下，page的部分被更新，甚至需要寫兩次page。

  Lsm-tree
  由于多次compaction，需要多次重寫數(shù)據(jù)，這就導(dǎo)致對數(shù)據(jù)庫的一次寫轉(zhuǎn)換化為磁盤的多次寫，這在SSD上就成了隱患，SSD只能進行有限次數(shù)的overwrite block

  在write-heavy application中，性能的瓶頸在database寫入磁盤的速率， 在這種情況下， 寫放大對性能有直接有影響： 引擎寫入磁盤數(shù)據(jù)越多， 有限帶寬下能每秒鐘寫入的數(shù)據(jù)越少。

  還有，相比B-tree，LSM-tree更能支撐比較高的write throughout， 一部分原因在于他有更低的寫放大（雖然這個依賴引擎的配置） ， 一部分原因在于順序?qū)慶ompact SST file，而不像B-tree那樣，需要更新多個page。 這個不同在HDD體現(xiàn)的更加明顯（順序?qū)戇h高于隨機寫， 差距在1000）

  另外，LSM-tree可以更好的進行壓縮，因此可以在磁盤上產(chǎn)生更小的件， 再看B-tree, 由于fragmentation, 有些Disk space不能被使用， 由于LSM-tree不是page-oriented 的并且會不斷的做compaction, 因此LSM-tree的磁盤占有更小， 特別是在使用level compaction。

  在很多SSDs上， the firmware internally uses a log-structured algorithm to turn ran‐ dom writes into sequential writes on the underlying storage chips, so the impact of the storage engine’s write pattern is less pronounced 。 然而， 在SSDs 上， 更低的寫放大/以及reduces fragmentation依然有優(yōu)勢： 在有限的IO帶寬下， representing data more compactly allows more read and write requests

• LSM-tree的劣勢

  1. compaction 可能會影響正在進行的read/write, 由于disk have limited resouces, 因此某些讀操作必須等到expensive compaction完成之后才能進行， 這種對throughout/average response time 影響一般很小， 但是在at the percentiles，query的response time 有時候很高， 比較而言，B-tree的性能一般是穩(wěn)定的。

  2. disk 的寫入帶寬被多個thread共享： logging、flush、compaction, 當(dāng)database越來越大， 更多的帶寬被compaction占用。

  3. 如果 compaction的速率低于incoming write，unmerged segments越來越多，導(dǎo)致run out of disk， 而且，在讀數(shù)據(jù)時， 由于需要檢查的文件越來越多，read的性能也會降低。

  4. B-tree每個key只存在一個地方，在LSM-tree，同一個key可能會存在多個文件中，這個特性是B-tree特別容易提供強事務(wù)特性，