中年engineerの独り言 - crumbjp

LinuxとApacheの憂鬱

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だけがヒット。

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

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

次回

crumbjp.hateblo.jp

Faiss解説シリーズ（第一回）基本編

最近、根詰めて触っているので詳しくなって来たついでに解説記事を書いてみた

Faissとは

Facebookが開発しているC++NNS(Nearest neighbor search)エンジン

  • 手に入るライブラリの中では最高峰の速度
  • 高次元ベクトルで問題になりがちなメモリー問題に対応できる機能群
  • 億を超える数のベクトルを想定した多種のインデックスアルゴリズム
  • これらを組み合わせる事で柔軟に用途にマッチしたトレードオフ戦略が取れる

簡単に言えば、どんなケースでも利用できる超柔軟なライブラリである。

NNSとANN（Approximate nearest neighbor）の超基礎

NNS

高次元のベクトルでは、あるベクトル群から、任意のベクトルに近いベクトルを抽出する場合には、総当りが第一選択肢だ。

低次元ならば、グリッドやハッシュなどの工夫によって効率良く抽出できる。高次元ではこれらの工夫は計算量的に裏目に出る。（次元の呪い）

ANN（Approximate nearest neighbor）

問題によっては抽出されるベクトルが厳密で無くとも良い場合がある。マッチ漏れや順位の上下などをある程度許容することで高速化を目指すアプローチだ。

詳しく勉強したい人へオススメ

Faissのインデックス

原文

処理の流れ

f:id:hiroppon:20210505025539p:plain:w800

オレンジの部分がそれぞれ柔軟に差し替え可能。

ベクトルAが数万次元であっても（TransformやEncodeのトレードオフを受け入れる事で）ベクトルCを百次元未満にできれば、検索処理やメモリの負荷を大幅に削減できる。

またインデックス部分も単純にメモリ展開するだけだったり、グラフ構造や分散構造を選択できる。（もちろん各構造において色々なトレードオフがある）

Metric

原文

ベクトルの距離計算の定義。主に以下の２つ

Faissでの表記 意味 備考
L2 平方ユークリッド距離 大小比較するだけならユークリッド距離と同意
InnerProduct あるいは IP 内積 ベクトルを正規化しておけば（分母が１になるので）そのままコサイン類似度として使える。

基本インデックス

原文

今回のメインコンテンツ。FlatとIVFだけ覚えるだけでも良い。

Flat

与えられたベクトルをメモリ空間にそのまま展開する。

検索は総当り。よって誤差は出ない。 それでもBLASに食わせ易く信じられないほど速い。

メモリーにそのまま展開するためベクトルのメモリー内順序で処理しID管理はしない（できない）。 利用側がベクトルを追加した順番を覚えておかなければならないので取り回しが悪い。

スクリプトなどで一時的なインデックスという使い方に良い。

IVF

総当りに耐えられない数のベクトルを、クラスタリングして小さな nlist 個のインデックスに分けておく。 検索時は、指定したベクトルに近いクラスタ（インデックス）を nprobe 個を対象に検索する。

クラスタリングの常として検索対象に入らなかったクラスタに、本当は近かったベクトルが入っている場合もあり、それらは検索結果から漏れる。

個人的には大体これを使う。

HNSW

ほぼグラフDBと同じ構造。

f:id:hiroppon:20210505025522p:plain:w200

詳しく知りたい人はココ

検索時にグラフが追えなくなってしまう為、一度入れたデータの削除ができない。

LSH

閾値の上下の２値化によるハッシュ

あまり精度を必要とせず、大まかな比較になる事が多い。

速度とメモリの制限が非常に厳しい場合の選択肢。

主なTransform

主に次元圧縮え使う事が多い。

Faissでの表記 意味 備考
PCA 主成分分析 意味が薄い次元を省略し次元圧縮
OPQ ベクトル回転 後述のPQの効率化用
RR ランダム回転 どう使うのか良くわからない
L2norm 正規化 ベクトルの大きさを1にする。MetricにInnerProductを指定すればcos類似度となる(実際の値は1-cos類似度)が予め入力ベクトルを正規化しておいた方が良い
ITQ 勉強中 後述のLSHと一緒に使う
Pad パディング どう使うのか良くわからない

主なEncoding

Faissでの表記 意味 備考
PQ 直積量子化 解りやすい解説
SQ Scalar quantizer encoding ちょっと良く分からない。単純なベクトル量子化の事だろうか？
RQ 回帰分析の残差 回帰分析に上手く乗るデータ（トレーニングデータで実データを説明できるか？）では残差を量子化すると効率が良い
LSH しきい値以上か未満の2値に量子化 高次元ベクトルで次元圧縮をしたくない場合の選択肢

PQを使ってれば間違いないがちょっと考える事が多いので後日別途解説する予定。

Prefixes

Faissでの表記 意味 備考
IDMap Flatインデックス専用 メモリー上での実装のみでマップ情報込みでインデックスを永続化できない

永続化出来ないのでプロセスが起動している間でしか使わないインデックスで採用する事になるが、そういうケースのデータ投入でID管理出来ないような順不同並列投入する事もあまり考えられない為、採用しにくい。

私見だが使い物にならない。

Suffixes

TransformやEncodeを経たデータの距離には誤差がある。 検索結果を返す前に生ベクトルで距離計算をやり直してソートする機能。

生ベクトルを保持する必要があるためメモリー負荷が大きい。

以下の２つがある。

  • RFlat
  • Refine

サンプルコード

速度が重要な問題なので、サンプルコードも高速な言語であるGOを採用。

サンプルコード

f:id:hiroppon:20210505025827p:plain:w400

Flat L2

最もシンプルなFlatインデックスで平方ユークリッド距離計算。

func Sample1() {
    fmt.Println("*** Sample1 Flat L2")
    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)
}

2 次元、 Flat 、L2 を指定したインデックスを作成

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

2 次元のベクトルを 4 個同時に投入。前述の通りメモリ展開順にラベルが 0, 1, 2, 3 と振られる。

   index.Add([]float32{0,0,1,0,0,1,1,1})

実行結果

*** Sample1 Flat L2
Ntotal: 4
Distances: [0.010000001 0.80999994 1.01 1.81], Labels: [1 3 0 2]

Flat IP

メトリックに内積を指定

func Sample2() {
    fmt.Println("*** Sample2 Flat IP")
    index, _ := faiss.IndexFactory(2, "Flat", faiss.MetricInnerProduct)
    index.Add([]float32{0,0,1,0,0,1,1,1})
    distances, labels, _ := index.Search([]float32{1, 0.1}, 4)
    fmt.Printf("Distances: %v, Labels: %v\n", distances, labels)
}

実行結果

*** Sample2 Flat IP
Distances: [1.1 1 0.1 0], Labels: [3 1 2 0]

Transform(L2norm)

正規化ベクトルの内積＝1-cos類似度 （１に近い程、近距離と見なされる）

func Sample3() {
    fmt.Println("*** Sample3 L2norm Flat IP")
    index, _ := faiss.IndexFactory(2, "L2norm, Flat", faiss.MetricInnerProduct)
    index.Add([]float32{0,0,1,0,0,1,1,1})
    distances, labels, _ := index.Search([]float32{1, 0.1}, 4)
    fmt.Printf("Distances: %v, Labels: %v\n", distances, labels)
}

実行結果

*** Sample3 L2norm Flat IP
Distances: [0.99503714 0.77395725 0.09950372 0], Labels: [1 3 2 0]

Suffix RFlat

TransformやEncodeとRFlatの組み合わせは上手く動かない。

Transform(L2norm) と RFlatを同時に使うと、RFlatの際にTransformが無視されて、単なる内積が帰ってしまう。

func RFlatDontWorkWithTransform() {
    fmt.Println("*** RFlatDontWorkWithTransform")
    index, _ := faiss.IndexFactory(2, "L2norm,Flat,RFlat", faiss.MetricInnerProduct)
    index.Add([]float32{0,0,1,0,0,1,1,1})
    distances, labels, _ := index.Search([]float32{1, 0.1}, 4)
    // RFlat returns simple IP, (Ignoring transform layer)
    fmt.Printf("Distances: %v, Labels: %v\n", distances, labels)
}

実行結果

*** RFlatDontWorkWithTransform
Distances: [1.1 1 0.1 0], Labels: [3 1 2 0]

Suffix Refine

RFlatの代わりにRefineを使ってインデックスと同じ定義をしてあげれば良い。

func Refine() {
    fmt.Println("*** Refine")
    index, _ := faiss.IndexFactory(2, "L2norm,Flat,Refine(L2norm,Flat)", faiss.MetricInnerProduct)
    index.Add([]float32{0,0,1,0,0,1,1,1})
    distances, labels, _ := index.Search([]float32{1, 0.1}, 4)
    fmt.Printf("Distances: %v, Labels: %v\n", distances, labels)
}

実行結果

*** Refine
Distances: [0.99503714 0.77395725 0.09950372 0], Labels: [1 3 2 0]

続き

全然書ききれないので、第２回も準備中。サンプルや検証を中心にしようと思っている。

crumbjp.hateblo.jp

Faissでベクトル検索するDBを開発した

広告プラットフォームcraft に投入

24000次元のSCDVベクトルを数百万件入れてインデクシングしています。

PQ圧縮しているのでメモリー負担は殆ど無く小さなサーバーで運用できています（トレーニングの時だけメモリーが大変）

順次利用範囲を広げていく予定。

faissdb

https://github.com/crumbjp/faissdb

https://github.com/crumbjp/faissdb/raw/main/img/Architecture.png

  • Faissインデックスを使ったベクトル検索が出来るDB
  • ベクトルはユニークキーで管理（Faissの面倒なID管理をしなくて良い）
  • 複数のFaiss indexを扱える。（検索対象が用途的に、全体データ、weeklyデータ、monthlyデータ、といった具合に分けたい時には予めfaiss indexを３つ作っておかなきゃならない）
  • PRIMARY-SECONDARY の簡易レプリケーション
  • クライアントI/FがgRPCなのでクライアントライブラリの開発が容易

依存技術

開発の経緯

faissを使いたいが・・・

C/C++のfacebook製のベクトルANN検索ライブラリ。群を抜いて完成度と柔軟性が高い。

この手のライブラリは作ったインデックスを更新出来ないのが普通だがfaissではインデックスのアルゴリズムを指定する事で、用途に応じたインデックスのメリットと制限をコントロール出来る。

しかしあくまで純粋な検索ライブラリなのでサービスに使うには周辺の処理（メモリー管理やデータ管理など）を自前で書かなきゃならない。

またC/C++以外の既存の言語バインディングが貧弱。

高速実装のトレードオフでインデクスの永続化周りは非常に弱い。

golang

容易にCライブラリを叩く事ができる言語の中では最も高級言語の内の一つ。

goルーチンがメチャクチャ便利なのでデータストアを書くのには向いている。

golang内で取得したメモリーに関してはGCが面倒を見てくれるがCライブラリを叩く場合は帰ってくるデータのメモリーの扱いを気にしなきゃならないので結局ソースは全部読まなきゃ使えない。

駄目なら全部自分で書く覚悟が出来てる時だけgolangを使うのであまり気にならないが・・・

gRPC

protocol-bufferベースの言語非依存RPCライブラリ。

が、クロス言語でコールする場合はちょくちょくバグがあったりして地雷を回避しながらじゃないと使えない。

インターフェース定義ファイル（.proto）から各言語実装をジェネレート出来、使う側は限りなく言語ネイティブで実装できるので負担が少ない。

一緒にベクトルの世界に溺れたい人募集中です

SCDVが出来るまで

SCDVとは？

数多ある文章を評価する手法の中で速くて安くて旨いと噂されているもの

趣旨

実験的な実装やその結果は色々手に入るが実際にある程度の規模のサービスに使うとなると、どんな苦労があるのかを紹介しようと思う。 コードレベルの詳細な解説は他所に譲る。

大本

SCDV : Sparse Composite Document Vectors using soft clustering over distributional representations - ACL Anthology

解説サイト

丁寧に解説してくれているサイトが沢山あるので詳しくはそちらを見て欲しい。

手順（詳しくは上記のリンクを参照）

１．日本語コーパスを作る ２．Word2VecとIDFを算出 ３．WrodVectorをGMMでトピッククラスターに分類 ４．WordTopickVectorを得る ５．実際の記事にWordTopicVectorを適用し、文章ベクトルを得る。

０．ベクトル精度の評価方法

最終的にユーザ行動で判断する。

関連性の高いものを出すべき所で、関連性が高い（とシステムが判断した）ものを出した場合、ユーザーのリアクションに現れる。その数字を見て判断する。

面白いのは高関連度帯と低関連度帯で全く逆の成績（ユーザの反応）を得る場合があった。

大まかに見ると（高関連度帯）非常に上手く行っているモデルでも細かく見ていくと齟齬が多いということで サービスとしては文章ベクトルはあらゆる箇所で応用して使って行きたいのでなるべく細かいところまで精度を求めたい。

１．日本語コーパスをつくる

一般的なWebメディアの記事は、表記の揺れや偏り、口語調、中には非論理的な記事も含まれる場合があるので それを嫌って試しに日本語WikiのみでSCDVまで作ってみたが全く使い物にならなかった。

表記ゆれや、WEB特有の無効なワードに付き合って行く必要がある。

無効ワード

WEBでは文章の意味に関与しないワードが多数あり、これはコーパスを作る段階でも、実際文章を評価する段階でも除外しなければならない。 またascii や半角カナなども全角大文字正規化して扱っている。

ページ構造にまつわるもの

  • タイトル、トピック、コンテンツ
  • 次ページ、前ページ、ＮＥＸＴ
  • トップページ、ＴＯＰ
  • ＮＥＷ、新着

WEBメディア語

  • オススメ、おススメ
  • 大人気、話題、必見
  • あなた（に、へ）

EC語

  • サイズ、幅、奥行き、高さ、重量、ＫＧ
  • 価格、通常価格、特別価格、本体価格、販売価格
  • ＹＡＨＯＯ、楽天市場、ＡＭＡＺＯＮ

イベント系？

  • オリジナル、プレゼント、キャンペーン、期間中
  • 開催日時、ＴＥＬ

お腹いっぱいすぎる。。。

まだまだ数百あるが根本的に果がない。 先に述べた、高関連度帯ではある程度無視できるが、細かい精度を求めると記事元メディアや記者単位にの適度な頻出度になる単語も多くIDFでは影響を取り切れない。

地道に確定データを作って行けばDeepLearnで検出できるとは思う。

データ量

日本語Wikiと、我々の広告サービスでタグが埋まっているサイトの記事データからコーパスを作るが

wikiが200万記事6GB、サービス側のデータが260万記事14GB程度となる。

サービス用tokenizer

最終的にサービスで使うので、サービス用のtokenizerで処理する。

mecab-ipadic-neologd は必須アイテム。

nodejsからmecabを使う場合、mecabコマンドを叩いて（fork）いてるライブラリばかりで使い物にならないので ネイティブバインディングを自作している。 mecab-gyp - npm

  • 正規化
  • 名詞、動詞のみを抽出。（動詞は含めた方が若干良さそう）
  • 非自立、数、形容動詞語幹、副詞可能などと、上記無効ワードを除外
  • さらに特殊条件（ひらがな１文字など）で色々除外
  • これでも抜けてくる除外したいワードを目検で取る。（なる、ある、ほか、等）

最終的に、１０億ワード（９００万ユニーク）１０GBのコーパスが出来た。

他にも色々込み入ったロジックを実装している事もあり、100並列で１〜２時間かかる。

２．Word2VecとIDFを算出

隣のドキュメントと混ざらないようにwindowサイズ分のパディングを入れておく。

（あまりコレやっている人が居なそうなのはなぜだろう・・・）

gensimで一発。96コアのサーバーで130並列位かけると100%使ってくれる。

これも数時間かかる。

頻出度により約64万単語になった。

３．WrodVectorをGMMでトピッククラスターに分類

sklearnのGaussianMixture で丸一日！！

とにかく時間がかかる。並列化も望めないので悩みのタネ。

しかしここで最終的な文章ベクトルの精度の全てが決まるので何度も実行する事になる。

更にここで視覚的に精度を検証する術がない。

つまり最後まで行ってからココに戻ってくる。。つらい・・・

t-SENによる視覚化

f:id:hiroppon:20210302212900p:plainf:id:hiroppon:20210302213023p:plainf:id:hiroppon:20210302213049p:plainf:id:hiroppon:20210302213117p:plain

評価不能・・・

Word2Vecってワード数が少なくてもこうなるので評価の仕方が本当にわからない。

トピックベクトルまで行っちゃうと今度は色分けする意味が無くなるし困ったものだ。。

４．WordTopickVectorを得る

64万単語、200次元(word-vector)、400クラスターともなると使用メモリーが数十GBを超える。 処理途中も合わせると更に必要になる。単にnumpyで素朴に

(words * clusterWeights) * idf

って訳には行かない。

単語はファイルに落としておいてストリーム処理する。そこまでやるなら並列化は簡単。

単にベクトル演算なので詳細は略。

次元の謎

word2vecは200 〜 300次元、clusterは 50、60 〜 という話だが、この辺はどうにも体感値が違うようだ。

word2vecでは、200次元と300次元の違いが僅かで、cluster は 大きければ大きい程よさそう。 扱ってるコンテンツの幅が広いのが原因だろうか。。

word2vecを400次元以上にするとまた変わるのかもしれないが、試すのはいつになる事やら・・・

５．実際の記事にWordTopicVectorを適用し、文章ベクトルを得る。

ランタイムで記事データを分類するとなると得たベクトルはその最大精度では使えない。 8万次元ものベクトルをユーザアクセスの度に扱うのは重すぎるからだ。

wordTopicVector 自体を1% ~ 3% 程度にスパース化しておく。これで実効１０００次元。

これを文章に適用していくと、文章ベクトルが数万次元になってしまうので、それもまた1%程度にスパース化（＆正規化）する。

これでドキュメント同士の比較は数百回の掛け算処理になる。

あとドキュメント中に同じ単語が複数回現れる時の扱いでかなり精度が変わるのでここは工夫が必要。

セイコーの腕時計の記事とシチズンの腕時計の記事では、各々セイコーとシチズンを連呼する（しかもIDFも大きい）。上手く扱わないと文章ベクトル自体がセイコーとシチズンになり、記事の共通部である腕時計との距離がどんどん離れて行ってしまう。

Webの記事は表現が節操がないといつも思う

学問的にはともかくサービスとしてはオーダーメイドチューンすべき所だ。

データストア

ここまでデータを圧縮してもランタイムで使うならば毎回DBから引く訳にも行かずメモリーに貯める訳にも行かない。

そもそもメモリーに全ては入らず、一部であってもランタイム用のワーカープロセス１つずつに持つのは非効率（サーバーメモリが潰れる）

じゃあredisに入れる？

f:id:hiroppon:20210303004709p:plain:w300

即死！！

wordTopicVector も文章ベクトルも置き場に困る。 100GBクラスで即応性があり格安で使えるデータストアが必要！！！

これが解決しないなら更に次元を落とすしかない・・・

成果

実際のサービスでの配信での成績の一例

ユーザーは今見ている記事と関係ある記事ほどクリックする確率が高いと仮定すると文章ベクトルの類似度とクリック率に一定の関係が現れるはずだ。 ElasticSearchのmltスコアによる分析と比較して検証する。

よくできました 💮

f:id:hiroppon:20210303110318p:plain:w400

ElasticSearchと同程度のクリック数を切り取りながらもCTRの高い層を抽出出来ている。

これはSCDVによる類似度分析の結果をユーザ行動が支持したといえる。

細かい部分も大丈夫そう💮

f:id:hiroppon:20210303110308p:plain:w400

ElasticSearchのmlt scoreが高いゾーンでもSCDVの分解能が機能しているともいえる。

もっとがんばろう💢

f:id:hiroppon:20210303110313p:plain:w400

ElasticSearch よりも大きくクリックを削っているにも関わらずCTRも低くなってしまっており完敗。

色々見ていくと、ある特定のジャンルを苦手にしているようにも見え、GMMの段階でおかしくしちゃっているトピックがあるんじゃないかと考えている。

まとめ

今回、SCDVによる文章評価を曲がりなりにも本番投入まで持っていき、ある程度の有用性や可能性を見出すことが出来た。

ただ、精度面、性能面での大きな課題もあり、しかもバーターでバランスを取るとなると安定させるためには未だ相当の労力が必要そうだ。

特に重要なポイント

  • Tokenizer 全ての入り口にして、精度に最大寄与する部分。特に細かい部分の精度を求めた時ほどココの撃ち漏らしの影響が大きくなる。
  • 次元 WordVector と ClassSize のバランス。最終的な性能まで含めて考慮する。
  • GMM 時間がかかる上にWordTopicVectorの精度に大きく関わる。単体で評価しにくいのも厄介。

この辺、検討している人がいたら参考にして頂けたら。また情報交換などぜひぜひ。

AWSでもsysctlやらなきゃならんのか・・・

問題

構成

f:id:hiroppon:20201220100901p:plain

突発的に、１台のサーバーで５秒間だけ、502 Bad Gateway が数百〜数千出て困った。（②の部分）

f:id:hiroppon:20201219114822p:plain:w300

  • nginx.conf
 proxy_connect_timeout 5;

5秒はnginx設定によるモノなのだろうが、なんで一瞬だけ出るのか全然解らなかった。

nginxのerror.log にはこう出てて、これってproxy_passの設定ミスってる時の奴だよな。。と。。（③の部分）

  • /var/log/nginx/error.log
upstream prematurely closed connection while reading response header from upstream, client: 172.XX.XX.XX, server: _, request: "GET / HTTP/1.1", upstream: ...

一瞬、nginx -> node 間の unix socket の接続が詰まってパイプ詰まり問題でクライアント側まで詰まったのだろう。

パイプ詰まりにはバッファリングが常套手段なんだが、

しかしそもそもCPUもメモリーも問題無いのに、なんで詰まるんだ？？

色々調べる内に全然違う部分の問題を発見する

$ netstat -s | grep -e 'pruned' -e 'collapsed'
    1919109 packets pruned from receive queue because of socket buffer overrun
    15131248 packets collapsed in receive queue due to low socket buffer

なんか多くないか？これ多少は出るのは良いんだが秒単位でガンガン増えてくのはおかしい。

EC2は色々なサイズのサーバーをスグに作れるし、気軽にサイズを変えられるし、そうするとCPU,メモリーどころかネットワーク帯域まで丸ごと変わるので細かいチューンをする気は無かった。

だけど、これ明らかにソケットバッファが足りてない！

これを踏まえて仮説を立てる

④の通信が滞って最終的には詰まり、瞬間的に③が何かしらの一時的リソース不足（※１）で受け付けられなくなり、②、①の502に至る。 だから④の通信をチューンすれば解決するのでは？

  • ※１これも少なくとも５秒以内に解消する一瞬の問題なので捕まえられずにいる。計算上nfileやmaxconnでは無い事は解っている。heapsizeとかはあり得る。socketの先のカーネルで秒単位で起きる事といえば、ネットワークの輻輳が何かしらのロックを引き起こしている。とか。。しかしこれは追う気が起きない。多分追っても問題解消しねーし。

検証

えー今の時代にこんな細かい所調整すんのかよ・・・

net.core.somaxconn = 30000
net.core.netdev_max_backlog = 30000
net.ipv4.tcp_tw_reuse = 1

今までのsysctlの設定まさに動けば良い！的ｗこれが今風だと思っていた・・・

他はデフォを使っていて、特に関係ありそうな所はこの辺り。

net.core.rmem_default = 212992
net.core.rmem_max = 212992
net.core.wmem_default = 212992
net.core.wmem_max = 212992
net.ipv4.tcp_rmem = 4096        131072  6291456
net.ipv4.tcp_wmem = 4096        16384   4194304

ん？TCPのバッファってcore超えてて良いんだっけ？

調べたらMAX側が削られるだけらしい。

それでも200KBって少ない感覚だが昔の感覚と今の光配線やスイッチ性能だとレイテンシが段違いなんだろうな。

まずはネットワークバンドを確認

r6g.2xlargeは最大10Gbps だがPear To Pear だとどうなのよ？

# iperf
Command 'iperf' not found, but can be installed with:
apt install iperf

あ、、最近こんなことしないから入ってもいねーや

# apt install iperf

で、RDSやelasticCacheへは直接計測出来ないから、隣の別AZサーバー（placement groupではない）へ向けて計測

10K 位がメインの通信サイズ

ServerA

# iperf -s  -w 1M

ServerB

# iperf -w 10K -c ServerA
------------------------------------------------------------
Client connecting to ServerA, TCP port 5001
TCP window size: 20.0 KByte (WARNING: requested 10.0 KByte)
------------------------------------------------------------
　：
[ ID] Interval       Transfer     Bandwidth
[  3]  0.0-10.1 sec  37.4 MBytes  31.1 Mbits/sec

案外細っ！、いやAZ超えればこんなもんか。やっぱ実測は大事。 1window 辺り3.2ms

1M 位が最大レベルの通信サイズ

ServerB

# iperf -w 1M -c ServerA
------------------------------------------------------------
Client connecting to ServerA, TCP port 5001
TCP window size: 2.00 MByte (WARNING: requested 1.00 MByte)
------------------------------------------------------------
　：
[ ID] Interval       Transfer     Bandwidth
[  3]  0.0-10.0 sec   766 MBytes   643 Mbits/sec

1window辺り15ms

Round Trip Time (RTT)

# ip tcp_metrics
:
XXX.XXX.XXX.XXX age 2306.848sec cwnd 10 rtt 14817us rttvar 14478us source XXX.XXX.XXX.XXX
:

redisへの計測値 elasticCacheと隣のEC2の経路は違うから、まあ参考値でしか無いが、redisとはかなり大きめのデータをやり取りしているようだ。

アプリとしては小さなキーを扱っているのだが、multiで纏めて送っているケースも多いのでまあ納得。

そしてこれは計算しなくても感覚的にやばい。

計算

TCPは再送があるので、向うにデータが到着して届いたよ。の返事が来るまで送信データを捨てられない。 elasticCacheはバンドの実測が出来ないので仮に1M windowの時のbpsを使う。

643 Mbits/sec * 14.817ms = 9527331 bits = 1190916 bytes

約1MBのバッファが必要なようだ。色々仮置数字がある計算なので、僕はこういう時は３倍にする。（感覚以外の裏付け無し）

設定を変えてもう一回計測

# sysctl -w net.core.rmem_max=3145728
# sysctl -w net.core.wmem_max=3145728
# iperf -w 1M -c ServerA
------------------------------------------------------------
Client connecting to ServerA, TCP port 5001
TCP window size: 2.00 MByte (WARNING: requested 1.00 MByte)
------------------------------------------------------------
　：
[ ID] Interval       Transfer     Bandwidth
[  3]  0.0-10.0 sec  3.72 GBytes  3.19 Gbits/sec

おお！全然違うじゃねーか！！ ちなみに10Kの方は 31.1 => 201 Mbits/sec

こうなると50MB近くバッファが必要になるな。でもこういう時には大体効かないもんだ。しかしやってみる

# sysctl -w net.core.rmem_max=52428800
# sysctl -w net.core.wmem_max=52428800
# iperf -w 1M -c ServerA
------------------------------------------------------------
Client connecting to ServerA, TCP port 5001
TCP window size: 2.00 MByte (WARNING: requested 1.00 MByte)
------------------------------------------------------------
　：
[ ID] Interval       Transfer     Bandwidth
[  3]  0.0-10.0 sec  3.78 GBytes  3.24 Gbits/sec

うん。3Mでいい。

設定

そもそも

EC2はサーバサイズをフレキシブルに変えられるのも大きなメリットで、一緒に変わるネットワークバンドに合わせたチューンに依存したシステムは事故の元。本当は、ソケットバッファサイズは弄りたくない。

問題点の最終検証も兼ねてソケットバッファ以外の悪あがきをしてみる。

fin_timeout やコネクション数を弄って、枯渇リスクを回避できるか？

net.ipv4.tcp_fin_timeout = 5
net.ipv4.tcp_max_syn_backlog = 4096

net.core.netdev_max_backlog = 60000
net.core.somaxconn = 60000
net.ipv4.tcp_tw_reuse = 1

この辺の悪あがきも効かず。

net.ipv4.conf.default.accept_source_route = 0
net.ipv4.tcp_rfc1337 = 1

socket buffer をチューン

net.core.rmem_max=3145728
net.core.wmem_max=3145728

効いた！！

f:id:hiroppon:20201220115411p:plain:w300

１日平和だった。ビックリするくらい劇的に改善！！

やっぱAWSパワーで解決はだめだ。順を追って丁寧に解決していくインフラ的な作業はまだまだ残るのだな・・・

おっさんの悩み

インフラ知識は本来コンピューターの全ての基本なのだが、これだけ発達した技術の中では全部身につけるのは非効率だと思う。 若い技術者は即効性のあるサービスに直結する新技術を学んで、すぐに戦力として活躍して欲しいし、殆どの人はそうしている。

それが効率的だ。

しかしそうすると誰もインフラが解らないチームが出来上がる。 一つ一つ細かく紐解いていく事が出来ない（思いも寄らない）から金で解決する事になる。でもこれって技術力の敗北だよね？

技術者全体、業界全体として力が失われていく圧力に他ならない。（今のSI界隈を見てると強く感じる）

また民芸の後継者問題よろしく、インフラ解る人が劇的に減ってきて、歯止めが掛かる気配がない。 やっぱり若い技術者もしっかりインフラをやらせた方が良いんだろうか？ぐるぐる。。。

Graviton2のアクセラレータの効果

前回の続き 2020-06-18から1日間の記事一覧 - 中年engineerの独り言 - crumbjp

2xlarge以上は圧縮アクセラレータが付くらしい

https://d1.awsstatic.com/events/reinvent/2019/REPEAT_1_Deep_dive_on_Arm-based_EC2_instances_powered_by_AWS_Graviton_CMP322-R1.pdf

P24.

• 1Tbit/s of compression accelerators
　• 2xlarge and larger instances will have a compression device
　• DPDK and Linux kernel drivers will be available ahead of GA
　• Data compression at up to 15GB/s and decompression at up to 11GB/s

本番をサーバの負荷

・c6g.xlarge x 11 から c6g.2xlarge x 10 に変更

f:id:hiroppon:20200720173617p:plain
CPU

微妙にCPU数が減っているにも関わらず負荷は低減した。 プロセスの構成は、nginx => nodejs (express) 。

・nginx のCPU負荷が劇的に低減 => gzip on; の部分が効いたと思われる。

・nodejsの負荷も下がった。socketIOのペイロード圧縮部分が効いていると思われる。

というわけで、c6g.xlarge x2 よりは c6g.2xlarge x1 の方がお得。