中年engineerの独り言 - crumbjp

LinuxとApacheの憂鬱

dockerコンテナ(ubuntu 20.04 LTS arm64)内でChromiumを動かすのが大変だった件

経緯

ubuntu 18.04 LTSのサポートが1年を切ったのでubuntu 20.04 LTSにアップデートしようとしていた。

実サーバー側の検証はそれ程大きな問題はなかったがCI環境でE2Eテストを行う部分で、コンテナ内でChromium headlessを使っており、これが思いの外難産だった。

技術的背景

1. Google Chromeが使えない

本来、googleがバイナリ配布しているChromeが使えれば良いのだが、Linux arm64バイナリは提供されていない。 なのでChromiumを使う必要がある

2. Ubuntu 19.10以降、ChromiumのAPT(deb)パッケージが廃止

バイナリはsnap版に移行し、debパッケージはsnap installに迂回するようになった。

ubuntu.com

3. Dockerコンテナ内でsnapが使えない

普通にDocker buildするとsnapdが立てられないのでsnap install が失敗する。

# snap install chromium
error: cannot communicate with server: Post http://localhost/v2/snaps/chromium: dial unix /run/snapd.socket: connect: no such file or directory

解決法

Dockerコンテナでsnapdを動かす

偉い人が作ったDockerコンテナジェネレータがあったので、これを改造して使ってみた。

github.com

これを紐解くと以下のようなDockerfileになる。

なるほど、、systemd経由でsnapdを起動する構造はそのままで、/sbin/init から上げて行くわけね。

Dockerfile

FROM --platform=linux/arm64 ubuntu:20.04
ENV container docker
ENV PATH "/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/snap/bin"
ENV LANG C.UTF-8
ENV LC_ALL C.UTF-8
RUN apt-get update && DEBIAN_FRONTEND=noninteractive apt-get install -y fuse snapd snap-confine squashfuse sudo init && apt-get clean && dpkg-divert --local --rename --add /sbin/udevadm && ln -s /bin/true /sbin/udevadm
RUN systemctl enable snapd
VOLUME ["/sys/fs/cgroup"]
STOPSIGNAL SIGRTMIN+3
CMD ["/sbin/init"]

ハマった点

無事snapdは上がり、snapコマンドは通る

snap list
Name  Version                      Rev    Tracking     Publisher    Notes
core  16-2.56.2+git3949.06393d8a6  13434  latest/edge  canonical**  core

ところが、実際のinstallは失敗する

# snap install chromium
error: cannot perform the following tasks:
- Run configure hook of "chromium" snap if present (run hook "configure": aa_is_enabled() failed unexpectedly (No such file or directory): No such file or directory)

調べていくと、workaroundを提示している人が居た

github.com

# mount -t securityfs securityfs /sys/kernel/security

確かに、/sys/kernel/security が空だったのでmountすることで見事に解決した。

# snap install chromium
chromium 102.0.5005.115 from Canonical✓ installed

しかしDockerfileで解決出来ないのは困ったな。。

MongoDBの統一トポロジー(useUnifiedTopology)について

最近のMongoDBドライバーはエラーが出る

(node:8746) [MONGODB DRIVER] Warning: Current Server Discovery and Monitoring engine is deprecated, and will be removed in a future version. To use the new Server Discover and Monitoring engine, pass option { useUnifiedTopology: true } to the MongoClient constructor.

で、その新トポロジーの説明はこれ。

mongodb.github.io

すごくザックリ内容を紹介すると

  • 接続中(connected)という状態とはなんぞや?
  • 実際のネットワークが接続状態という事に意味はあるのか?
  • 別にになっていなくても処理可能な状態を保っていれば良いよね?
  • だからisConnectedも将来廃止するよ。
  • 直ちに処理出来ない状態でもドライバー内でなんとか辻褄取るよ
  • でも失敗したら30秒位でエラー返すよ

なので、useUnifiedTopologyautoReconnect を両方指定すると怒られる。

(node:8962) [MONGODB DRIVER] DeprecationWarning: The option `autoReconnect` is incompatible with the unified topology, please read more by visiting http://bit.ly/2D8WfT6

新しいトポロジーでは、利用者側は接続状態を気にしなくて良い事になっているからね。

ザックリ図解

現行ReplicaSet

f:id:hiroppon:20211124122931p:plain readPreferenceに合致するコネクションを割り当てる事しかしない。

一度コネクションを取得した後は素通し。

コネクションプール内のコネクションが全部エラーで破棄されるまでエラーが続く。

新統一トポロジー

f:id:hiroppon:20211124122936p:plain 1層咬んでいるのでエラーにならない所を勝手に探してくれる。

全部ダメならタイムアウトserverSelectionTimeoutMS までリトライする。

実際の挙動

createConnection

現行ReplicaSet

require('mongoose').createConnection('mongodb://localhost:27017/foo', {
  autoReconnect: true, 
  readPreference: 'secondaryPreferred'
})

直ちにエラーが帰る

MongoNetworkError: failed to connect to server [localhost:27017] on first connect [Error: connect ECONNREFUSED 127.0.0.1:27017
    at TCPConnectWrap.afterConnect [as oncomplete] (node:net:1161:16)
    at TCPConnectWrap.callbackTrampoline (node:internal/async_hooks:130:17) {
  name: 'MongoNetworkError'
}]

新統一トポロジー

 require('mongoose').createConnection('mongodb://localhost:27017/foo', {
  useUnifiedTopology: true, 
  readPreference: 'secondaryPreferred',
  serverSelectionTimeoutMS: 30000,
})

約30秒後にこうなる

> Uncaught MongooseServerSelectionError: connect ECONNREFUSED 127.0.0.1:27017
    at NativeConnection.Connection.openUri (/****/node_modules/mongoose/lib/connection.js:847:32)
    at Mongoose.createConnection (/****/node_modules/mongoose/lib/index.js:291:17) {
  reason: TopologyDescription {
    type: 'Unknown',
    setName: null,
    maxSetVersion: null,
    maxElectionId: null,
    servers: Map(1) { 'localhost:27017' => [ServerDescription] },
    stale: false,
    compatible: true,
    compatibilityError: null,
    logicalSessionTimeoutMinutes: null,
    heartbeatFrequencyMS: 10000,
    localThresholdMS: 15,
    commonWireVersion: null
  }
}

fetch

図解の通りに動くので、動作確認のコード例だけ。

このコードを動かしてレプリカセットのノードを落としたり上げたりすればいい。

新統一トポロジーの方は全ノードを落として、再起動せずにタイムアウトに抵触するまではエラーが出ない。

現行ReplicaSet

let conn = null;
require('mongoose').createConnection('mongodb://localhost:27018/foo', {
  replicaSet: 'RS',
  autoReconnect: true,
  readPreference: 'secondaryPreferred'}).then(r => conn=r).catch(r => console.log('---', r));
(async () => {
  for(let i = 0; i < 100000;i++) {
    try {
      let r = await conn.db.collection('tests').findOne({i: 1});
      console.log(i, r);
    } catch(e) {
      console.log(e);
    }
  }
})();

新統一トポロジー

let conn = null;
require('mongoose').createConnection('mongodb://localhost:27018/foo', {
  replicaSet: 'RS',
  useUnifiedTopology: true,
  readPreference: 'secondaryPreferred'}).then(r => conn=r).catch(r => console.log('---', r));
(async () => {
  for(let i = 0; i < 100000;i++) {
    try {
      let r = await conn.db.collection('tests').findOne({i: 1});
      console.log(i, r);
    } catch(e) {
      console.log(e);
    }
  }
})();

注意

良い改善だとは思うが、ハイロードな環境下では、30秒ものオペレーションを貯めたり再送して重複処理するのは危険極まりない

しっかり設計せずに移行するのは危険だ。

10TBクラスのmongodb ReplicaSet 運用ナレッジ

オススメの構成

[primary]
  - priority = 2
[secondary]
  - priority = 1
   :
 (必要なだけ) 
   :
[backup]
  - priority = 0
  - hidden = true

POINT

1. Primaryが好き勝手変動すると運用上の取り回しが悪いのでなるべく同じノードがPrimaryになるようにする

2. バックアップ中はOplog反映遅延が起こるのでクライアントクエリーをさせないhidden属性にしておく

3. 増強やバックアップや復旧を円滑に行うため、全てのノードでデータディレクトリは別のEBSボリュームにしておく

 

 例えば10TBクラスのEBSでヘビーユースのReplicaSetだと毎日差分スナップショットを取っても4時間ほど掛かりバックアップ後にOpTimeが追いつくまで5~6時間かかる。

スナップショット(バックアップ)のとり方

データ整合性を確保するために、スナップショット中の書き込みを抑止する必要がある。

rs:PRIMARY> db.fsyncLock();

** ここでスナップショットを取る **

rs:PRIMARY> db.fsyncUnlock();

スクリプトにしてcron.dailyにでも放り込んでおくと良い

#!/bin/bash
cd /path/to
bash snapshot.sh --tmp
mongo --host backup-prd1 -u root -p `cat safe_file` <<<'db.fsyncLock()';
bash snapshot.sh
mongo --host backup-prd1 -u root -p `cat safe_file` <<<'db.fsyncUnlock()';

EBSの場合、差分スナップショットなので直前に一回捨てスナップショットを取っておくと差分が小さくなり、lock期間を短くする事が出来る。

snapshot.shは、awsコマンドなりSDKなりで適当に実装すればいい

Oplog設定・設計

config
replication:
  oplogSizeMB: 614400 #600GB
起動中に変更する場合
db.adminCommand({replSetResizeOplog: 1, size: 614400})
サイズの決め方

以下のコマンドで確認しながら最低3日分位は確保する。理由は当記事を読んでいけば解る。出来れば7日分程度欲しいが更新が激しい場合は非効率になってしまう場合もある。

rs:PRIMARY> rs.printReplicationInfo()
configured oplog size:   614400MB
log length start to end: 183206secs (50.89hrs)
oplog first event time:  Mon Jul 05 2021 21:52:36 GMT+0900 (JST)
oplog last event time:   Thu Jul 08 2021 00:46:02 GMT+0900 (JST)
now:                     Thu Jul 08 2021 00:46:02 GMT+0900 (JST)

うわ。。足りてないね・・・

oplog first event time がこのノードが保持している一番古いOplogなのでこれ以上遅れてしまったSecondaryはもう同期出来なくなる。

遅延状態の確認方法
rs:PRIMARY> rs.status().members.map((member)=> [member.name, member.optimeDate.toLocaleString()])
[
        [
                "primary-prd1:27017",
                "Thu Jul  8 00:16:10 2021"
        ],
        [
                "secondary-prd1-prd4:27017",
                "Thu Jul  8 00:16:09 2021"
        ],
        [
                "secondary-prd2:27017",
                "Thu Jul  8 00:16:09 2021"
        ],
        [
                "secondary--prd3:27017",
                "Thu Jul  8 00:16:09 2021"
        ],
        [
                "backup-prd1:27017",
                "Wed Jul  7 16:18:33 2021"
        ]
]

ノードが壊れた場合

パターン

1. データファイル破損

エラーになってmongodが起動しない

 → ノード再構築

2. [rsBackgroundSync] replSet error RS102 too stale to catchup...

反映しなければならないOplog古すぎ、ReplicaSetメンバーの誰も持っていない

状態は1. と同じ。

3. [initandlisten] Taking 999 samples and assuming that each section of oplog contains approximately...

mongodを再起動した際に、エラーにはならないがこのログで止まる

 → ひたすら待つ。1日待っても良い。Secondary復帰後もOplog反映が遅くどんどん遅延して行くが1日位で正常なパフォーマンスに戻り追いつき始める

ノード再構築

1. 単純にデータディレクトリ以下を全て消す

この場合のmongodの挙動は以下

1. mongod起動(STARTUP2)

2. 他のreplicaSetメンバーから接続され同期が始まる(STARTUP2)

3. 同期元のノードからCollection毎にデータ取得 -> Index構築 を繰り返す(STARTUP2)

4. 全てのDB/Collectionの構築が終わったら2.時点のOplogを起点に差分を反映する(STARTUP2)

5. Oplogが追いついたら完了(SECONDARY)

 大きなCollectionでIndexが大量あれば、3.は時間がかかる。

 私の運用しているReplicaSetでは余裕で2週間はかかるのでOplogを巨大にしない限り4.の段階で Stale となる。

 それをやったとしてもOplogが追い付くまでに掛かる時間も膨大で完了まで1ヶ月以上は覚悟しなければならない。

 TBクラス以上の大きなReplicaSetでは現実的ではない。

2. なるべく新しいスナップショットからデータディレクトリを復旧(本命)

この場合のmongodの挙動は以下

1. mongod起動(STARTUP2)

2. データディレクトリ上の最後のcheckpointの状態でデータ復旧。1日近く掛かる事もある

3. 2.終了時に直ちにSECONDARYとなるがSnapshotを取った時点のデータなのでOpTimeが激しく古い状態(SECONDARY)

4. 通常のReplicaSetメンバーと同様の扱いでOplog反映を始める(SECONDARY)

 3. の時点でクライアントクエリーを処理するとセマンティック上の問題が起きるので、プロセス起動前に rs.reconfig() を行いhiddenノードにしておく必要がある

 4.が始まっても原因不明のパフォーマンス劣化状態が続く。1日程度で通常のパフォーマンスになるので3日分程度のOplogは必ず確保する必要がある。

Oplog遅延見積もり
snapshotに掛かる時間(5時間)+(3.)に掛かる時間(24時間)+(4.)開始後24時間で2時間程度しか反映が進まない
= 5 + 24 + 24 - 2
= 最大51時間遅延する

手順

SECONDARYが壊れたら?

1. rs.reconfig() で壊れたノードをhiddenに変更する

2. dailyで取っているバックアップノードのスナップショットからノード再構築

3. rs.reconfig() で再構築したノードのhiddenを解除する

バックアップノードが壊れたら?

1. rs.reconfig() で1つのSECONDARYをhiddenに変更する

2. hiddenセカンダリーの捨てスナップショットを2〜3回取る(1回目はフルスナップショット、2回目は長時間のフルスナップショット分の差分、3回目は2回目のスナップショットも本来最短で取れる差分よりは大きい分の差)

3. fsyncLock() を掛けて本スナップショットを取り完了後にfsyncUnlock()

4.3.のスナップショットからバックアップノード再構築

5.3.で起きた遅延が解消したら、rs.reconfig() で再構築したノードのhiddenを解除する

ARM環境まとめ

最近のARM(aarch64)周り

この1年で本番環境を全てarm64サーバーに切り替えたりDocker環境を作ったりしてarm64周りのナレッジが溜まってきた。

ハマり続けたメモ。思い出したら追記する

ブチ当たった問題の情報がネットに無い場合も多く、もしかしたらarm64周りを弄ってるエンジニアの中でもカッティングエッジに近い所まで来てるんじゃないかな・・・・

ビジネス環境

勢いがある。時間を先行投資する価値を感じる。

株主不安

SoftbankがARMの競合と目されているNVIDIAへ売却

AWS

Graviton2インスタンスが提供されており、intel CPUインスタンスより2割程安く、HWアクセラレータ周りも充実している

ElasticCache(Redis)

5%程割安で、しかし明らかに2倍くらい速度が遅い。

Redisは1CPUしか使わないので影響が出やすいのと、Speculative_executionの差なのか?

Apple

M1チップ搭載のMacが販売開始

Linux

amd64 / arm64

良く目検に失敗する・・・aarch64に統一してほしい・・・

Ubuntuパッケージ

ミラーサーバーがaarch64をサポートしていない場合がある

原因特定までメチャクチャ時間がかかる

Ubuntu 日本語環境

ubuntu-ja.listが使えない

Docker on Mac

ARM版のLinuxも一応動く

しかしカーネルエミュレータ周りの互換性がイマイチでそこかしこでエラーを吐く

遅い、固有の問題多すぎ。

互換性に問題のあるdockerコンテナなぞ価値なし!

Chrome

Chromeが提供されておらず、Chromiumを使うしかない

Ruby webdrivers

何も考えずx86_64のライブラリを引っ張ってきて起動でコケる

Feature specではOSにインストール済みのChromiumをバイナリを使う

JS karma

環境変数CHROME_BINにインストール済みのChromiumバイナリのパスを指定

JS puppeteer

launchのパラメータexecutablePathにインストール済みのChromiumバイナリのパスを指定

screen

化石エンジニア御用達の仮想コンソール

なぜかアタッチに分単位の時間がかかる

ElasticSearch

docker imageは7.8以降のみ対応

完全対応は7.13以降

大体、2020年6月以前のバージョンは非対応

7.13も起動が異常に遅い問題を確認している

rubyjs/libv8

https://github.com/rubyjs/libv8/issues/261

RailsでJS実行する際に必要だがビルド出来ない問題が2018年から放置

docker使って自前ビルドしたlibv8をvender/cacheに放り込ん動かす

1時間超えのCIを10分以下にした話

経緯

app.wercker.com

今までwercker を使っていたのだが、数年前は良いサービスだったのにOracleなんかに買われたせいで最近はインスタンスが目に見えて遅かったり、不安定だったりやってられないので、引っ越しを検討していた。

比較したサービス

wercker

最近明らかに遅いインスタンスが混ざり込む様になった

(超相乗り状態?)

  • 並列実行数=2
  • 1vCPU 2GB RAM
無料プランのみ??

情報が出てこない・・・

CircleCI

circleci.com

言わずと知れた最大手。CI業界の基準

ピュアなコンテナ環境ではなさそう(chrootっぽい何か?)

その影響か、ホストのカーネルの問題か解らないが、稀にCircleCI無いでしか起きないSEGV等が起きたり互換性周りの面倒事が起きる。

実行環境のリソースは細かく選択でき、料金が異なる。

料金はクレジットの単位で設定されており

25000クレジット$15で購入するので

$15 / 25000credit = $0.0006 / credit

resource class
Class vCPUs RAM credit
small 1 2GB 5 / 分
medium (default) 2 4GB 10 / 分
medium+ 3 6GB 15 / 分
large 4 8GB 20 / 分
xlarge 8 16GB 40 / 分
2xlarge(2) 16 32GB 80 / 分
2xlarge+(2) 20 40GB 100 / 分

なぜか、料金表が見当たらず、、赤字は予想。

Free Plan
  • 無料枠 2500 クレジット / week
  • 並列実行数=1
  • 3ユーザまで
  • Mediumのみ

よって無料枠は

 250分 / 週 = 4.2時間 / 週

  • パブリックリポジトリの場合 400000クレジット/月を付与
Performance Plan

クレジットの使用 - CircleCI

  • 並列実行数=80
  • 3ユーザ($15)+ ユーザ毎($15)
  • Docker レイヤー キャッシュへのアクセス(実行毎200クレジット)
  • 1口辺り25000クレジット($15)x 毎月最低2口 = $30〜

仮にsmallを100時間稼働させた場合(他にも、dockerイメージのキャッシュで実行毎200クレジット掛かったりするが、イメージDLと実行時間の相殺の問題なので一旦無視。)

 (ユーザ料金)$15 + 6000分 * 5credit * $0.0006 = $33(支払いは$45)

となる。

スタートアップなら此位で収まるプロダクトも多いだろう。

エンジニアが少ない場合でも、多い場合でも、ユーザ毎$15が重くなりがちな料金体系(少数エンジニアで生産性が高ければお得)

セルフホスティング

どうやら自前のホスティング環境で実行することも出来るようだが、わざわざCircleCIを選ぶ理由が思いつかないので、調べていない。

Github actions

github.co.jp

今まで仲良くしていたCIサードパーティに手の平を返して牙を向いたGithub様の刺客!

バックエンドはMicrosoft Azure。

明らかにインフラリソースの優遇を受けているであろうダンピング価格でCI環境を提供している。

パブリックリポジトリは全部無料

プライベートリポジトリでも巨大な無料枠が用意されている。

rootのHOMEが"/home/github" になっておりイメージの環境調整が面倒

プライベートリポジトリの場合は、JOBの実行時間とストレージ使用量がそれぞれ無料枠+従量の料金体系になっている。CIとして使う場合はストレージ使用量は気にならず、JOB実行時間だけ考えれば良い。

ジョブ実行時間の従量部分は 0.008$ / 分

Free
  • 無料枠2000分 / 月、ストレージ500MB
  • 並列実行数=20
Pro(月額$4)
  • 無料枠3000分 / 月、ストレージ1GB
  • 並列実行数=20

仮に100時間稼働させた場合(細かいことを言えば、どのCIを使おうが掛かる月額4$は除外しても良いが・・・)

 $4 + 3000分 * $0 + 3000分 * $0.008 = $28

一見、CircleCIより少し安い位だけど、プルリが少なくて50時間程度だった場合はほぼ無料になってしまう。

セルフホストランナー

サーバを自前で用意する。無料

CIが走った時にspot instanceでランナーを起動したいが、ランナーをGithubに接続する際に必要なワンタイムトークンを生成するAPIが提供されていないので困難。

github.community

実際の引っ越しの成果

元々の状態

f:id:hiroppon:20210611022858p:plain:w600

71分、これは早いインスタンスを引いた時で、ハズレを引くと3倍遅いしハズレ率が5割以上。

安定しないCIなんぞ糞である

Github actionsに引っ越し

f:id:hiroppon:20210611023513p:plain:w600

65分、あまり変わらないように見えるがハズレが無く安定したのでかなりのストレス軽減

だが、、もっと早くなるのが解っている!

並列化

.github/workflows/main.yml
name: CI
on:
  push:
    branches: [ master ]
  pull_request:
    branches: [ master ]
  workflow_dispatch:
jobs:
  test:
    runs-on: ubuntu-latest
    strategy:
      max-parallel: 12
      matrix:
        test_script:
          - run_sherpajs.sh
          - run_sherpa_server.sh
          - run_sherpa_admin_advertisement_br.sh
          - run_sherpa_admin_advertisement_br_multi.sh
          - run_sherpa_admin_advertisement_br_movie.sh
          - run_sherpa_admin_advertisement_sn.sh
          - run_sherpa_admin_advertisement_internal.sh
          - run_sherpa_admin_action_widget.sh
          - run_sherpa_admin_campaigns_sherpa.sh
          - run_sherpa_admin_campaigns_company_user.sh
          - run_sherpa_admin_others.sh
          - run_sherpa_admin_report.sh
    container:
      image: crumbjp/sherpa_ci
      credentials:
         username: crumbjp
         password: ${{ secrets.DOCKERHUB_PASSWORD }}
    steps:
      - uses: actions/checkout@v2

      - name: prepare
        run: bash ci/prepare.sh

      - name: services
        run: bash ci/services.sh

      - name: run ${{ matrix.test_script }}
        run: bash ci/run_parallel.sh ${{ matrix.test_script }}

マトリックスを使うと並列テストが作れる。

f:id:hiroppon:20210611023953p:plain:w600

12分!これが無料だから恐ろしい!!

しかし12並列ともなると10分のテストで120分ものジョブ時間を消費するので、我々の開発状況では3000分の無料枠は数日で使い切ってしまった。このペースだと従量課金で$300/月程度になりそうなのでセルフホストランナーも検討。

t4g.medium (vCPUx2 4GB RAM) x 720時間 = $31.1

2ランナー/サーバー x 6 = 12ランナー $186.6

コスト的には検討に乗りそうだ。

ARMのdocker imageは色々苦労があるがそれはまた別の機会に・・・

f:id:hiroppon:20210611023948p:plain:w600

中を見るとInitialize containers(docker イメージDL)に結構時間を掛けている。

Githubが用意しているランナーに我々のdockerイメージがキャッシュされている可能性はほぼ無い。

セルフホストランナーであればここが削れるはずだ。

セルフホストランナー化

f:id:hiroppon:20210611113343p:plain:w600

10分切った!

我々のプロダクトでは固定のStaging環境を維持しており、これをセルフホストランナーに流用して元々余らせていたリソースを活用。

本番サーバーでもリザーブインスタンスの期間の関係でリソースを余らせているサーバーを幾つか見繕って流用。 (一時的な処置)

結果、実質の出費無しで12本のランナーを確保することができた。

f:id:hiroppon:20210611115512p:plain:w600

目論見通りInitialize containersは数秒に収まっている。

またランナーにジョブが飛んでくるまでに30秒〜2分位のラグがあるようだ。

ローカルマシンより早い

今までローカルテストで確認してからプルリを作っていたが、もうカジュアルにプルリ作ってCIでテスト通す方が楽。 しかも料金は気にしなくて良い。

開発スタイルがガラっと変わりました。

もう腿を火傷する必要は無い!!

まとめ

1. CI環境は多くの場合、github actions が良い選択

2. ヘビーユースならばセルフホストランナーの方が良い

3. 並列テスト最高

Faiss解説シリーズ(第三回)パフォーマンス

crumbjp.hateblo.jp

インデックス毎の性能と精度のバランスを取る上で考慮すべき要素

モリー使用量

Faissインデックスは基本的にオンメモリー上で処理を行う。

すべてのデータが何らかの形でメモリー上に展開できなければならない。

これが最優先事項

Flatにデータを展開して物理的に乗らないようならば次元圧縮などを用いてデータ量の削減をしなければならない。

インデックスにリンク構造(HNSW等)を採用するならばその分のメモリー設計も必要となる。

検索速度、ベクトル追加速度

オンラインの高速応答が必要なのか、非同期処理である程度遅くとも精度を重視するのかで大きく選択肢が異なる。

ベクトルの変換やエンコードなどを行う場合は、モリー使用量とトレードオフの関係になり易い

レーニング時間、検索精度

ベクトルの変換やエンコードをする場合は、その処理が複雑になればなるほどトレーニング時間が必要となる。

精度面は神経質になるとキリがないので、ANN検索と割り切って用途として許容し得る最小限の精度に抑えた上で上記のバランスを取れる選択肢を検討していく方が設計し易いだろう。

コード解説

テストデータ

データ生成プログラム(JS)

'use strict';
const _ = require('lodash');
const normalize = (vector) => {
  let l = Math.pow(_.reduce(vector, (r, v) => r + v*v, 0), 0.5);
  return vector.map(v => v/l);
};

for(let a = 1; a <= 10000; a++) {
  let v = [
    Math.pow(a, 0.1),   // increase
    Math.cos(a/1000),   // loop
    Math.pow(a, 0.09),  // increase
    Math.pow(1/a, 0.1), // decrease
    Math.pow(a, 0.08),  // increase
    Math.sin(a/1000),   // loop
    Math.cos(a/2000),   // loop
    Math.pow(1/a, 0.09),// decrease
    Math.pow(a, 0.06),  // increase
    Math.sin(a/2000),   // loop
  ];
  if(process.argv[2]) {
    for(let i in v) {
      v[i] = v[i] * (1.0 + Math.random()/100);
    }
  }
  let n = normalize(v);
  console.log(`${n[0]},${n[1]},${n[2]},${n[3]},${n[4]},${n[5]},${n[6]},${n[7]},${n[8]},${n[9]}`);
}

1. a に対して単調増加するフィールドと、単調減少するフィールド、繰り返しフィールドがある。

  直積量子化の際の回転(フィールドの組み合わせ)が重要になる。

2. a が近いベクトル同士の距離は近くなる。

  近いデータを検索出来ている事が確認しやすい

生成データ: data.csv

検索用データ:上記データにランダム誤差を加えたもの random.csv

テストコード解説

コード

const (
    DIM = 10
    NRESULT = 5
    INDEX_FILE = "/tmp/faiss.idx"
    SAMPLE_INDEX = 7000
    NSEARCH = 3000
)

インデックスのサイズは一回ファイルに吐き出してからファイルサイズを取得する

func DumpIndexFileSize(index faiss.Index) {
    faiss.WriteIndex(index, INDEX_FILE)
    file, _ := os.Open(INDEX_FILE)
    defer file.Close()
    stat, _ := file.Stat()
    fmt.Printf("Index size: %v bytes\n", stat.Size())
}

測定関数(efSearchはHNSW検索の深さ、nprobeはLVFの検索クラスター数)

各種、10次元10000ベクトルのインデックスを作成し、精度と検索時間を評価する。

func IndexPerformance(description string, efSearch float64, nprobe float64, train bool) {
    fmt.Println("*** ", fmt.Sprintf("%s, efSearch: %v, nprobe: %v", description, efSearch, nprobe))
    searches := *GetData("random.csv", DIM)
    data := *GetData("data.csv", DIM)
    index, _ := faiss.IndexFactory(DIM, description, faiss.MetricInnerProduct)
    parameterSpace, _ := faiss. NewParameterSpace()
    if efSearch > 0 {
        parameterSpace.SetIndexParameter(index, "efSearch", efSearch)
    }
    if nprobe > 0 {
        parameterSpace.SetIndexParameter(index, "nprobe", nprobe)
    }
    if train {
        startAt := time.Now().UnixNano()
        index.Train(data)
        endAt := time.Now().UnixNano()
        fmt.Printf("Train() Elapsed: %v ms\n", (endAt - startAt) / 1000000)
    }
    {
        startAt := time.Now().UnixNano()
        index.Add(data)
        endAt := time.Now().UnixNano()
        fmt.Printf("Add() Elapsed: %v ms\n", (endAt - startAt) / 1000000)
    }
    fmt.Printf("Ntotal: %v\n", index.Ntotal())
    distances, labels, _ := index.Search(searches[SAMPLE_INDEX*DIM:(SAMPLE_INDEX+1)*DIM], NRESULT)
    fmt.Printf("Sample Distances: %v, Labels: %v\n", distances, labels)
    DumpIndexFileSize(index)
    startAt := time.Now().UnixNano()
    for i := 0; i < NSEARCH; i++ {
        index.Search(searches[i*DIM:(i+1)*DIM], NRESULT)
    }
    endAt := time.Now().UnixNano()
    fmt.Printf("Search Elapsed: %v ms\n", (endAt - startAt) / 1000000)
}

Flatインデックス

IndexPerformance("Flat", 0, 0, false)

実行結果

***  Flat, efSearch: 0, nprobe: 0
Add() Elapsed: 1 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 400045 bytes
Search Elapsed: 2369 ms

今回の測定の基準値。

誤差が無いので精度面はこの結果が正しい結果。

そのままメモリー展開するだけなので10000件の追加も一瞬。

直積量子化エンコード

IndexPerformance("PQ2x8", 0, 0, true)
IndexPerformance("PQ2x8,RFlat", 0, 0, true)
IndexPerformance("PQ5x8", 0, 0, true)

実行結果

***  PQ2x8, efSearch: 0, nprobe: 0
Train() Elapsed: 23368 ms
Add() Elapsed: 68 ms
Ntotal: 10000
Sample Distances: [1.0010208 1.0010208 1.0010208 1.0010208 1.0010208], Labels: [7032 7033 7034 7036 7035]
Index size: 30326 bytes
Search Elapsed: 451 ms
***  PQ2x8,RFlat, efSearch: 0, nprobe: 0
Train() Elapsed: 23855 ms
Add() Elapsed: 70 ms
Ntotal: 10000
Sample Distances: [0.99997026 0.99996835 0.9999664 0.99996436 0.99996233], Labels: [7032 7033 7034 7035 7036]
Index size: 430412 bytes
Search Elapsed: 468 ms
***  PQ5x8, efSearch: 0, nprobe: 0
Train() Elapsed: 39089 ms
Add() Elapsed: 50 ms
Ntotal: 10000
Sample Distances: [1.0006516 1.0006516 1.0006516 1.0006516 1.0006516], Labels: [6942 6943 6944 6945 6941]
Index size: 60326 bytes
Search Elapsed: 756 ms

PQ2x8

10次元32bitから2次元8bitに直積量子化することで、インデックスのサイズが400kB => 30kBに激減。 データが小さくなった事で、検索速度も早くなった。

ただし量子化の辞書化の為の訓練時間がかかる。またベクトル追加の際も直積処理の分時間がかかる。

検索精度もイマイチだが、Distancesが同値で、量子化の解像度が足りていない事がわかる。

PQ2x8,RFlat

生データを保存するために、インデックスサイズ = Flat分 + PQ2x8分 となる。検索はPQ2x8部分を使っているので検索速度はPQ2x8に準ずる。

最大のメリットであるモリー削減を失っているので用途は限定的

PQ5x8

5次元としたがPQ2x8と比較してインデックスサイズと検索時間が悪化している。量子化の解像度も足りていない。

ベクトル回転(OPQ)&直積量子化エンコード(PQ)

IndexPerformance("OPQ2,PQ2x8", 0, 0, true)
IndexPerformance("OPQ5,PQ5x8", 0, 0, true)

実行結果

***  OPQ2,PQ2x8, efSearch: 0, nprobe: 0
Train() Elapsed: 52593 ms
Add() Elapsed: 70 ms
Ntotal: 10000
Sample Distances: [1.0000875 1.0000875 1.0000875 1.0000875 1.0000875], Labels: [6970 6971 6972 6973 6969]
Index size: 30797 bytes
Search Elapsed: 480 ms
***  OPQ5,PQ5x8, efSearch: 0, nprobe: 0
Train() Elapsed: 103295 ms
Add() Elapsed: 54 ms
Ntotal: 10000
Sample Distances: [1.0009259 1.0009259 1.0009259 1.0008681 1.0008681], Labels: [7008 7010 7009 6967 6965]
Index size: 60797 bytes
Search Elapsed: 767 ms

OPQ2,PQ2x8

直積量子化の前に同じような傾向を持つフィールドが固まるように回転させる。

しかし元データが、単純増加、単純減少、繰り返しのパターンなので、2次元では足りていない。

フィールドの組み合わせを探す為、トレーニング時間が劇的に増加

OPQ5,PQ5x8

劇的に精度が改善している

フィールドの組み合わせパターンが増えた分、トレーニング時間が増加している。

物凄いざっくり

f:id:hiroppon:20210507183021p:plain:w800 OPQについて

うーん。。ここの解説はどうしたら良いんだ。。簡潔である程度正確なイメージが作れない。

SQ8

scalar quantizer が何なのか良く解らなかったが、データサイズ(8bit/32bitに近い)や実行時間(10次元の量子化オーバーヘッド)から見て、やはり単純なベクトル量子化のようだ。

原始的過ぎて積極的に採用する理由がない

IndexPerformance("SQ8", 0, 0, true)

実行結果

***  SQ8, efSearch: 0, nprobe: 0
Train() Elapsed: 0 ms
Add() Elapsed: 2 ms
Ntotal: 10000
Sample Distances: [1.000603 1.0004168 1.000348 1.0003289 1.0003289], Labels: [6993 6928 7039 6991 6990]
Index size: 100161 bytes
Search Elapsed: 6255 ms

HNSW

階層型のインデックスで、精度とメモリー使用量のトレードオフの関係にある。

階層毎に保持するネイバーの数が問題となる。

IndexPerformance("HNSW2", 2, 0, false)
IndexPerformance("HNSW4", 2, 0, false)
IndexPerformance("HNSW8", 2, 0, false)
IndexPerformance("OPQ5,HNSW8_PQ5x8", 2, 0, true)

実行結果

***  HNSW2, efSearch: 2, nprobe: 0
Add() Elapsed: 415 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 -3.4028235e+38], Labels: [7002 7003 7001 7004 -1]
Index size: 759350 bytes
Search Elapsed: 1409 ms
***  HNSW4, efSearch: 2, nprobe: 0
Add() Elapsed: 262 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 -3.4028235e+38], Labels: [7002 7003 7001 7004 -1]
Index size: 892782 bytes
Search Elapsed: 1488 ms
***  HNSW8, efSearch: 2, nprobe: 0
Add() Elapsed: 249 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 1205650 bytes
Search Elapsed: 1435 ms
***  OPQ5,HNSW8_PQ5x8, efSearch: 2, nprobe: 0
Train() Elapsed: 70060 ms
Add() Elapsed: 313 ms
Ntotal: 10000
Sample Distances: [1.2529714e-05 1.2529714e-05 1.2529714e-05 1.2529714e-05 1.2529714e-05], Labels: [6993 7001 7006 6999 6991]
Index size: 866402 bytes
Search Elapsed: 1591 ms

HNSW2 efSearch2

検索精度は問題ないが、ネイバー数と探索深度が足りず、5件目が帰っていない。

今回は、投入に非常に近い値で検索しているので、良い精度が得られている。

投入データと少し遠い値で検索を掛けた時は精度が劇的に落ちる。

一見、検索速度は遅く見えるが、ツリー探索の特性上、処理量はデータ数に対数的に振る舞うので大規模データに強い。

(メモリーどうすんだ?という問題が残るが)

HNSW4 efSearch2

ネイバーが4の時点で、Flatインデックスの倍のサイズになった。

5件目が帰っていない理由は不明。枝の末端だったのだろうか?

HNSW8 efSearch2

OPQ5,HNSW8_PQ5x8

PQを掛けてメモリーサイズを減らしつつ、ネイバー数も稼ぐアプローチ

IVF

個人的にはIVF,PQが小規模でも大規模でも使い易く第一選択肢だと思っている

nlists = 100

   IndexPerformance("IVF100,Flat", 0, 1, true)
    IndexPerformance("IVF100,Flat", 0, 2, true)
    IndexPerformance("IVF100,Flat", 0, 100, true)
    IndexPerformance("OPQ5,IVF100,PQ5x8", 0, 1, true)
    IndexPerformance("OPQ5,IVF100,PQ5x8", 0, 2, true)

実行結果

***  IVF100,Flat, efSearch: 0, nprobe: 1
Train() Elapsed: 103 ms
Add() Elapsed: 32 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 484939 bytes
Search Elapsed: 99 ms
***  IVF100,Flat, efSearch: 0, nprobe: 2
Train() Elapsed: 97 ms
Add() Elapsed: 32 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 484939 bytes
Search Elapsed: 128 ms
***  IVF100,Flat, efSearch: 0, nprobe: 100
Train() Elapsed: 103 ms
Add() Elapsed: 32 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 484939 bytes
Search Elapsed: 2731 ms
***  OPQ5,IVF100,PQ5x8, efSearch: 0, nprobe: 1
Train() Elapsed: 108424 ms
Add() Elapsed: 56 ms
Ntotal: 10000
Sample Distances: [1.0002648 1.0001966 1.0001966 1.0001553 1.0001428], Labels: [7018 7005 7006 7072 7065]
Index size: 145691 bytes
Search Elapsed: 423 ms
***  OPQ5,IVF100,PQ5x8, efSearch: 0, nprobe: 2
Train() Elapsed: 106859 ms
Add() Elapsed: 55 ms
Ntotal: 10000
Sample Distances: [1.0002648 1.0002615 1.0002615 1.0002615 1.0002488], Labels: [7018 6998 6996 6997 6982]
Index size: 145691 bytes
Search Elapsed: 407 ms

IVF100,Flat nprobe: 1

精度も検索速度も優秀

インデックスサイズもそれほど大きくならない。

検索負荷 = Flat負荷 x 1/100 + オーバーヘッド

IVF100,Flat nprobe: 2

検索負荷 = Flat負荷 x 2/100 + オーバーヘッド

IVF100,Flat nprobe: 100

検索負荷 = Flat負荷 x 100/100 + オーバーヘッド

クラスターへ検索しに行っているので、Flatインデックスの検索量と同じ。 オーバーヘッドは思ったより小さく優秀。

OPQ5,IVF100,PQ5x8 nprobe: 1

量子化により、大幅にデータサイズを抑えつつ高速化。精度面を若干妥協。

OPQ5,IVF100,PQ5x8 nprobe: 2

nprobe の調整により、かなり近いデータも取得できている。

一覧表

Train Add Search Size 精度 備考
Flat 1 ms 2369 ms 400045 bytes 7002 7003 7001 7004 7000
PQ2x8 23368 ms 68 ms 451 ms 30326 bytes 7032 7033 7034 7036 7035 精度が悪い
PQ2x8,RFlat 23855 ms 70 ms 468 ms 430412 bytes 7032 7033 7034 7035 7036 良い所無し
PQ5x8 39089 ms 50 ms 756 ms 60326 bytes 6942 6943 6944 6945 6941 精度が悪い
OPQ2,PQ2x8 52593 ms 70 ms 480 ms 30797 bytes 6970 6971 6972 6973 6969
OPQ5,PQ5x8 103295 ms 54 ms 767 ms 60797 bytes 7008 7010 7009 6967 6965 モリーと精度が良い
SQ8 0 ms 2 ms 6255 ms 100161 bytes 6993 6928 7039 6991 6990 検索遅すぎ
HNSW2, efSearch: 2 415 ms 1409 ms 759350 bytes 7002 7003 7001 7004 -1 モリー効率悪い
HNSW4, efSearch: 2 262 ms 1488 ms 892782 bytes 7002 7003 7001 7004 -1 モリー効率悪い
HNSW8, efSearch: 2 249 ms 1435 ms 1205650 bytes 7002 7003 7001 7004 7000 モリー効率悪い
OPQ5,HNSW8_PQ5x8, efSearch: 2 70060 ms 313 ms 1591 ms 866402 bytes 6993 7001 7006 6999 6991 モリー効率悪い
IVF100,Flat, nprobe: 1 103 ms 32 ms 99 ms 484939 bytes 7002 7003 7001 7004 7000 高速
IVF100,Flat, nprobe: 2 97 ms 32 ms 128 ms 484939 bytes 7002 7003 7001 7004 7000 高速
IVF100,Flat, nprobe: 100 103 ms 32 ms 2731 ms 484939 bytes 7002 7003 7001 7004 7000
OPQ5,IVF100,PQ5x8, nprobe: 1 108424 ms 56 ms 423 ms 145691 bytes 7018 7005 7006 7072 7065 全てのバランスが良い
OPQ5,IVF100,PQ5x8, nprobe: 2 106859 ms 55 ms 407 ms 145691 bytes 7018 6998 6996 6997 6982 全てのバランスが良い

OPQ深堀り

この記事を書きながら気付いた点を追加検証。

今回のデータは意図的に同じような振る舞いをする次元がシャッフルされて組み込まれている。

OPQを掛ける時に

1. サブベクトルに分けずに全フィールドを見通せば精度が劇的に上がるのではないか?

2. OPQの後にPQを掛けるので、OPQの出力次元は、PQの次元と合わせた方が速度、精度共に有利ではないか?

IndexPerformance("OPQ1_2,PQ2x8", 0, 0, true)
IndexPerformance("OPQ1_5,PQ5x8", 0, 0, true)
IndexPerformance("OPQ1_5,HNSW8_PQ5x8", 2, 0, true)
IndexPerformance("OPQ1_5,IVF100,PQ5x8", 0, 1, true)
IndexPerformance("OPQ1_5,IVF100,PQ5x8", 0, 2, true)

実行結果

***  OPQ1_2,PQ2x8, efSearch: 0, nprobe: 0
Train() Elapsed: 37700 ms
Add() Elapsed: 25 ms
Ntotal: 10000
Sample Distances: [0.07687946 0.07687946 0.07687946 0.0767533 0.0767533], Labels: [7062 7061 7063 6998 6997]
Index size: 22285 bytes
Search Elapsed: 446 ms
***  OPQ1_5,PQ5x8, efSearch: 0, nprobe: 0
Train() Elapsed: 57581 ms
Add() Elapsed: 44 ms
Ntotal: 10000
Sample Distances: [0.22191425 0.22191425 0.22191425 0.22183329 0.22178258], Labels: [6984 6985 6986 7044 7011]
Index size: 55477 bytes
Search Elapsed: 842 ms
***  OPQ1_5,HNSW8_PQ5x8, efSearch: 2, nprobe: 0
Train() Elapsed: 22025 ms
Add() Elapsed: 296 ms
Ntotal: 10000
Sample Distances: [1.4171669e-06 1.4171669e-06 1.4171669e-06 1.4171669e-06 1.4171669e-06], Labels: [7006 7001 7007 7003 7002]
Index size: 861082 bytes
Search Elapsed: 1744 ms
***  OPQ1_5,IVF100,PQ5x8, efSearch: 0, nprobe: 1
Train() Elapsed: 59567 ms
Add() Elapsed: 56 ms
Ntotal: 10000
Sample Distances: [0.22194861 0.22186598 0.22186598 0.22186598 0.22186598], Labels: [7027 7053 7055 7054 7052]
Index size: 138371 bytes
Search Elapsed: 408 ms
***  OPQ1_5,IVF100,PQ5x8, efSearch: 0, nprobe: 2
Train() Elapsed: 60427 ms
Add() Elapsed: 52 ms
Ntotal: 10000
Sample Distances: [0.22194861 0.22186598 0.22186598 0.22186598 0.22186598], Labels: [7027 7053 7055 7054 7052]
Index size: 138371 bytes
Search Elapsed: 412 ms

OPQの段階で次元が減った分、PQの辞書次元が減り、若干インデックスサイズが小さくなった。

精度は少し良くなった様な感じはあるが誤差の範囲だろう。

OPQチューニングの正解

ちょっとズルだが、元データの構造を知っているので OPQ1_3 が一番良いはずだ。

IndexPerformance("OPQ1_3,PQ3x8", 0, 0, true)
IndexPerformance("OPQ1_3,HNSW8_PQ3x8", 2, 0, true)
IndexPerformance("OPQ1_3,IVF100,PQ3x8", 0, 1, true)
IndexPerformance("OPQ1_3,IVF100,PQ3x8", 0, 2, true)

実行結果

***  OPQ1_3,PQ3x8, efSearch: 0, nprobe: 0
Train() Elapsed: 43282 ms
Add() Elapsed: 37 ms
Ntotal: 10000
Sample Distances: [0.07851314 0.07850463 0.07850463 0.07850028 0.078476], Labels: [6888 6853 6854 6878 6861]
Index size: 33349 bytes
Search Elapsed: 585 ms
***  OPQ1_3,HNSW8_PQ3x8, efSearch: 2, nprobe: 0
Train() Elapsed: 19069 ms
Add() Elapsed: 286 ms
Ntotal: 10000
Sample Distances: [8.4947663e-07 8.4947663e-07 8.4947663e-07 8.4947663e-07 8.4947663e-07], Labels: [7006 7001 7004 7005 6999]
Index size: 838954 bytes
Search Elapsed: 1576 ms
***  OPQ1_3,IVF100,PQ3x8, efSearch: 0, nprobe: 1
Train() Elapsed: 43502 ms
Add() Elapsed: 42 ms
Ntotal: 10000
Sample Distances: [0.07815711 0.07815711 0.07815711 0.07815711 0.07815711], Labels: [7014 7015 7016 7017 7013]
Index size: 115443 bytes
Search Elapsed: 244 ms
***  OPQ1_3,IVF100,PQ3x8, efSearch: 0, nprobe: 2
Train() Elapsed: 43467 ms
Add() Elapsed: 40 ms
Ntotal: 10000
Sample Distances: [0.07864998 0.07864998 0.07864998 0.07864998 0.07864998], Labels: [6996 6997 6998 6999 6995]
Index size: 115443 bytes
Search Elapsed: 275 ms

OPQ1_3,PQ3x8 だけちょっと納得が行かないが、その他は大きく精度が向上した。

次回

もうちょっと複雑なやつ

Faiss解説シリーズ(第二回)ハマりポイント集

crumbjp.hateblo.jp

Faissインデックス毎の制限について

サンプルコード

FlatインデックスはID管理出来ない

func AddWithIDsDontWorkOnFlatIndex() {
    fmt.Println("*** AddWithIDsDontWorkOnFlatIndex ")
    index, _ := faiss.IndexFactory(2, "Flat", faiss.MetricL2)
    index.AddWithIDs([]float32{0,0,1,0,0,1,1,1}, []int64{0,1,2,3})
}

実行結果

*** AddWithIDsDontWorkOnFlatIndex
Error in virtual void faiss::Index::add_with_ids(faiss::Index::idx_t, const float *, const faiss::Index::idx_t *) at /Users/crumbjp/git/faiss/faiss/Index.cpp:39: add_with_ids not implemented for this type of index

(ID管理出来ない)Flatインデックスでベクトルの削除を行うとどうなるか?

func RemoveIDsOnFlatIndex() {
    fmt.Println("*** RemoveIDsOnFlatIndex")
    index, _ := faiss.IndexFactory(2, "Flat", faiss.MetricL2)
    index.Add([]float32{0,0,1,0,0,1,1,1})
    fmt.Printf("Ntotal: %v\n", index.Ntotal())
    distances, labels, _ := index.Search([]float32{1, 0.1}, 4)
    fmt.Printf("Distances: %v, Labels: %v\n", distances, labels)
    selector, _ := faiss.NewIDSelectorBatch([]int64{0})
    defer selector.Delete()
    index.RemoveIDs(selector)
    fmt.Printf("Ntotal: %v\n", index.Ntotal())
    distances, labels, _ = index.Search([]float32{1, 0.1}, 4)
    fmt.Printf("Distances: %v, Labels: %v\n", distances, labels)
}

0 番目の要素を削除する。

   selector, _ := faiss.NewIDSelectorBatch([]int64{0})
    defer selector.Delete()
    index.RemoveIDs(selector)

実行結果

*** RemoveIDsOnFlatIndex
Ntotal: 4
Distances: [0.010000001 0.80999994 1.01 1.81], Labels: [1 3 0 2]
Ntotal: 3
Distances: [0.010000001 0.80999994 1.81 3.4028235e+38], Labels: [0 2 1 -1]

3ベクトルしか無いインデックスに4個取得しようとしているので、最後のラベルは見つからなかった事を示す -1 が返却される。 注目すべきは、削除した 0 番目は切り詰められて、全ベクトルのインデックスが変わってしまっている。

ID管理出来ない上に、IDが変わってしまうので超管理し難い

事実上Flatインデックスでは『削除』は出来ないものと思って良い

HNSWインデックスでは削除出来ない

func RemoveIDsOnHNSW() {
    fmt.Println("*** RemoveIDsOnHNSW ")
    index, _ := faiss.IndexFactory(2, "HNSW32", faiss.MetricL2)
    index.Add([]float32{0,0,1,0,0,1,1,1})
    fmt.Printf("Ntotal: %v\n", index.Ntotal())
    selector, _ := faiss.NewIDSelectorBatch([]int64{0})
    defer selector.Delete()
    index.RemoveIDs(selector)
}

ちなみに、HNSWだけ指定した場合はFlatインデックスの一種となる。制限もFlatインデックスに準拠する。

   index, _ := faiss.IndexFactory(2, "HNSW32", faiss.MetricL2)

実行結果

*** RemoveIDsOnHNSW
Ntotal: 4
Error in virtual size_t faiss::Index::remove_ids(const faiss::IDSelector &) at /Users/crumbjp/git/faiss/faiss/Index.cpp:43: remove_ids not implemented for this type of index

IVFインデックスにはトレーニングが必須

func IVFRequiresTrain() {
    fmt.Println("*** IVFRequiresTrain")
    index, _ := faiss.IndexFactory(2, "IVF4,Flat", faiss.MetricL2)
    index.AddWithIDs([]float32{0,0,1,0,0,1,1,1}, []int64{0,1,2,3})
}

4 クラスターに分割する

   index, _ := faiss.IndexFactory(2, "IVF4,Flat", faiss.MetricL2)

実行結果

*** IVFRequiresTrain
Error in virtual void faiss::IndexIVFFlat::add_core(faiss::Index::idx_t, const float *, const int64_t *, const int64_t *) at /Users/crumbjp/git/faiss/faiss/IndexIVFFlat.cpp:44: Error: 'is_trained' failed

クラスタリングを行い小さなインデックスに分割するので、予めテストデータからクラスターを作っておかなければならない。

インデックスが分割されているので検索クエリーを 何個のクラスターに投げるか?が重要

func IVFWithNprobe() {
    fmt.Println("*** IVFWithNprobe")
    index, _ := faiss.IndexFactory(2, "IVF4,Flat", faiss.MetricL2)
    index.Train([]float32{0,0,1,0,0,1,1,1})
    index.AddWithIDs([]float32{0,0,1,0,0,1,1,1}, []int64{0,1,2,3})
    fmt.Printf("Ntotal: %v\n", index.Ntotal())
    distances, labels, _ := index.Search([]float32{1, 0.1}, 4)
    fmt.Printf("Distances: %v, Labels: %v\n", distances, labels)
    parameterSpace, _ := faiss. NewParameterSpace()
    parameterSpace.SetIndexParameter(index, "nprobe", 2)
    distances, labels, _ = index.Search([]float32{1, 0.1}, 4)
    fmt.Printf("Distances: %v, Labels: %v\n", distances, labels)
}

デフォルトは一番近い 1 クラスター にクエリーを投げる。nprobe パラメータで指定

   parameterSpace, _ := faiss. NewParameterSpace()
    parameterSpace.SetIndexParameter(index, "nprobe", 2)

実行結果

*** IVFWithNprobe
WARNING clustering 4 points to 4 centroids: please provide at least 156 training points
Ntotal: 4
Distances: [0.010000001 3.4028235e+38 3.4028235e+38 3.4028235e+38], Labels: [1 -1 -1 -1]
Distances: [0.010000001 0.80999994 3.4028235e+38 3.4028235e+38], Labels: [1 3 -1 -1]

4つのクラスターに4つのvectorを入れている(かつトレーニングデータが実データと一緒)ので 1クラスターに1vectorが入っている状態。 (トレーニングにはもっとデータが必要だという警告が出ている)

最初のクエリーでは、 nprobe のデフォルト値 1 が採用され、1クラスターにのみクエリーを投げて 1 vectorだけがヒット。

次のクエリーでは nprobe2 に変更しているので、 2クラスターにクエリーを投げて 2 vectorがヒットした。

IVFでは nprobe の調整により、パフォーマンスと精度のバランスを取る事が重要だ。

次回

crumbjp.hateblo.jp