Miniposts in 2023

IndexAboutMinipostsPosts

2023/12/27

朝，輪読会．

Saeed Kargar and Faisal Nawab. 2023. Hamming Tree: The Case for Energy-Aware Indexing for NVMs. Proc. ACM Manag. Data 1, 2, Article 182 (June 2023), 27 pages. https://doi.org/10.1145/3589327 (opens in a new tab)

バイトアドレッサブルなデバイス（ここではNVM）でエネルギー効率を高めるために，書き込みを最適化する論文． 既存研究ではWrite Amplification を削減したりしていたが，ビット反転の回数を減らすこと（つまり，書かずに済むようにすること）が重要だそうだ． この論文では，索引としてHamming-Tree というものを用意し，空きメモリ位置と使用済みメモリ位置，さらにビットの状態を管理させる．空きメモリへの書き込みを行う際には，ハミング距離が最小になる位置を選択してくれる．

これが多分，今年の最後の更新．

2023/12/21

MySQLには os_event_t という型がある． これを使うと条件変数，STLでいうところの std::condition_variable が実現できる． これはInnoDB内部で定義・実装されたもので，使いこなすとPSI (パフォーマンススキーマ)上で統計を確認できるようになって便利だ．

ところが，MySQLにはこれとは別に mysql_cond_t という型もあり，こちらも使われている． これはInnoDBではなくMySQLのレイヤで実装されているので，あらゆるコード中で使うことができる． MariaDBのコード中でも os_event_t ではなくこれを使うよう置き換える議論がされている (opens in a new tab) のをみた．

で，このような構造は他にもある (opens in a new tab)． thread, mutexなんかはInnoDBとMySQLでどちらもラッパーを提供していて，どちらもPSIを使うことができる． 正直，違いがよくわからない． また調べてみる．

一周回って， std::mutex　をラップした， PSI相当の情報を管理できるクラスをSTLが提供してくれて，みんなそれを使うっていうのでどうですかね・・・？

2023/12/20

所用があって Database Engineering Meetup #1 (opens in a new tab) 参加できなかった． かなしい．

だが，公開されている資料はどれもとっても面白かった． しかし，データベースと呼ばれる技術領域はあまりにも広大で，知らないことが多い． いつまで経っても「少しわかったな」という気分にならない． ダニングクルーガー効果すら得ることはなく，「浅瀬でパチャパチャ遊んでるな俺」という気分しか持てないのだが，もしかすると多くの人がそんな感じなのかもしれない．

まあ，ダラダラ仕事してて学びが足りないだけなんだが？

2023/12/16

アドベントカレンダーを書いた．数年来思っていることを言語化できてすっきりしたが， 同時にこの程度の考えはすでに研究として精力的に取り組まれているのだなと思うと，自分の手の遅さと目先の利かなさに失望するよね．

2023/12/06

朝，輪読会．（輪読会しか書くことがないのが悲しい）

Differentially Testing Database Transactions for Fun and Profit https://dl.acm.org/doi/abs/10.1145/3551349.3556924 (opens in a new tab)

同じデータベースを生成して同じクエリを流したときの実行結果の差分から，Transaction BugsとCompatibility issues を調査する論文． MySQL互換DBMS（MySQL,MariaDB,TiDB)に対して調査して，とくにTiDBが互換性はあっても状態遷移やSELECT文の観測結果が異なることを示した．

こういうブラックボックステストの中でもシンプルなアプローチは好ましいと思う．実用化に近い． 強いて言うなら，マイグレーションのためのツールではなく日常的に使える運用のためのツールが欲しい．つまり，理想的な実行結果を生成して，そことの差分を見るほうが好み．（もちろんそういう研究もすでにある．）

2023/11/24

Time flies.

朝，論文輪読会．

Socrates: The New SQL Server in the Cloud https://www.microsoft.com/en-us/research/uploads/prod/2019/05/socrates.pdf (opens in a new tab)

Cloud-native database by Microsoft. HekatonなどこれまでのSQL Server開発の知見を活かしている． Amazon Aurora の論文を読んだことがあるとスムーズに読めた． 一番面白いと思ったのは landing zone という概念． Shared storageへのflushはやはりレイテンシが気になるのか，可能な限り早く返せるようにしようという工夫があった．

2023/11/08

若干忙しい． 論文．

Detecting Isolation Bugs via Transaction Oracle Construction

pdf: http://www.tcse.cn/~wsdou/papers/2023-icse-troc.pdf (opens in a new tab)

code: https://github.com/criszy/Troc (opens in a new tab)

Isolation bugs を検出するツールの研究．ランダムにテーブル定義とクエリを生成し，トランザクションを各ステートメント(SQL)に分割して，並行実行した際の結果と実際の結果を比較することで分離レベルバグを検出する． なかなか面白かった．ブラックボックスでやることに限界を感じる内容だったのもあるし，開発者に親しみのあるアプローチでもあった（この分野は，NP-Completeと真っ向勝負するタイプの研究をよく見る）．

2023/10/26

「Googleのソフトウェアエンジニアリング」を輪読した．今日は2章を読んだ．

Richard Hammingによる講演 ``You and Your Research'' (opens in a new tab) が紹介されている．読んでみると，とても面白かった．

``Look, if you adopt the present method and do what you can do single-handedly, you can go just that far and no farther than you can do single-handedly. If you ! will learn to work with the system, you can go as far as the system will support you.''

``Look Ed, you've got to give your researchers a machine. If you give them a great big machine, we'll be back in the same trouble we were before, so busy keeping it going we can't think. Give them the smallest machine you can because they are very able people. They will learn how to do things on a small machine instead of mass computing.'' As far as I'm concerned, that's how UNIX arose. We gave them a moderately small machine and they decided to make it do great things. They had to come up with a system to do it on. It is called UNIX!

Public talks are necessary; private talks are necessary; written papers are necessary. But I am inclined to believe that, in the long-haul, books which leave out what's not essential are more important than books which tell you everything because you don't want to know everything. I don't want to know that much about penguins is the usual reply. You just want to know the essence.

すばらしいスピーチなので，引用は尽きることがない．

しかし，ここ一年弱ほど，平日は5日間でおおよそ4.5の勉強会に参加している． どれも小規模なもので，参加する実利が大きい．資料をあまり用意せず，皆が顔見知りになり，発言を自由にさしはさめる．そして，欠席も気軽だ． こういう小さい負荷を日々積み重ねることはとても良い習慣になっていると感じる．プログラミングについてもこうありたいものだが．

2023/10/20

朝，論文輪読会． とても面白い論文を読んだ．

pdf: https://www.cidrdb.org/cidr2023/papers/p30-cheng.pdf (opens in a new tab)

slide: https://www.cidrdb.org/cidr2023/slides/p30-cheng-slides.pdf (opens in a new tab)

研究者は誰もが SERIALIZABLE を前提に議論をし，研究をしているが，現場ではIsolation Levelがデフォルトから変更されることはまれである（SIGMOD'17 のKeynoteでAndy Pavloがそのようなサーベイをしていた (opens in a new tab)のを思い出す．）

では，READ COMMITTED ではどのようなバグ（anomaly)が発生するのか？開発者はどう現実に対処しているのか？これから研究者はどの方向を向いて仕事をするべきか？というのを調べたのがこの論文だ．このテーマ自体は古くからある．同好の士のためにいくつかリンクを並べておく:

この論文では，SERIALIZABLEを高速にしても解決できない問題があること，SERIALIZABLEにした結果ロックを使うことになるなら開発者はそれを好まないこと，とはいえBug detection より Bug prevention のほうが望まれていることなどが述べられていた． しかし調査手法は手作業である．大変だ．Concurrency Bug を調査して一般化する，という試み自体も自動化できればより進展するのかもしれない．

2023/10/13

朝，論文輪読会． とても面白い論文を読んだ．

https://s3fifo.com/ (opens in a new tab) https://blog.jasony.me/system/cache/2023/08/01/s3fifo (opens in a new tab) https://dl.acm.org/doi/10.1145/3600006.3613147 (opens in a new tab)

ブログのほうは，刺激的なセンテンスが多くわかりやすい．

I believe modern eviction algorithms should be designed with FIFO queues.

we find that shorter request sequences (fewer objects) often have higher one-hit-wonder ratios.

三つの(lock-free) FIFO queue でcache eviction algorithmを設計するというもので，アルゴリズムもかなりシンプル (ブログにgifがあり，それだけでほぼ理解できる)． 多くのシステムをこれに置き換えても（工数の面でも性能の面でも）reasonableだろうなと思わせる魅力があった．

2023/10/03

ScaleDBを読み進めた． Scrapbox (opens in a new tab)にこの論文の小ネタも追加した． InsertされてからScanされるまでの時間を計測するという発想がなかった．面白い．

2023/09/29

朝，論文輪読会． とても面白い論文を読んだ． ScaleDB: A Scalable, Asynchronous In-Memory Database (opens in a new tab)

Syed Akbar Mehdi, Deukyeon Hwang, Simon Peter, Lorenzo Alvisi: ScaleDB: A Scalable, Asynchronous In-Memory Database. 361-376, OSDI'23

インデックスへのInsert/DeleteとConcurrency Control，つまり排他制御がインメモリDBの性能ボトルネックになることは，（研究レベルの簡単なソフトウェアで，という前提をおけば）誰もが肌感で知っていることだと思う． この論文は，これら二つの役割を統合した一つのインデックス構造を提案し，並列性を高めている． 具体的には，インデックスへの反映をハッシュテーブルにバッファリングし，エポックごとに適用することで並行処理をやりやすくしていたり，そのハッシュテーブルで直接point accessを返したり，親近感の湧くノウハウが多く含まれている．

というか，私自身もこれに似た研究をしていた． LineairDBにもこれに近いインデックスを採用している．

2023/09/21

Safe Retry (opens in a new tab) についてページを作った． 結構面白い性質だと思うけど， Fairness/Starvation-free ほど直感的にありがたみを感じる性質ではない．

2023/09/15

朝，論文輪読会．

Haonan Lu, Siddhartha Sen, and Wyatt Lloyd. 2020. Performance-optimal read-only transactions. In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI'20). USENIX Association, USA, Article 19, 333–349.

の Extended version. https://www.cs.princeton.edu/techreports/2020/005.pdf (opens in a new tab)

N+O+C を performance optimal read-only transactions と定義している．

NOC: One round of Non-blocking communication with a Constant amount of metadata

これに Strict serializabilityを加えてNOCS. このNOCS is impossible を定理立てて証明しているのが個人的見どころ． 証明の中では C がfully exploitされていて，metadata が constant ではN+O+Sが不可能であることを帰納法で証明している． 具体的には，NOCSではメタデータがサーバ数に比例して増大する． この論文ではその解決としてNOCを維持してSを一部妥協したPORTというデザインを提案している．

研究的には，Sをあきらめるならよくあるsnapshot readsでもよいわけだから（この論文でもそれに言及している），Sを諦めずefficientに実装する方法を考えることがテクニカルだと思う． でも，実践的には，freshnessが保障されないことをアプリケーションユーザに意識させるほうがうまくいくしスケールするだろうとも思う．

2023/09/14

はじめる．

© nikezono.devRSS