Block の候補生成 — 約束¶

翻訳について: 正本は英語版です。日本語版が古い場合は英語版を参照してください。

Status: 約束とその適合検査のデータが master にあります。もう 1 つの読み方 (CPERSONA_BLOCK_INDEX が on の時に、データベースの横のファイルから読むもの。2.6.7 から既定で on) も master にあります。想起の答えは変わりません。

0. これは何か¶

Block の腕 (Block による到達) は、すべての記録を節の大きさに分けた Block を、 1 次元 1 ビットの Hamming 距離で探します。その探索は 2 つに分かれます。

候補生成。 1 回の呼び出しで見てよい Block の行を読み、それぞれの問いへの Hamming 距離を測り、書き下された順序で近いものをいくつか残します。
並べ直し。 残した行の保存済みベクトルを読み、cosine で並べ直します。

前半が返すのは整数と識別子だけなので、その速い実装に「今の想起と同じ行を同じ順で返すこと」を厳密に求められます。このページは前半を約束として書き、実装をそれに照らしてどう検査するかと、速い実装を何にするかの決定を記録します。

速い実装が要る理由。 今の前半は、呼び出しのたびに行を SQLite から読みます。実際の長さの記憶 10 万件では、Block は 3,480,069 行、1 記録あたり 34.8 行あり (コーパス)、 Intel N150 ではこの読み出しだけで 360〜375 ms かかります (第 3.1 節)。

1. 約束¶

入力。

行。キーの順 (種類のバイト順、次に親の id、次に Block 番号) に並んでいます。各行は種類・親の id・ Block 番号、記録の agent id・project id・channel、ビット列を作ったモデルのラベル、そしてビット列 (まだ無ければ無し) を持ちます。
問い。ビット列、agent id、project id (無し・空・名前のどれか)、channel (空・名前のどちらか)、 2 つのモデルのラベル。
3 つの上限。見てよい行の数、そのうち 1 記録が取ってよい数、返す行の数 (深さ)。どれも、呼び出し側が受け取りたい件数からは導きません。

手順。 規範です。どこか 1 段でも違う実装は、違う行を返します。

受け入れ。 ビット列があり、ラベルが 2 つのモデルのラベルのどちらかに等しく、agent id が問いと等しく (空の agent id は「名前のあるエージェントが持たない行」の区分で、ワイルドカードではありません)、下の 2 つの軸が許す行を受け入れます。受け入れない行は、どちらの上限も使いません。
project。 無しはすべての project を読みます。空は全体の共有分 (project id が空の行) だけを読みます。名前はその project と全体の共有分を読みます。
channel。 空はすべての channel を読みます。名前はその channel と、channel 共通の行 (channel が空の行) を読みます。
調べる。 受け入れた行をキーの順にたどります。1 記録の取り分は、Block 番号の順で先頭から 1 記録の上限までで、それより後の行は飛ばします。調べる上限が満ちたら止まります。取り分は受け入れた行で数えるので、ビット列の無い行や別のラベルの行は、記録の取り分を使いません。
測る。 ビット列の長さが問いと違う行には距離がありません。取り分と調べる上限の 1 枠は使いましたが、順位には入りません。幅が違えば次元が違い、その間の距離は意味の無い数になるからです。それ以外の調べた行には、問いへの Hamming 距離を付けます。
並べる。 測った行を、距離、種類、親の id、Block 番号の昇順に並べます。キーは一意なので、 2 つの行が同点になることはありません。深さまでの先頭の行を返します。

出力。 返す行ごとに、種類・親の id・Block 番号・距離。本文もメタデータも浮動小数のスコアも返しません。

今のままのもの。 保存済みベクトルによる並べ直しと、その後に続く処理は、この約束に含みません。返す行にまだ保存済みベクトルが無い時 (ベクトルを作っている途中の配備) は、腕は今と同じく自身の経路で答えます。

2. 適合検査¶

golden。 tests/golden/block_candidates.json が場面を持ちます: キーの順の行、問い、上限、そして返るべき行。これを書くのは scripts/capture-block-candidates.py で、想起が使う関数 (blocks._examined、blocks._measured、blocks._order) を本物のデータベースの上で走らせます。返るべき行を手で書く人はいません。行は順不同で挿入するので、答えは表のキーで決まり、届いた順には左右されません。

場面が覆うもの。 768 次元のモデルの幅と想起そのものの上限。深さの切れ目が同じ距離の並びの中に落ち、書き下された順だけが決める場面。それぞれの上限が効く場面と、両方が同時に効く場面。記録の中で受け入れられない行 (ビット列が無い、別のモデルのラベル) と、幅の違う行 (狭いものも広いものも) が並ぶ場面。3 つの軸のすべての読み方。測った行が深さより少ない場面。そして空の答え。

何が守るか。 tests/test_block_candidates_golden.py は、ファイルがコードの返すものと違ってきた時と、場面がこのページの名指す規則を検査しなくなった時 (たとえば、切れ目が同点の中に落ちる場面が無くなった時) に失敗します。サーバーのコードを壊すと (同点の順序、1 記録の上限を 1 つずらす、ビット列の無い行を受け入れる、幅の検査を緩める) 1 つ目のテストが失敗します。行を別の方法で読む実装も同じファイルで検査され、すべての場面で行を順どおりに返した時に合格します。

3. 決定¶

3.1 行は SQLite でなく、連続ファイルから読む¶

速い実装は、Block のビット列を、SQLite のデータベースからではなく、サーバーが書く連続ファイルから読みます。

10 万件のコーパスで測りました (探索、登録外)。想起が調べる 25 万行を、サーバー自身の読み出しで読んだ時と、同じ行をファイルから読んだ時の比較です。Intel N150 では、計測の横で 8 GB の仮想マシンが動いていました。

調べる 25 万行の読み出し	Apple M 系のノート PC	Intel N150
SQLite (今の想起の読み方)	127〜140 ms (初回 762 ms)	360〜375 ms (初回 1,384 ms)
連続ファイル	1.2 ms	6.1 ms

ファイルは記録の粗探索の索引 (1 ビット粗探索 §3) にならいます: サーバーが書き、開く時に検証し、修復はせず、消してかまいません。ただし、その索引と違って watermark までを読むのではありません。キーは種類から始まるので、作った後に書かれた Block はファイルのどの行よりも後ろに並ぶとは限らず、Block の行は足されるだけでなく消されたり移されたりもし、watermark はそれを見ません。代わりに、作った後に Block が変わった記録の記録 (変更記録) を通して読みます (第 3.4 節)。

3.2 距離はサーバーのプロセスの中で、SIMD のライブラリで取る¶

Hamming 距離と近い行の選び出しは、別の言語の別のプロセスではなく、Python のプロセスの中で、CPU のベクトル命令を使うライブラリで行います。

同じ行で測りました (探索、登録外)。問いはコーパスの Block のビット列 25 個で、その中央値です。どの実装も、25 問すべてでサーバーのコードと同じ行を同じ順で返しました。

Hamming 距離と近い 200 行	Apple M 系のノート PC	Intel N150
今のサーバーのコード (行のタプルの上で)	34.0 ms	169.7 ms
同じ参照表を配列の上で	23.1 ms	96.3 ms
NumPy `bitwise_count`	4.0 ms	13.1 ms
FAISS `IndexBinaryFlat` (1 スレッド)	1.1 ms	6.6 ms
SimSIMD	1.9 ms	4.9 ms
Go (同じファイルを読む別のプログラム)	1.3 ms	3.6 ms

この計測の前の計画は、Go の別プロセスでした。今の上限では、N150 で SIMD のライブラリより約 1 ms 速いだけで、そのうえ PyPI のパッケージの横にプラットフォームごとの実行ファイルという 2 種類目の配布物を増やすことになります。利得のほとんどは SQLite を読まないことから来ます (第 3.1 節)。どのライブラリを使い、それを必須にするか任意にするかは、実装と一緒に決めます。

3.3 既定は on、答えは変わらない¶

ファイルから読む実装は、CPERSONA_BLOCK_INDEX=false にしない限り on です。2.6.7a2 で入った時は明示して有効にするものでしたが、基準機で 10 万件に対して実行前に登録した計測で、想起が速くなり、答えはすべて変わらず、変更記録が Block の構築に足す費用が 1% 未満だったので、既定で on にしました (結果)。ファイルが正確に答えられない状態では、呼び出しを SQLite の読み出しに送ります (第 3.4 節)。その読み出しと同じ行を同じ順で返すことを、「答えがどこまで悪くなってよいか」の上限ではなく、次のもので求めます: この約束の golden をファイル経由で読むこと。作った後の無作為な書き込み (新しい記録、作り直し・削除・付け替え・別のキーへの移動、幅の違う行) の後に、上限が効く時と効かない時の両方で、記録が境目をまたぐほど小さく分けてファイルを読み、SQLite の読み出しと行ごとに比べること。第 3.4 節の規則に手で入れた変異が、どれもこれらのテストを赤くすること。変異を入れていない規則が 2 つあります。1 つのプロセスの中のテストではその失敗を観測できないためで、読み出しが 1 文であることと、掃除が 1 トランザクションであることです。

距離は新しい依存を足さずに第 3.2 節に従います。NumPy 2.0 以上では NumPy の bitwise_count、それより前では今の参照表です。どちらも同じ値を返し、テストがその一致を保ちます。

3.4 ファイルが正確であり続ける仕組み¶

ファイルは、ビット列を持つすべての Block の行を、作った時点の状態でキーの順に持ちます。想起は、その後に Block が変わった記録の行を SQLite から読み、それ以外の記録の行をファイルから取り、2 つをキーの順に混ぜてから、両方の上限を当てます。1 つの記録は変わったか変わっていないかのどちらかなので、2 つの部分が同じ記録を持つことはなく、変わった記録の集合が漏れなく揃っている限り、混ぜた列は SQLite の読み出しが作る列と同じです。この節の残りは、その集合を揃え続ける仕組みと、読み手が拒む状態です。

変更記録。 Block のテーブルのトリガーが、行の出来事ごとに 1 行書きます。行が挿入・削除・更新された記録と、更新で行が別の記録へ移る時はその移り先の記録もです。書き手の中の呼び出しでなくトリガーにしたのは、古い版や SQLite のシェルからの書き込みも記録するためです。
番号。 変更記録の各行は、サーバー自身の時計 (block_log_clock.head) から次の番号を取ります。 AUTOINCREMENT は使いません。その管理表は編集や消去ができ、そうされるとファイルがすでに含むと称する番号を再び配るためです。
ファイルを使っている間だけ。 変更記録が off の間、トリガーは何も書きません。作る処理が on にし、ファイルを off にして起動したサーバーが off にします。記録が off でも、トリガーは Block の行を書くたびに記録が on かを確かめます。基準機では、記録の Block を書き直す時間に off で 0.37 ms、on で 0.61 ms を足し、どちらも Block の構築の 0.02% 未満でした (結果)。 on にするたびに世代が上がり、記録の空白より前に作ったファイルは拒まれます。
作る処理。 変更記録を on にしてから、時計・スキーマの版・すべての行を 1 つのスナップショットで読み、記録用のトリガーがすべてスキーマの定義どおりに存在しなければファイルを書きません。後でする確認は作った後の変化にしか気づけず、記録が揃わないまま始まった作り直しには気づけないためです。ファイルが持てない値 (ep と mem 以外の種類、整数でないキー、32 ビットを超える Block 番号、blob でないビット列) があれば作るのを断ります。
掃除。 作った後、ファイルが含んだ変更記録の行を消し、印 (pruned_through) をその先へ進めます。これは 1 トランザクションで行い、印は上がるだけです。遅れて終わった古い作り直しが印を下げることはありません。
読み出し。 1 つの文が、変わった記録の今の行、時計、スキーマの版を返すので、どれもデータベースの同じ状態から来ます。絞り込みの条件は結合の中にあるので、条件を満たす行が 1 つも残っていない変わった記録も返り、そのファイル側の行はやはり落とされます。
拒むもの。 ファイルが無い・壊れている・幅が違う。変更記録が off、またはファイルと違う世代。スナップショットより新しいファイル (built_seq が時計より大きい)。必要な変更がすでに掃除されている。作った後のスキーマの変更 (トリガーを消して作り直すと、その間の書き込みを取りこぼしえます)。変わった記録の行が 35,000 を超える (SQLite の読み出しが調べる 25 万行より十分低く置いた上限)。ファイルが持てない値の変わった行。どれも呼び出しを SQLite の読み出しに送ります。
幅の違う行。 ビット列の幅がファイルの幅と違う行は、ビット列を 0 にして「測れない」印を付けてファイルに入ります。SQLite の読み出しと同じく両方の上限の中で位置を占め、測られることはありません。

ファイルはサーバーのキューで作り直されます。起動時と、キューが Block を書いた後に、ファイルが無い・使えない・変更記録から遅れすぎている時です。想起がそれを積むことはありません。python -m cpersona.block_index build で手で作れ、status は今の想起がそれを読めるかを報告します。

守らないもの (ここに書くことで代えます): 別のプログラムからの INSERT OR REPLACE が、SQLite の再帰トリガーが off の時に、rowid で別の記録の行を置き換えるもの (SQLite はその削除にトリガーを走らせません)。別の接続の一時トリガーが記録用のトリガーを止めるもの。時計や変更記録を手で編集すること。

4. この段に含めないもの¶

想起が短くなる時間。 上の読み出しを 10 万件のコーパスで測ってから、想起全体の数字を述べます。どちらにしても、いちばん遅いのは下のキーワードの腕です。
調べる上限を外すこと。 10 万件ではこの上限 (25 万行) がすでに効いていて、1 回の呼び出しが見るのは Block の約 7%、キーの順で先頭のものです。外すと腕が届く記録が変わるので、答えの変更として、それだけで測ります。
記録の粗探索。 同じ仕組みを別の母集団に当てるものです。
並べ直し。 この約束に含みません。
キーワードの腕。 N150 で想起のいちばん遅い腕はキーワードの腕、つまり SQLite の中の全文検索の順位付けで、この段は触りません。