連続配置埋め込み索引¶

翻訳について: 原文は英語版です。日本語版が古いときは英語版を参照してください。

ステータス: 2.5.9 で出荷済み (最初は 2.5.9a1)。スキーマのバージョンも新しいランタイム依存も増やしていません。返る答えはスキャンが返すものとビット単位で同一です (同スコア行の順序を含みます)。索引を作るのは運用者のコマンドで、サーバーは読むだけです (運用)。スキーマ 20 からは、保持する行の変更ログを通して読みます (§5)。構築後にその場で変わった行が build 時の写しのまま使われる場合は、これで起きなくなりました。

1. 何が変わり、何が変わらないか¶

ローカルのベクトル検索は、最新 MAX_MEMORIES 行をコサインで順位付けします。そのスキャンの phase 1 が、埋め込みを読み出します。

SELECT id, embedding FROM memories
 WHERE <isolation> AND embedding IS NOT NULL [AND <source>]
 ORDER BY created_at DESC
 LIMIT ?

基準のマシン・768 次元・10 万行での実測では、時間の内訳は次のとおりです。

区間	時間	占有
SQLite の行読み出し (索引順・blob 込み)	485.9 ms	72.9%
`b"".join` + `frombuffer`	162.3 ms	24.4%
行列積そのもの	18.1 ms	2.7%
同じ演算を連続配置ファイルから	95.1 ms	7.0 倍速

律速は演算ではありません。保存されたバイト列を、Python オブジェクトを 1 行ずつ作りながら numpy 配列にするところです。本設計は (id, embedding) の供給元を、 numpy が求める形にすでに並んだファイルへ移すだけで、他は何も変えません。

演算は意図して numpy のままにします。この変更の価値は「厳密であること」であり、再実装が失うのはまさにその後半です。

同じバイト列での実測で、手書きの Go 内積は numpy と 77.9% の行で不一致でした (最大絶対差 1.9e-5)。しかも Go の 2 実装同士が、94.4% の行で食い違いました。すべては総和順序の問題で、ブロック化された BLAS の順序を手書きループで再現することはできません。

ある行の内積は他のどの行にも依存しないので、mat @ query_vec の呼び出しを保つ限りスコアは同一になり、既存の等価性ゲートはそのまま効きます。

ひとつ但し書きがあります。fallback の走査を、窓をチャンクで読む形にした後で実測して分かったことです。「同じ呼び出し」は「同じバイト列を同じ形で」までを含みます。

ある行の内積は他の行に依存しませんが、BLAS は行数でカーネルを選ぶため、プラットフォーム依存の閾値を下回ると最下位ビットが動きます。Apple Accelerate では、64 次元で 64 行未満、768 次元で 16 行未満の行列が窓全体の結果と約 1 ULP 食い違い、それより大きい行列はすべてビット一致しました。

索引は選択した行を 1 つの行列として採点し、走査は今では 512 行以上のチャンクで採点します (短い尾は直前のチャンクに併合します)。したがって、どちらもこれまでに測った閾値の上に留まります。テストはこれを仮定せず、テストを実行するそのマシンで実測します。

2. 索引が保たねばならない不変条件¶

走査窓は MAX_MEMORIES のままにします。索引はコーパス全域を見ることもできますが、現在より多くの行を順位付けするスキャンは違う答えを返します。それは別のゲートを必要とする別の機能であって、本設計ではありません。

行の順序は created_at DESC、次に id ASC です。この順序が tie-break そのものです。survivors は scan 順を保ち、top-limit のカットは scan 順へ戻し、 heapq.nlargest は安定です。

しかもこれは順序だけでなく、membership も決めます。created_at を共有する行の群を limit が切るとき、生き残るのは id の小さい方です。本番コーパスでは 1.6% の行が同一 agent の別の行と created_at を共有しており (最大 9 行)、普通のテスト fixture には現れない程度に稀で、稼働中には起きる程度には多いという頻度帯にあります。

さらに、その順序を継承するのでなく明示します。現在 id ASC は、末尾列が created_at DESC である索引を SQLite が歩く副産物にすぎず、SQL は一切それを要求していません。加えて、ある軸の組み合わせは索引走査ではなくソートに解決します。ソータは安定を保証しません。

, id ASC の追加は仮定せず実測しました。ソートを誘発する項は、この作業が速くしようとしているスキャン自体の費用になるからです。結果は全ケースで同一順序・同一プランでした。測定記録: benchmarks/measurements/results-scan-order-stability.md。

スキャンの他の部分は触りません。2 段構成、hydrate 前の limit カット、isolation 軸を再適用する by-id hydrate は、すべてそのままです。

3. 索引は権威ではない¶

isolation_where() が isolation 述語の単一の出所であり続け、hydrate はそれを再適用し続けます。索引が軸の列を持つ理由はただ 1 つ、top-k のカットが hydrate より前に起きるからです。

軸を無視する索引はコーパス全体を順位付けし、hydrate が後で落とす行で top-k を埋め、短くて誤った答えを返します。バケットがコーパスに対して小さいほど、被害は大きくなります。

したがって索引はフィルタしますが、「その行が誰のものか」について正しいことは決して求められません。義務は一方向だけです。

索引候補 ⊇ 権威が認める行

索引のフィルタが	起きること	深刻度
緩すぎる	hydrate が余分を落とす	正しい。無駄なだけ
厳しすぎる	行が気づかれずに消える	検出不能な recall 損失

守るのは片側だけなので、機械検査できます。ランダムなコーパスとランダムな軸値で包含を assert し、故意に厳しくした索引でそれが赤くなることを変異で確認します。

4. ファイル形式¶

ヘッダと、それに続く固定幅の並走配列です。

部位	内容
ヘッダ	マジック、形式のバージョン、次元、dtype、行数、watermark、build 時点の変更ログの位置 (§5)、および埋め込みモデル・次元・スコアリングのバージョンにわたる fingerprint
`embeddings`	`float32[count][dim]`、連続配置、正規順序
`ids`	`int64[count]`
`agent_code` / `project_code` / `channel_code` / `source_code`	`int32[count]`、ヘッダ内の小さな文字列表に intern
`created_at`	固定 19 バイト ASCII、列の正規形 `YYYY-MM-DD HH:MM:SS`

agent_code は isolation 述語が等値で比較する軸を担い、残る 3 つは小さな集合との比較になります。いずれにせよ、行ごとの判定は整数の比較です。

軸は低カーディナリティなので、intern は安価です。本番コーパスで agent 7 種・ project 12 種・channel 15 種・source id 38 種。軸一式で 1 行あたり 16 バイト、隣にある埋め込みは 3,072 バイトです。

source_code が存在するのは、カーディナリティを仮定せず実測したからです。source フィルタは JSON フィールドとの照合 (1 つの id なら完全一致、名前空間なら前方一致) で、一見「索引には無理なもの」に見えます。しかし値が 38 種なら、照合は文字列表に対して小さなコード集合へ解決でき、行ごとの判定は整数の所属判定になります。これが無いとマルチユーザー会話からの recall はすべて旧経路に落ち、それは実トラフィックの相当部分にあたります。

形式で表現できない行は、落とさずに列挙します。正規の 19 文字形から外れた created_at (import 経路が復元レコード自身の値を持ち越します) は配列から除外し、その id をヘッダに列挙します。クエリ経路は後述の tail 読み出しにその列挙を合流させるので、行は到達可能なままです。

列挙には上限があり、超えたらビルダーは構築を拒否します。穴の空いたコーパスを、知らせずに提供するより、現行経路に留まるほうが正しいからです。本番コーパスではこの列挙は空でした。両テーブルとも、created_at はすべて正規形です。

固定幅 ASCII であることが、merge を安全にしています。SQLite はこれらの値をテキストとして比較し、この形式の同一長文字列では、バイト比較と時系列比較が同じ比較になります。

読み込み側は各配列を np.memmap で写しますが、Windows では写さずにメモリへ読み込みます。 Windows はメモリに写されたままのファイルの置き換えを拒否し、サーバーは読み込んだ索引を動いている間ずっと持ち続けるので、写す方式では、検索したことのあるサーバーが動いている間の再構築がすべて PermissionError で失敗していました。読み込む方式は再構築が置き換えるファイルにハンドルを残しませんが、費用はかかります。サーバーが索引を持っている間、すべてのエージェントの行と float32 の行列を含むファイル全体がメモリに常駐します。これが代わりを務める走査は、1 つのエージェントの窓を 1 チャンクずつしか持ちません。100 万行・ 1,024 次元では約 4.1 GB です。再構築の後の読み直しは、新しいファイルを読む前に古いコピーを手放すので、2 つが同時に常駐することはありません。

どちらの方式でも、読み込み側はファイルを 1 回だけ開き、ヘッダ・サイズの検査・すべての配列をその 1 つのハンドルから取ります。再構築は新しいファイルを同じパスに移すので、配列ごとにパスを開き直す読み込み側は、その移動が 2 つの配列の間に入ると、新しいファイルのバイトを古いヘッダのオフセットで読んでしまいます。

5. 鮮度 — watermark¶

記憶システムにとって、古くなった索引は遅い索引より悪いものです。1 時間前に構築された索引は直近 1 時間の記憶を、知らせずに落とします。そしてそれは最も引かれやすい記憶です。

索引は構築時点の最大 id を記録し、その watermark 以下の行にしか答えない。スキャンはそれを超える分を SQLite から厳密に読む。

ここから次の 5 つが導かれます。これが「再構築スケジュール」ではなく本設計である理由です。

新しい記憶が見えない窓が存在しなくなります。「窓が小さい」ではなく、窓が無いということです。
再構築の頻度が correctness の問題でなくなり、純粋な性能のつまみになります。遅れれば tail が伸びてレイテンシが観測可能に劣化するだけで、誤った答えは返しません。
tail は厳密です。最も引かれやすい最新の行が、派生物から提供されることはありません。
削除に索引側の経路が一切不要です。構築後に消えた行はファイルに残ります。下の変更ログがその行を名指しし、クエリは窓を切る前にそれを選択から外すので、 scan と同じく窓の位置は次の行に渡ります。索引に delete も修復も compaction も要りません。破損したら捨てて作り直します。
tail の読み出しは SQLite が最も得意な形 (索引順の最新数行) です。

watermark が答えられる問いは 1 つで、重要な問いはそれだけではありません。 watermark が示せるのは「その行が build 時に存在したか」であり、「その行が build 時に embedding を持っていたか」は示せません。

ベクトルがまだ NULL で builder が飛ばした行では、この 2 つが分かれます。その行は行列に入らず、id は watermark 以下なので tail も読まず、保守が embedding を埋めた瞬間に scan は返し、索引は返さなくなります。これは本節が冒頭で否定している「誰にも気づかれずに取りこぼす」状態そのもので、しかも到達経路は check_health(fix=True) です。その prefetch は、まさにそういう行を埋めるために存在します (bug-278)。

そこで build は、それらも列挙します。unembedded_ids がヘッダで excluded_ids の隣に並び、同じ exact な tail 読み出しに乗ります。上限は 2 つのリストの合計に掛かります (同じ文にバインドされるためです)。超えたコーパスは、自分の穴を列挙できない索引を出荷するのではなく、build を見送ります。

どちらのリストにも見えない変更は、変更ログが名指しします。build が保持した行はその場で変わることもあります。update_memory は同じ id に新しい本文と新しいベクトルを書き、埋め込み欠落の修復はファイルが既に持つ行にベクトルを書き、再タグ付けは行を別の project・channel・agent へ移し、修復は時刻を書き換え、あるいは行が削除されます。 watermark はそのどれも示せず、ファイルは build 時のベクトルと軸でその行を順位付けし続けます。

そこで memories と episodes のトリガー (スキーマ 20) が、写している列 (ベクトル、 4 つの軸、created_at、記録では coarse 索引が期間を絞る timestamp) が変わった行と、削除された行の id を記録します。挿入は記録しません。id は AUTOINCREMENT から来るので、新しい行は最初からどの watermark よりも上にあります。各ファイルは build 開始時のログの位置 (世代・ログの先頭・スキーマ cookie) を持ちます。クエリは 1 つの文で、その先頭より後に記録された id を読み、窓の上限を取る前にファイルの選択から外し、 tail や列挙済みの穴と一緒に exact に読みます。こうして各行は今の位置と今のスコアを取ります。

このログは block 索引の設計をこれらのファイルに当てたもので (block 契約 §3.4)、 3 つのファイルで時計を 1 つ共有します。ログが動くのはファイルがある間だけです。 build は最初の行を読む前にログを有効にするので、build が見落としうる書き込みはどれもより大きい番号を持ちます。ファイルが 1 つも残っていなければ、サーバーは起動時にログを止めます。build がファイルを公開した後、存在するすべてのファイルが既に持っているログ行は捨てられます。ログがファイルを保証できないときは、クエリは scan に渡します。build 以降にログが止まった・再開した、ファイルに要る変更がすでに捨てられた、ログの先頭がファイルより後ろ (古い複製から戻したデータベース)、スキーマ変更 (トリガーを落として作り直すと書き込みを取りこぼしうる)、変更行が列挙穴の上限を超えた、のいずれかの場合です。

選んだ行の embedding が消えた・行が削除されたことを検出する 2 つの probe は、ログが名指ししない変更への後ろ盾として残ります。その範囲形式はログが名指しした id を飛ばすので、記録済みの穴を含む id の連なりも連なりのまま問い合わせます。

merge は ordered merge であって concatenation ではありません。tail は索引より一様に新しいと仮定して前に繋ぎたくなりますが、それを保証するものはありません。

import 経路は復元レコードの元の created_at を持ち越す一方、id は AUTOINCREMENT で新規採番されます。そのため、古い export を既に新しい行を持つ DB に戻すと「新しい id × 古い created_at」が生まれます。本番コーパスに現在その逆転はありませんが、それは誰にも気づかれずに真でなくなる類の事実です。

両側とも既にソート済みなので、(created_at DESC, id ASC) で merge しても前置と費用は変わらず、この故障モードだけが消えます。

6. 不在・破損・次元不一致¶

索引は最も強い意味で任意です。置き換えられる側のスキャンはそのまま残り、正しいままであり、フォールバックであり続けます。3 つの条件がそこへ戻します。ファイルが無い、ファイルが自身の整合検査 (マジック、形式のバージョン、ヘッダが次元と行数を示すこと、行数とファイル長の一致) に落ちる、クエリベクトルの次元がヘッダと一致しない、の 3 つです。 fingerprint は比べません。その中の埋め込みモデル名はファイルを読む人のための記録で、守っているのは次元です。

モデル入れ替えの途中で残る混在次元のコーパスは第 4 の条件で、これは読み手ではなくビルダーが拒否します。

現行スキャンは、幅違いの行を skip する前に窓を適用します。最新 MAX_MEMORIES 行の中で生き残ったものを順位付けするということです。単一幅しか持たない索引は、他の幅が存在する限り、その窓を再現できません。自分の幅の最新 MAX_MEMORIES 行を順位付けてしまうからで、それは行数が増えるということです。各行のスコアが同一でも、行数が違えば答えが違います。

よってコーパスが混在している間は、ビルドを拒否します。この状態は構造的に一時的で、その間ずっと、この索引が置き換える側のスキャンは正しいまま (ただ遅いだけ) です。それこそ、本設計全体が安全に行おうとしているトレードオフです。

フォールバックは見えなければなりません。痕跡がログ 1 行だけなら、1 週間使えなくなっている索引は「なぜか速くない」としか読めません。このプロジェクトが、既に一度犯した失敗です。この条件は、システムの健全性を読む者が出会う場所に報告します。

7. 本設計が意図的に含まないもの¶

あらゆる近似。量子化も近傍近似も行いません。それらで得られるのは常駐メモリの節約であり、「どこまでの劣化を許すか」という別の問いを伴う別の問題です。混ぜれば、この変更を既存スイートで検定可能にしている厳密性を失います。
第 1 弾での episodes。ただし、その後も外したままにはしていません。episode 側のスキャンは構造的に同一で、形式もそのまま適用できましたが、episodes は行数の 5 分の 1 だったので、第 1 弾は memories だけを索引化し、次の一手は測定に委ねました。

測定の答えは、索引の無い episode スキャンが、5 倍の行数を持つ索引済み memory スキャンよりクエリあたり高い、でした。そこで episode テーブルも自分の索引ファイルを持ち、同じ読み出し経路で供給されます。episodes には source 列が無いので、読み出し経路は索引を引く前に episode スキャンの source 規則を適用します。索引がテーブルに無い列を問われることはありません。 - 修復。索引は派生物です。backup せず、直しもしません。削除して作り直します。 - 構築後の再タグ付け: もう対象外ではありません。行を別の project / channel へ移すと、以前は索引の軸列が次の再構築まで古いままで、厳しい方向では行を取りこぼし、稀なこととして受容していました。§5 の変更ログがその行を名指しし、クエリはそれを live で読みます。

8. どう検定するか¶

等価性ゲートは既に存在します。本リポジトリのベンチマークハーネスは連続行列を事前ロードし、同じ mat @ q を呼び、無改変の検索と 2 つの水準で比較します。結果 id 列とそのコサイン、そして recall 経路全体の message id 列を、実コーパス上で比較します。これは置き換えではなく、バックエンドの追加として使います。

既存ゲートには見えないものが 2 つあるので、それを足します。

同スコア行。十分に分離したベクトルのコーパスは、どんな tie-break でも同じ順位になります。等しい類似度の行を含む fixture を与えなければ、ゲートは一度も試していない順序を「一致」と報告します。
軸付きクエリ。既存ハーネスは channel / project / source フィルタがあると元の関数にフォールバックするので、軸を持つ呼び出し (つまり実運用のほぼすべて) は一度も通っていません。

等価性ゲートと包含 assert の両方を、変異で確認します。故意に 1 箇所崩した順序はゲートを赤くしなければならず、故意に厳しくした索引は包含テストを赤くしなければならず、各変異が自分の検査だけを殺すことを確認します。