In-MemoryDBの技術

In-Memory DBの技術 〜近代から現代へ〜 ＮＴＴ ソフトウェアイノベーションセンタ 熊崎宏樹 Copyri ght©2014 NTT corp. All Rights Reserved.

このスライドについて 話すこと • 近代のDB界隈の潮流 • トランザクション技術の変遷 話さないこと • 特定の商用DBの宣伝やF.U.D. • 機械学習 • OLAP（分析）系の話 Copyri ght©2014 NTT corp. All Rights Reserved.

In-Memory DBって？ 市中でよく見かける「インメモリ技術」は大きく２種類 ①「ディスクに書き込まないから高速です」 • • 嘘をついてはいないが、本命ではない tmpfsに書き込んでるから高速ですとか言う ②「大容量になったメモリを活用しています」 • ディスクにはちゃんと書き込んで永続化する • 現代のサーバの進化に合わせて再設計されたDBの事 この資料の主題 Copyri ght©2014 NTT corp. All Rights Reserved.

サーバの進化 OracleDBの最初のバージョン(V2)が発売されたのは1977年 • 当時はミニコン後期、AppleⅡ発売の年 • DECからミニコン・VAX-11/780発売 • メインメモリは2MB、最大8MB • ディスクはハイエンドで100MB程度 • メモリ＜＜(10倍以上)＜＜ディスクの時代 2016年現在 • Broadwell-EPならメモリは最大24TB • ディスクは単発だと10TBがやっと（ヘリウム充填） • メモリ＞＞ディスクの時代 Copyri ght©2014 NTT corp. All Rights Reserved.

アーキテクチャの変遷：In-Disk DB • ディスクが中心 • メモリはキャッシュ及びバッファとして使う • mmap/read等でディスクのページをメモリに写しとり書き戻す • PostgreSQLはshared_bufferという形でキャッシュしてワーカで共有 • HDDのランダムアクセスの遅さがネックになりがち • シーケンシャルアクセスでパフォーマンスを上げるテクの 研究が進んだ • WAL、グループコミット、ログ構造化、ARIESなどなど • ＣＰＵネックになるまで頑張る Copyri ght©2014 NTT corp. All Rights Reserved.

In-Disk DB 基本構造 • データを保持するディスクと、ログを保持するディスクがある • 物理的に同一でも構わない • メモリにあるB+ treeは飽くまでキャッシュに過ぎない • どこかのタイミングでWrite Backする必要がある B+ tree B+ tree Data Disk log buffer log Log Disk Copyri ght©2014 NTT corp. All Rights Reserved.

In-Disk DB 基本構造 • トランザクションの進捗と同時にログを書き出し続けるのが一般的 • いつバッファがディスクに書き戻される(Steal)かトランザクション側は制御できない • 途中でクラッシュしたりアボートしたらUndoしないといけない。 • ログが書き終わったらトランザクション完了と見做すのが一般的 • データディスクへの反映は後回し(no-force)でもよい いつキャッシュをディ スクに書き戻すかは LRUやチェックポイン ト次第 PostgreSQLは GCLOCKだったはず B+ tree B+ tree Data Disk log buffer ログバッファのデータ はトランザクションの 完了を待たずに書き 出し続ける log Log Disk Copyri ght©2014 NTT corp. All Rights Reserved.

In-Memory DB 基本構造 • メインメモリがプライマリなストレージなので、メインメモリに載るデータしか使 えない(亜種はある) • メモリ上のデータとディスク上のデータに対応関係があるとは限らない • いつの間にかバッファマネージャがページをディスクに書き出す(Steal)事はない • コミット時にDBがページをディスクに強制的に書き出す(Force)事もない B+ tree Snapshot Data Disk log buffer 現在主流なのはコミッ トが完了したときに Redoログだけを書き 出すタイプ log Log Disk Copyri ght©2014 NTT corp. All Rights Reserved.

アーキテクチャの変遷：In-Memory DB • メモリがメインのデータ置き場であり作業場 • メモリに入りきらないデータはそもそも入れては行けない • ディスクは永続化を担当 • ログとスナップショットの保存 • 原理的にはログ以外でフルのデータを持たなくてもよい • つまり再起動時は毎回ログで0から生成する事も可能 • 再起動の高速化及びログ領域の節約のためログからスナップ ショットデータを作る事は一般的 • In-Disk DBからページの永続性管理を解放する事で様々なマ ルチコア用の最適化を流しこめるようになる • In-MemoryDBにはそもそもページという概念がない • ページの生存管理にロックが要らない(地味に大きい) • 永続性とリカバリについてはこれまでと同等にしっかりサポート Copyri ght©2014 NTT corp. All Rights Reserved.

In-Memory DB 基本構造 • Force, Stealの関係を整理すると以下 No Force Redoログ必要軸 Force In-Memory In-DiskDBの DBはここ ほとんどは ここ 遅い ログ不要 Undoログ だけ必要 (実例を見たこ とない) No Steal Steal Undoログ必要軸 Copyri ght©2014 NTT corp. All Rights Reserved.

In-Memory DB 実装 商用In-MemoryDBはDiskにも何らかの形でデータを置く事がほとんど • Hekaton(SQL Server) • ページという単位にデータ構造が縛られなくなったのでアグレッシブな最適化が いくつも搭載されている • 厳密にはDiskも併用しているが、どう併用しているかは未調査 • SAP HANA • ページに縛られなくなったので、最近更新された行は行指向でデータを保持し、し ばらく更新されていない行は徐々に列指向型へ変化させていくデルタ型最適化を 施している • Anti-Caching(H-store) • Stonebraker先生の研究室で作られたOLTP用ストレージエンジン • Indexとキーだけをすべてmemoryに持ち、残りはDiskに書き出す • テーブルを各コアに割り当てるために水平に切り分割統治 • Siberia • Hekatonの改良の一つ。使われていない行をまるっとディスクに書き出してブルー ムフィルタで存在を管理する • ディスクに書き出したデータだけ列指向型に書き換える等ができる Copyri ght©2014 NTT corp. All Rights Reserved.

FOEDUS • 2015年に登場したインメモリOLTPエンジン • SIGMODはDB学会の最高峰の一つ • レイテンシが低くスループットが高いNVRAM向けに最適化 • MassTreeをベースにした楽観的並行制御 • 古典的なTree Lockプロトコルとは大きく違う • Siloをベースにした並列ログとリカバリプロトコル • グローバルカウンタが排除されてスケーラビリティ向上 • Log Gleanerによるスナップショットの並列作成 • Dual PageによるMemoryとNVRAMの連携 • NVRAMのデータが常にどこかの瞬間のフルスナップショットになる • Snapshot Isolationレベルで良いトランザクションはNVRAMを読めば良い • Master Treeと新しいコミットプロトコルによる低いAbort率 Copyri ght©2014 NTT corp. All Rights Reserved.

MassTree • 複数階層のB+treeで木の部分集合を保持する事で木を辿る際の比較演 算がcmp命令一個で済む木構造 • 従来のB+treeと比べて30%程高速に読み書きができる • レンジスキャンはその代わり遅い 1～8byte 9～16byte 17～24byte Copyri ght©2014 NTT corp. All Rights Reserved.

Silo • ログIDのためにuniqueかつmonotonicに増える単一カウンタを作りたくない • 40ms毎に全体で共有するepochをインクリメントし、それを元に各CPUコアがログを作れ ばよい • 同一epochのログが全部揃わない限りリカバリされない&クライアントにackも返却しない • 全部のコアが緩やかに協調するのでキャッシュ競合が減る 12a 次のEpochは 13だよー 11a 10a 9a 8a 7a 12b 11b 10b 9b 8b 7b 12c 11c 10c 9c 8c 7c 12d 11d 10d 9d 8d 7d Copyri ght©2014 NTT corp. All Rights Reserved.

Log Gleaner • 貯まったRedo-LogからMap-Reduce的にディスク用のツリー構造を作成する • 通常のトランザクション実行時でも10分に1度ほど起動する • リカバリプロセスが行う事そのもの 図は論文から抜粋 Copyri ght©2014 NTT corp. All Rights Reserved.

ベンチマーク • TPC-CでSiloをも超える圧倒的パフォーマンス • 1389万トランザクション/秒出ている(ネットワーク通信無し) • TPC-Cで登録されている世界記録は約50万トランザクション/秒 図は論文から抜粋 Copyri ght©2014 NTT corp. All Rights Reserved.

In-Memory DBの世間的な需要 • サービスの高度化に伴いExaData等の高速DBの需要は伸び続けている • NTTドコモ「ピーク時には300万SQL/秒捌かないといけない」 • NTTドコモの6600万顧客のリアルタイムビリング基盤「MoBills」を支えるデータ ベース基盤とは • http://www.atmarkit.co.jp/ait/articles/1601/20/news013_3.html • 現状でもCassandra等の分散NoSQLエンジンの採用事例が増加している事か らも「性能が出る永続DB」への需要は常にある • 流通、金融、製造、通信販売、電力、監視網の企業から現行のIn-Disk DBでは性 能が足りないから解決策が必要といわれている（別紙参照） Copyri ght©2014 NTT corp. All Rights Reserved.

• http://www.atmarkit.co.jp/ait/articles/1601/20/news013_3.html