Miniposts
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 のほうが望まれているということなのだろう． このへんの感覚が面白かった．