# Riak 的 Bitcask-用于快速鍵/值數據的日志結構哈希表 > 原文： [http://highscalability.com/blog/2011/1/10/riaks-bitcask-a-log-structured-hash-table-for-fast-keyvalue.html](http://highscalability.com/blog/2011/1/10/riaks-bitcask-a-log-structured-hash-table-for-fast-keyvalue.html)  如果從頭開始，您將如何實現鍵值存儲系統？ Basho 使用 [Bitcask](http://downloads.basho.com/papers/bitcask-intro.pdf) （他們的 Riak 的新后端）決定采用的方法是一種有趣的組合，使用 RAM 存儲指向值的文件指針的哈希映射和用于高效寫入的日志結構文件系統。 在這次出色的 [Changelog 采訪](http://thechangelog.com/post/1525527959/episode-0-4-0-riak-revisited-with-andy-gross-mark-philli)中，來自 Basho 的一些人更詳細地描述了 Bitcask。 基本的木桶： * 密鑰存儲在內存中以便快速查找。 所有密鑰必須適合 RAM。 * 寫操作僅是追加操作，這意味著寫操作嚴格是順序執行的，不需要查找。 寫是直寫的。 每次更新值時，都會附加磁盤上的數據文件，并使用文件指針更新內存中的索引。 * O（1）隨機磁盤搜尋可滿足讀取查詢的需求。 如果所有密鑰都適合內存，則延遲是非常可預測的，因為不會在文件中四處尋找。 * 對于讀取，將使用內核中的文件系統緩存，而不是在 Riak 中編寫復雜的緩存方案。 * 舊值將被壓縮或“合并”以釋放空間。 Bitcask 具有[窗口合并](http://blog.basho.com/2011/01/05/riak-0.14-released/)： *Bitcask 對所有非活動文件執行定期合并，以壓縮舊版本存儲數據占用的空間。 在某些情況下，這可能會導致進行合并的 Riak 節點上的某些內存和 CPU 峰值。 為此，我們添加了指定 Bitcask 何時執行合并的功能。* * 通過 Bitcask 上方的[軟件層，使用](http://wiki.basho.com/An-Introduction-to-Riak.html)[向量時鐘](http://blog.basho.com/2010/01/29/why-vector-clocks-are-easy/)實現獲取和設置并發。 * 值索引的鍵存在于內存中以及提示文件中的文件系統中。 數據文件合并時生成提示文件。 重新啟動時，僅需要為非合并文件重建索引，該文件應占數據的一小部分。 Eric Brewer（CAP 定理）通過考慮您是否有能力將所有密鑰保存在內存中（這在現代系統中很有可能），使 Bitcask 產生了想法，您可以相對容易地設計和實現存儲系統。 [提交日志](http://wiki.apache.org/cassandra/Durability)可用作數據庫本身，提供了原子性和持久性。 只需寫入一次即可保留數據。 單獨寫入數據文件，不需要提交日志。 值更新后，首先將其附加到磁盤提交日志中。 然后，將鍵映射到磁盤指針的內存中哈希表將更新為指向文件和文件中記錄的偏移量。 因此，讀取僅需要一個文件 I / O。 哈希鍵可找到文件指針，您只需查找偏移量并讀取該值。 對于寫入，它只是文件的追加。 很漂亮 在純內存數據庫和虛擬存儲層支持的基于磁盤的數據存儲之間，這是一個很好的折衷方案。 一些潛在的問題： * 如果您懷疑密鑰的數量將超過 RAM，那么將工作集保留在內存中的體系結構將是一個更好的選擇。 * 它比純內存數據庫要慢。 * 問題通常在垃圾回收階段作為資源高峰而出現，同時回收用于刪除值的空間。 Bitcask 希望通過將垃圾收集的調度安排到特定時期來降低成本，盡管在擁有國際用戶的 24x7 物業中，這可能還不夠。 * 在每次寫入時進行同步可能會有些痛苦。 如果將寫入緩沖并同步復制到備份節點以提高可用性，則可以提高寫入吞吐量。 * 我不相信操作系統緩存。 操作系統緩存不知道您的訪問模式。 自定義緩存可能會帶來復雜性，但是很難相信當出現問題時它的性能不會更好或無法調整。 Basho 似乎對這種方法感到滿意，但仍然讓我感到不安。 如果流量具有均勻分布或類似 pareto 的分布，會發生什么？ 對您的應用進行基準測試！ ## **相關文章** * [變更日志采訪](http://thechangelog.com/post/1525527959/episode-0-4-0-riak-revisited-with-andy-gross-mark-philli)，其中描述了 [Bitcask](http://downloads.basho.com/papers/bitcask-intro.pdf) 。 * [Bitcask-Justin Sheehy 和 David Smith 編寫的用于快速鍵/值數據的對數結構哈希表](http://downloads.basho.com/papers/bitcask-intro.pdf)，靈感來自 Eric Brewer。 * [Redis Diskstore](http://groups.google.com/group/redis-db/browse_thread/thread/d444bc786689bde9) 。 這是 Redis 的操作方式。 * [RethinkDB 內部：緩存體系結構](http://www.rethinkdb.com/blog/2011/01/rethinkdb-internals-the-caching-architecture/#)。 這是 RethingDB 的工作方式。 * [Bitcask Rocks](http://pl.atyp.us/wordpress/?p=2868) ，作者：Jeff Darcy。 *至少對于這些簡單測試而言，Bitcask 的性能與廣告中所宣傳的相同。 如果不進行調整，則讀寫操作似乎都在攤銷大量操作的查找成本。* * [克服 I / O 瓶頸：J Ousterhout 的日志結構文件系統](http://www.google.com/url?sa=t&source=web&cd=3&ved=0CCoQFjAC&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.37.9531%26rep%3Drep1%26type%3Dpdf&ei=n8ckTcS1O46WsgObqPCDAg&usg=AFQjCNFxzphJrEx281Sm9nZuA7iQR1XpBg&sig2=16OP4cTwBPgjjUp1B5Qx4Q)案例 * [Riak SmartMachine 基準測試：技術細節](http://joyeur.com/2010/10/31/riak-smartmachine-benchmark-the-technical-details/) * [P O'Neil 的日志結構化合并樹（LSM-Tree）](http://www.google.com/url?sa=t&source=web&cd=2&ved=0CB0QFjAB&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.44.2782%26rep%3Drep1%26type%3Dpdf&ei=780kTdPyGI7ksQPAvMzNAQ&usg=AFQjCNGGoN9IFTLShcv2HbL0RVQdElfxow&sig2=kO9xiGo1mgbywgsRpPi4Kg) * [該死的涼爽算法：日志結構化存儲](http://blog.notdot.net/2009/12/Damn-Cool-Algorithms-Log-structured-storage)，作者：Nick Johnson * [HBase Architecture 101-Lars George 的預寫日志](http://www.larsgeorge.com/2010/01/hbase-architecture-101-write-ahead-log.html) * [Cassandra Wiki 耐久性條目](http://wiki.apache.org/cassandra/Durability) * [Alfred-是 node.js 的快速進程內鍵值存儲。](http://pgte.github.com/alfred/) *Alfred 將數據存儲在僅附加文件*中。 * [Bigtable：結構化數據的分布式存儲系統](http://osdi2006.blogspot.com/2006/10/paper-bigtable-distributed-storage.html) “如果您懷疑您將擁有比 RAM 更多的密鑰，那么在內存中保留工作集的體系結構將是一個更好的選擇。” 是的，DB / Java（http://www.oracle.com/technetwork/database/berkeleydb/overview/index-093405.html）幾乎是開箱即用的，并且與 Bitcask 具有相對相似的整體方法。 這些年來，有很多類似系統的例子，Basho 選擇了基礎知識，并根據自己的需求構建了一些特定的東西。 可以在 Gray 和 Reuter 的“事務處理：概念和技術”中找到許多理論（例如，扎根于 System R（http://zh.wikipedia.org/wiki/IBM_System_R））。 “在每次寫入時進行同步可能會有些痛苦。如果對寫入進行緩沖并且將數據同步復制到備份節點以實現高可用性，則可以提高寫入吞吐量。” 好吧，如果您真正是同步的并且不想延遲等待寫操作的人，則緩沖的好處有限。 實際上，許多系統都會引入延遲，以便可以進行緩沖。 同步復制到備份節點會帶來一系列問題，需要適當調整網絡堆棧。 您還面臨著處理副本丟失的所有麻煩。 我相信，通常 Riak 會在存儲層之外處理該問題。 “將舊值壓縮或“合并”以釋放空間。”-有些人可能會說這是 DB 語言中的檢查點。 “我不相信操作系統緩存。OS 緩存不知道您的訪問模式。自定義緩存可能會帶來復雜性，但是很難相信它會在出現問題時表現不佳或變得更可調。” 自定義緩存只能在編寫或更新之前知道其開發人員所看到的訪問模式。 換一種說法，任何高速緩存的性能僅與到目前為止公開和調整的訪問模式集一樣好。 隨著時間的流逝，操作系統緩存已暴露于許多不同的訪問模式，并且在大多數情況下都表現出合理的平衡。 我確定在特定情況下自定義緩存會更好，但是 Riak 工作負載是否足夠具體/可預測？ 可能不是現在，也許以后。 我忘了說了，電池保護的寫緩存之類的東西是使磁盤同步更便宜的另一種方法。 在[文章](http://www.varnish-cache.org/trac/wiki/ArchitectNotes)中比較了 Squid 和 Varnish 的體系結構，作者聲稱自定義內存管理會因分頁而影響性能。 考慮到這一點，他建議您最好將其留給操作系統。 這些論點對這里討論的情況也無效嗎？ @Hugh Redis 開發人員現在正在考慮他先前決定繞過操作系統頁面緩存的決定-https://groups.google.com/d/topic/redis-db/1ES8eGaJvek/discussion 去年，我曾提醒他有關那篇不錯的 Varnish 文章-請在此處查看評論＃29 http://antirez.com/post/redis-virtual-memory-story.html 好吧，有些人喜歡刻苦學習；-) 與矢量時鐘的鏈接已斷開。 正確的鏈接應該是 http://basho.com/posts/technical/why-vector-clocks-are-easy/