先週開催されたVLDB(Very Large Data Base)というDatabase分野のトップカンファレンスで松信さんがFirst authorの論文 MyRocks: LSM-Tree Database Storage Engine Serving Facebook's Social Graph が発表され、Best Industrial Paper Awardを受賞されました。
↑ VLDB 2020 Awards - VLDB2020 Tokyoのスクショ
特にTwitterやブログ等で書いている人がいないようなので、この内容を紹介します。
VLDBはDatabase分野ではトップ中のトップカンファレンスで、新規のアーキテクチャやアルゴリズムが掲載されるものだと思っていました。
なので、VLDBにMyRocks論文が掲載されたと知って正直驚きましたが、内容を読んでみると松信さんを始め、Facebookエンジニアの（技術的なレベルの高さの）異常さが見れて、こういった現実世界における最先端のDB開発・運用手法が掲載されることも重要だなと、納得しました。
VLDBの論文は公開されているので、詳細はそちらを参照してください。
新規のアルゴリズムをゴリゴリ証明しつつ提案する、といった内容ではないので、DB分野の論文としてはかなり読みやすいと思いました。
特に4.4節 "Actual Migration"からの内容は実運用の緊迫感が感じ取れ、その後のまとめもメッセージ性が高いので、NHKのプロフェッショナル 仕事のなんちゃらみたいな番組にしてほしいなあと思いましたw
3行に要約
- FacebookのメインデータであるUser Database(UDB)をMySQLのInnoDBストレージエンジンから、自社で開発したLSM-treeベース(RocksDB)のMyRocksストレージエンジンに移行したことでストレージ容量を約60%削減
- B+ Treeベースのストレージエンジン(InnoDB)からLSM Treeベース(MyRocks)に移行するために課題となった最適化を紹介
- 2016年に最初のMyRocksのデプロイを行い2017年にマイグレーションを完了、さらにFacebook MessangerのHBaseもMyRocksに移行(NoSQL->RDBMSへの事例)
全体の章立て
- Abstract
- 1章: Introduction
- 2章: 背景と目的
- 3章: MyRocks, RocksDBの開発について
- 設計と目的
- パフォーマンス課題と解決手法
- 4章: プロダクションでのマイグレーション
- 5章: マイグレーションの結果
- 6章: Lesson Learned
- 7章: 関連プロダクト
- 8章: 結論と今後の課題
- 9章: 謝辞
ここでは以下の項目に絞って簡単に内容をまとめることにします。
- MyRocks開発の目的
- MyRocks, RocksDBへの最適化
- マイグレーションプロセス
- 移行によるパフォーマンス改善
- 結論と今後の課題
実際にはFacebookの地理(Region)分散されたMySQLアーキテクチャの仕組みやRocksDBのアーキテクチャ、マイグレーションシステムの概要などについても説明されています。ここで省いている内容や図表についてはこの論文へのリンクから原文を読めますので、そちらを参照してください
MyRocks開発の目的
- Facebookのsocial activity(likeやshare, commentなど)のメインデータであるUser DB(UDB)は数十ペタバイトになり、MySQLのInnoDBで管理されていた
- InnoDBはB+ treeをベースとしていて、Write amplificationとディスクスペース効率の悪さを改善する必要があった
- これらを解決するのに適したLSM TreeベースのDBMSへの移行を検討したが、UDBは様々なアプリケーションから利用されていて、DBMSを変えることは現実的ではなかった
- そこでFacebookで開発しているRocksDBをストレージとして利用するMyRocksストレージエンジンを開発することでクライアントへの影響がほとんどないままデータを効率的に利用することを目指す
- ディスクサイズはInnoDBの半分(50%)になることを目指し、これによってサーバへの集積率があがるので、CPU利用率やDisk I/Oも低く抑える必要がある
MyRocks, RocksDBへの最適化
主に3.2, 3.3節の内容をもとにMyRocks, RocksDBで改善された項目を紹介します。 詳しい実装方法やその効果は具体的に説明されていないものがほとんどなので、項目と簡単な説明だけリストアップします。
CPU Reduction
- Mem-comparable Key
- B+ TreeではKeyの検索に1度の2分探索をすればよいが、LSMでは各Levelで2分探索する必要があるため比較コストを気にする必要がある
- 例えばMySQLではcase insensitiveな検索が可能だが、これを実現するoverheadがあるので、MyRocksでは常にMySQLのデータからRocksDBでバイト単位で比較可能な方法(bytewise-comparable way)でデータを変換している
- Reverse Key Comparator
- RocksDBのMemtableは単方向のSkiplistで実装されているため降順のscanに弱い
- これに対応するためにReverse Key Comparatorを実装した
- Faster Approximate Size to Scan Calculation
Latency Reduction/Range Query Performance
- Prefix Bloom Filter
- 少量のrange scanの場合、LSMでは各レベルで検索を行わないといけないoverheadが無視できない
- 対策としてデータの先頭数バイトによるPrefix Scanを実装し、prefixが含まれていないsorted runsをスキップできるようにした
- Reducing Tombstone on Deletes and Updates
- Tombstone(論理削除を表すkey)が増えると検索の効率が悪くなっていく
- RocksDBではCompactionの操作を最下層(Lmax)まで連続して行うことでtombstoneを減らすようにしている
- さらにRocksDBに
SingleDeleteという操作を実装した- これは
Deleteとは異なり、対応するkeyが見つかった時点で即座に消えるもので、Keyが重複して保持される場合には利用できない
- これは
- Triggering Compaction based on Tobmstones
- Delete操作の際にTombstoneが多い範囲が見つかった場合、すぐに次のcompactionを実行して、Tombstoneを減らす
- これをDeletion Trigger Compaction(DTC)と呼ぶ
- DTCと前述の
SingleDeleteによる性能向上と安定性向上がFigure 5で示されている
Space and Compaction Challenges
- DRAM Usage Regression
- RocksDBではBloom filterがDRAMに常駐させるため、メモリを圧迫する
- 対策としてRocksDBを拡張し、最後のsorted runsへのbloom filter作成をスキップできるようにした
- level間の比率を10にし、Lmaxのsorted runsが全体の90%あるとするとbloom filterをスキップすることで90%のメモリ使用量削減ができる
- SSD Slowness Because of Compaction
- Physically Removing Stale Data
- PutによりNULLに設定されたkeyはdeleteと違いcompactionで完全に消されないまま残ることがある
- SSTファイルのageをチェックし定期的にcompactionを走らせてこれらの削除を促進する
- Bulk Loading
- More Compression Oppotunity
マイグレーションプロセス
実装したMyRocksのBug, パフォーマンス劣化を洗い出すために、ベンチマークツールやProductionのデータを利用してInnoDBのMySQLのデータと比較を行う。 4章では主にこのプロセスでのMyRocksへのQuery test用のツールとそのテストで見つかった、Gap Lockに由来するRepeatable Readの実装の違いによるバグの対策について説明されている。
MyShadowとData Correctness Checks
- Facebookでは独自のaudit pluginでproductionのデータをすべて収集する仕組みがある
- audit pluginで取得したproductionの全クエリを
Replayerから検証用のMyRocksに再現するMyShadowというシステムを構築し、MyRocksにバグやパフォーマンス問題がないかを確認する - Figure 7に概要の図があるのでそちらを参照
- Data correctness checksではMyRocksとInnoDBベースのreplicaを作成し、あるタイミングでレプリケーションをとめて、データの整合性を確認する
- Figure 8の概要の図を参照
Gap Lock and Isolation Behavior Differences
- InnoDBではRepeatable Readを実現するためにGap Lockを利用している
- MyRocksではRRの実現に、実装の容易さからPostgreSQLなどに見られるSnapshot Isolation modelを採用した
- これによりStatement basedのレプリケーション(実行されたクエリをそのままreplicaに伝搬するMySQLのレプリケーションモード)ではLock方法の違いから不整合が起きることがあり、Row basedのレプリケーション(行単位で変更分を伝搬するMySQLのレプリケーションモード)に切り替えた
- この分離レベルの実装の違いはPrimary instanceとしてWriteを行ったときにも発生し、Snapshot Isolation modelでは強豪が発生した場合にerror率が高くなることがわかった
- 回避策としてアプリケーション開発者と相談し,問題がない部分ではRead committedでトランザクションを実行するように変更した
Actual Migration
- 前述のMyshadowとData Correctoness Checksによる確認の後、2016年から本番環境でのマイグレーションを開始した
- MySQLのレプリケーションコンポーネントはストレージエンジンとは分離されているため、レプリケーションクラスタ内でストレージエンジンのことなるMySQLが混在できる
- レプリケーション構成を変化させて、以下のような段階に分けてマイグレーションを行った (Figure 9を参照)
「MyRocksのインスタンスをPrimaryに昇格することは数年をかけた努力の集大成で、入念な計画とテストを重ねたとはいえ、まだ恐怖があった。 そして、もうすべてのBugを解決したと盲信する(原文: leap of faith that we found all problems)必要があった。」と書かれている。 この辺は、DB開発や運用をしている人にはこの章は激熱な内容だと思うので、必読ですw
- マイグレーションの最中はすべてのアプリケーションを注意深く観察し、不自然な挙動がないかをチェックした
- MyRocksに移行が進んだ後InnoDBベースのインスタンスを残し、すぐにMyRocksからrollbackできるように待機させておいた
- 結局、すべての作業はスムーズに進行した
- 数ヶ月後に、自信を持ってすべてのInnoDB instanceを削除することができた
- 2016年の中旬に作業を開始し、2017年8月にはほぼすべてのInnoDBインスタンスがMyRocksベースのMySQLインスタンスに移行された
移行によるパフォーマンス改善
結論と今後の課題
- 結論
- 今後の課題
- MyRocksのパフォーマンスチューニングを単純にする
- InnoDBとパフォーマンス上遜色がないようにprefix bloom filterやreverse key comparator，Lmaxのskipなどを多大な努力で改良したが、これらが動的に最適化されるような仕組みを構築する
感想とMyRocks実験
論文中で「UDBのInnoDB, MessangerのHBaseをMyRocksに移行するなど、2014年に開始した調査がずいぶん遠くまで来たと感じる」と書いている部分があり、調査の開始から自作のストレージエンジンの開発、テスト、改良、合計数十PBのインスタンスのマイグレーションまでが4年弱で達成されているのに圧倒されて鳥肌が立った。Facebookのエンジニアってやばい。。。(語彙力)
一方で圧縮機能を有効化したInnoDBに対して、Disk sizeが37.7%になったという点には正直疑問が残っています。
論文中でもUDBのschemaに特化して最適化していたり、MyRocksに合わせた最適化のためにUDB自体のschemaや設定を変えているような記述が見かけられます。
一般的な用途で我々がMyRocksを利用したとして、これだけの性能改善の恩恵を受けられるのでしょうか？
実験
というわけで試しにMySQL(InnoDB)とPercona Server with MyRocksを立てて、sysbench oltp-read-writeのスキーマでInnoDBだとDatasizeが約120GBになるデータセットで比較してみた。
(2020/09/08追記: このブログのコメントで指摘されているようにInnoDBで断片化が起こるケースが再現されていない可能性、MyRocks/RocksDBの圧縮が有効になっていない可能性があります。検証については本当に何も知らずにやってみた程度のものです。続きの検証は別のブログに書きます)
MySQLは最新の8.0.21, MyRocksは標準のMySQLではサポートされていないため、Percona MyRocksをPerconaのInstallation Guideに従って入れた。現時点の最新バージョンは8.0.20。
どちらもほぼデフォルトの設定で構築。(sysbenchが対応していないので、--default-auth=mysq_lnative_passwordにだけ変更)
何も考えずにデフォルトの設定で比較するなって話はあるのだけれど、とりあえずスタート地点として比較してみた。
以下のsysbench prepareコマンドで、InnoDBだと約120GBのデータになる
sysbench /usr/share/sysbench/oltp_read_write.lua \ --db-driver=mysql \ --table-size=100000000 \ --tables=5 \ --mysql-host=localhost \ --mysql-port=3306 \ --mysql-user=sysbench \ --mysql-password=**** \ --mysql-db=sysbench \ --db-ps-mode=disable \ prepare
Storage Engineが異なるので/path/to/sysbench/oltp_common.luaに修正が必要 70行目あたり
mysql_storage_engine =
{"Storage engine, if MySQL is used", "rocksdb"},
結果
| Storage engine | Disk Size | comment |
|---|---|---|
| InnoDB(非圧縮) | 114GB | ${DATA_DIR}/sysbench ディレクトリの容量 |
| MyRocks | 101GB | ${DATA_DIR}/.rocksdb ディレクトリの容量 |
InnoDBの89%程度にしかならなかった。。。
Percona MyRocksのrocksdb_で始まるVariableは150以上ある、特にrocksdb_default_cf_optionsなどに圧縮アルゴリズムを設定できそうなので、こういった部分をチューニングする必要もありそう。
とはいえ、ここからInnoDBの圧縮機能を有効にして、さらにその40%近くまで減るのだろうか？？
Facebookは最近5.6から8.0への5.7飛ばしのmajor version upgradeに取り組んでいる(過去のPercona Live等のカンファレンスで直接聞いた)はずで、この論文での比較も8.0のInnoDBではなくバージョン5.6(5.6のGA versionの最初のリリースは2013年)との比較の可能性が高い。
もちろん当初からMySQLやInnoDBに手を入れていて、Facebook MySQLというのが公開されているので、OSSのMySQLとは別の改良がもありそうですが、最新のInnoDBの進化も激しいのでそことの比較はもう少し変わった結果になる気がしました。
MyRocksのconfigurationを勉強すればもっと差は出そうだけれど、やはりサポートが公式になくて、何かあったら自分で直すとなるとプロダクション環境で使うのはまだ難しいと思いました。
ちなみにMySQLのサポートサービスを提供しているSmart Styleさんの技術ブログでMyRocksを紹介している記事でも、デフォルトの設定ではディスクサイズがInnoDBの圧縮機能有効時よりも悪い結果が示されています。 それなりに内部を理解して調整したり、利用するデータセットやschemaを制限しないといけない可能性も高そうです。
↓Smart StyleのMyRocks紹介記事 www.s-style.co.jp
