Miniposts
2024/11/06
二ヶ月空いた．
輪読
Wang, Junchang, and Manos Athanassoulis. "CUBIT: Concurrent Updatable Bitmap Indexing." arXiv preprint arXiv:2410.16929 (2024). https://arxiv.org/abs/2410.16929 (opens in a new tab)
bitmap index というものをほとんど知らなかったが，非常に便利なデータ構造だ． selectivityが高く，cardinalityが低い（「テストの点数が8０点以上だった生徒を取り，1000人中200人を拾う，とか）ようなクエリのときにはtreeよりもscanよりも高速かつ省メモリ，低レイテンシが実現できる． 問題はこのbitmap indexをupdateする際のアプローチがナイーブすぎた（latchを使ったり，そのlatch自体が粗粒度すぎたり，out-of-placeで更新するからメモリ消費が大きかったり）こと． これをOLTP界隈やインデックス界隈ではしばしば使われる log-structured なデータ構造 (update delta, log sequence) に並べてそのログバッファの先頭をCASでアロケートしていくアプローチを採用することによってlock-freeにして，さらには読み出し側でlazyにlogをcompaction/apply/materialize していくことでwait-freeに読み出しも可能，ということを謳っている． 実際に実験ではduckdbに実装して，大幅なパフォーマンス向上と省メモリ化をもたらしている．
総じて，OLTPの視点から見るとそれほど目新しく無いアプローチだが，bitmap index に適用するとこれほど性能が向上するのだなあという感銘があった． LSMの偉大さを改めて理解する．コロンブスの卵割り行脚というか，枯れた技術の水平思考というか．
2024/08/09
Yu Liang, Song Liu, Hong Hu: Detecting Logical Bugs of DBMS with Coverage-based Guidance. USENIX Security Symposium 2022: 4309-4326
自動テストの方式として fuzzing / fuzzer というものがある． これは，既存のテストケースの一部をランダム変異させて実行し， 新たなバグを見つけるとかカバレッジが上がったとかしたらキューに詰めて， またキューからpopするときにランダム変異をしていく・・・ということを繰り返す手法だ． メモリエラーやassertion failure を発見するのに役立つ． この論文では，この fuzzing をDBMSの論理バグ検出に応用している． 論理バグというのはクエリがvalidでないと発見できないので， 「メモリエラーやassertion failureは起きないけど，間違った結果を返しそうなクエリ」を生成する必要があって，そのためにはランダム変異では質が足りない． そこをなんとかするためのあれこれのテクニックが提案されている．
この論文では，結果として， SQLite/MySQL/PostgreSQLにツール (SQLRight) を運用したところ， 18件の論理バグを発見したことが報告されている． PostgreSQLのバグは0件だった． ちなみに，ほとんどの論理バグは NoRec というoracle（クエリ変異のためのヒント）を使ったときに検出されており，NoRecがとても強力なoracleであることがわかる．
NoRecは単体で論文になっている． https://arxiv.org/abs/2007.08292 (opens in a new tab)
ざっくり説明すると，
SELECT * FROM t0 WHERE φ;というクエリを
SELECT (φ = TRUE) FROM t0;に変換すると，オプティマイザを無効化しつつ等価なクエリを生成できる，というシンプルな話．この二つのクエリの実行結果を見比べれば，オプティマイザのバグが検出できる．
面白い！
2024/07/26
朝，輪読会．
Peter Kraft, Qian Li, Xinjing Zhou, Peter Bailis, Michael Stonebraker, Xiangyao Yu, Matei Zaharia: Epoxy: ACID Transactions Across Diverse Data Stores. Proc. VLDB Endow. 16(11): 2742-2754 (2023) https://petereliaskraft.net/res/p2732-kraft.pdf (opens in a new tab)
複数のデータストアをトランザクショナルに操作したいという欲求に応えるデータストア（というかアーキテクチャ），Epoxyの提案． たとえば実験では PostgreSQL, MySQL, Elasticsearch, MongoDB, GCS という異なるデータストアをまとめてACIDに扱えることを示している．オーバヘッドもまあ許容範囲？ すごく目を細めてみるとラムダアーキテクチャとかカッパアーキテクチャに見えてこなくもない． アイデアも実装もスマートだと思うけど，結局これ (Epoxy) をバイパスして直接各データストアローカルで走る野良トランザクションが湧いてきて潜在的anomalyには誰も気づかないところまで幻視した．
2024/07/10
朝，輪読会．
Yacine Taleb, Kevin McGehee, Nan Yan, Shawn Wang, Stefan C. Müller, Allen Samuels: Amazon MemoryDB: A Fast and Durable Memory-First Cloud Database. SIGMOD Conference Companion 2024: 309-320 https://www.amazon.science/publications/amazon-memorydb-a-fast-and-durable-memory-first-cloud-database (opens in a new tab)
AWSによるAmazon MemoryDBのアーキテクチャ紹介論文 (Industrial track). 一言でいえば，Auroraの知見を活用して同じ設計をRedisに水平展開したもの， Redisをマネージドサービスにしたのみならず，S3にログとスナップショットを置いて永続性を保証したり，strong consistencyを保証したり，といった工夫がされている． リーダー選出アルゴリズムや障害検出アルゴリズムも独自のものを作っているようだが，詳述はされていなかった．
これだけすっきりと水平展開できるAuroraのアプローチは金の卵だったなと改めて思う次第．
2024/05/15
朝，輪読会．
Are Your Epochs Too Epic? Batch Free Can Be Harmful
Daewoo Kim, Trevor Brown, and Ajay Singh. 2024. Are Your Epochs Too Epic? Batch Free Can Be Harmful. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP '24). Association for Computing Machinery, New York, NY, USA, 30–41. https://doi.org/10.1145/3627535.3638491 (opens in a new tab)
以前から作っている LineairDB (https://github.com/LineairDB/LineairDB (opens in a new tab)) は（なるべく）すべてのデータ構造とアルゴリズムにEpoch-Based Reclamation (EBR)を採用しているソフトウェアなのだが，昔これのメモリアロケータを自作していた． EBRをベースにthread local cache & object poolingをする簡単な実装だったのだが，なぜか (高価なmalloc/freeの回数を大幅に減らせたにも関わらず）jemallocにしてコア数多めのマシンで動かすとほんのり遅くなる・・・という実験結果を目にすることがあった． この論文の話がその答えと同じで，「メモリアロケータはローカルでキャッシュしてるからあまり素人考えせずにfreeを投げてしまっていい」というオチ． もともとmalloc/freeの回数を減らすために各ソフトウェアが努力してきたことが，メモリアロケータの最適化によって裏目に出た，という年月を感じさせるトピックだった．
2024/05/10
朝,輪読会．
https://www.vldb.org/pvldb/vol15/p1911-lee.pdf (opens in a new tab)
Mijin An, Soojun Im, Dawoon Jung, and Sang-Won Lee. 2022. Your read is our priority in flash storage. Proc. VLDB Endow. 15, 9 (May 2022), 1911–1923. https://doi.org/10.14778/3538598.3538612 (opens in a new tab)
SSDにreadとwriteをparallelに実行できるI/Oインタフェースを追加するとbuffer poolのpage replacement時にread stallがなくなるよねという提案． 面白い． 「バッファプールからdirty pageをevictしないと新しいpageを読み出しできない」という状況は(background writerが適切に動作している限り)稀だと思われるが，実はそうではなくて，SSDほど高速なストレージだとよく起こる話らしい．
こういうI/OインタフェースがあったらDBからしたら確かに凄く嬉しい．しかし，他のソフトウェアでこのインタフェースを欲しがるものってあるのだろうか？ファイルシステムも欲しそうかな？
2024/04/03
朝，輪読会．
https://www.cs.princeton.edu/~mfreed/docs/cuckoo-eurosys14.pdf (opens in a new tab)
Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman: Algorithmic improvements for fast concurrent Cuckoo hashing. EuroSys 2014: 27:1-27:14
Cuckoo Hashing (opens in a new tab) の最適化をおこなった論文． Algorithmic... と謳っているが実際はHTMの適用が大きく貢献している． Cuckoo Hashing はすごく好きで，自前で実装したこともあるのだが，不勉強なもので実際に使われている例を知らない．insertのパフォーマンスがピーキーなのと，thread-safeにする際の対応がやはり難しいのだろう． このチームの論文から libcuckoo (opens in a new tab) が生まれているのだが，このリポジトリの実装はこの論文とは全然違っていて，理想と現実を感じさせる． （具体的には，cuckoo path をoptimisticに計算することが可変長のkey/valueだと困難なので，lockを使って計算していて，それでこの論文の性能利得がだいぶ消されている）
2024/03/08
朝，輪読会．
https://www.usenix.org/conference/osdi23/presentation/gupta (opens in a new tab)
Vishal Gupta, Kumar Kartikeya Dwivedi, Yugesh Kothari, Yueyang Pan, Diyu Zhou, Sanidhya Kashyap: Ship your Critical Section, Not Your Data: Enabling Transparent Delegation with TCLOCKS. OSDI 2023: 1-16
Lock delegationはロックホルダーに自分のクリティカルセクションを代行してもらうロック実装のアプローチで，キャッシュラインの監視や通知にかかるオーバヘッドとデータのコピーにかかるオーバヘッドが削減されるため性能上良いとされている． しかし，「自分のクリティカルセクションを代行してもらう」というのを実装しようとするとfunctorのようなAPIになるので，既存の lock/unlock でブロックを囲うやり方から透過的に移行することができない，という問題があった．
この論文では transparent delegation lock を提案している． アプローチとしては，レジスタとスタックを専用の領域に退避して，プログラムカウンタをロックホルダーに渡す，というもの． LevelDBをコード改変なしでかなり高速化できていて，なかなかよいアプローチに見える． 一方で，カーネルに適用しようとすると課題が多いということも書いてあった． current マクロが噛み合わないらしい．
個人的には，グリーンスレッドを提供している言語処理系なら組み込みのロックをこれに変更することもできなくはないのかな？と思った．そんな並行性が必要な処理を書くな，というツッコミは，正しいと思います．
2024/03/06
最近， Transactional Information Systems を輪読しており， Recovery algorithmsについて理論から勉強している． これは自分にしかわからないメモ．
この本では，「ログはwriteの情報のみを含めばよい」ということが書いてある． これは一般的には広く受け入れられている考え方だと思うが，しかし，自分はそれは議論を限定しすぎていると思う． total order をもつ write steps のsequence をログにするのは， too muchだ． version orderを一意に定めたいという欲求があるからであり，必要十分条件ではないのではないだろうか？
version order が一意に定まっていれば，リカバリ前とリカバリ後でstateが同じとなることが保証される． これは何者にも変え難いメリットではある． ただ，リカバリログの必要十分条件を定義しようとしたとき，total orderは不要として，複数のありうるorderからリカバリ時に選択するという考え方もできると思う． とはいえ，そうした場合には，ヒストリの正しさを保証するためにreadのログも要求することになるかもしれない．う〜ん・・・．
2024/02/21
朝，輪読会．
Shuai An and Yang Cao. 2022. Making Cache Monotonic and Consistent. Proc. VLDB Endow. 16, 4 (December 2022), 891–904. https://doi.org/10.14778/3574245.3574271 (opens in a new tab)
Cache Serializability に関する論文はいくつか出ているが，これもその一つ． 例えばMySQLのキャッシュとしてRedisを使ったときに，Redisから読む値が必ず最新のものであることを保証したい場合がある．そういう性質を "monotonic and consistent" と称して定義して，形式的に踏み込んで議論して，システムの提案と評価までやっている． Eager/Lazyという二つの戦略が紹介されており，Eager，つまり「あらゆるreadが常に，すぐに最新の値を返せる」ようなキャッシュはNP-Hardであることが説明されている．結構意義深い話のようにも思う．
2024/02/07
朝，輪読会．
Andreia Correia, Pascal Felber, and Pedro Ramalhete. 2020. Persistent memory and the rise of universal constructions. In Proceedings of the Fifteenth European Conference on Computer Systems (EuroSys '20). Association for Computing Machinery, New York, NY, USA, Article 5, 1–15. https://doi.org/10.1145/3342195.3387515 (opens in a new tab)
30分では到底理解が追いつかないほど事前知識が不足していた． それもまた面白かった． たとえば，「wait-free を実現するためにはNスレッドに対して2Nのレプリカが必要」ということが当然のごとく前提として語られているのだが，その意味すら私にはわからなかった． lock-freeならたくさん実装したことあるんだけどね・・・
この論文はもともと Concurrency Freaksの記事 (opens in a new tab) で見つけたものだった．この記事はなかなかユーモラスかつ同意できる論旨で良かった． たしかに，全ての基盤システムがwait-freeかつlinearizableかつserializableであるべきだよなぁとは常々思う．
2024/01/30
朝，輪読会．
Kaisong Huang, Tianzheng Wang, Qingqing Zhou, and Qingzhong Meng. 2023. The Art of Latency Hiding in Modern Database Engines. Proc. VLDB Endow. 17, 3 (November 2023), 577–590. https://doi.org/10.14778/3632093.3632117 (opens in a new tab)
大容量メモリ上で動き，CPU使用効率を高めるためにトランザクションとコルーチンを一体化させたシングルノードのデータベースCoroBaseの改善． CoroBaseではメモリI/Oのストールが全CPU時間の50%に達することがあり，これを改善するために効率的なスケジューリングを実装している．
問題設定（ネットワークを考慮しないけど無限にリクエストがパイプライン化できて，しかもトランザクショナルで，シングルノードで，2ソケット~4ソケットCPUくらいのマシンで，SQLはバイパスしてC++で直接クエリが実行される）が全くリアルと感じられなかったが，論文のwritingはうまいし納得感もある．
2024/01/26
朝，輪読会．
P Liu, S Weng, K Li, L Ni, C Yang*, R Zhang, W Qian, D Qiao. Leopard: a general test suite for isolation level verification. CIDR, 2024: 1-7. https://www.cidrdb.org/cidr2024/papers/p44-liu.pdf (opens in a new tab)
分離レベルの違反（つまりAnomaly）をブラックボックスで，オンラインでテストできるという夢のような技術！の論文． なんとすでに18ものデータベースに既に対応しており，しかし4つの検証アルゴリズムで事足りたと言うのが腕前の高さを感じる． GUIのインタフェースやビジュアライザもついていて，既に起業でもできそうな雰囲気を感じる（需要があるかはわからないが）． しかし，Exampleとして示されているユースケースが，「分離レベル違反ではないがドキュメントに書かれている挙動と違う挙動だったのを検出した」というケースになっているのが一抹の不安を感じた．それってブラックボックスだとどうすればわかるのでしょう？
2024/01/10
朝，輪読会．
Paras Jain, Peter Kraft, Conor Power, Tathagata Das, Ion Stoica, Matei Zaharia: Analyzing and Comparing Lakehouse Storage Systems. https://www.cidrdb.org/cidr2023/papers/p92-jain.pdf (opens in a new tab)
データウェアハウス + データレイクで Lakehouse Storage Systems というものが普及している． 実態は S3のような分散ストレージに配置したParquet / ORC のファイルを高機能（ACID/Audit/Indexなど）でアクセスするためのラッパとして使われるソフトウェアで，zookeeperとかDynamoDBを内部コンポーネントとして実装されているようだ． ACIDトランザクションを実装する方法が軒並みOCC/MVCCで，かつwriterを一方的にabortさせる方式が取られていることが面白かった． OCCといえばreader aborts...と考えてしまいがちだが，データウェアハウス的な用途を考えるとwriter aborts のほうが望まれているということなのだろう． このへんの感覚が面白かった．