Escolhendo uma função hash no problema de fragmentação de dados

Nós, da Miro, estamos trabalhando no processo de fragmentação dos bancos de dados Postgres e usamos diferentes abordagens, dependendo dos requisitos do negócio. Recentemente, enfrentamos a tarefa de fragmentar novos bancos de dados, durante a qual escolhemos uma nova abordagem de fragmentação para nós, com base em hashing consistente .

Durante a implementação dessa abordagem, uma das questões centrais era qual implementação da função hash não criptográfica deveríamos escolher e usar. Neste artigo, descreverei os critérios e o algoritmo de comparação que desenvolvemos e usamos na prática para encontrar a melhor implementação.

Sobre a abordagem arquitetônica

Existem muitos produtos ( mongo , redis , etc.) que usam hashing consistente para sharding, e nossa implementação será muito semelhante a eles.

Vamos, na entrada, ter um conjunto de entidades com chaves de fragmentação selecionadas, do tipo string. Para essas chaves, usando a função hash, obtemos um código hash de um determinado comprimento, para o qual definimos o slot necessário através da operação do módulo. O número de slots e a correspondência entre entidades e slots são fixos. Também é necessário manter a correspondência entre os intervalos de slots e shards, o que não é uma tarefa difícil, e um arquivo de configuração é bastante adequado para o local de armazenamento. 

As vantagens desta abordagem são:

• distribuição uniforme de entidades em fragmentos;

  
  
  
  
  

• determinar a correspondência de entidades e shards sem armazenamento adicional com um mínimo de custos de recursos;

  
  
  
  
  

• a capacidade de adicionar novos shards ao cluster.

  
  
  
  
  

Contras:

• ineficiência de algumas operações de busca, nas quais é necessário fazer consultas para todos os shards;

  
  
  
  
  

• um processo de resharding 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.