- Marginalia Search は最近の変更により、RAM 要件を半減し、アップグレード中に検索エンジンを停止しなければならなかった運用負担を大きく下げた
- 障害は最新リリース後のインデックス切り替え過程で表面化し、URL データベースをアップグレード時に消去する構造が長時間のオフラインにつながっていた
- URL ストアは巨大な MariaDB テーブル・インデックス中心の構成から、単一の SQLite データベース と、プロセス側で生成する 64 ビット URL ID 構造へと変更された
- 逆インデックス生成は、高密度な term ID 用 lexicon と大規模ランダム書き込みを捨て、小さな preindex を作ってからマージする方式へ移行した
- 新しい構造により、不適切なデプロイでも数時間以内に復旧できるファイルバックアップが可能になり、Wikipedia のように変化の少ない大規模データの処理結果を再利用しやすくなった
1週間で変わった検索エンジン運用条件
- Marginalia Search は1週間のコーディングで、複数の長期的な問題を同時に軽減した
- 検索エンジンの RAM 要件 が半減した
- アップグレード中にシステムをオフラインに落とす必要がなくなった
- インデックス可能な文書数のハード上限がなくなった
- コーパスに含められるキーワード数のソフト上限が4倍に増えた
- 低性能なハードウェアでもシステムを運用可能な状態に保つことが長期目標であり、今回の変更は、32GB RAM の開発マシンが余裕に感じられた以前の改善よりも大きな前進だった
障害を拡大させた既存のアップグレード構造
- Marginalia Search は最新リリースの問題で、ほぼ1週間オフライン状態になった
- 直接原因は比較的小さなスケーラビリティ問題の連鎖だったが、正常でも1日、問題があると2〜3日かかるプロセスを何度か再起動しなければならなかった
- 障害がユーザーに大きく見えた理由は、インデックス切り替え中にシステムをオフラインにする必要があったためだ
- 既存構造ではアップグレード中に URL データベースが削除され、10億行近いテーブルに対する高速な行の挿入・更新処理がボトルネックになっていた
- 新しいデータをロードするプロセスが大量の RAM を消費した
- 同じように RAM を使うインデックスサービスと同時実行しにくかった
- 主キーが 32 ビット整数のため、20億を超えにくい制約があった
URL データベースの再設計
- URL データベースは検索エンジンの古い構成要素であり、初期の設計判断が現在のシステム構造と合わなくなっていた
- 中核には、新しいインデックスをロードするときだけ書き込まれ、主キー参照でのみ読まれる2つのテーブルがあった
- URL テーブルは各 URL に固有の数値 ID を割り当てる
- PAGE_DATA テーブルはインデックスされたリンクのタイトルや説明といった情報を保持する
- ドメイン内でパスの一意性を維持する追加インデックスがあったが、その役割に対して非常に大きかった
- 新構造では、2つのテーブルを単一テーブルの SQLite データベース にまとめ、ローダープロセスが固有 ID 生成を担い、インデックスしない URL の一覧は別テーブルで扱う
- MariaDB と SQLite を併用する方式は慣例的な選択ではないが、2つのストアは異なる要件を担っている
- システムには比較的小さな永続的世界観が必要である
- 同時に、テラバイト級の状態をプラグアンドプレイのように交換できなければならない
- DOCUMENT テーブルと DOMAIN テーブルはデータベースをまたいで疎結合しているが、実際の join は不要である
- 災害時には、DOMAIN テーブルの重要部分を DOCUMENT テーブルから再構築できる
インデックスなしで 64 ビット URL ID を作る
- 既存の URL テーブルは 32 ビット ID を使用しており、整数オーバーフローに近い状態は既知のスケーラビリティ問題だった
- URL データベースを消去していた理由の1つも、ID カラムのオーバーフローを防ぐためだった
- 単純なカウンターだけでは URL の重複を処理できず、見たことのあるすべての URL のコレクションをメモリに保持する方式も避ける必要があった
- 新方式では、データベースが ID を割り当てるのではなく、64 ビット ID を直接構成する
- 下位 26 ビットは連番として使う
- 26〜56 ビットは文書 ID として使う
- 最上位ビット群はインデックス整列のためのトリック用に予約する
- この配置により、ドメインあたり約6,700万文書を扱える
- 英語版 Wikipedia の約10倍規模である
- ドメインは20億個まで扱える
- これは Marginalia が Web のどこかで参照を見たドメイン数のほぼ100倍である
- データ整合性の責任はデータベースからデータ生成プロセスへ移るが、そちらで強制するコストははるかに低い
URL 再設計が減らしたメモリ負荷
- 巨大なインデックスとホット・コールド URL データが混在する大きなテーブルをなくしたことで、MariaDB サーバーはもはや 36GB RAM を必要としない
- MariaDB に残るホットデータは多くても数百 MB 程度で、サーバーに割り当てる RAM も 2GB 以上は不要になる可能性が高い
- SQLite データにも主キー用インデックスは必要だが、実際にホットになるインデックス部分は 1GB 未満と見込まれる
- インデックス対象データ量が一桁規模で減った
- インデックス対象は単一の 64 ビット long である
- 追加のユニーク制約がない
- ローダー出力がファイルの束になったことで、自動バックアップを作りやすくなった
- 不適切なデプロイが起きても、以前のようにほぼ1週間ではなく、数時間以内に復旧できるようになった
逆インデックス生成のボトルネック
- ローダーは URL データベースと、文書中心の
(document, words[]) ジャーナルを出力し、検索にはこれを (word, documents[]) 形式へ転置したインデックスが必要になる
- 既存方式は、キーワード文字列を高密度な term ID にマッピングする lexicon を使っていた
- 最初の単語には ID 0、次の単語には ID 1 を与える方式だった
- 文字列は 64 ビットハッシュで long にマッピングされる
- 構造は実質的に long-to-int オープンハッシュマップである
- この構造は規模が大きくなるとすぐに飽和する
- Java は20億個を超える配列を許容しない
- 使用中の実装は10億個規模ですでに限界だった
- 10億エントリでは RAM を 12GB 使用する
- 運用中の index service は 60GB RAM を使っており、その大半はオフヒープメモリである
- オンヒープサイズが 32GB を超えると CompressedOOPs を使いにくくなる点も問題だった
既存の逆インデックスアルゴリズムにおける書き込み増幅
- 既存アルゴリズムは、最大の word ID を見つけ、その大きさの counts 配列を作り、単語ごとの文書位置を計算してメモリマップトファイルに文書データを書き込んでいた
- この方式は word ID のドメインが高密度に埋まっている前提のため、lexicon を必要とした
- より大きなボトルネックは、約 1TB のデータをほぼ完全にランダムな順序でメモリマップトファイルへ書き込む工程だった
- SSD は読み取りではランダムアクセスをうまく処理するが、小さな書き込みでは 書き込み増幅（write amplification） の問題が生じる
- SSD はディスク上の1バイトを更新する場合でも、ページ全体を消去して書き直さなければならない
- 隣接書き込みをまとめるキャッシュはあるが、テラバイト規模のランダム書き込みには効果がない
- 1TB を書く間に、ドライブ側では約 0.5PB の書き込みが発生することになる
- 一時的な緩和策として
RandomWriteFunnel があった
- 書き込みをまず小さなファイルバケットに分散する
- その後、大きなファイルを順次書き込む
- 元の方式よりは良いが、それでも非常に遅い
小さな preindex を作ってマージする
- 新しい逆インデックス生成は、すべてのデータがメモリに収まる小さなインデックスを複数作ってからマージする方式である
- ソート済みリストのマージは高速で、機械式ハードディスクにも向いている
- この方式では lexicon が不要になる
- term ID として 64 ビット文字列ハッシュを直接使える
- 初期に生じた問題は、入力が圧縮されている点と、インデックスのマージ方法だった
- 圧縮入力の一部を高速に読む代わりに、複数の小さなファイルを作って1つずつ読む
- インデックスを作成してからマージするのではなく、インデックスを作る前にデータをマージする
- 新しい抽象化である
preindex は、単語 ID 配列、カウント配列、文書データ配列で構成される
- 入力が小さいため、preindex の大半は RAM 上で作成でき、生成しながらディスクにコミットし、その後のマージ段階で最終 preindex を作る
- 最終 preindex は、従来どおり words テーブルと各 document block に静的 btree インデックスを追加して逆インデックスへ変換され、この工程は比較的高速である
運用とデータ再利用に生じた変化
- lexicon の除去により RAM 要件が下がり、新しい逆インデックス生成は従来アルゴリズムより高速になった
- 既存の lexicon は、処理されたデータ束ごとに別々の方言を作っていた
- 同じ単語でも、ある実行ではある ID が割り当てられ、別の実行では別の ID が割り当てられる可能性があった
- このため、すべてのデータを同時に処理しなければならなかった
- lexicon を捨てたことで、異なるデータ束をマージできるようになった
- Wikipedia のように大きく、めったに変わらないデータの処理結果を再利用し、より頻繁に変化するインデックスデータと組み合わせられる
- 今回の変更は、既知のほぼすべてのスケーラビリティ問題と運用上の不便を軽減し、さらに多くの副次的効果を検討できる状態を作った
2件のコメント
Marginalia - 独立運営のDIY検索エンジン
Hacker News の意見
世の中の他の流れとは正反対の方向へ進むプロジェクトで、こういう成功例を見ると本当に気分がよくなる
Engildification と呼びたいくらいで、こういうものはもっと増えるべきだ
Sleeping At Night の記事も気に入ったし、最近の「Lie Still in Bed」の記事とあわせて、睡眠トレーニングの問題を解決してみるためのとてもシンプルな選択肢に見える
Marginalia 検索エンジンは作者が最近フルタイムに移行したばかりで、知る限りチーム規模は1人なので、エンシッティフィケーションのリスクから最も遠いところにいる。むしろこの規模でこそ宝石が生まれ、創造性・奇抜さ・ビジョンが輝く
このコメントは「デスクワークを辞めて独立して働こう」会の提供でお送りしました
リソース消費を半分に減らし、より小さな画面で以前より生産性が上がり、夜は丸太のようにぐっすり眠る
興味のある人向けのリンク: https://www.marginalia.nu/log/86-sleep/
ちなみに Hacker News でも見たことがありそうな有料検索エンジン Kagi は、Marginalia をデータソースの一つとして使っている
https://help.kagi.com/kagi/search-details/search-sources.htm...
“non-commercial” レンズを使うと、Kagi 自体のインデックスやいくつかの独立系ソースの結果とともに、こうした結果が優先される
この記事を読むと、人間は人為的な制約なしには優れたものを作りにくい存在なのではないかと思えてくる
Marginaliaが途方もなく効率的な理由は、Victorが実行ハードウェアとメモリ容量を意図的に制限しているからだ
単に32GiBを追加すれば当面は動くだろうが、非効率な設計は残り、あとでさらに複雑になった状態で同じ問題が噴き出して、直すのが難しくなるかもしれない
この仮定が正しいなら、最近のソフトウェアが肥大化し、遅く、バグが多い理由も説明できる。個々のソフトウェアは独立して見るとほとんど限界に達していないので、それぞれの部品は非効率でも、最新のM2 ProとGiB級の接続によって、問題になる地点をずっと先回りし続けているのだ
結論としては、自分に制限を課すほうが、長期的には自分にとっても皆にとってもよい、ということなのかもしれない
多くのアプリケーションでは、小さな最適化にそれほど多くの時間を費やすのは割に合わない。サーバーに32GiBのRAMを50ドル未満で追加できるのに、開発者を40時間以上、時給最低20ドルで使う選択と比べれば、ビジネスの観点では答えは明らかだ。しかもWebサイトが丸1週間落ちていたわけで、それだけで多くの事業は死にかねない
技術者はこうした深掘りが好きなので、些細なコードでも何年もかけて微細に最適化したがるが、終わりのないヤクの毛刈りでは金は稼げない。コードがごく少数のマシンでしか動かないなら、普通はその価値はない。こうした最適化は、保守しにくいコードに終わることも多い
今どきのユーザー端末で動くアプリのソフトウェア肥大化は、開発者の端末とユーザーの端末の不一致から来る部分が大きいと思う。開発者は仕事をするために高性能ワークステーションが必要で、それで基本的なテストもするが、ユーザーは5年前には中級以下だったような端末で実行している
管理者に「メモリを150MB節約できます」と売り込むのは難しいが、「メモリを150MB節約すれば、ユーザーの10%にとってアプリの性能がひどい状態からなんとか使える状態まで上がります」なら売り込める
昔は実際にそうやってソフトウェアを作っていた。だからPentium 1のようなマシンでも、今日期待するものの大半を備えたOSが問題なく動かせた。一方で今は、あらゆる軸でリソースが文字どおり千倍ほど多いスマートフォンでも、Webページのスクロールがもたつく。Word 95チームは常に限界と性能のトレードオフにぶつかっており、その結果は明確に動くか動かないかだった
ただRAMを追加していたら、依然として劣った設計に閉じ込められ、すぐまたさらに多くのRAMを買うことになっていただろう。今回の変更で驚くべき点は、リソース使用量を減らしただけでなく、空いたRAMのおかげでディスクキャッシュが増え、システムがより有能で速くなったことにある
[1] たとえばこれは単一のPiで動いており、更新を許可していないため、稼働中のWikipediaよりはるかに速い: https://encyclopedia.marginalia.nu/article/Hacker_News
だから古いコンピューターはよく感じられたし、古いゲームもあれほど素晴らしかったのかもしれない
私たちが扱うシステムの複雑さに関係しているのかもしれない。RAM、物理的な空間、食べ物、材料、時間、お金のような資源が限られていると、どう使うか計画しなければならず、賢くならざるを得ない
実質的に無限の資源があれば、作りたいように作れるが、最終状態を気にする必要は少なくなる。とにかく始めて、動くときに見ればよい
本物のゲーマーというわけではないが、数KB/MBのROMカートリッジの中に、あれほど多くの感情と冒険と楽しめる時間を詰め込んだ人間の能力にはいつも驚かされる。Ocarina Of Time ROMは、私がiPhoneで撮った最近の写真8枚分くらいの大きさしかない
Raspberry Pi 2は毎秒40億を超えるDhrystone命令を処理でき、Pi 4は毎秒100億を超える
もちろん現代の基準では、1970年代半ばのSABREは航空会社の中核システムとしてはかなり基本的なものだったが、理論上は単一のPi 2で100社を超える航空会社の簡略化されたシステムを同時に動かすことも可能だ
現代のプログラムは最適化から非常に遠い。数学演算が多い場合を除けば、1000倍や10000倍の改善も可能だ
Microsoftはこの問題に大きく悩まされていると思う。5年前の3000ドルのノートPCでも、Teams通話、いくつかのOffice、30タブのブラウザを同時に動かすと、受け入れがたいほど遅くなる
それぞれを個別にテストすれば、1つだけ実行しているときは問題ないが、実際の人々はそうは使わない
明確に定義されたハードウェア上で実行時間を制限し、明示的な判断の後でだけその制限を引き上げるような人為的な制限が解決策になるのかもしれない
ただし私は、性能面が「データベースに愚かなことをせず、それ以外は顧客がその心配に金を払わないのだから気にするな」に帰着する業務用ソフトウェアしか書いていないので、完全に見当違いかもしれない
marginalia.nuのアップデートが上がるたびにいつもうれしい。このサイトでは貴重なユーザーなので、これからも投稿してほしい
ありがとう。検索エンジンの趣味プロジェクトをやっているのだが、どういうわけかずっと「Magnolia」の変種ばかり検索していた。私にはMarginaliaという名前がどうも覚えにくい。今はSearxを把握しているところだ
Marginaliaが過去1日、過去1週間のような時間フィルタ検索に対応しているのか気になる。特殊キーワードを見ると、検索パラメータは年ベースのものだけを受け取るように見える
year>2005 (beta) 文書は見たところ2005年以降に公開されたもの
year=2005 (beta) 文書は見たところ2005年に公開されたもの
year<2005 (beta) 文書は見たところ2005年以前に公開されたもの
年フィルタもかなり粗く、ほとんどのWebページの日付を正確につかむのはとても難しい
「SSDがディスク上のどこかにある単一バイトを更新するたびに、ページ全体を消去して書き直さなければならない」という話が、本当にSSDに当てはまるのか気になる
生のフラッシュではそうではない。「空」の all-ones 値を上書きする場合や、1を0にだけ変える場合なら可能。書き込みは読み取りより数桁遅いが、消去よりもさらに数桁速く、摩耗予算に反映されるのは消去だけ
SSDコントローラがこの点を活用していないなら、オウンゴールのように聞こえる。ただし内部が実際にログ構造なら、できないかもしれないとは思う
以前、人気のあるフラッシュチップをいくつか扱うドライバを書いたことがあるが、当時扱ったチップはいずれも、読み取りと書き込みに固定サイズのページ単位I/Oしか使っていなかった
SSDはチップの集合体なので、SSD内の各チップも固定サイズのページI/Oだけをサポートしているだろうと予想する
通常、コントローラはこうした最悪パターンを避けるために、オーバープロビジョニング、バッファリング、書き込みの並べ替えといったさまざまな手法を使うが、限界はある
SSDで書き込める最小単位はページで、消去できる最小単位は複数のページからなるブロック
そのため、書き込み処理がページ内の1バイトだけに影響する場合でも、SSDはそのバイトだけを消去することはできない。とはいえ、必ずブロック全体を消去しなければならないわけでもない
SSDは「読み取り-修正-書き込み」型の処理を行える。変更されるバイトを含むページ全体をSSDのキャッシュバッファに読み込み、ページキャッシュ内でそのバイトだけを修正し、空いている新しいブロックを消去し、修正済みページをキャッシュから新しいブロックに書き込み、FTLマッピングテーブルを新しいブロック上の更新済みページを指すように更新する
したがって、1バイトだけが変わってもページは書き直す必要がある。ただし、その中の多くのページが修正されるまでは、ブロック全体の消去は避けられる
書き込みが発生すると、ページは物理デバイス内で移動する。ドライブ自身が、どのアドレスが何に使われているか、健全性がどうかなどを含むマップを保持している。一種のスパースな保存方式
TRIMのようなコマンドや、定期的なメンテナンス、ガベージコレクションもある
実際、満杯ではないドライブに書き込む場合、データを入れるページを探し、そこにデータがあるか確認し、必要なら読み取り/修正/書き込みを行い、データをどこに書くか決めてから書く。ウェアレベリングのため、元の場所に戻らない可能性が高い
コントローラが性能のためにはるかに複雑な手順を実行する、という点はその通り。だから空の新しいドライブはしばらくの間よりよく動作し、予備ページのない古くて満杯のドライブより実際に遅くなることもある
出典を付け加えると、キャッシュ一貫性を備えたメモリマップド・フラッシュアクセラレータの主任エンジニアだった。Linuxのユーザー空間でドライブを非常に効率よくマッピングできるようにしたが、結局しばらくすると、単なる別のハードドライブに見える「簡単な」プログラミングモデルに屈した
Mojeekの私の上司も、おそらくこれとかなり似た道を歩んだのだろうと思い浮かんだ。この記事は過去の会話とかなり重なる
Mojeekは2004年に始まり、大部分は1人の開発者が骨格を作り、情報検索とインフラのほぼすべてを構築した
資金やハードウェアの制約、32ビット対64ビットIDの判断、シャーディング、更新速度といったことが非常になじみ深く聞こえる
昔のGoogleの「Google dance」も思い出す。当時は検索結果が月に1回更新され、今では毎日揺れ動く。すべて進化の過程であり、Marginaliaがビッグテックの外側のウェブを見るもう一つの視点を提供しているのはよいことだ
読みやすかった
多くの人は最適化を深い黒魔術のように考えているが、たいていは一般的なバグ修正よりむしろ簡単。過剰なリソース使用をバグと同じように扱えばよい
簡単に再現できるバグの大半は、直すのに魔法を必要としないと思う。バグをつつけるなら、たいてい分類できるし、まれな設計上の欠陥も再現可能になれば概ねすぐに姿を現す
誰も性能を批判的に見ていないソフトウェアは、簡単に再現できるバグが何百個もあるのに誰もデバッグしていないソフトウェアと同じ。難しいものにぶつかるまでは、かなり長い間、一つずつ削っていける
こうした態度は、かつて人々が分岐先アドレスを、ドラムヘッドがCPUが命令を必要とする瞬間に合わせて到着するよう調整していた時代の名残に近いと思う。リソースが極度に限られ、すべてを手作業でアセンブリで書き、グローバルなメモリ位置がプログラムの段階によって異なる意味を持っていた時代には、すでに非常に賢い人たちが性能を批判的に見ていたため、彼らが見つけられなかったものを見つける必要があった。現代のコードでは珍しいことだ
リクエストXをサービスYに送るとバグが再現するなら、犯人を見つけるまでテストケースをどんどん小さくすればよい
最適化はしばしばアーキテクチャの問題。バッファを再利用できるのにコピーしている場合もあるが、そういうものはすぐに尽きるし、プロファイラが必要な情報を教えてくれる
大きな性能向上は、データフロー全体を変え、かなりの部分を取り除いて、コードが必要なことをできるだけ少ない手順で行うようにするところから生まれることが多い
なぜキー・バリューストアではなくSQLiteを選んだのか気になる。IDで読み取るだけで、他の列は必要なさそうなので、リレーショナルデータベースは不要に見える
SQLiteには単一ファイルという利点がある。そのため、コピーしたり共有したりといった気の利いたことができる
制約がイノベーションを生むもう一つの事例で、よいと思う。イノベーションは豊かさよりも限界の中で見つかることのほうが多い