Elegir una función hash en el problema de fragmentación de datos

En Miro estamos trabajando en el proceso de fragmentación de bases de datos de Postgres y utilizamos diferentes enfoques según los requisitos comerciales. Recientemente, nos enfrentamos a la tarea de fragmentar nuevas bases de datos, durante la cual elegimos un nuevo enfoque para fragmentar, basado en hash consistente .

Durante la implementación de este enfoque, una de las preguntas centrales fue qué implementación de la función hash no criptográfica deberíamos elegir y utilizar. En este artículo, describiré los criterios y el algoritmo de comparación que desarrollamos y usamos en la práctica para encontrar la mejor implementación.

Sobre el enfoque arquitectónico

Hay muchos productos ( mongo , redis , etc.) que usan hash consistente para fragmentar, y nuestra implementación será muy similar a ellos.

Supongamos que, en la entrada, tenemos un conjunto de entidades con claves de fragmentación seleccionadas, de un tipo de cadena. Para estas claves, utilizando la función hash, obtenemos un código hash de cierta longitud, para el cual definimos el slot requerido mediante la operación módulo. El número de ranuras y la correspondencia de entidades a ranuras es fijo. También es necesario mantener la correspondencia entre los rangos de ranuras y fragmentos, lo cual no es una tarea difícil, y un archivo de configuración es bastante adecuado para la ubicación de almacenamiento. 

Las ventajas de este enfoque son:

• distribución uniforme de entidades entre fragmentos;

  
  
  
  
  

• determinar la correspondencia de entidades y fragmentos sin almacenamiento adicional con un mínimo de costos de recursos;

  
  
  
  
  

• la capacidad de agregar nuevos fragmentos al clúster.

  
  
  
  
  

Contras:

• ineficiencia de algunas operaciones de búsqueda, en las que es necesario realizar consultas para todos los fragmentos;

  
  
  
  
  

• proceso de fragmentación bastante complicado.

  
  
  
  
  

Requisitos 

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.