Database Internalsの輪読会の第7回 chapter 6, B-Tree Variantsの発表予定です。
chapter 6は6つの論文を軸にB treeの応用(亜種)について書かれていますが、それぞれの論文を紹介するにはページ数が少なく、「こんなのもあるよー」程度になっています。そのため、適当に読み飛ばす人も多いのではと思いますが、一つ一つの論文を読んでみるとかなり面白いです。
ここではchapter 6で紹介されている6つの論文を中心にB treeの研究を漁ってみた経過を超簡単にまとめます。 これらは論文を読みながら作ったメモなので、詳細については当日発表します。 興味のある方は勉強会に参加してみてください。
databaseinternals.connpass.com
僕はそもそもデータのIndexingに興味があり、この勉強会と関係なくこの調査及び実践(実装)は継続するつもりです。 仕事ではなく趣味でやっているため進捗は遅いですが、Indexingについて読むべき論文や面白い分野があればコメントいただけると泣いて喜びます。 間違いの指摘もお願いします。
調査した論文の関係図
chap 6の参考文献6本とその周辺論文の調査概要
- 緑の四角はchap6で紹介されている論文
- 他の論文はこれらがreferしている論文のうち主要(と思われる)もの
- 矢印はreferの方向の逆 (進化の流れみたいに見せたいので)
- 下から上に向かって大雑把に時系列
- 色付けした領域は僕独自のカテゴライズ(今後の発展に期待)
- 大かっこでつけたタグは以下の説明で概要を整理している (何も書いてないものは未整理)
- 論文の中もしくはDBMSのdocumentで論文を明示している場合は楕円でDBMSを表示
chap6のメイン論文6本
[co] Copy-on-Write B-Trees
- 基本情報
- Making Data Structures Persistent
- James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan
- STOC 1986
- 背景, 提案手法
- 一般的なデータ構造は
persistent
ではない. (ここでいうpersistentは変更前のデータにアクセス可能かどうかでhalf/full persistet)といっている) - linked data, とくにsearch treeをpersistentにする方法について議論する
- 一般的なデータ構造は
- 実験結果・比較対象
- なし
- コメント
- introの前半しか読んでない
[la] Lazy-Adaptive tree
- 基本情報
- Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices
- Devesh Agrawal , Deepak Ganesan , Ramesh Sitaraman , Yanlei Diao , and Shashi Singh
- VLDB 2009
- 背景
- 提案手法
Cascaded Buffers
: 木への更新をbufferingする領域をいくつかの階層のノードに配置Adaptive Buffering
: Cascaded Buffersのサイズを固定にせず、An online adaptive algorithm
によって動的に変化させることで効率化
- 実験結果・比較対象
- コメント
[fd2] FD tree
- 基本情報
- Tree Indexing on Solid State Drives
- inan Li, Bingsheng He, Robin Jun Yang, Qiong Luo, Ke Yi
- VLDB 2010
- 背景
- flash diskやSSDがmagnetic hard diskの代替として活躍しているが、flash diskの
erase-before-write mechanism
のせいでrandom writeの速度はrandom readより1,2桁違うレベルで遅い。 - これを解決することがflash disk利用の課題
- この論文の提案するFD treeでB+ treeと同等の検索性能、LSM treeと同等のinsert性能を実現する
- flash diskやSSDがmagnetic hard diskの代替として活躍しているが、flash diskの
- 提案手法
- 木を2分割してhead treeとそれ以下で構造を変える:
- 木をhead tree(B tree)と他(
sorted runs
)に分割 - head treeに対しては即時の更新をする(random writeの局所化)がsorted runsへの更新は遅延させる(random writeをsequencial化)
- 木をhead tree(B tree)と他(
logarithmic method
: 隣接するレイヤーのkey数を定数倍で変えるFractional cascading
: ([frc]を参照) Fractional cascadingにより検索を高速化- https://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf
- 木を2分割してhead treeとそれ以下で構造を変える:
- 実験結果・比較対象
- SSD(mtron, intel)とHard disk上で[b+], [lsm], [bftl]の3つと比較
- 4byteのunique key, 30bitのvalue + 2bitのtype(詳細は論文参照のこと)で128MB ~ 8GB分のデータを生成し、16MBのbuffer_pool(メモリ)で実験
- 検索においてはB+treeとほぼ同等(具体的な数値なし), insertにおいてはLSMより10 ~ 50%低速になったが、全体としては[B+], [btfl], [lsm]に対して24.2x, 5.8x, 1.8x倍速い結果となった
- hard disk上の実験でも1.1~2.6倍な結果となったらしい
- コメント
- ccに関しては言及なし
- table2のコスト計算謎が多い
- 3.4のdeamortized operationがよくわからん
[bw1] Bw tree
- 基本情報
- 背景
- Multi core CPUを活用するためには、(1) 高い並列度を実現するためにlatchが大きな障壁になる、また(2) マルチコアプロセッサを有効活用するためにはCPU cacheのhit率を上げる必要がある
- (3)モダンなstorage(flash disk)のIOパフォーマンス特性に対応する必要がある(log sturectured file systemの詳細は別論文としている)
- 提案手法
- (1)を解決するためにlatch freeな手法の提案(
SMOs: Structure Modification Operations
) - (2)を解決するため、また(1)の前提として
delta updating
の提案 - (3)の解決そして
LSS(Log Structured Store)
を構築(詳細は他の論文にするとしている)
- (1)を解決するためにlatch freeな手法の提案(
- 実験結果・比較対象
- Berkeley DBのB tree modeとLatch free skip listとの比較
- 3つのEvaluation Datasets
- BerkeleyDBに対して5.8x ~ 18.7x高速
- latch freeによってBwはCPU利用率99%だったのに対し、BerkeleyDBは60%
- Latch free Skip listに対して3.7x~4.4x高速, CPU L2 cacheまでのヒット率がBwは90%に対しskip listは75%
- コメント
- SQL serverのHekaton storageエンジンの内部実装の様子(論文中には書かれてない)
- Bw-tree自体は10,000行のC++でCAS updateにはWin32 nativeの
Interlocked CompareExchange64
を使う Node SplitにB-link treeの"atmic split installation technique"を採用
[mass], [b+], [art]のほうが全体的に良い結果
[co] Cache-Oblivious B-Trees
- 基本情報
- Cache-Oblivious B-Trees
- Michael A. Bender, Erik D. Demaine, Martin Farach-Colton
- SIAM 2005
- 背景
- CPUキャッシュ、メモリ、diskとアクセス速度の違いは大きい、こういた状況にそれぞれ対応するのは良くないので、ハードウェアの特性(特にblockサイズ)を考慮しなくてもよいデータ構造が必要
- 提案手法
- van-Emde-Boas likeな木へcache-oblibious algorithm, packed memory structureを導入した構造の提案
- 論文内でcache obliviousな木を3種類提案
- 実験結果・比較対象
- 実測はなし
- コメント
- 実用的なのか怪しい、cache obliviousにすることが目的になっていそう(それでよいのかも)
- 参考
- Cache-Oblibious データ構造入門 by iwiwiさん
- 上のスライドを読まないと目的を理解することすら厳しかった
Refer or 比較される論文
[bt] B tree
- 基本情報
- Organization and Maintenance of Large Ordered Indexes
- Bayer, E. McCreight
- Acta Informatica, 1972
- コメント
[b+] B+ tree (Ubiquitous)
- 基本情報
- The Ubiquitous B-Tree
- DOUGLAS COMER
- ACM Computing Surveys 1979
- コメント
[bl] B-link tree
- 基本情報
- Efficient locking for concurrent operations on B-trees
- Philip L. Lehman, s. Bing Yao
- ACM Transactions on Database Systems December 1981
- 背景, 提案手法
- 実験結果・比較対象
- コメント
[fd1] FD tree for flash disk
- 基本情報
[sl] Skip list
- 基本情報
- Skip lists: a probabilistic alternative to balanced trees
- William Pugh
- Communications of the ACM 1990
- 背景, 提案手法
- 実験結果・比較対象
- コメント
Actual DBMS
DBMSのドキュメント内などで論文を参照しているもの
[pg] Postgresql
btreeの実装に関するREADMEでb-link tree[bl]の実装を含むと書いている REL_12_4 tagのnbtreeのREADME
さらにdeleteのロジックについて"A Symmetric Concurrent B-Tree Algorithm"を使っているらしい
We also use a simplified version of the deletion logic described in Lanin and Shasha (V. Lanin and D. Shasha, A Symmetric Concurrent B-Tree Algorithm, Proceedings of 1986 Fall Joint Computer Conference, pp 380-389).
optional 参考文献
[frc] Fractional Cascading: I. A Data Structuring Technique
- https://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf
- Bernard Chazelle, Leonidas J. Guibas
- Algorithmica 1986
[lsfs] The design and implementation of a log-structured file system
- https://dl.acm.org/doi/abs/10.1145/146941.146943
- Mendel Rosenblum, John K. Ousterhout
- ACM Transactions on Computer Systems 1992
[ipl] Design of flash-based DBMS: an in-page logging approach
- https://dl.acm.org/doi/abs/10.1145/1247480.1247488
- Sang-Won Lee, Bongki Moon
- SIGMOD 2007
[fdb] FlashDB: dynamic self-tuning database for NAND flash
- https://dl.acm.org/doi/abs/10.1145/1236360.1236412
- Suman Nath, Aman Kansal
- IPSN 2007
[bftl] An efficient B-tree layer implementation for flash-memory storage systems
- https://dl.acm.org/doi/abs/10.1145/1275986.1275991
- Chin-Hsien Wu, Teiwei Kuo, LiPing Chang
- ACM Transactions on Embedded Computing Systems 2007
[cco] Concurrent Cache-Oblivious B-Trees
- Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Bradlay C. Kuszmaul
- SPAA 2005
[silo] Speedy Transactions in Multicore In-Memory Databases
- Silo
- Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden
- SOSP 2013
[mass] Cache craftiness for fast multicore key-value storage
- Masstree
- Yandong Mao, Eddie W Kohler, Robert Tappan Morris
- EuroSys 2012
[hy] HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots
- https://ieeexplore.ieee.org/document/5767867?arnumber=5767867
- Viktor Leis, Alfons Kemper, Thomas Neumann
- ICDE 2011
[art] The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases
- Viktor Leis, Alfons Kemper and Thomas Neumann
- ICDE 2013
[rb] A dichromatic framework for balanced trees
- Red Black tree
- https://ieeexplore.ieee.org/abstract/document/4567957
- Leo J. Guibas ; Robert Sedgewick
- SFSC 1978
[avl] An algorithm for organization of information
- AVL木
- http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26964&option_lang=eng
- G.M.Adel'son-Vel'skii, E.M.Landis
- 1962
Database internals本のchap 6のReference 6本以外の参考文献
- LMDB(Lightning Memory-Mapped Database)
- Copy-on-Writeの実例として
- https://symas.com/lmdb/ (本文中リンク)
WiredTiger
- Lazy B-Treesの実例として
- MongoDBのストレージエンジン
- https://docs.mongodb.com/manual/core/wiredtiger/
Concurrent maintenance of skip lists
- pugh90aとして参照されてる論文skip listのccの優位性の説明
- Skip Lists and Probabilistic Analysis of Algorithms
- Skip Listの提案論文