データシャーディング問題でのハッシュ関数の選択

Miroでは、Postgresデータベースをシャーディングするプロセスに取り組んでおり、ビジネス要件に応じてさまざまなアプローチを使用しています。最近、新しいデータベースをシャーディングするという課題に直面しました。その間、一貫したハッシュに基づいて、シャーディングへの新しいアプローチを選択しました。

このアプローチの実装中、中心的な質問の1つは、非暗号化ハッシュ関数のどの実装を選択して使用する必要があるかということでした。この記事では、最適な実装を見つけるために開発して実際に使用した基準と比較アルゴリズムについて説明します。

建築的アプローチについて

シャーディングに一貫したハッシュを使用する多くの製品（mongo、redisなど）があり、実装はそれらと非常に似ています。

入力に、文字列タイプの選択されたシャーディングキーを持つエンティティのセットがあるとします。これらのキーについては、ハッシュ関数を使用して、特定の長さのハッシュコードを取得します。このコードに対して、モジュロ操作によって必要なスロットを定義します。スロットの数とエンティティのスロットへの対応は固定されています。また、スロットとシャードの範囲の対応を維持する必要がありますが、これは難しい作業ではなく、構成ファイルは保管場所に非常に適しています。 

このアプローチの利点は次のとおりです。

• シャード間でのエンティティの均等な分散。

  
  
  
  
  

• 最小限のリソースコストで、追加のストレージなしでエンティティとシャードの対応を決定します。

  
  
  
  
  

• クラスターに新しいシャードを追加する機能。

  
  
  
  
  

短所：

• すべてのシャードに対してクエリを実行する必要がある一部の検索操作の非効率性。

  
  
  
  
  

• かなり複雑なリシャーディングプロセス。

  
  
  
  
  

要件 

java- -.

- , 256 , - - , 4 . - 2 4 .

-:

1. , , ;

   
   
   
   
   

2. . , , ;

   
   
   
   
   

3. ( );

   
   
   
   
   

4. . , .

   
   
   
   
   

: - ; - , . 

. 

  , . 

java-  - -:

1. DJB2  (32-);

   
   
   
   
   

2. SDBM (32-);

   
   
   
   
   

3. LoseLose (32-);

   
   
   
   
   

4. FNV-1 / FNV-1a (32-);

   
   
   
   
   

5. CRC16 (16-) ;

   
   
   
   
   

6. Murmur2/Murmur3 (32-).

   
   
   
   
   

 

1. , 216,553 ;

   
   
   
   
   

2. , UTF-8.

   
   
   
   
   

(- ) -  "2", "4", "8", "16", "32", "64", "128", "256".

:

1. , - ops/ms (- );

   
   
   
   
   

2. - . . , - , .

   
   
   
   
   

JMH.  :

, 256 . - , .

• - warmup- - 50;

  
  
  
  
  

• - measurement- - 100;

  
  
  
  
  

• - throughput
  
  
  
  

  
  
  
  
  

• -Xms1G, -Xmx8G
  
  
  
  

  
  
  
  
  

• GCProfiler

  
  
  
  
  

.

, α=0,05, . .

:

1. , , ;

   
   
   
   
   

2. -  , , ;

   
   
   
   
   

3.   ,
   
   

   
   
   
   
   

   

   
   
   
   
   

   n — , — , -  

   
   
   
   
   

   

   
   
   
   
   

   - , a a b -

   
   
   
   
   

4. ,

   
   
   
   
   

   ,

   
   
   
   
   

   - , , - , ;

   
   
   
   
   

5. , α k ;

   
   
   
   
   

6. , , — .

   
   
   
   
   

. 

:

, 256. 16384, 8192, 4096, 2048, 1024, , . 

- , -. , .

.

( ) .

:

, , loseLose, crc16 sdbm. 

16 256 :

murmur2 , murmur;  crc16 sdbm .

, crc16, murmur2, murmur3 . 

, .

, loseLose, Djb2, Sdbm, , ,   :

Fnv1 Fnv1a , :

.

:

, crc16, murmur2, murmur3 , .

, : .

.   murmur2/murmur3 8 . 

. , : crc16, murmur2/murmur3. crc16, murmur2/murmur3.

, , murmur2/murmur3.