tom__bo’s Blog

MySQL!! MySQL!! @tom__bo

B-tree variantsの調査 

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を表示

f:id:tom__bo:20200823212344p:plain
btree-relations

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
  • 背景
    • Flash Diskが様々な環境で使われるようになり、それを含むSSDも普及してきた
    • 特にFlash Disk(raw NAND flashes)の特性を考慮したIndexを提案
  • 提案手法
    • Cascaded Buffers: 木への更新をbufferingする領域をいくつかの階層のノードに配置
    • Adaptive Buffering: Cascaded Buffersのサイズを固定にせず、An online adaptive algorithmによって動的に変化させることで効率化
  • 実験結果・比較対象
    • 直接flash diskを操作するためにエミュレータ実装し、Toshiba raw NAND flash chip上で実験.別途SSDでの実験もあり
    • 組み込み用途が主眼なのか、基本的に4byte integerのkey, valueのデータセットで8KB ~ 1MBのメモリで実験. workloadは多様でLTU(Lookup-to-Update ratio)を調整した実験もある
    • [bftl], [fdb], [ipl]とそれぞれのベースに採用しているB+ treeと比較してraw NAND flashe上では2x ~ 12x以上のパフォーマンスを発揮した
  • コメント
    • Concurrency Controlについては言及がない (比較実験にはreduced TPC-Cのworkloadはある)
    • 主にraw NAND flashesに集中していて、SSDとは違いbyte addressableで、IO costもSSDとは異なる点を主張しつつ進んでいく

[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性能を実現する
  • 提案手法
    • 木を2分割してhead treeとそれ以下で構造を変える:
      • 木をhead tree(B tree)と他(sorted runs)に分割
      • head treeに対しては即時の更新をする(random writeの局所化)がsorted runsへの更新は遅延させる(random writeをsequencial化)
    • logarithmic method: 隣接するレイヤーのkey数を定数倍で変える
    • Fractional cascading: ([frc]を参照) Fractional cascadingにより検索を高速化
    • https://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf
  • 実験結果・比較対象
    • 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

  • 基本情報
    • The Bw-Tree: A B-tree for New Hardware Platforms
    • Justin J. Levandoski, David B. Lomet, Sudipta Sengupta
    • 2013 IEEE 29th International Conference on Data Engineering (ICDE)
  • 背景
    • 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)を構築(詳細は他の論文にするとしている)
  • 実験結果・比較対象
    • Berkeley DBのB tree modeとLatch free skip listとの比較
    • 3つのEvaluation Datasets
      • Xbox LIVEの実workload, 27million get-set操作. 平均で94byte, 1200 byteのkey, value. (R:W = 7.5:1)
      • Storage deduplication trace. 現実のdeduplication traceのデータ27million chunks, 12million unique chunks. 20byte, 44byteのkey, value. (R:W = 2.2:1)
      • 仮想のデータセット8byte integerのkey, value. (R:W = 5:1)
    • 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にすることが目的になっていそう(それでよいのかも)
    • 参考

Refer or 比較される論文

[bt] B tree

  • 基本情報
    • Organization and Maintenance of Large Ordered Indexes
      1. 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

  • 基本情報
    • Tree Indexing on Flash Disks
    • inan Li, Bingsheng He, Robin Jun Yang, Qiong Luo, Ke Yi
    • IEEE Data Engineering 2009

[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).

https://github.com/postgres/postgres/blob/0ad348f38ea9aaafe51f9197c8a2498aaec70ff1/src/backend/access/nbtree/README#L9

optional 参考文献

[frc] Fractional Cascading: I. A Data Structuring Technique

[lsfs] The design and implementation of a log-structured file system

[ipl] Design of flash-based DBMS: an in-page logging approach

[fdb] FlashDB: dynamic self-tuning database for NAND flash

[bftl] An efficient B-tree layer implementation for flash-memory storage systems

[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

[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

[avl] An algorithm for organization of information

Database internals本のchap 6のReference 6本以外の参考文献

  • LMDB(Lightning Memory-Mapped Database)
  • WiredTiger

  • Concurrent maintenance of skip lists

    • pugh90aとして参照されてる論文skip listのccの優位性の説明
  • Skip Lists and Probabilistic Analysis of Algorithms
    • Skip Listの提案論文