狠狠撸

狠狠撸Share a Scribd company logo

尝颈苍别补颈谤顿叠の绍介

?
?
S
Sho Nakazono

いつかの発表资料です

1 of 13
Download to read offline
LineairDB Introduction 2021/06/24 NTT ソフトウェアイノベーションセンタ 中園 翔 (@nikezono)
LineairDB 101 ? NTTが公開したOSS のトランザクションエンジン ? インメモリ?単一ノード?組み込み?メニーコア向け ? すべての機能が Epoch-based でデザインされている ? NWR: Blind Updateに強い高速ConcurrencyControl向け最適化 (NTT + 川島研, 論文投稿中) ? Parallel Logging & CPR checkpointing (SIGMOD 2019) ? Epoch-based ROWEX Index (VLDB 2020) ? サポートしている機能 ? Strict Serializability (Linearizability + Serializability) ? Durability (Logging & Checkpointing) ? Range Scan & Phantom Avoidance (WIP) ? Key/Value Interface: #Begin, #Get, #Put, #End, #Scan, #Sync ? (現状) サポートしていない機能 ? Distributed Transaction ? Query Interface. SQL/JDBC/ODBC/etc…
Result on YCSB-A (Read 50%, Blind update 50%) CPU four Intel Xeon E7-8870 (total 144 logical cores) Memory 1TB (no swap-out) YCSB Table size 100K YCSB Record size 8-bytes Epoch size 1000ms Contention (θ) 0.9 (highly contended) # of threads to process txns 70
? 以下，参考資料 – LineairDBの改善点 ? Concurrency Control編 ? Logging編 ? Checkpointing編 – Epoch FrameworkのPros/Cons
Modern In-Memory Database Architecture 1. DRAMの大容量化 Index (Tree) も Logging も，すべてがメモリに乗る前提の設計が必要 -> Disk I/Oよりキャッシュを意識したIndexが良い (B+Tree -> ART, Masstree) -> Dirty Pageが存在しないのでUndo Logが必要ない (No-steal, Force) -> I/Oよりも メモリ上のConcurrency Control で性能が律速される 1. CPUのメニーコア化 単一スレッドで動くコンポーネントは基本的にボトルネックに -> マルチスレッドプログラミングの重要性が増す -> LineairDBの改善点: Logging, Concurrency Control, Concurrent Index ?
従来のConcurrency ControlはUpdate-heavyなワークロードに弱い． Version order == Operation orderの従来理論ではLock/Latchが不可避． Concurrency Control: Updateの性能問題 Write(x) T1 T2 T3 Write(x) Write(x) wait wait Read(x) コア数を上げると、むしろ スループットが減少する。 既存トランザクション処理手法
LineairDBでは Blind Update を Epochごとに1 versionを残し省略する． 省略することでログ?ロック?インデックス更新などを全て短縮． LineairDBのCC: with Epoch Framework CPUコア数 8倍．世界最速． ト タ ル ス ル プ ト [million txns / s] Write(x) T1 T2 T3 省略可能 Read(x) Write(x) Write(x)
マルチスレッドプログラミングに必要な “同期” や “順序決定” の オーバヘッドを最小にするため，実時間を Epoch に区切る. LineairDBのトータルデザイン: Epoch Framework Worker #1 Worker #2 Worker #3 Wall-Clock Time Worker #1 Worker #2 Worker #3 Epoch 1 Epoch 2 Commit Point wait Txn Txn Txn Txn Txn Txn Txn Txn Txn wait Txn Txn Txn Txn Txn Txn Txn Txn Txn Committed Active
Logging: Centralized vs Distributed Logging ?Centralized Log Bufferを作ると，Latchが厳しい. ?Distributedだと，”ログが永続化された順序(LSN)” が失われる Worker #1 Worker #2 Worker #3 Centralized Log Buffer Latch? Centralized Logging Distributed Logging Worker ? #1 Thread Local Log Buffer Worker ? #2 Thread Local Log Buffer Worker ? #3 Thread Local Log Buffer #1->#2->#3 Commitもリカバリも この順で これが分からないと Commitを返す順序も #1 || #2 || #3
LineairDBのLogging: with Epoch Framework ?Log Formatに “所属するepoch”を入れておけば， ? ?Distributed LoggingしてもCommitはまとめて返せる ? Distributed Logging Worker ? #1 Thread Local Log Buffer Worker ? #2 Thread Local Log Buffer Worker ? #3 Thread Local Log Buffer #1 || #2 || #3 全WorkerのすべてのTxnsのロ グが永続化されるまで， Epochを進行させない Wenting Zheng, Stephen Tu, Eddie Kohler, and Barbara Liskov. 2014. Fast databases with fast durability and recovery through multicore parallelism. In Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation (OSDI'14). USENIX Association, USA, 465–477. Commit Point ここまで待てば， ActiveなTXはおらず， どの順番でCommitを 返しても問題なし
Disk-basedでよく用いられる“Fuzzy Checkpointing”は使えない． ?In-memory CheckpointingはConcurrency Controlの問題がある． Checkpointing: Disk-based vs In-Memory Committe d Disk-based Checkpointing In-Memory Checkpointing Active Transaction Log File(s) Active Active Txns Log は触らずに， Committed Txns LogをPagesに反映させればOK. Pages Pages TXN Worker TXN Worker TXN Worker x y z Checkpointer Checkpointerの処理は実質 ロングトランザクション． Read Lockがなければ， Consistent なCheckpoint
LineairDBのCheckpoint: with Epoch Framework １ページにつき，２つのバッファを用意．（live/stable) ”checkpoint epoch” を定期的に作り，stable imageを作成． In-Memory Checkpointing TXN Worker TXN Worker TXN Worker x y z Checkpointer 例えば: 1. 30秒おきに，Checkpoint Epoch ceを作る． 2. ce に属するTxnsは，普段の バッファに加えて “Stable Image” も更新する． 3. ce が充分古くなったら，こ れを読み出すだけで(Latch なしで) Checkpoint完了 x y z Live Images Stable Images Guna Prasaad, Badrish Chandramouli, and Donald Kossmann. 2020. Concurrent Prefix Recovery: Performing CPR on a Database. SIGMOD Rec. 49, 1 (March 2020), 16–23. DOI:https://doi.org/10.1145/3422648.3422653
? Epoch Frameworkの性質 ? Epochは一定時間と “e-1に属するTxnsが全て終了” で進行する ? -> ある epoch e において，e-2 に属するActive Txns は存在しない ? 同一epochトランザクションは，全て同じタイミングでCommitされる ? Pros ? ルーズに同期することで，マルチスレッド処理で必要な “順序” が得られる ? epochは「バッチでタイムスタンプを作っている」と捉えられる ? -> Distributed Logging, Checkpointing, Index, CC，全てに有用 ? Cons ? Commitまでの平均レイテンシが伸びる ? Long Transactionが入ると Epochの進行が止まる -> 誰もCommitできない！ ? バッチ処理との相性が極めて悪い. Epoch Framework Pros/Cons

More Related Content

尝颈苍别补颈谤顿叠の绍介

  • 2. LineairDB 101 ? NTTが公開したOSS のトランザクションエンジン ? インメモリ?単一ノード?組み込み?メニーコア向け ? すべての機能が Epoch-based でデザインされている ? NWR: Blind Updateに強い高速ConcurrencyControl向け最適化 (NTT + 川島研, 論文投稿中) ? Parallel Logging & CPR checkpointing (SIGMOD 2019) ? Epoch-based ROWEX Index (VLDB 2020) ? サポートしている機能 ? Strict Serializability (Linearizability + Serializability) ? Durability (Logging & Checkpointing) ? Range Scan & Phantom Avoidance (WIP) ? Key/Value Interface: #Begin, #Get, #Put, #End, #Scan, #Sync ? (現状) サポートしていない機能 ? Distributed Transaction ? Query Interface. SQL/JDBC/ODBC/etc…
  • 3. Result on YCSB-A (Read 50%, Blind update 50%) CPU four Intel Xeon E7-8870 (total 144 logical cores) Memory 1TB (no swap-out) YCSB Table size 100K YCSB Record size 8-bytes Epoch size 1000ms Contention (θ) 0.9 (highly contended) # of threads to process txns 70
  • 4. ? 以下，参考資料 – LineairDBの改善点 ? Concurrency Control編 ? Logging編 ? Checkpointing編 – Epoch FrameworkのPros/Cons
  • 5. Modern In-Memory Database Architecture 1. DRAMの大容量化 Index (Tree) も Logging も，すべてがメモリに乗る前提の設計が必要 -> Disk I/Oよりキャッシュを意識したIndexが良い (B+Tree -> ART, Masstree) -> Dirty Pageが存在しないのでUndo Logが必要ない (No-steal, Force) -> I/Oよりも メモリ上のConcurrency Control で性能が律速される 1. CPUのメニーコア化 単一スレッドで動くコンポーネントは基本的にボトルネックに -> マルチスレッドプログラミングの重要性が増す -> LineairDBの改善点: Logging, Concurrency Control, Concurrent Index ?
  • 6. 従来のConcurrency ControlはUpdate-heavyなワークロードに弱い． Version order == Operation orderの従来理論ではLock/Latchが不可避． Concurrency Control: Updateの性能問題 Write(x) T1 T2 T3 Write(x) Write(x) wait wait Read(x) コア数を上げると、むしろ スループットが減少する。 既存トランザクション処理手法
  • 7. LineairDBでは Blind Update を Epochごとに1 versionを残し省略する． 省略することでログ?ロック?インデックス更新などを全て短縮． LineairDBのCC: with Epoch Framework CPUコア数 8倍．世界最速． ト タ ル ス ル プ ト [million txns / s] Write(x) T1 T2 T3 省略可能 Read(x) Write(x) Write(x)
  • 8. マルチスレッドプログラミングに必要な “同期” や “順序決定” の オーバヘッドを最小にするため，実時間を Epoch に区切る. LineairDBのトータルデザイン: Epoch Framework Worker #1 Worker #2 Worker #3 Wall-Clock Time Worker #1 Worker #2 Worker #3 Epoch 1 Epoch 2 Commit Point wait Txn Txn Txn Txn Txn Txn Txn Txn Txn wait Txn Txn Txn Txn Txn Txn Txn Txn Txn Committed Active
  • 9. Logging: Centralized vs Distributed Logging ?Centralized Log Bufferを作ると，Latchが厳しい. ?Distributedだと，”ログが永続化された順序(LSN)” が失われる Worker #1 Worker #2 Worker #3 Centralized Log Buffer Latch? Centralized Logging Distributed Logging Worker ? #1 Thread Local Log Buffer Worker ? #2 Thread Local Log Buffer Worker ? #3 Thread Local Log Buffer #1->#2->#3 Commitもリカバリも この順で これが分からないと Commitを返す順序も #1 || #2 || #3
  • 10. LineairDBのLogging: with Epoch Framework ?Log Formatに “所属するepoch”を入れておけば， ? ?Distributed LoggingしてもCommitはまとめて返せる ? Distributed Logging Worker ? #1 Thread Local Log Buffer Worker ? #2 Thread Local Log Buffer Worker ? #3 Thread Local Log Buffer #1 || #2 || #3 全WorkerのすべてのTxnsのロ グが永続化されるまで， Epochを進行させない Wenting Zheng, Stephen Tu, Eddie Kohler, and Barbara Liskov. 2014. Fast databases with fast durability and recovery through multicore parallelism. In Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation (OSDI'14). USENIX Association, USA, 465–477. Commit Point ここまで待てば， ActiveなTXはおらず， どの順番でCommitを 返しても問題なし
  • 11. Disk-basedでよく用いられる“Fuzzy Checkpointing”は使えない． ?In-memory CheckpointingはConcurrency Controlの問題がある． Checkpointing: Disk-based vs In-Memory Committe d Disk-based Checkpointing In-Memory Checkpointing Active Transaction Log File(s) Active Active Txns Log は触らずに， Committed Txns LogをPagesに反映させればOK. Pages Pages TXN Worker TXN Worker TXN Worker x y z Checkpointer Checkpointerの処理は実質 ロングトランザクション． Read Lockがなければ， Consistent なCheckpoint
  • 12. LineairDBのCheckpoint: with Epoch Framework １ページにつき，２つのバッファを用意．（live/stable) ”checkpoint epoch” を定期的に作り，stable imageを作成． In-Memory Checkpointing TXN Worker TXN Worker TXN Worker x y z Checkpointer 例えば: 1. 30秒おきに，Checkpoint Epoch ceを作る． 2. ce に属するTxnsは，普段の バッファに加えて “Stable Image” も更新する． 3. ce が充分古くなったら，こ れを読み出すだけで(Latch なしで) Checkpoint完了 x y z Live Images Stable Images Guna Prasaad, Badrish Chandramouli, and Donald Kossmann. 2020. Concurrent Prefix Recovery: Performing CPR on a Database. SIGMOD Rec. 49, 1 (March 2020), 16–23. DOI:https://doi.org/10.1145/3422648.3422653
  • 13. ? Epoch Frameworkの性質 ? Epochは一定時間と “e-1に属するTxnsが全て終了” で進行する ? -> ある epoch e において，e-2 に属するActive Txns は存在しない ? 同一epochトランザクションは，全て同じタイミングでCommitされる ? Pros ? ルーズに同期することで，マルチスレッド処理で必要な “順序” が得られる ? epochは「バッチでタイムスタンプを作っている」と捉えられる ? -> Distributed Logging, Checkpointing, Index, CC，全てに有用 ? Cons ? Commitまでの平均レイテンシが伸びる ? Long Transactionが入ると Epochの進行が止まる -> 誰もCommitできない！ ? バッチ処理との相性が極めて悪い. Epoch Framework Pros/Cons