- Lichessはリクエスト負荷のため 7-piece Syzygy tablebaseサーバー の定期的なRAID検査が滞っていたことから、全ブロックを走査する方式ではなく 読み取り時の整合性検証 に切り替えた
- 長時間のダウンタイムなしで17TiBのtablebaseを移行するため新サーバーを用意し、32GiB RAM・2×201GiB NVMe・6×5.46TiB HDD構成で実際のリクエストログを再生して検証した
- 本番環境で記録した 100万件のリクエスト を12並列クライアントで再生した結果、平均応答よりもユーザーが体感する テールレイテンシ が主要なボトルネックであることが判明した
- 実装面では
mmap より pread(2) のほうがエラー処理とテールレイテンシの点で有利で、POSIX_FADV_RANDOM・MADV_RANDOM のようなランダムアクセスヒントは概ね逆効果だった
- 容量の限られたSSDにはtable prefixを載せ、リクエスト内部のprobeを並列化して遅いディスクアクセスを減らし、ベンチマーク改善が本番の応答時間にもつながるかを確認した
RAID全体検査の代わりに読み取り時検証へ移行
- Lichessの 7-piece Syzygy tablebaseサーバー は、tablebaseリクエストが多い間は定期的なRAID整合性検査を完了しにくかった
- 新構成では dm-integrity on LVM を使い、すべてのデータブロックを定期的に検査する代わりに、ブロックが 読み出されるたびに検証 する
- 17TiBのtablebaseを数時間のダウンタイムなしで移行するため、新サーバーを別途構築した
- 実際の切り替え前に、tablebase全体を対象にした 制御されたベンチマーク を実行できた
- その後、新サーバーへ切り替え、旧サーバーを退役させた
新サーバー構成
- RAMは従来と同じ 32GiB を維持した
- ストレージは旧サーバーになかった 2×201GiB NVMe を追加し、476GiBディスクの残り領域はOSと作業領域として確保した
- HDDは従来の5台から 6×5.46TiB HDD に増えた
- OSはDebian bookworm、カーネルは
Linux 6.1.0-21-amd64 系だった
- デフォルトのI/OスケジューラはNVMeで
none、HDDで mq-deadline が選ばれていた
RAID 5構成とモニタリング
- RAID 5は単一ディスク障害から復旧でき、ランダムリードを複数ディスクに分散できるため、tablebaseサーバーに適している
- 初期構成は次のとおりだった
lvcreate --type raid5 --raidintegrity y --raidintegrityblocksize 512 --name tables --size 21T vg-hdd
- 初期テスト性能は良好だったが、モニタリングがなければ一部ディスクが同程度に参加していない問題を見逃していた可能性がある
--stripes を省略すると、すべての物理ボリュームがデフォルトで使われるわけではない- ディスクごとの読み取り活動の監視 が、誤ったRAID設定を見つけるのに必要だった
実リクエストログから見えたボトルネック
- 通常条件ではサーバーは毎秒 10〜35件のリクエスト を受ける
- 本番環境で 100万件のリクエスト を記録し、選択したシナリオで12並列クライアントがこれを順次送信した
- tableは遅延オープン方式で開かれ、アプリケーションおよびOSキャッシュは段階的に埋まっていく
- 最初の 80万件の応答時間 はウォームアップとして除外した
- その後の 20万件のリクエスト の応答時間を分析した
- 平均応答時間は十分高速だったが、テールレイテンシ が高く、最適化の焦点となった
- ECDFグラフは、各応答時間より速く完了したリクエストの割合を示し、x軸は対数スケールである
- グラフではクライアントの 30ms ping time を反映するため、各応答時間に30msを加えた
- これは対数スケールのx軸で低レイテンシ領域の数ミリ秒差が過度に強調されないようにするための処理である
mmap より有利だった pread(2)
- Syzygy tablebase実装である shakmaty-syzygy は、tableファイルのオープン方法と読み取り方法を差し替えられるインターフェースを提供している
- 主な候補は2つだった
mmap: tableファイルをメモリにマップし、そのメモリ領域へのアクセス時にディスク読み取りが透過的に発生するpread(2): 読み取りごとにシステムコールを実行し、戻り値で読み取りエラーを報告する
mmap はマッピング後に追加のシステムコールが不要だが、読み取りが通常のメモリアクセスのように見えるため、エラーをシグナルのようなout-of-bandな方法で処理する必要がある- サーバー実装では、より堅牢なエラー処理だけでも
pread を使う十分な理由になり、ベンチマークでも注目シナリオでは pread のほうが高性能だった
- 考えられる原因の1つは、メモリマップされた単一データブロックへのアクセスがページ境界をまたぐと、2回のディスク読み取りにつながる可能性がある点である
- チェスエンジンにすぐ
pread を適用する必要はない
- エンジン対局でのtablebase利用は、通常すべてのWDL tableを十分高速なストレージに置ける場合に行われる
- この場合、一般的な応答時間帯はそのグラフに現れないほどであり、システムコールのオーバーヘッドを減らせる メモリマッピング のほうが適している
ランダムアクセスヒントの逆効果
posix_fadvise(fd, 0, 0, POSIX_FADV_RANDOM) と、そのメモリマップ版に相当するヒントは、結果としてほとんど 逆効果 だったPOSIX_FADV_RANDOM は、ファイルアクセスがランダムで自動read-aheadが有用でない可能性が高いことをOSに伝え、ページキャッシュ圧迫を減らすためのヒントである- 人がエンドゲームを分析するときのtablebaseアクセスパターンは、予想よりランダムではない可能性がある
- チェスエンジンではprobeが異なる可能性のあるエンドゲームへより分散するため、結果が異なるかもしれない
容量の限られたSSDに置くtable prefix
- table probeではまず、ポジションをtable headerのエンコード情報に基づいて整数インデックスへエンコードする
- 次に、そのインデックスの結果が入っている圧縮データブロックを見つける必要がある
- Syzygyは、正しい項目の近くを指す sparse block length list を提供し、続いてblock length listから関連するデータブロックを見つける
- table sectionのサイズは次のとおりである
| Table section |
WDL |
DTZ |
Total |
| Headers and sparse block length lists |
38GiB |
9GiB |
47GiB |
| Block length lists |
274GiB |
64GiB |
339GiB |
| Compressed data blocks |
8433GiB |
8458GiB |
16891GiB |
- SSD領域を適応型キャッシュ層として使い、hotなlist entryやdata blockをキャッシュすることもできる
- テールレイテンシ削減を目標にするなら、最悪ケースを考えて sparse block length listとblock length list をSSDに置く方法が適している
- この配置により、hot/coldに関係なくtable probeあたりの遅いディスク読み取りを最大 1回 に制限できる
- このサーバーではRAID 1ミラーリングを行うにはSSD容量が足りず、選択的最適化であることを理由に冗長性を諦めて RAID 0 を使った
リクエスト内部probeの並列化
- チェスエンジンの一般的なtablebaseリクエストは、単一のWDL値に対するリクエストである
- ユーザーインターフェースでは、すべての手について DTZ値 を表示しようとする
- Syzygy内部のcapture解決まで含めると、平均リクエストは 23回のWDL probe と 70回のDTZ probe を発生させる
- 初期実装では、リクエスト処理自体は並列化していたが、各リクエスト内部のprobeは逐次実行していた
- より細かい並列性は低レイテンシ帯ではオーバーヘッドになるが、テールレイテンシを大幅に削減 する
- ディスクが物理的に多数の並列読み取りを処理できなくても、I/Oスケジューラが各リクエストをより早く終えられるように読み取りを計画できる可能性が高まる
- この方法により、ディスクヘッドが次のリクエストセクタに到達するまでの時間を短縮するよう、関連するディスクアクセス順序をより適切に計画できる
本番での確認と元データ
1件のコメント
Hacker News のコメント
Lichess は、良いワインのように思わず静かに感嘆してしまうサービス。チェスコミュニティにとって本当に素晴らしく、毎日使いながら機能と性能にずっと刺激を受けている
特に、限られた予算の 1〜2人規模 のチームだと知ると、さらに驚かされる
応答時間ごとに 30msを加えたECDF を見せていた部分が興味深かった
定数を足すのは人工的に見えるかもしれないが、実際には30msのpingを持つクライアント視点で結果を見る方法であり、対数スケールのx軸が低い領域での数msの差を誇張しないようにもしている。標準的な手法なのかもしれないが、かなり賢いやり方に見える
コスト削減が本当に必要だったのか、それとも単に1台のマシンに 20TB SSD を入れて終わりにできない別の理由があったのか気になる。4TB SSDもだいたい300ドル程度だし、HPやDellのSFFドライブもそれほど高くはない
おそらくテストと最適化そのものに興味があったのだと思うし、プロダクトの観点なら限られた時間を別のプロジェクトに使っただろう
組織がフランス拠点であることがコストにどう影響するのかは分からないが、言及する価値はある
これ以上に時間投資を正当化できるとすれば、ユーザー体験がもっと悪いプロジェクトがある場合か、営利組織で他に稼げる機会があり、顧客の苦痛にはあまり関心がないと認める場合くらいだろう
強力すぎて安いハードウェアと、単に「今日はここまで」にしたがる怠け者が組み合わさった結果のように見える。自分の仕事に誇りを持て、という話もあるだろう
この最適化には疑問のある選択がいくつかある。最適化の理由は、入出力が多すぎて RAID検査 が完了できないというもの
記事を読む限り、17TiBのデータに対するRAID検査が実際に完了したことがあるのかは不明。代わりに定期的なRAID検査を無効にし、データを読むときにページ単位でエラーチェックするよう変更しているが、この2つは同じではなく、重要なデータなら両方を使うべき
データを読もうとしたときにだけ破損を発見するのでは、古いデータ破損が残り続け、バックアップの保持期間を過ぎて元データを復旧できなくなる可能性もある。さらに RAID 0 に変えた点も根底にあり、最速の選択ではあるものの、そのNVMe構成がその負荷に耐えるとかなり大きく信頼していることになる
バックアップがきちんと取られていることを願う。良い解決策は、一時サーバを立ててバックアップを復元し、全データ検査を実行したうえで、成功すればバックアップ・復元手順とファイル整合性も合わせて検証すること。それでも本番サーバでRAID検査を完了できる余裕は確保すべきで、性能のためにRAID 0を使うのは避けたほうがよい
これは自由に入手できるデータセットで、少し大きいだけ。https://en.wikipedia.org/wiki/Endgame_tablebase の説明のほうが分かりやすい。だからバックアップもしていない
lishogi もあるが、まだ規模が小さいので、このような最適化が必要なほどではない
チェス変種の中では将棋が一番面白く、シャンチーはそこまでではない
lichess は女性の lich という意味だと考えればいいのだろうか。baron/baroness のような感じで
厳密には男性の lich は “werlich”、女性の lich は “wiflich” で、複数形には “-en” が付く。ただしアンデッドに性別はたいてい関係ないので、中性形が圧倒的によく使われる
“lichess” はドイツ語とフランス語の語根が混ざった奇妙な組み合わせなので、自然に英語の他の単語と区別がつかない
公平な比較ではないが、Lichessチームの エンジニアリング品質 には本当に感心する。主な競合はGCP移行を誇っていた一方で、人気の増加に伴って繰り返し障害を起こしており、人数はおそらく100倍くらい多いと思う
Lichess の弱点はモバイルアプリだったが、Flutterで作り直したv2はまだベータなのに、すでにかなり良い
そして Thibault が自分の報酬として年6万ドルも受け取っていないことも覚えておくべき
ただ、Lichess をどう発音するのか気になる。Lie chessなのか、Le chessなのか、League chessなのか