狠狠撸

狠狠撸Share a Scribd company logo

Checkpointing Algorithms on In-memory DBMS

?Download as PPTX, PDF?
?
S
Sho Nakazono

インメモリ顿叠におけるチェックポイント技术のサーベイとか议论のまとめです．

1 of 23
Download to read offline
Checkpoint Algorithms on In-memory Databases nikezono, 11/25, 2022, system-readings
Checkpoint 101 ? チェックポイント: データベースのリカバリのための機能 ? 運用中のある時点のイメージを生成する ? その時点までに終わったトランザクションの情報を全て反映する ? 「ある時点」がいつなのかハッキリ言えない(一貫性がない)とNG ? `Point of consistency [1]` とよばれている Thread 1 ?1, ?? OK NG Thread 2 ?1 ?2 ?3 ?4 ?? ?? ?? ?2 ?? ?????????? Checkpoint Image: ?1, ??, ?2, ?? Depends ?? ?? ??????? ?? ?4
Checkpoint の意義 1. ログ(WAL)のサイズを有界にする ? 書き込みをする全トランザクションがログ (WAL) を書くため 2. リカバリ時間を高速にする ? WALを最初からリプレイしていると長い月日を要するため ? Compactionされたイメージにに最近のWALを適用する，というのが良い 3. チェックポイントベースの永続性を提供する ? FASTER-CPR [2] とか Redis の RDB 永続性とか． ? 一定時間おきに一貫性のあるスナップショットを取るだけ，というレベル ? 最近のものは揮発しても許してくれるね
Checkpointing on Disk-based DBMS ? ディスクベースのデータベース ? ディスク上にデータがもう載っている ? CommittedもAbortedもDirtyもディスクに書きこまれている ? ディスク上のデータが point of consistency を満たせばOK ? Aborted/Dirtyを適切に処理できればCommittedだけ残るので，OK ? Fuzzy Checkpointing というアルゴリズムが有名 ? Active transactionsのリストと Dirty Page Tableを作って保存しておき，運用中に 管理する ? Recovery時にこのリストを使ってdirty/abortを適切に処理する ? 詳細は ARIES [3] で．今日は語りません
Checkpointing on In-Memory DBMS ? インメモリデータベース ? ディスク上にデータがない ? ディスクにはログ（WAL）しかない ? アプローチはいろいろ ? WALをコンパクションする ? 定期的に全データをflushする ? 今日はこのアプローチの話をします
全データをflushする ? どうやるんだ ? Full-scan のread-only txn を走らせる? 重すぎ…… ? 2PL だと全データにロックかけることになる ? でも↓のNGパターンは起こらない Thread 1 ?1, ?? Thread 2 ?1 ?2 ?3 ?4 ?? ?? ?? ?2 ?? ?????????? Checkpoint Image: ?1, ??, ?2, ?? ?? ?? ??????? ?? ?4 もっと軽量に consistent な線を引く方法ないかな???
Making Virtual Point of Consistency ? Physical Point of Consistency (PPoC): 物理的な全停止状態 ? Logical Point of Consistency (LPoC): 論理的なPoC 1. Copy-On-Update ? Checkpoint用のバッファを用意して，各トランザクションに適宜退避させていく 2. Zig-Zag, Ping-Pong [4] ? Wait-freeなLPoC生成手法．固定長データ & たまにPPoCが必要 3. CALC [5] ? 可変長データOK&PPoC不要なLPoC生成手法．中央データ構造がある 4. CPR [6] ? 中央データ構造のない，かつ並列化されたLPoC生成手法 5. Hyper ? プロセスをforkしてコピーを取り，checkpointをしていく
Zig-Zag [4] ? データベースが各データにつき二つバッファ (AS) を管理する ? トランザクションに書かせるものと，チェックポイントに使うもの ? 分けることによってロックで排他しあう必要がなくなる ? 要約 ? 二つのバッファ ??[2]と二つのビットマップ??, ??を用意する ? ビットマップが，「どちらのバッファを使うべきか」を示す ? MR は 最新のデータが欲しいとき読むべきものを， MW は書くべきものを示してい る ? トランザクションは データ i を読むとき AS[MR[i]] [i]を使う ? チェックポイントは AS[?MW[i]][i] を使う ? 定期的にswitchする．PPoCに到達したときに行う
? データベースが各データにつき二つバッファ (AS) を管理する ? トランザクションに書かせるものと，チェックポイントに使うもの ? 分けることによってロックで排他しあう必要がなくなる ? 要約 ? 二つのバッファ ??[2]と二つのビットマップ??, ??を用意する ? ビットマップが，「どちらのバッファを使うべきか」を示す ? MR は 最新のデータが欲しいとき読むべきものを， MW は書くべきものを示してい る ? トランザクションは データ i を読むとき AS[MR[i]] [i]を使う ? チェックポイントは AS[?MW[i]][i] を使う ? 定期的にswitchする．PPoCに到達したときに行う Zig-Zag [4]
(Interleaved) Ping-Pong [4] ? Zig-Zagには欠点がある ? PPoCを作らないと次のチェックポイントに移行できない ? チェックポイント中はノンブロッキングだけど，まだ足りない ? Ping-Pongを提案 ? PPoCなし．代わりにさらに空間消費量を増やす ? AS, Odd, Even の３つの領域を作って各データをコピーする ? トランザクション ? ASとOdd or Evenのどっちか，指定されているほうに書き込む ? チェックポイント ? Odd or Even のどっちか，トランザクションに触られない方から読み込む ? スイッチング ? Odd or Even の指定を行うビットをアトミックに書き換える
(Interleaved) Ping-Pong [4] ? Zig-Zagには欠点がある ? PPoCを作らないと次のチェックポイントに移行できない ? チェックポイント中はノンブロッキングだけど，まだ足りない ? Ping-Pongを提案 ? PPoCなし．代わりにさらに空間消費量を増やす ? AS, Odd, Even の３つの領域を作って各データをコピーする ? トランザクション ? ASとOdd or Evenのどっちか，指定されているほうに書き込む ? チェックポイント ? Odd or Even のどっちか，トランザクションに触られない方から読み込む ? スイッチング ? Odd or Even の指定を行うビットをアトミックに書き換える
Zig-Zag and Ping-Pong [4]
CALC [1] ? Zig-Zag/Ping-Pongの改善 ? 固定長配列としてしか AS を用意できなかった点を改善 ? SwitchingにPPoCが必要だった点を改善 (Zig-Zagのみ) ? チェックポイントを5-phasesに分割 1. REST: チェックポイントしていない状態 2. PREPARE: VPoCを作る準備をする状態 3. RESOLVE: VPoCの後に位置する状態． ここで行われる変更はチェックポイントには入らない． 全員がPREPARE 状態に遷移したことを確認したら各自 RESOLVE に入っていく 4. CAPTURE: バックグラウンドでチェックポイントを書く状態 全員がRESOLVE状態に遷移したことを確認したら各自 CAPTUREに入っていく 全員がCAPTUREに入ったらバックグラウンドのcheckpointerが起動する 5. COMPLETE: チェックポイントが完了したことを示す状態
CALC [1] Cont’d ? CALCの考え方 ? チェックポイントは VPoC (PREPAREと RESOLVEの間) の後に実行される REST PREPARE RESOLVE CAPTURE COMPLETE VPoC Checkpointer works ? CheckpointerがVPoC時点での各データを読み取れるようにしたい
CALC [1] Cont’d ? CALCの考え方 ? チェックポイントは VPoC (PREPAREと RESOLVEの間) の後に実行される REST PREPARE RESOLVE CAPTURE COMPLETE VPoC Checkpointer works Stable versions (delta) ? CheckpointerがVPoC時点での各データを読み取れるようにしたい ? CALCでは， stable versions を読めば取れるようにする ? PREPARE 状態で最後にデータを更新した人は stable versionsも更新する ? RESOLVE 状態で最初にデータを読んだ人は stable versionsにもコピーする
CALC [1] Cont’d ? 各キーにバッファを二つ (live, stable) 用意する ? `stable_status` というビット配列を用意する ? Checkpointerから見て，db[key].stable は stable_status[key] is true のときVPoCのもの ? そうでない場合は，live version が更新されていないということなので，そのまま読める
CALC [1] Cont’d ? ナイーブなスナップショットとFuzzy checkpointだとスループットがゼロになるが，期間は短い ? Zig-Zag / Ping-Pong はチェックポイント中のスループットが落ちる． ? Ping-Pong はデータ1つにつき3つのバッファ (AS, Odd, Even) を用意するため，メモリ/キャッシュ効率が悪い ? 結局 Long Txが交じる (b) だと PPoC を作るためにみんな性能が悪くなるが， CALC はよくやっている．
CPR [2] ? CALCの改善 ? CALCは中央データ構造 commit_log が必要で，これを廃した ? commit_log には各スレッドのいる状態/これから始まる状態が書いてあった ? LineairDBでこれを実装 & 改善しました
CPR [2] Cont’d ? 状態遷移を Epoch Framework [5] でやっているのがnovelty ? atomic<int> epoch と atomic<int>[] thread_local_epoch で状態遷移する ? thread_local_epoch が全て同じ数値になったとき epoch をインクリメントする
CPR [2] Cont’d ? CPR は 4-phases からなる ? VPoCの前後の状態を作って，そこで各トランザクションがよしなに stable versionsを操作してい く???というのはCALCと 全く同じ ? 状態遷移を Epoch Framework [5] でやっているのがnovelty ? atomic<State> state と atomic<State>[] thread_local_state で状態遷移する ? thread_local_State が全て同じになったとき 次の phase に行く．ブロッキングしないのが売り ? PREPARE が IN-PROGRESS のデータを読んでしまうときは，アボートする ? このアボートは CALC でも必要なハズだが，論文中に一切記述がない IN- PROGRESS WAIT FLUSH REST PREPARE ? (? + 1) ? ? ? Aborts some transactions
LineairDB ? データベース全体に 統合されたEpoch Managerを用意 ? IN-PROGRESS phase のとき，トランザクションが各データを stable にコピーする ? PREPARE フェーズを削除 ? これはアボートのための状態だが， LineairDBでは e+1 のTxが e のデータを読むこと はない IN- PROGRESS WAIT FLUSH REST PREPARE ? (? + 1) ? ? ? Aborts some transactions IN- PROGRESS WAIT FLUSH REST ? (? + 1) Epoch Manager
Unknowns ? WALをコンパクションしてチェックポイントする手法，少なす ぎ ? なぜ？ ? ファイルを触ると並行性が低い（e.g., lock) から？
References 1. Kun Ren, Thaddeus Diamond, Daniel J. Abadi, and Alexander Thomson. 2016. Low-Overhead Asynchronous Checkpointing in Main-Memory Database Systems. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16). Association for Computing Machinery, New York, NY, USA, 1539–1551. https://doi.org/10.1145/2882903.2915966 2. Guna Prasaad, Badrish Chandramouli, and Donald Kossmann. 2020. Concurrent Prefix Recovery: Performing CPR on a Database. SIGMOD Rec. 49, 1 (March 2020), 16–23. https://doi.org/10.1145/3422648.3422653 3. C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz. 1992. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Trans. Database Syst. 17, 1 (March 1992), 94–162. https://doi.org/10.1145/128765.128770 4. Tuan Cao, Marcos Vaz Salles, Benjamin Sowell, Yao Yue, Alan Demers, Johannes Gehrke, and Walker White. 2011. Fast checkpoint recovery algorithms for frequently consistent applications. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data (SIGMOD '11). Association for Computing Machinery, New York, NY, USA, 265–276. https://doi.org/10.1145/1989323.1989352 5. Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. 2013. Speedy transactions in multicore in-memory databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). Association for Computing Machinery, New York, NY, USA, 18–32. https://doi.org/10.1145/2517349.2522713

More Related Content

Checkpointing Algorithms on In-memory DBMS

  • 1. Checkpoint Algorithms on In-memory Databases nikezono, 11/25, 2022, system-readings
  • 2. Checkpoint 101 ? チェックポイント: データベースのリカバリのための機能 ? 運用中のある時点のイメージを生成する ? その時点までに終わったトランザクションの情報を全て反映する ? 「ある時点」がいつなのかハッキリ言えない(一貫性がない)とNG ? `Point of consistency [1]` とよばれている Thread 1 ?1, ?? OK NG Thread 2 ?1 ?2 ?3 ?4 ?? ?? ?? ?2 ?? ?????????? Checkpoint Image: ?1, ??, ?2, ?? Depends ?? ?? ??????? ?? ?4
  • 3. Checkpoint の意義 1. ログ(WAL)のサイズを有界にする ? 書き込みをする全トランザクションがログ (WAL) を書くため 2. リカバリ時間を高速にする ? WALを最初からリプレイしていると長い月日を要するため ? Compactionされたイメージにに最近のWALを適用する，というのが良い 3. チェックポイントベースの永続性を提供する ? FASTER-CPR [2] とか Redis の RDB 永続性とか． ? 一定時間おきに一貫性のあるスナップショットを取るだけ，というレベル ? 最近のものは揮発しても許してくれるね
  • 4. Checkpointing on Disk-based DBMS ? ディスクベースのデータベース ? ディスク上にデータがもう載っている ? CommittedもAbortedもDirtyもディスクに書きこまれている ? ディスク上のデータが point of consistency を満たせばOK ? Aborted/Dirtyを適切に処理できればCommittedだけ残るので，OK ? Fuzzy Checkpointing というアルゴリズムが有名 ? Active transactionsのリストと Dirty Page Tableを作って保存しておき，運用中に 管理する ? Recovery時にこのリストを使ってdirty/abortを適切に処理する ? 詳細は ARIES [3] で．今日は語りません
  • 5. Checkpointing on In-Memory DBMS ? インメモリデータベース ? ディスク上にデータがない ? ディスクにはログ（WAL）しかない ? アプローチはいろいろ ? WALをコンパクションする ? 定期的に全データをflushする ? 今日はこのアプローチの話をします
  • 6. 全データをflushする ? どうやるんだ ? Full-scan のread-only txn を走らせる? 重すぎ…… ? 2PL だと全データにロックかけることになる ? でも↓のNGパターンは起こらない Thread 1 ?1, ?? Thread 2 ?1 ?2 ?3 ?4 ?? ?? ?? ?2 ?? ?????????? Checkpoint Image: ?1, ??, ?2, ?? ?? ?? ??????? ?? ?4 もっと軽量に consistent な線を引く方法ないかな???
  • 7. Making Virtual Point of Consistency ? Physical Point of Consistency (PPoC): 物理的な全停止状態 ? Logical Point of Consistency (LPoC): 論理的なPoC 1. Copy-On-Update ? Checkpoint用のバッファを用意して，各トランザクションに適宜退避させていく 2. Zig-Zag, Ping-Pong [4] ? Wait-freeなLPoC生成手法．固定長データ & たまにPPoCが必要 3. CALC [5] ? 可変長データOK&PPoC不要なLPoC生成手法．中央データ構造がある 4. CPR [6] ? 中央データ構造のない，かつ並列化されたLPoC生成手法 5. Hyper ? プロセスをforkしてコピーを取り，checkpointをしていく
  • 8. Zig-Zag [4] ? データベースが各データにつき二つバッファ (AS) を管理する ? トランザクションに書かせるものと，チェックポイントに使うもの ? 分けることによってロックで排他しあう必要がなくなる ? 要約 ? 二つのバッファ ??[2]と二つのビットマップ??, ??を用意する ? ビットマップが，「どちらのバッファを使うべきか」を示す ? MR は 最新のデータが欲しいとき読むべきものを， MW は書くべきものを示してい る ? トランザクションは データ i を読むとき AS[MR[i]] [i]を使う ? チェックポイントは AS[?MW[i]][i] を使う ? 定期的にswitchする．PPoCに到達したときに行う
  • 9. ? データベースが各データにつき二つバッファ (AS) を管理する ? トランザクションに書かせるものと，チェックポイントに使うもの ? 分けることによってロックで排他しあう必要がなくなる ? 要約 ? 二つのバッファ ??[2]と二つのビットマップ??, ??を用意する ? ビットマップが，「どちらのバッファを使うべきか」を示す ? MR は 最新のデータが欲しいとき読むべきものを， MW は書くべきものを示してい る ? トランザクションは データ i を読むとき AS[MR[i]] [i]を使う ? チェックポイントは AS[?MW[i]][i] を使う ? 定期的にswitchする．PPoCに到達したときに行う Zig-Zag [4]
  • 10. (Interleaved) Ping-Pong [4] ? Zig-Zagには欠点がある ? PPoCを作らないと次のチェックポイントに移行できない ? チェックポイント中はノンブロッキングだけど，まだ足りない ? Ping-Pongを提案 ? PPoCなし．代わりにさらに空間消費量を増やす ? AS, Odd, Even の３つの領域を作って各データをコピーする ? トランザクション ? ASとOdd or Evenのどっちか，指定されているほうに書き込む ? チェックポイント ? Odd or Even のどっちか，トランザクションに触られない方から読み込む ? スイッチング ? Odd or Even の指定を行うビットをアトミックに書き換える
  • 11. (Interleaved) Ping-Pong [4] ? Zig-Zagには欠点がある ? PPoCを作らないと次のチェックポイントに移行できない ? チェックポイント中はノンブロッキングだけど，まだ足りない ? Ping-Pongを提案 ? PPoCなし．代わりにさらに空間消費量を増やす ? AS, Odd, Even の３つの領域を作って各データをコピーする ? トランザクション ? ASとOdd or Evenのどっちか，指定されているほうに書き込む ? チェックポイント ? Odd or Even のどっちか，トランザクションに触られない方から読み込む ? スイッチング ? Odd or Even の指定を行うビットをアトミックに書き換える
  • 13. CALC [1] ? Zig-Zag/Ping-Pongの改善 ? 固定長配列としてしか AS を用意できなかった点を改善 ? SwitchingにPPoCが必要だった点を改善 (Zig-Zagのみ) ? チェックポイントを5-phasesに分割 1. REST: チェックポイントしていない状態 2. PREPARE: VPoCを作る準備をする状態 3. RESOLVE: VPoCの後に位置する状態． ここで行われる変更はチェックポイントには入らない． 全員がPREPARE 状態に遷移したことを確認したら各自 RESOLVE に入っていく 4. CAPTURE: バックグラウンドでチェックポイントを書く状態 全員がRESOLVE状態に遷移したことを確認したら各自 CAPTUREに入っていく 全員がCAPTUREに入ったらバックグラウンドのcheckpointerが起動する 5. COMPLETE: チェックポイントが完了したことを示す状態
  • 14. CALC [1] Cont’d ? CALCの考え方 ? チェックポイントは VPoC (PREPAREと RESOLVEの間) の後に実行される REST PREPARE RESOLVE CAPTURE COMPLETE VPoC Checkpointer works ? CheckpointerがVPoC時点での各データを読み取れるようにしたい
  • 15. CALC [1] Cont’d ? CALCの考え方 ? チェックポイントは VPoC (PREPAREと RESOLVEの間) の後に実行される REST PREPARE RESOLVE CAPTURE COMPLETE VPoC Checkpointer works Stable versions (delta) ? CheckpointerがVPoC時点での各データを読み取れるようにしたい ? CALCでは， stable versions を読めば取れるようにする ? PREPARE 状態で最後にデータを更新した人は stable versionsも更新する ? RESOLVE 状態で最初にデータを読んだ人は stable versionsにもコピーする
  • 16. CALC [1] Cont’d ? 各キーにバッファを二つ (live, stable) 用意する ? `stable_status` というビット配列を用意する ? Checkpointerから見て，db[key].stable は stable_status[key] is true のときVPoCのもの ? そうでない場合は，live version が更新されていないということなので，そのまま読める
  • 17. CALC [1] Cont’d ? ナイーブなスナップショットとFuzzy checkpointだとスループットがゼロになるが，期間は短い ? Zig-Zag / Ping-Pong はチェックポイント中のスループットが落ちる． ? Ping-Pong はデータ1つにつき3つのバッファ (AS, Odd, Even) を用意するため，メモリ/キャッシュ効率が悪い ? 結局 Long Txが交じる (b) だと PPoC を作るためにみんな性能が悪くなるが， CALC はよくやっている．
  • 18. CPR [2] ? CALCの改善 ? CALCは中央データ構造 commit_log が必要で，これを廃した ? commit_log には各スレッドのいる状態/これから始まる状態が書いてあった ? LineairDBでこれを実装 & 改善しました
  • 19. CPR [2] Cont’d ? 状態遷移を Epoch Framework [5] でやっているのがnovelty ? atomic<int> epoch と atomic<int>[] thread_local_epoch で状態遷移する ? thread_local_epoch が全て同じ数値になったとき epoch をインクリメントする
  • 20. CPR [2] Cont’d ? CPR は 4-phases からなる ? VPoCの前後の状態を作って，そこで各トランザクションがよしなに stable versionsを操作してい く???というのはCALCと 全く同じ ? 状態遷移を Epoch Framework [5] でやっているのがnovelty ? atomic<State> state と atomic<State>[] thread_local_state で状態遷移する ? thread_local_State が全て同じになったとき 次の phase に行く．ブロッキングしないのが売り ? PREPARE が IN-PROGRESS のデータを読んでしまうときは，アボートする ? このアボートは CALC でも必要なハズだが，論文中に一切記述がない IN- PROGRESS WAIT FLUSH REST PREPARE ? (? + 1) ? ? ? Aborts some transactions
  • 21. LineairDB ? データベース全体に 統合されたEpoch Managerを用意 ? IN-PROGRESS phase のとき，トランザクションが各データを stable にコピーする ? PREPARE フェーズを削除 ? これはアボートのための状態だが， LineairDBでは e+1 のTxが e のデータを読むこと はない IN- PROGRESS WAIT FLUSH REST PREPARE ? (? + 1) ? ? ? Aborts some transactions IN- PROGRESS WAIT FLUSH REST ? (? + 1) Epoch Manager
  • 23. References 1. Kun Ren, Thaddeus Diamond, Daniel J. Abadi, and Alexander Thomson. 2016. Low-Overhead Asynchronous Checkpointing in Main-Memory Database Systems. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16). Association for Computing Machinery, New York, NY, USA, 1539–1551. https://doi.org/10.1145/2882903.2915966 2. Guna Prasaad, Badrish Chandramouli, and Donald Kossmann. 2020. Concurrent Prefix Recovery: Performing CPR on a Database. SIGMOD Rec. 49, 1 (March 2020), 16–23. https://doi.org/10.1145/3422648.3422653 3. C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz. 1992. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Trans. Database Syst. 17, 1 (March 1992), 94–162. https://doi.org/10.1145/128765.128770 4. Tuan Cao, Marcos Vaz Salles, Benjamin Sowell, Yao Yue, Alan Demers, Johannes Gehrke, and Walker White. 2011. Fast checkpoint recovery algorithms for frequently consistent applications. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data (SIGMOD '11). Association for Computing Machinery, New York, NY, USA, 265–276. https://doi.org/10.1145/1989323.1989352 5. Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. 2013. Speedy transactions in multicore in-memory databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). Association for Computing Machinery, New York, NY, USA, 18–32. https://doi.org/10.1145/2517349.2522713