Miniposts in 2025

2025/04/23

輪読

CRDV: Conflict-free Replicated Data Views Nuno Faria and José Pereira. 2025. CRDV: Conflict-free Replicated Data Views. Proc. ACM Manag. Data 3, 1, Article 25 (February 2025), 27 pages. https://doi.org/10.1145/3709675 (opens in a new tab)

いままでなかなか扱いづらかったCRDTをSQLで記述できるようにする取り組み． Relational operatorでmerge ruleを記述できるとかなりユーザフレンドリーになる． タイトルからは「CRDTをViewで使えるようにするのかな？」と思っていたが，それは方法にすぎず，モチベーションはCRDTをSQLで扱うことだった．

具体的には， 論文の図1がわかりやすい． データベースの変更を History テーブルへの inserts とみなして溜め込んで， Present viewで最終状態を計算するのに必要なinsertsをフィルタし，Value view で最終状態を計算する (mergeする) 3層構造にする． ユーザ定義関数もValue viewに対する操作として定義するため，下のレイヤの実装の詳細は隠蔽される． （CRDTの型のような）直接的な実装の制約がなくなるので性能も出しやすい．

一見して遅延評価的にマージするLSM-treeとかと似た話のように見えるが，これはCRDT (CALM theorem) なのでセマンティクスが少し違う． The same item に対しては total orderではなく causalityだけを保持して，同時並行的に書かれたデータについてはユーザ定義のマージ関数で最終状態を決定するのだ． (よってLSNやロックのような順序付けの機構は不要だが，causalityのためにvector clockだけは必要)

アプローチはViewとTriggerがあれば実装可能なため，PostgreSQL,Oracle,SQL Server, MySQLでもテーブル定義とトリガの使い方，レプリケーションの設定だけで再現できる？と思われる（ <=> カーネル改造が不要，凄い）．

誤解があるかもしれないので，もう少し読んでみてもいい．面白い． まあ，手元のDBMSでCRDTが表現できたとして，やはりまだ分散システムになじみのない開発者には扱いが難しいように思う・・・が，それはCRDTが現実世界のアナロジーから遠く離れていることが問題であって，この研究の素晴らしさを毀損しない．

2025/04/11

輪読

Frank McSherry, Michael Isard, and Derek G. Murray. 2015. Scalability! but at what cost? In Proceedings of the 15th USENIX conference on Hot Topics in Operating Systems (HOTOS'15). USENIX Association, USA, 14.

スケーラビリティを求めたビッグデータ向けの分散システムは，分散すること，スケールすることの代償に高いオーバヘッドを支払っていることが多い． この論文では，「シングルスレッドの性能に到達するために必要な並列数（ノード数とか）」をCOSTと定義しており，実際のグラフ処理システムなどでCOSTを計測している． システムによってはCOSTがunbound，すなわちどれだけリソースを投下してもシングルスレッドの処理性能に勝てないシステムがあることも明らかになった． ようするに，「小さいデータならクラスタを使うよりラップトップで処理したほうが早いこともあるよね」という話． だから，「よりスケールする」（性能が右肩上がりになる）という，論文のイントロでよく書かれる文言は実は問題を捉えていないよね？と主張している．

この論文は，社会人一年目の配属されたてのとき，右も左もわからない自分を見かねた先輩が手渡してくれた論文で，とても思い出深い． あの時は「スケーラビリティ」という言葉の意味すらよくわかっていなかった（ローカルPCでアプリをビルドするだけの日々で，バックエンドもさくらVPSの1インスタンスで事足りた）が，年を重ねるごとにこの論文の主張の誠実さがわかってくる． それを受けてか，私もよく後輩にオススメする論文だ．

2025/03/04

輪読

https://lamduy-nguyen.github.io/assets/pdf/latency.pdf (opens in a new tab)

Nguyen, L., Alhomssi, A., & Ziegler, T. Moving on From Group Commit: Autonomous Commit Enables High Throughput and Low Latency on NVMe SSDs. VLDB'25 To be appeared.

Group CommitといえばディスクI/Oの最適化テクニックだ． HDDのディスクI/OのIOPSが足りないのと，ランダムI/Oだとシークが発生するのが耐え難いので，シーケンシャルに書けるようにバッファリングして，一回のflushでまとめて書き出しましょう，それまでcommitは遅延しましょう，という発想だった． しかしSSDやNVMe SSDの時代を迎えて，もはや市販品のSSDでもIOPSはHDDの数百倍以上に増大しており，ランダムI/Oの性能も非常に高くなった． したがって，Group Commitには新しい性能上の問題が生まれている... それが「インメモリ上のバッファ管理，具体的にいうとリングバッファにデータを詰めるところの並行データ構造だ」というのがこの論文の論旨． そこの性能改善のためにはある程度ログを分散してwriteして（結果的にgroup commitの当初の形ではなくなっても）良い結果が出るという興味深い洞察もある． この著者そして研究室の論文はすべて面白い．

Group Commitについては思うところがあるので，今度まとめて記事を書きたい．

2025/01/29

輪読

Tejasvi Kashi, Kenneth Salem, Jaemyung Kim, and Khuzaima Daudjee. Eventual Durability. PVLDB, 17(13): 4733 - 4745, 2024. doi:10.14778/3704965.3704979

"Eventual Durability" の二語からなるキャッチーなタイトルの論文． 中身は非常にシンプルで， データベーストランザクションにおける "committed" というtermの意味を分解して， "durable" (従来の意味での commit) と　"lost"に区別している． "lost" はserializability, durabilityの意味ではNGである． つまり，これを読んだトランザクションは将来lostする可能性がある値を読むことになる． これだけだと使い物にならないので，recoverabilityの議論を加えているのが少し面白いと感じたところで， serializabilityとrecoverabilityの両方を保証することで， "lostする値を読むかもしれないけど，そのときは自分もlostするよ（永続化はされないよ）" というインタフェースをユーザに提供することができている． (ただし，その代償として， cascading aborts よしなに cascading losts はする). シナリオの面でも納得感はある． Weak Isolation が許容されるのであれば Weak Durability も許容されてしかるべきかもしれないし．もともとデータベースは precommit とか　group commit の文脈で durable と　commit を分割していたので，それをユーザに明示的に見せることは問題がなさそうだ． 実際， MySQL だとサーバ変数で sync_flush を調整できるわけだし． この論文でも PostgreSQLの synchronous_commit をうまくexploitして実装していて，このモデルがリーズナブルに実装できることを示している．

内容は，アプリケーションユーザに負担を肩代わりさせるだけの話だし，昔からありそうなトピックなので賛否両論あるだろうが，問題の整理とライティングが良い．

2025/01/08

年が明けた．

輪読

Ling Zhang, Matthew Butrovich, Tianyu Li, Andrew Pavlo, Yash Nannapaneni, John Rollinson, Huanchen Zhang, Ambarish Balakumar, Daniel Biales, Ziqi Dong, Emmanuel J. Eppinger, Jordi E. Gonzalez, Wan Shen Lim, Jianqiao Liu, Lin Ma, Prashanth Menon, Soumil Mukherjee, Tanuj Nayak, Amadou Ngom, Dong Niu, Deepayan Patra, Poojita Raj, Stephanie Wang, Wuwen Wang, Yao Yu, William Zhang: Everything is a Transaction: Unifying Logical Concurrency Control and Physical Data Structure Maintenance in Database Management Systems. CIDR 2021 https://www.cidrdb.org/cidr2021/papers/cidr2021_paper06.pdf (opens in a new tab)

DBMSの物理データ構造 (e.g., B-tree) にはtransactional と maintanance で二つの異なる性質のactionが飛んできて，これらを同期・調停するのが大変なのだが， でかいキューを噛ませてtimestamp順に実行されるようにして，すべての（トランザクションであろうがそれ以外の処理であろうが）actionをdeffered actionとして順序づけて実行するようにすればCorrectnessの保証は簡単． 実装も簡単． ordering guaranteeも強く保証でき，かつオンラインDDLやself-driving database のためにも有用なbuilding blocks になるという提案．

任意の複数のシステムについて，一貫性を保った統合が必要とされたとき，キューがあればいいじゃない，という話になるあれをトランザクションの世界で見た，という感じはする． 性能（並列性）を高めるための工夫をしていくとだんだんもとのAPIに戻っていって元の木阿弥になりそうな感もあるが，しかし実装者としてはこれくらいシンプルなアーキテクチャのほうがありがたい．