Auswahl einer Hash-Funktion im Data-Sharding-Problem

Wir bei Miro arbeiten am Sharding von Postgres-Datenbanken und verwenden je nach Geschäftsanforderungen unterschiedliche Ansätze. Vor kurzem standen wir vor der Aufgabe, neue Datenbanken zu sharden. Dabei haben wir einen neuen Ansatz für das Sharding für uns gewählt, der auf konsistentem Hashing basiert .

Bei der Implementierung dieses Ansatzes war eine der zentralen Fragen, welche Implementierung der nicht kryptografischen Hash-Funktion wir auswählen und verwenden sollten. In diesem Artikel werde ich die Kriterien und den Vergleichsalgorithmus beschreiben, die wir entwickelt und in der Praxis verwendet haben, um die beste Implementierung zu finden.

Über den architektonischen Ansatz

Es gibt viele Produkte ( Mongo , Redis usw.), die konsistentes Hashing für das Sharding verwenden, und unsere Implementierung wird ihnen sehr ähnlich sein.

Lassen Sie uns an der Eingabe eine Reihe von Entitäten mit ausgewählten Sharding-Schlüsseln eines Zeichenfolgentyps haben. Für diese Schlüssel erhalten wir mit der Hash-Funktion einen Hash-Code einer bestimmten Länge, für den wir den erforderlichen Slot durch die Modulo-Operation definieren. Die Anzahl der Slots und die Entsprechung von Entitäten zu Slots ist festgelegt. Es ist auch notwendig, die Entsprechung zwischen den Bereichen von Steckplätzen und Shards aufrechtzuerhalten, was keine schwierige Aufgabe ist, und eine Konfigurationsdatei ist für den Speicherort gut geeignet. 

Die Vorteile dieses Ansatzes sind:

• gleichmäßige Verteilung der Entitäten auf die Scherben;

  
  
  
  
  

• Bestimmen der Korrespondenz von Entitäten und Shards ohne zusätzlichen Speicher mit einem Minimum an Ressourcenkosten;

  
  
  
  
  

• die Möglichkeit, dem Cluster neue Shards hinzuzufügen.

  
  
  
  
  

Nachteile:

• Ineffizienz einiger Suchvorgänge, bei denen Abfragen für alle Shards erforderlich sind;

  
  
  
  
  

• ziemlich komplizierter Resharding-Prozess.

  
  
  
  
  

Bedarf 

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.