目次
書いた背景
ChatGPTで論文読んでまとめてもらうやつやりたいけど読みたいものがない。
— RyuichiWatanabe@gurasan (@ryuichi_1208) 2023年11月14日
って感じでちょうどよさそうな題材があったから色々調べてみました。
Dragonflyとは
Dragonfly は最新のアプリケーションワークロードのために構築されたインメモリデータストアでRedis や Memcached の API と互換性があります。実装言語はC++となっています。
DragonflyはRedisの25倍のスループットで昨年話題になっていました。25倍！すごい！となったと同時にこれ実際どんな技術要素で成り立っているんだろうと気になったので調べてみたメモです。ちなみに私自身はデータベースのパフォーマンス分野については素人なので間違ってる内容がありそうなので見つけた方はコメントで教えていただけると。
あと、READMEの最後に書いてある
And finally, Our mission is to build a well-designed, ultra-fast, cost-efficient in-memory datastore for cloud workloads that takes advantage of the latest hardware advancements. We intend to address the pain points of current solutions while preserving their product APIs and propositions.
がとてもかっこよくて好きです。使命を持ってソフトウェアを開発していく。いいですね〜。
スループット25倍の話
話題になったのは1以上前の↑の記事。スループットのグラフを見ると確かにGET/SETなどでもRedisとものすごい差をつけています。さすがはRedisやmemcachedよりも大幅な高速化と高効率化を目指しているだけあってすごい数値です。
ここでRedisはシングルスレッドでAtomic性を保証してきたアーキテクチャなのでマルチスレッドで動くと行っているDragonflyとは検証方法がフェアじゃないという意見もあるとようでした。これにはRedisも公式で対抗(?)した記事を出していてやるならRedisのCluster構成をしてコア数をしっかり使い切るようといった方法でベンチマークを取る必要があることが書かれていて実際そのような計測ではRedisに軍配が上がるような数値も出ていたようです。
計測方法次第ではRedisと性能差はそこまでないってこと？
これはYesと言えそうです。ただ今回私がロマンを感じたのは性能というよりかは13年前にRedisがAtomic性を保証するために取ったシングルスレッドというアーキテクチャを現代で再考したらどうなるかの部分です。マルチスレッドの DragonflyがどのようにしてRedisと同等のAtomic性を保っているのかを見ていきます。
どうやって性能を出しているのか
READMEには以下のような記述があります。
To provide atomicity guarantees for multi-key operations, we use the advancements from recent academic research. We chose the paper "VLL: a lock manager redesign for main memory database systems” to develop the transactional framework for Dragonfly. The choice of shared-nothing architecture and VLL allowed us to compose atomic multi-key operations without using mutexes or spinlocks. This was a major milestone for our PoC and its performance stood out from other commercial and open-source solutions.
シェアードナッシングアーキテクチャと VLL の選択により、ミューテックスやスピンロックを使用せずにアトミックなマルチキー操作を構成するといったもののようです。シェアードナッシングアーキテクチャは、分散コンピューティングやデータベース設計で使用される一種のアーキテクチャで、主な特徴は、各ノードが自身のメモリとストレージリソースを持ち、他のノードと共有しないという点です。これにより、データの分散と拡張性が向上し、多くの並行処理が可能になります。データを共有するようなアーキテクチャをシェアードエブリシングアーキテクチャと言います(Amazon Aurora などは Shared-everthingのはず)
マルチスレッドでスレッドごとにデータを持つ場合にシェアードナッシングだと複数キーに対する操作がAtomicに行えなくなります。そこで出てくるのが論文「"VLL: a lock manager redesign for main memory database systems"」とのことです。せっかくなのでChatGPTにAbstの部分を要約してもらいました。
ロックマネージャーは、悲観的な同時実行制御を使用するデータベースシステムにおいてますますボトルネックになりつつあります。本論文では、主記憶データベースシステム用の悲観的な同時実行制御の代替アプローチとして、Very Lightweight Locking（VLL）を紹介します。VLLは、従来のロックマネージャー操作に関連するほぼすべてのオーバーヘッドを排除します。また、高競合ワークロード下で高いトランザクションスループットを達成するために、システムがVLLを実装するためにSelective Contention Analysis（SCA）プロトコルを提案します。これらのプロトコルは、従来のシングルマシンのマルチコアデータベースサーバー環境と、データが多数のコモディティマシンにわたってパーティション分割された分散データベースの両方で実装されています。さらに、VLLとSCAを拡張して範囲ロックを可能にする方法を示します。実験により、VLLはロッキングのオーバーヘッドを大幅に削減し、両方の設定においてトランザクショナルスループットを増加させることが示されました。
論文であげられているのはロックマネージャーのオーバーヘッドを効果的に減らし、トランザクションのスループットを向上させるための技術であるようです。VLLを3行でまとめると
- VLL（Very Lightweight Locking）は、主記憶データベースシステムにおけるロックマネージャーのオーバーヘッドを大幅に削減するアプローチ
- ロック情報をデータと同じメモリ位置に配置し、トランザクションが必要なすべてのロックを一度に要求することにより、効率化を実現する
- Selective Contention Analysis（SCA）を通じて高競合環境下でのトランザクショナルスループットを向上させる
ロックマネージャーとは
ロックマネージャーのオーバーヘッドを減らすというのは何となくわかったのですがロックマネージャーとは何でしょう？となったのでChatGPTに聞いてみました。ロックマネージャーは、データベースシステムや他のマルチユーザー環境で、データの整合性と一貫性を維持するために使用されるコンポーネントです。その主な役割は、複数のトランザクションやプロセスがデータベース内のデータに同時にアクセスする際の競合を管理し、制御することです。
以下のような役割があるとのこと。これを中央集権的に管理することは確かにオーバーヘッドが大きくなりそうとなりそうでDragonflyが挙げていた課題にもとても納得が行きました。
- ロックの管理: ロックマネージャーは、データ項目へのアクセスを制御するためにロックを提供します。これには排他ロック（他のトランザクションが同時にその項目にアクセスできないようにする）や共有ロック（読み取り専用アクセスを許可するが、書き込みは排他的に制御する）が含まれます。
- デッドロックの検出と解決: ロックマネージャーは、複数のトランザクションがお互いに待っている状態（デッドロック）を検出し、それを解決するメカニズムを提供します。これは通常、デッドロック検出アルゴリズムやタイムアウトによって行われます。
- ロックの要求と解放: トランザクションがデータ項目に対するロックを要求すると、ロックマネージャーはその要求を処理し、適切なロックを割り当てます。トランザクションが完了した後、ロックは解放され、他のトランザクションがアクセスできるようになります。
- ロックのキュー管理: 同時に複数のトランザクションが同じデータ項目にアクセスしようとする場合、ロックマネージャーはこれらの要求をキューに入れ、順番に処理します。
- 一貫性の維持: ロックマネージャーは、データベースの一貫性を維持するために、トランザクションがデータベースのルールと制約を遵守することを保証します。
- パフォーマンスの最適化: ロックマネージャーは、パフォーマンスを最適化するために、ロックの粒度（大きなデータセットに対するロックか、小さな項目に対するロックか）やロック戦略を選択します。
VLLの実装をGoで書いてもらった
論文にもサンプル実装がありますが擬似言語っぽくて私にはわかりにくかったのでGoで書き直してもらいました。マルチスレッド対応、デッドロックの処理、分散環境でのデータ同期など、より複雑な機能が必要になるがこれくらいならわかりやすくて良いです。トランザクションは必要なすべてのロックを一度に要求します。ロックが利用可能な場合、トランザクションは処理を続けます。利用可能でない場合は、取得したすべてのロックを解放し、トランザクションは失敗するようになっています。
package main import ( "fmt" "sync" ) type Record struct { Data string Cx int // Exclusive lock count Cs int // Shared lock count } type Transaction struct { LockedRecords []*Record } func (t *Transaction) RequestLock(record *Record, exclusive bool) bool { if exclusive { if record.Cs == 0 && record.Cx == 0 { record.Cx++ t.LockedRecords = append(t.LockedRecords, record) return true } } else { if record.Cx == 0 { record.Cs++ t.LockedRecords = append(t.LockedRecords, record) return true } } return false } func (t *Transaction) ReleaseLocks() { for _, record := range t.LockedRecords { if record.Cx > 0 { record.Cx-- } else if record.Cs > 0 { record.Cs-- } } t.LockedRecords = nil } // 与えられたTransactionオブジェクトが操作を行うために必要なロックを取得しようと試み、そのプロセスが成功したかどうかを判断する func ProcessTransaction(transaction *Transaction, records []*Record) bool { for _, record := range records { if !transaction.RequestLock(record, true) { transaction.ReleaseLocks() return false // Lock acquisition failed } } // Perform transaction operations // ... transaction.ReleaseLocks() return true } func main() { databaseRecords := []*Record{{Data: "data1"}, {Data: "data2"}} transaction := &Transaction{} success := ProcessTransaction(transaction, databaseRecords) fmt.Println("Transaction successful:", success) }
まとめ/感想
Dragonflyは、現代のソフトウェア設計における多くの最新技術と研究の成果を統合して実装されたシステムです。これには、効率的なカーネル機能、進歩したキャッシュアルゴリズム、そして最新のトランザクション処理の研究が含まれます。普段深く考えずに使っているテクノロジーが今も進化し続けているというのはとてもロマンを感じで今回記事を書いてみてとても楽しかったです。
今年の初めくらいにTiDBに入門した時は論文を読むのはハードルが高くて手が出なかったのですがChatGPTと一緒に読むことでだいぶ楽に読むことができました。「概要を書いて」や「⚪︎⚪︎」はどういう意味？や実装を他言語で書き換えてもらったりして一人で読むとしたらめっちゃ時間がかかりそうな部分も時短できてよかったです。
