最初にいくつかのコンテキスト、最後に解決策 :
SCANコマンドから>終了の保証
SCANアルゴリズムは、反復されたコレクションのサイズが指定された最大サイズに制限されたままである場合にのみ終了することが保証されます。そうでない場合、常に増加するコレクションを反復すると、SCANが完全な反復を終了しない可能性があります。
これは直感的に簡単に確認できます。コレクションが大きくなると、考えられるすべての要素にアクセスするために行う作業が増えます。反復を終了できるかどうかは、SCANへの呼び出しの数とそのCOUNTオプション値を次のレートと比較して異なります。コレクションは大きくなります。
しかし、COUNTオプションには次のように書かれています:
重要:すべての反復に同じCOUNT値を使用する必要はありません。呼び出し元は、次の呼び出しで渡されるカーソルがコマンドの前の呼び出しで取得されたカーソルである限り、必要に応じて1つの反復から別の反復にカウントを自由に変更できます。
スキャンの保証から、覚えておくことが重要です:
- 特定の要素が複数回返される場合があります。重複した要素の場合を処理するのはアプリケーション次第です。たとえば、複数回再適用した場合に安全な操作を実行するために、返された要素のみを使用します。
- 完全な反復中にコレクションに常に存在しなかった要素は、返される場合とされない場合があります。未定義です。
解決策の鍵はカーソル自体にあります。 RedisのSCANカーソルの意味を理解するを参照してください。 カーソルは実際にはテーブルサイズに対するインデックスのビット反転であるため、スキャンの進行状況の割合を推測することができます。
DBSIZE
の使用 またはINFO keyspace
コマンドを使用すると、いつでもキーの数を取得できます:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
もう1つの情報源は、文書化されていないDEBUG htstats index
です。 、ただ感じをつかむために:
> DEBUG htstats 0
[Dictionary HT]
Hash table 0 stats (main hash table):
table size: 262144
number of elements: 200032
different slots: 139805
max chain length: 8
avg chain length (counted): 1.43
avg chain length (computed): 1.43
Chain length distribution:
0: 122339 (46.67%)
1: 93163 (35.54%)
2: 35502 (13.54%)
3: 9071 (3.46%)
4: 1754 (0.67%)
5: 264 (0.10%)
6: 43 (0.02%)
7: 6 (0.00%)
8: 2 (0.00%)
[Expires HT]
No stats available for empty dictionaries
テーブルサイズは、キーの数に続く2の累乗です。キー:200032 =>テーブルサイズ:262144
解決策:
目的のCOUNT
を計算します すべてのスキャンの引数。
頻度(F
)でSCANを呼び出すとします。 10 Hz(100 msごと)のHz)で、5秒(T
s)。したがって、これをN = F*T
で終了する必要があります 呼び出し、N = 50
この例では。
最初のスキャンの前に、現在の進捗状況が0であることがわかっているため、残りのパーセントはRP = 1
です。 (100%)。
すべてのSCAN
の前 通話(または、DBSIZE
のラウンドトリップ時間(RTT)を節約したい場合は、COUNTを調整するすべての通話数 呼び出し)、DBSIZE
を呼び出します キーの数を取得するにはK
。
COUNT = K*RP/N
を使用します
最初の呼び出しの場合、これはCOUNT = 200032*1/50 = 4000
です。 。
その他の呼び出しについては、RP = 1 - ReversedCursor/NextPowerOfTwo(K)
を計算する必要があります 。
たとえば、すでに20回の呼び出しを行ったとすると、N = 30
になります。 (残りの通話数)。 DBSIZE
に電話しました K = 281569
を取得しました 。これは、NextPowerOfTwo(K) = 524288
を意味します 、これは2^19です。
次のカーソルは10進数で14509=000011100010101101
バイナリで。テーブルサイズは2^19なので、18ビットで表します。
ビットを逆にして、101101010001110000
を取得します バイナリで=10進数で185456。これは、524288のうち185456をカバーしたことを意味します。そして:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
したがって、調整する必要があります:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
したがって、次のSCAN
6100
を使用して電話をかける 。次の理由で増加したことは理にかなっています:
- キーの数が200032から281569に増えました。
- 残りの通話の初期見積もりの60%しか残っていませんが、キースペースの65%がスキャンされるまで保留されているため、進捗は遅れています。
これはすべて、すべてのキーを取得していることを前提としています。 パターンマッチングの場合 、過去を使用して、検出されるキーの残りの量を見積もる必要があります。係数としてPM
を追加します (一致率)COUNT
へ 計算。
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
20回の呼び出しの後、keysFound = 2000
のみが見つかった場合 キー、次に:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
これは、これまでのところ、キーの2%のみがパターンに一致していることを意味します。
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
このアルゴリズムはおそらく改善される可能性がありますが、あなたはその考えを理解しています。
COUNT
でいくつかのベンチマークを実行してください SCAN
のミリ秒数を測定するために、最初に使用する数値 必要な呼び出しの数についての期待を緩和する必要があるかもしれないので、取ってください(N
)サーバーをブロックせずに妥当な時間でこれを実行し、F
を調整します およびT
それに応じて。