Memilih fungsi hash dalam masalah sharding data

Kami di Miro sedang mengerjakan proses sharding database Postgres dan menggunakan pendekatan yang berbeda tergantung pada kebutuhan bisnis. Baru-baru ini, kami menghadapi tugas untuk memecah basis data baru, di mana kami memilih pendekatan baru untuk pemenggalan, berdasarkan pencirian yang konsisten .

Selama penerapan pendekatan ini, salah satu pertanyaan utama adalah penerapan fungsi hash non-kriptografi mana yang harus kita pilih dan gunakan. Pada artikel ini, saya akan menjelaskan kriteria dan algoritma perbandingan yang kami kembangkan dan gunakan dalam praktik untuk menemukan implementasi terbaik.

Tentang pendekatan arsitektur

Ada banyak produk ( mongo , redis , dll.) Yang menggunakan hashing yang konsisten untuk sharding, dan penerapan kami akan sangat mirip dengannya.

Misalkan, pada input, kita memiliki sekumpulan entitas dengan kunci sharding yang dipilih, dari tipe string. Untuk kunci-kunci ini, dengan menggunakan fungsi hash, kami mendapatkan kode hash dengan panjang tertentu, yang kami tentukan slot yang diperlukan melalui operasi modulo. Jumlah slot dan korespondensi entitas dengan slot tetap. Penting juga untuk menjaga korespondensi antara rentang slot dan pecahan, yang bukan merupakan tugas yang sulit, dan file konfigurasi cukup cocok untuk lokasi penyimpanan. 

Keuntungan dari pendekatan ini adalah:

• pemerataan entitas di seluruh pecahan;

  
  
  
  
  

• menentukan korespondensi entitas dan pecahan tanpa penyimpanan tambahan dengan biaya sumber daya minimum;

  
  
  
  
  

• kemampuan untuk menambahkan pecahan baru ke kluster.

  
  
  
  
  

Kekurangan:

• ketidakefisienan dari beberapa operasi pencarian, di mana perlu membuat kueri untuk semua pecahan;

  
  
  
  
  

• proses resharding yang agak rumit.

  
  
  
  
  

Persyaratan 

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.