Devasa Anahtar Kümeleri için Hızlı ve Ölçeklenebilir Minimal Perfect Hashing

Antoine Limasset¹, Guillaume Rizk¹, Rayan Chikhi² ve Pierre Peterlongo¹

¹ IRISA Inria Rennes Bretagne Atlantique, GenScale ekibi, Campus de Beaulieu, 35042 Rennes, Fransa
² CNRS, CRIStAL, Université de Lille, Inria Lille – Nord Europe, Fransa

Özet

Minimal perfect hash fonksiyonları, statik kümeler üzerinde alan açısından verimli ve çakışmasız hashing sağlar. Bu tür fonksiyonları oluşturan mevcut algoritmalar ve uygulamalar, yüksek oluşturma süresi ile RAM veya harici bellek kullanımı nedeniyle işleyebilecekleri girdi elemanı sayısı açısından pratik sınırlamalara sahiptir. Basit bir algoritmayı yeniden ele alıyor ve özellikle oluşturma süresi ile bellek kullanımı açısından mevcut en iyi yöntemlerle son derece rekabetçi olduğunu gösteriyoruz.

BBhash adlı paralel bir C++ uygulaması sunuyoruz. Bu uygulama, 8 iş parçacığı ve 5 GB bellek kullanarak 10¹⁰ eleman için 7 dakikadan kısa sürede bir minimal perfect hash fonksiyonu oluşturabilir ve elde edilen fonksiyon eleman başına 3.7 bit kullanır. Bildiğimiz kadarıyla bu aynı zamanda 10¹² kardinaliteli bir girdi üzerinde başarıyla test edilmiş ilk uygulamadır.

Kaynak kodu: https://github.com/rizkg/BBHash

1998 ACM Konu Sınıflandırması: H.3.1, E.2
Anahtar kelimeler ve ifadeler: Minimal Perfect Hash Fonksiyonları, Algoritmalar, Veri Yapıları, Büyük Veri
Dijital Nesne Tanımlayıcısı: 10.4230/LIPIcs...

arXiv:1702.03154v2 [cs.DS] 16 Şub 2017

1 Giriş

N elemandan (anahtarlardan) oluşan S kümesi verildiğinde, bir minimal perfect hash fonksiyonu (MPHF), S kümesindeki her anahtarı [1, N] aralığında bir tam sayıya eşleyen enjeksiyonlu bir fonksiyondur. Başka bir deyişle, bir MPHF, S kümesindeki her anahtarı çakışmasız bir şekilde ve mümkün olan en küçük tam sayı aralığını kullanarak etiketler.

Dikkat çekici bir özellik, bu fonksiyonların depolanabileceği küçük alandır: anahtarların boyutundan bağımsız olarak anahtar başına yalnızca birkaç bit gerekir. Ayrıca bir MPHF sorgusu sabit zamanda gerçekleştirilir. Bir MPHF, bir anahtar–değer deposu (örneğin bir hash tablosu) kullanılarak kolayca elde edilebilir; ancak böyle bir temsil, hem anahtarların hem de tam sayı etiketlerinin açık biçimde saklanması nedeniyle makul olmayan miktarda alan kaplar.

Bir MPHF’yi temsil etmek için gereken teorik minimum alan miktarının şu olduğu bilinmektedir:

log₂(e)N ≈ 1.44N bit [10, 14].

Pratikte, büyük anahtar kümeleri (milyarlarca anahtar) için birçok uygulama anahtar sayısından bağımsız olarak anahtar başına 3N bitten daha az alan elde etmektedir [2, 9]. Ancak hiçbir uygulama büyük anahtar kümeleri için asimptotik olarak bu alt sınıra yaklaşmamaktadır.

MPHF’lerin genellikle devasa dizge kümelerini indekslemek için kullanıldığı düşünüldüğünde — örneğin biyoinformatikte [6, 7, 8], ağ uygulamalarında [12] veya veritabanlarında [5] — temsil alanının azaltılması önem taşır.

Bu uygulamaların birçoğunda MPHF’lerin aslında statik sözlükler oluşturmak için kullanıldığını gözlemliyoruz; yani anahtar kümesinin sabit olduğu ve hiçbir zaman güncellenmediği anahtar–değer depoları [6, 8]. Kullanıcının yalnızca MPHF’yi, statik kümede bulunduğu garanti edilen anahtarların karşılık gelen değerlerini almak için sorguladığını varsayarsak, anahtarların kendilerinin bellekte saklanması zorunlu değildir. Ancak sözlükteki ilişkili değerlerin genellikle saklanması gerekir ve çoğu zaman bunların boyutu MPHF’nin boyutundan çok daha büyüktür.

Bu tür sözlüklerin temsili iki bileşenden oluşur: alan açısından verimli bir MPHF ve görece daha fazla alan gerektiren bir değer kümesi. Bu uygulamalarda MPHF’nin anahtar başına 1.44 bit mi yoksa 3 bit mi kullandığı tartışılabilir biçimde kritik bir unsur değildir.

Pratikte büyük ölçekli uygulamalar için önemli bir darboğaz, MPHF’lerin oluşturma adımıdır; hem bellek kullanımı hem de hesaplama süresi açısından. MPHF’leri verimli biçimde oluşturmak aktif bir araştırma alanıdır.

Son yıllardaki birçok MPHF oluşturma algoritması, hipergrafların verimli soyulmasına (peeling) dayanmaktadır [1, 3, 4, 11]. Ancak bu yöntemler, elde edilen veri yapısına kıyasla oluşturma sırasında bir büyüklük mertebesi daha fazla alan gerektirir. Milyarlarca anahtar için, MPHF’nin kendisi sıradan bir bilgisayarın ana belleğine kolayca sığabilirken, oluşturma algoritması büyük bellekli sunucular gerektirir.

Bunu ele almak için Botelho ve çalışma arkadaşları [4], birçok daha küçük MPHF oluşturarak problemi bölmeyi önermiştir; Belazzougui ve diğerleri [1] ise hipergraf soyma için harici bellek kullanan bir algoritma önermiştir. Çok yakın zamanda Genuzio ve diğerleri [11], Gaussian elimination tekniği üzerinde pratik iyileştirmeler göstererek bunu oluşturma süresi, arama süresi ve son yapının alanı açısından [1] ile rekabetçi hale getirmiştir.

Bu teknikler, bildiğimiz kadarıyla mevcut en ölçeklenebilir çözümlerdir. Ancak mevcut uygulamalar değerlendirildiğinde, bir milyar anahtarı önemli ölçüde aşan kümeler için MPHF oluşturma işlemi zaman ve alan kullanımı açısından hâlâ engelleyici olmaktadır.

Önceki çalışmalarda [6, 12, 16], bit dizileri veya parmak izleri (fingerprints) kullanarak MPHF oluşturmak için basit bir fikir incelenmiştir. Ancak bu yaklaşım hipergraf tabanlı yöntemlere kıyasla görece daha az ilgi görmüş ve bağımsız bir MPHF kütüphanesi içinde herkese açık bir uygulaması bulunmamaktadır.

Bu makalede bu fikri yeniden ele alıyor ve yeni katkılar sunuyoruz: oluşturma sırasında alan kullanımının dikkatli bir analizi ve mevcut en iyi yöntemlerle kapsamlı karşılaştırmalar içeren verimli bir paralel uygulama.

Girdi bölümlendirmesi yapmadan, son yapının gerektirdiği alana neredeyse eşdeğer bellek kullanarak bir MPHF oluşturmanın mümkün olduğunu gösteriyoruz. BBhash ("Basic Binary representAtion of Successive Hashing") adlı yeni bir uygulama öneriyoruz ve şu özelliklere sahiptir:

• Oluşturma sırasındaki alan fazlalığı, MPHF’nin kapladığı alana kıyasla küçüktür
• Çok iş parçacıklı çalışır
• Çok büyük anahtar kümelerine ölçeklenebilir ( 1 trilyon anahtara kadar test edilmiştir )

Bildiğimiz kadarıyla yukarıdaki özelliklerden herhangi ikisini aynı anda sağlayan başka kullanılabilir bir uygulama yoktur.

Ayrıca algoritma bir zaman/bellek değiş tokuşu sağlar: son yapıda ve oluşturma sırasında eleman başına birkaç bit daha fazla kullanma karşılığında daha hızlı oluşturma ve daha hızlı sorgu süreleri elde edilebilir.

On milyar anahtar için 6 dakika 47 saniyede ve 5 GB’tan az çalışma belleği kullanarak, ayrıca bir trilyon anahtar için 36 saatten kısa sürede ve 637 GB bellek kullanarak bir MPHF oluşturduk. Genel olarak diğer mevcut MPHF oluşturma yaklaşımlarıyla karşılaştırıldığında uygulamamız, oluşturma sırasında en az iki büyüklük mertebesi daha alan verimli ve bir büyüklük mertebesi daha hızlıdır.

Ortaya çıkan MPHF, biraz daha yüksek alan kullanmasına rağmen diğer yöntemlere göre daha hızlı veya karşılaştırılabilir sorgu süreleri sunar.

MPHF Oluşturma Prosedürü

MPHF oluşturma prosedürümüz daha önce yayımlanmış teknikleri yeniden ele almaktadır [6, 12].

F₀ anahtar kümesi verildiğinde, klasik bir hash fonksiyonu h₀, anahtarları [1, |F₀|] aralığında bir tam sayıya eşler. |F₀| boyutunda A₀ adlı bir bit dizisi oluşturulur; burada i konumunda 1 olması, yalnızca ve yalnızca F₀ kümesinden tam olarak bir elemanın hash değerinin i olması durumunda gerçekleşir.

F₀ içindeki iki anahtarın aynı hash değerine sahip olması durumuna çakışma (collision) diyoruz. Çakışmaya dahil olan F₀ anahtarları yeni bir F₁ kümesine eklenir.

Süreç F₁ ve yeni bir hash fonksiyonu h₁ ile tekrar edilir. |F₁| boyutunda yeni bir A₁ bit dizisi oluşturulur ve A₀ için kullanılan prosedürle aynı şekilde doldurulur (yalnızca F₀ yerine F₁, h₀ yerine h₁ kullanılır).

Süreç F₂, F₃, ... ile devam eder ve bu kümelerden biri olan F_last+1 boş olana kadar sürer.

A₀, A₁, ..., A_last bit dizilerini bir A dizisi içinde birleştirerek bir MPHF elde ederiz.

Bir sorgu gerçekleştirmek için bir anahtar, h₀, h₁, ... hash fonksiyonlarıyla ardışık olarak hash edilir; bu işlem, hash fonksiyonu hᵢ tarafından verilen konumdaki Aᵢ değerinin 0 olduğu sürece devam eder. Sonunda, yapı gereği, A dizisinde bazı i = d için bir konumda 1 değerine ulaşılır. Buna anahtarın seviyesi (level) d denir. MPHF tarafından döndürülen indeks, A içindeki bu 1’in rank değeridir.

Şekil 1 – MPHF Oluşturma ve Sorgu Örneği

Girdi, N = 6 anahtardan oluşan F₀ kümesidir (k₁’den k₆’ya).

Tüm anahtarlar h₀ hash fonksiyonu ile hash edilir ve hash fonksiyonunun verdiği konumlara göre A₀ dizisine yerleştirilmeye çalışılır. k₃ ve k₆ anahtarları dizide çakışma yaşamaz; bu nedenle A₀ içindeki karşılık gelen bitler 1 olarak ayarlanır. Çakışmaya dahil olan F₀ anahtarları yeni bir F₁ kümesine yerleştirilir.

İkinci seviyede F₁ kümesindeki anahtarlar h₁ hash fonksiyonu ile hash edilir. k₁ ve k₅ anahtarları benzersiz biçimde yerleştirilirken k₂ ve k₄ çakışır; bu nedenle F₂ kümesinde saklanırlar.

h₂ hash fonksiyonu ile F₂ kümesindeki anahtarlar artık çakışmaz ve süreç tamamlanır.

MPHF sorgu işlemi oluşturma algoritmasına çok benzer. A = A₀, A₁, A₂ dizilerinin birleştirilmiş hali olsun. k₂ anahtarını sorgulamak için anahtar önce h₀ ile hash edilir. A₀ içindeki ilgili değer 0 olduğundan k₂ daha sonra h₁ ile hash edilir. A₁ içindeki değer yine 0’dır. Son olarak h₂ ile hash edildiğinde A₂ içindeki değer 1 olur ve sorgu durur.

MPHF tarafından döndürülen indeks, A içindeki bu 1’in rank değeridir (bu örnekte 5).

Bu örnekte k₁, k₂, k₃, k₄, k₅, k₆ anahtarları sorgulandığında döndürülen MPHF değerleri sırasıyla 4, 5, 2, 6, 3 ve 1’dir.

Oluşturma sırasında her d seviyesinde çakışmalar, |A_d| boyutunda geçici bir C_d bit dizisi kullanılarak tespit edilir. Başlangıçta tüm C_d bitleri 0 olarak ayarlanır. F_d kümesinden iki veya daha fazla anahtar hash fonksiyonu h_d tarafından verilen aynı i değerine sahipse C_d[i] = 1 yapılır. Son olarak C_d[i] = 1 ise A_d[i] = 0 olur.

Resmi olarak:

C_d[i] = 1 ⇒ A_d[i] = 0

(h_d[x] = i and A_d[i] = 0 and C_d[i] = 0) ⇒ A_d[i] = 1 (ve C_d[i] = 0)

(h_d[x] = i and A_d[i] = 1 and C_d[i] = 0) ⇒ A_d[i] = 0 and C_d[i] = 1

2.2.2 Sorgular

Bir x anahtarının sorgulanması, A_d[h_d(x)] = 1 olacak en küçük d değerinin bulunmasıyla gerçekleştirilir. x’in (minimal olmayan) hash değeri daha sonra şu şekilde olur:

(i < d |F_i|) + h_d(x)

2.2.3 Minimalite

Fonksiyonun görüntü aralığının [1, |F₀|] olmasını sağlamak için A_i bit dizilerindeki her 1 için kümülatif rank değeri hesaplanır.

d, A_d[h_d(x)] = 1 koşulunu sağlayan en küçük değer olsun. Minimal perfect hash değeri şu şekilde verilir:

∑_{i<d} weight(A_i) + rank(A_d[h_d(x)])

burada weight(A_i), A_i dizisinde 1 olan bitlerin sayısını ifade eder ve

rank(A_d[y]) = ∑_{j<y} A_d[j]

şeklindedir.

Bu, diğer MPHF’lerde de kullanılan klasik bir yöntemdir [3].

2.2.4 Daha Hızlı Sorgu ve Oluşturma Süreleri (Parametre γ)

Oluşturmanın çalışma süresi, her d seviyesinde A_d dizilerindeki çakışma sayısına bağlıdır.

Çakışmaları azaltmanın ve dolayısıyla her seviyede daha fazla anahtar yerleştirmenin bir yolu, bit dizilerini (A_d ve C_d) |F_d| değerinden daha büyük seçmektir. Bu amaçla γ ∈ ℝ, γ ≥ 1 parametresini tanımlıyoruz:

|C_d| = |A_d| = γ|F_d|

γ = 1 olduğunda A’nın boyutu minimaldir. γ ≥ 2 olduğunda çakışma sayısı önemli ölçüde azalır ve böylece oluşturma ve sorgu süreleri düşer; ancak MPHF yapısı daha büyük olur.

Yapının beklenen boyutu, [6]’da daha önce verilen basit bir argüman kullanılarak belirlenebilir.

γ = 1 olduğunda d seviyesinde çakışmayan anahtarların beklenen sayısı |A_d| e⁻¹ olur; dolayısıyla:

|A_d| = |A_{d-1}| (1 − e⁻¹) = |A₀| (1 − e⁻¹)ᵈ

Toplamda hashing şemasının gerektirdiği beklenen bit sayısı:

∑_{d≥0} |A_d| = eN

burada N = |F₀|.

γ ≥ 1 olduğunda d seviyesinde çakışma yaşamayan anahtarların beklenen oranı |A_d| e^{-1/γ} olur. Her A_d anahtar başına γ bit kullandığından, MPHF için gereken toplam bit sayısının beklenen değeri:

γ e^{1/γ} N

olur.

2.3 Analiz

Aşağıdaki gözlem ve lemmaların kanıtları Ek bölümünde verilmiştir.

2.3.1 MPHF’nin Boyutu

Oluşturma sırasında disk alanını analiz ediyoruz. Hatırlanacağı üzere d seviyesinin oluşturulması sırasında çakışmaları kaydetmek için |A_d| boyutunda C_d adlı bir bit dizisi kullanılır. C_d dizisi yalnızca d’inci seviyede gereklidir ve d + 1 seviyesinden önce silinir.

Lemma 1. γ > 0 için MPHF’nin alanı:

S = γ e^{1/γ} N bittir

Oluşturma sırasında maksimum alan γ ≤ log(2)⁻¹ olduğunda S, aksi halde 2S bit olur.

Uygulama

C++ ile yazılmış BBhash uygulamasını sunuyoruz. Şu adreste mevcuttur:

http://github.com/rizkg/BBHash

Rank Uygulaması

rank işlemini uygulamak için klasik bir teknik kullanıyoruz: A içinde bulunan 1 bitlerinin bir kısmının rank değerleri kaydedilir ve aradaki rank değerleri bu kayıtlı değerler kontrol noktaları olarak kullanılarak dinamik biçimde hesaplanır.

Pratikte sayaçlar için 64-bit tamsayılar kullanılır ve varsayılan olarak her 512 konumda bir yerleştirilir. Bu değerler iyi bir hız/bellek dengesi sağlar; MPHF’nin boyutunu 1.125 katsayısı kadar artırırken iyi sorgu performansı elde edilmesine olanak tanır.

Paralelleştirme

Paralelleştirme, anahtarların birden fazla iş parçacığı arasında bölünmesiyle sağlanır. Algoritma aynı bellek alanı üzerinde eşzamanlı olarak birden fazla iş parçacığında çalıştırılır.

A_i dizilerine eşzamanlı erişim için derleyicinin yerleşik fonksiyonları (örneğin sync_fetch_and_or) kullanılır. Bu paralelleştirme şemasının verimliliği sonuçlar bölümünde gösterilmiştir; ancak temelde dizilere yapılan rastgele bellek erişimleri nedeniyle sınırlıdır, çünkü bu erişimler önbellek kaçırmalarına yol açar.

Hash Fonksiyonları

MPHF oluşturma işlemi klasik hash fonksiyonları gerektirir. Önceki çalışmalar, yaygın hash fonksiyonlarının pratikte tamamen rastgele hash fonksiyonları kadar iyi davrandığını göstermiştir [2].

Bu nedenle hesaplama hızı ve dağılımın düzgünlüğü açısından verimli oldukları için xor-shift tabanlı hash fonksiyonlarını [13] kullanıyoruz [15].

Ele aldığımız uygulamalarda anahtar kümeleri genellikle RAM’e sığamayacak kadar büyüktür. Bu nedenle bunların diskten akış halinde okunmasını öneriyoruz. Oluşturma sırasında disk kullanımı açısından iki temel strateji vardır:

1. Her d seviyesinde F_{d+1} kümesine eklenecek anahtarlar doğrudan diske yazılır. F_{d+1} kümesi daha sonra d + 1 seviyesinde okunur ve d + 2 seviyesinden önce silinir.
2. Her seviyede, orijinal girdi anahtar dosyasındaki tüm anahtarlar okunur ve hangi anahtarların zaten i < d seviyesine atanmış olduğu ve hangilerinin F_d kümesine ait olacağı belirlenir.

Birinci strateji, geçici disk kullanımı pahasına açıkça daha hızlı oluşturma sağlar. Her d > 0 seviyesinde diskte iki geçici anahtar dosyası saklanır: F_d ve F_{d+1}. En yüksek disk kullanımı seviye 1 sırasında gerçekleşir; yani şu miktarın saklanmasıyla:

|F₁| + |F₂| = |F₀|((1 − e^(−1/γ)) + (1 − e^(−1/γ))²)

Lemma’nın tam kanıtı Ek bölümünde verilmiştir.

Devasa Anahtar Kümeleri için Hızlı ve Ölçeklenebilir Minimal Perfect Hashing

γ = 1 ile bu, yaklaşık ≈ 1.03N öğeyi temsil eder; dolayısıyla diskteki oluşturma ek yükü yaklaşık olarak giriş anahtar dosyasının boyutu kadardır. γ = 2 (sırasıyla γ = 5) olduğunda bu ek yükün azaldığını ve giriş anahtar dosyasının boyutunun yaklaşık ≈ 0.55’i (sırasıyla ≈ 0.21’i) oranına düştüğünü unutmayın.

Birinci strateji, uygulamamızda önerilen varsayılan stratejidir. İkinci strateji de uygulanmıştır ve isteğe bağlı olarak etkinleştirilebilir.

Yerleştirilememiş anahtarların beklenen sayısı, seviye sayısı arttıkça üstel olarak azalır ancak teorik olarak sonlu sayıda adımda sıfıra ulaşması garanti değildir. Oluşturma algoritmasının sonlanmasını sağlamak için uygulamamızda en fazla D seviyesinden oluşan bir sınır belirlenmiştir. Ardından kalan anahtarlar normal bir hash tablosuna eklenir. D değeri bir parametredir; varsayılan değeri D = 25 olup, bu durumda bu hash tablosunda saklanan anahtarların beklenen sayısı γ = 1 için ≈ 10⁻⁵N’dir ve γ ≥ 2 için pratikte ihmal edilebilir hale gelir; böylece son hash tablosunun boyut ek yükü nihai MPHF boyutuna göre ihmal edilebilir olur.

Büyük MPHF’lerin oluşturulması için BBhash’in performansını değerlendirdik. Çeşitli sayıda anahtar içeren dosyalar ürettik (1 milyondan 1 trilyona kadar anahtar). Testlerimizde bir anahtar, [0; 2⁶⁴] aralığındaki sözde rastgele bir pozitif tam sayının ikili gösterimidir. Her dosya içinde her anahtar benzersizdir. Ayrıca giriş anahtarlarının string (n‑gram) olduğu bir test de gerçekleştirdik; böylece anahtar olarak tam sayı kullanmanın sonuçları yanlı hale getirip getirmediğini doğruladık.

Testler, Xeon© E5 2.8 GHz 24 çekirdekli CPU, 256 GB bellek ve mekanik sabit disk bulunan bir küme düğümünde gerçekleştirildi. 10¹² anahtarlı deney dışında, çalışma süreleri diskteki giriş anahtarlarını okuma için gereken zamanı da içerir. Anahtar kümelerini içeren dosyaların işletim sistemi tarafından belleğe önbelleğe alınabileceğini ve değerlendirilen tüm yöntemlerin MPHF oluşturma sırasında bu etkiden yararlandığını unutmayın. Bu deneylerde kullanılan belirli komutlar ve parametreler için Ek bölümüne başvuruyoruz.

Öncelikle γ değerinin (BBhash’in ana parametresi) etkisini, ardından paralelleştirme stratejisine bağlı olarak çoklu iş parçacığı kullanımının etkisini analiz ettik. İkinci olarak BBhash’i diğer güncel yöntemlerle karşılaştırdık. Son olarak 10¹² öğe üzerinde bir MPHF oluşturma işlemi gerçekleştirdik.

Şekil 2’de (solda), farklı γ değerlerine göre oluşturma sürelerini, ortalama sorgu sürelerini ve üretilen MPHF’nin boyutunu raporluyoruz. Temel gözlem, γ ≥ 2 değerlerinin oluşturma ve sorgu sürelerini önemli ölçüde hızlandırdığıdır. Bu beklenen bir durumdur çünkü büyük γ değerleri MPHF’nin ilk seviyelerinde daha fazla öğenin yerleştirilmesine olanak tanır; böylece her anahtarın seviyesini hesaplamak için kaç kez hashlenmesi gerektiği sınırlanır. Özellikle ilk seviyeye yerleştirilen anahtarlar için sorgu süresi tek bir hash işlemi ve bir bellek erişimi ile sınırlıdır.

Tüm anahtarların ortalama seviyesi e^(1/γ)’dir; dolayısıyla γ arttıkça oluşturma ve sorgu sürelerinin azalmasını bekleriz. Ancak daha büyük γ değerleri aynı zamanda daha büyük MPHF boyutlarına yol açar. γ > 5 değerlerinin daha yüksek alan gereksinimi karşılığında çok az avantaj sağladığı gözlemlenir. İlgili bir çalışma MPHF boyutunu en aza indirmek için γ = 1 kullanmıştır [6]. Burada γ değerlerinin 1’den büyük kullanılmasının önemli pratik avantajlar sunduğunu savunuyoruz. Testlerimizde genellikle γ = 2 kullandık çünkü oluşturma ve sorgular sırasında çekici bir zaman/alan dengesi sağlar.

3.5 Sonlanma

4 Sonuçlar

4.1 γ Parametresinin Etkisi

Şekil 2 (sol): Tek bir CPU iş parçacığında çalıştırıldığında, bir milyar anahtardan oluşan bir küme üzerinde BBhash performansına gamma parametresinin etkileri. Süreler ve MPHF boyutu teorik analize uygun davranır; sırasıyla O(e^(1/γ)) ve O(γe^(1/γ)).

Şekil 2 (sağ): Çekirdek sayısına göre BBhash oluşturma süresinin performansı. Testler γ = 2 kullanılarak bir milyar anahtardan oluşan bir giriş kümesi üzerinde gerçekleştirildi. “En iyi teorik hız” eğrisi, tek çekirdekle elde edilen oluşturma süresinin çekirdek sayısına bölünmesiyle hesaplanmıştır.

Uygulamamızın birden fazla CPU çekirdeğini kullanma yeteneğini değerlendirdik. Şekil 2’de (sağ), iş parçacığı sayısına göre oluşturma sürelerini raporluyoruz. İş parçacığı sayısına göre neredeyse ideal bir hızlanma gözlemledik; ancak 10’dan fazla iş parçacığı kullanıldığında kazanımlar azalır. Bunun muhtemel nedeni, bellek erişimi darboğazına yol açan önbellek kaçırmalarıdır.

Bu sonuçlara ek olarak, varsayılan parametreler ve 8 iş parçacığı kullanarak BBhash’i 10 milyar anahtarlı ve 100 milyar anahtarlı bir anahtar kümesi üzerinde uyguladık. Bellek kullanımı sırasıyla 4.96 GB ve 49.49 GB, oluşturma süresi ise sırasıyla 462 saniye ve 8913 saniye oldu; bu da BBhash’in ölçeklenebilirliğini göstermektedir.

BBhash’i güncel MPHF yöntemleriyle karşılaştırdık. CHD (http://cmph.sourceforge.net/) sıkıştırılmış hash-and-displace algoritmasının bir uygulamasıdır [2]. EMPHF [1] rastgele hiper graf soyma yaklaşımına dayanır ve EMPHF içindeki HEM [4] uygulaması giriş verisinin bölümlenmesine dayanır; her iki yöntem de oluşturma sırasında harici bellek kullanır. Bağımsız uygulamaları bulunmadığı için bizim tekniğimize benzer yöntemlerle [6, 12, 16] karşılaştırma yapmadık. Karşılaştırma kodumuz https://github.com/rchikhi/benchmphf adresinde mevcuttur.

Şekil 3, değerlendirilen tüm yöntemlerin bir milyar öğe içeren MPHF’ler oluşturabildiğini gösterir; ancak yalnızca BBhash 10¹¹ öğe ve üzeri veri kümelerine ölçeklenebilir. Genel olarak BBhash, oluşturma sırasında zaman ve bellek kullanımı açısından sürekli olarak daha iyi performans göstermektedir.

Ayrıca ortaya çıkan MPHF boyutunu, yani oluşturma algoritmasının döndürdüğü veri yapısının alanını, ve bir milyar anahtardan oluşan bir veri kümesinde tüm kütüphaneler için ortalama sorgu süresini karşılaştırdık (Tablo 1). BBhash tarafından üretilen MPHF’ler 2.89 bit/anahtar (γ = 1 ve rank her 1024 konumda örneklenirken) ile 6.9 bit/anahtar (γ = 5 ve rank örnekleme 512 iken) arasında değişir. Uygulamamız ile BBhash yapısının teorik alanı arasındaki 0–0.8 bit/anahtar boyut farkı, rank yapısı tarafından kullanılan ek alandan kaynaklanır.

Sorgu süresi ve yapı boyutu açısından makul bir uzlaşmanın γ = 2 ve rank örnekleme 512 ile 3.7 bit/anahtar olduğunu düşünüyoruz; bu değer diğer kütüphanelerin MPHF boyutlarından (2.6 ile 3.5 bit/anahtar aralığında) biraz daha büyüktür. Giriş bölümünde tartışıldığı gibi, anahtar başına 1 bit daha kullanmak performans için kabul edilebilir bir değiş tokuştur.

Oluşturma süreleri yöntemler arasında bir veya iki büyüklük mertebesi farklılık gösterir; BBhash en hızlı olanıdır. Varsayılan parametrelerle (γ = 2, rank örnekleme 512), BBhash’in oluşturma sırasındaki bellek ayak izi Sux4j dışında diğer kütüphanelere göre 40× ila 60× daha küçüktür; Sux4j ile karşılaştırıldığında ise BBhash yine 4× daha küçüktür. Sorgu süreleri yöntemler arasında yaklaşık bir büyüklük mertebesi içindedir (179–1037 ns); γ ≥ 2 olduğunda BBhash’in küçük bir avantajı vardır.

Sux4j, düşük oluşturma belleği ve sorgu süreleri ile çekici bir denge sağlar ancak yüksek disk kullanımı gerektirir. Testlerimizde Sux4j’in yüksek disk kullanımı çok büyük MPHF’lerin oluşturulmasında sınırlayıcı bir faktör oldu.

EMPHF, EMPHF HEM ve Sux4j’in diskte bölümlendirme stratejisi uyguladığını ve bunun prensipte bizim yöntemimiz de dahil olmak üzere diğer yöntemlere de uygulanabileceğini belirtmek gerekir. Tek bir büyük MPHF oluşturmak yerine, giriş anahtarları kümesini diskte bölümlere ayırır ve birçok küçük MPHF’yi bağımsız olarak oluştururlar. Teoride bu teknik, MPHF oluşturma algoritmasının paralellik kullanmasına ve daha az bellek tüketmesine olanak tanır; ancak bunun karşılığında daha yüksek disk kullanımı gerekir.

Pratikte bu tekniği kullanan mevcut uygulamaların paralelleştirilmediğini gözlemledik. EMPHF HEM, bellek eşlemeli dosyalar nedeniyle testlerimizde nispeten yüksek bellek kullansa da (1 milyar öğe için yaklaşık 30 GB), 16 GB kullanılabilir belleğe sahip başka bir makinede de oluşturma işlemini başarıyla tamamladı. Bununla birlikte, bu şemanın ölçeklenebilirliğinde bazı sınırlamalar olduğunu gözlemledik: 100 milyar öğelik bir giriş üzerinde EMPHF ve EMPHF HEM’i çalıştıramadık. Yine de bu bölümlendirme tekniğini umut verici ancak BBhash gibi verimli “monolitik” MPHF oluşturma tasarımlarından bağımsız bir yaklaşım olarak görüyoruz.

4.4 Gerçek Bir Veri Kümesinde Performans

Anahtar olarak sözde rastgele tam sayılar kullanmanın sonuçları yanlı hale getirmediğini doğrulamak için BBhash’i string anahtarlar kullanarak çalıştırdık. Google Books Ngram veri kümesinden (sürüm 20120701) çıkarılmış n‑gram’ları kullandık. Ortalama n‑gram boyutu 18’dir. Ayrıca 18 uzunluğunda rastgele kelimeler de ürettik. Tablo 2’de raporlandığı gibi, rastgele tam sayı anahtarlarla elde edilen sonuçlara çok benzer sonuçlar elde ettik.

Tablo 2. ASCII string anahtarlar kullanıldığında BBhash performansı (γ = 2, 8 iş parçacığı).

4.5 Bir trilyon anahtarın indekslenmesi

10¹² anahtar için bir MPHF oluşturarak çok büyük ölçekli bir test gerçekleştirdik. Bu deney için 750 GB RAM’e sahip bir makine kullandık. Bu kadar çok anahtarı saklamak 8 TB disk alanı gerektireceğinden, bunun yerine [0, 2⁶⁴ − 1] aralığında 10¹² sözde rastgele tam sayıdan oluşan bir akışı deterministik olarak üreten bir yöntem kullandık. Bu akıştaki değerleri diske yazmadan giriş anahtarları olarak kabul ettik. Bu nedenle raporlanan hesaplama süresi önceki sonuçlarla karşılaştırılmamalıdır çünkü bu deneyde disk erişimi yoktur.

Test γ = 2, 24 iş parçacığı kullanılarak gerçekleştirildi ve |Fᵢ| ≤ toplam anahtarların %2’si olduğunda anahtarlar belleğe yüklendi (yani indekslenecek kalan anahtar sayısı 20 milyarın altına düştüğünde).

MPHF oluşturma işlemi 35.4 saat sürdü ve 637 GB RAM gerektirdi. Bu bellek kullanımı yaklaşık olarak bit dizileri (≈459 GB) ile belleğe yüklenen 20 milyar anahtar için gereken bellek (≈178 GB) arasında paylaşılmıştır. Nihai MPHF anahtar başına 3.71 bit yer kapladı.

5 Sonuç

MPHF’lerin oluşturulması ve sorgulanması için kaynak açısından verimli ve yüksek derecede ölçeklenebilir bir algoritma öneriyoruz. Algoritmik tercihlerimiz sadelikten esinlenmiştir: yöntem yalnızca bit dizilerine ve klasik hash fonksiyonlarına dayanır. Çakışmaları bit dizilerinde kaydederek MPHF oluşturma fikri yeni değildir [6, 12]; ancak bildiğimiz kadarıyla BBhash, mevcut en iyi yöntemlerle rekabet edebilen ilk uygulamadır.

Oluşturma süreci özellikle zaman açısından verimlidir çünkü paralelleştirilmiştir ve esas olarak anahtarların hashlenmesi ile bellek erişimlerinden oluşur. Ayrıca oluşturma sırasında kullanılan ek veri yapılarının kanıtlanabilir biçimde yeterince küçük olması, oluşturma sırasında düşük bir bellek ek yükü sağlar. Başka bir deyişle, MPHF’nin oluşturulması sonuçta elde edilen MPHF’nin kendisinden çok daha fazla alan gerektirmez. Bu özellik, pratikte büyük anahtar kümeleri üzerinde MPHF oluştururken önemlidir.

Deneysel sonuçlar BBhash’in ürettiği MPHF’lerin diğer yöntemlerle üretilenlere kıyasla biraz daha büyük olduğunu göstermektedir. Bununla birlikte, büyük anahtar kümelerini (10⁹ anahtardan fazla) indeksleme açısından BBhash, oluşturma süresi, sorgu süresi, bellek ve disk kullanımı bakımından açık ara en verimli yöntemdir. Yaklaşımımızın ölçeklenebilirliği, 10¹² anahtar kadar büyük kümeler için MPHF oluşturularak doğrulanmıştır. Bildiğimiz kadarıyla başka hiçbir MPHF uygulaması bu kadar çok anahtar üzerinde test edilmemiştir.

γ parametresi aracılığıyla bir zaman/alan dengesi sağlanır. γ = 1 değeri yaklaşık 3N bit yer kaplayan MPHF’ler üretir ve oluşturma sırasında düşük bellek ek yükü sağlar. Daha yüksek γ değerleri hem oluşturma sırasında hem de nihai yapı boyutunda daha fazla alan kullanır, ancak daha hızlı oluşturma ve sorgu süreleri sağlar. Sonuçlarımız γ = 2 değerinin anahtar başına 3.7 bit kullanarak iyi bir zaman‑alan dengesi sunduğunu göstermektedir.

Hiper graf tabanlı yöntemlerle [1, 3, 4, 11] karşılaştırıldığında BBhash önemli ölçüde daha iyi oluşturma performansı sunar; ancak ortaya çıkan MPHF boyutu anahtar başına 1 bit kadar daha büyük olabilir. Bununla birlikte, MPHF boyutunun anahtar başına birkaç bit ile sınırlı olduğu sürece genellikle bir darboğaz olmadığını savunuyoruz; çünkü birçok uygulama MPHF’leri anahtarlarla çok daha büyük değerleri ilişkilendirmek için kullanır. Bu nedenle bu çalışmanın milyarlarca ve daha fazla anahtarı indeksleme olanağı sunarak birçok HPC uygulamasının önünü açacağına inanıyoruz.

İlginç bir gelecek çalışma yönü, yöntemimizi kullanarak daha alan verimli MPHF’ler elde etmektir. Bu hedefe ulaşmanın bir yolu olarak hash şemasını biraz değiştirmeyi düşünüyoruz. Her seviyede birkaç hash fonksiyonunu test etmeyi ve çakışma sayısını en aza indiren fonksiyonu seçip (ve saklayıp) kullanmayı amaçlayan CHD algoritmasından esinlenen bir fikri incelemek istiyoruz. Daha uzun oluşturma süreleri pahasına, bu yaklaşımın nihai yapı boyutunu önemli ölçüde azaltabileceğini öngörüyoruz.

Teşekkür

Bu çalışma Fransız ANR-12-BS02-0008 Colib’read projesi tarafından finanse edilmiştir. Karşılaştırma testleri için gerekli hesaplama kaynaklarını sağlayan GenOuest BioInformatics Platform’a teşekkür ederiz. Yararlı tartışmalar ve yönlendirmeler için Djamal Belazzougui’ye teşekkür ederiz.

Kaynaklar

1. Djamal Belazzougui, Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini ve Sebastiano Vigna. Rastgele hiperçizgelerin önbellek-duyarsız soyulması. Data Compression Conference (DCC) içinde, sayfa 352–361. IEEE, 2014.
2. Djamal Belazzougui, Fabiano C. Botelho ve Martin Dietzfelbinger. Hash, yer değiştirme ve sıkıştırma. European Symposium on Algorithms içinde, sayfa 682–693. Springer, 2009.
3. Fabiano C. Botelho, Rasmus Pagh ve Nivio Ziviani. Basit ve alan açısından verimli minimal mükemmel hash fonksiyonları. Algorithms and Data Structures içinde, sayfa 139–150. Springer, 2007.
4. Fabiano C. Botelho, Rasmus Pagh ve Nivio Ziviani. Neredeyse en uygun alanda pratik mükemmel hashing. Information Systems, 38(1):108–131, 2013.
5. Chin-Chen Chang ve Chih-Yang Lin. Birliktelik kurallarının çıkarımı için mükemmel hashing şemaları. The Computer Journal, 48(2):168–179, 2005. doi:10.1093/comjnl/bxh074.
6. Jarrod A. Chapman ve diğerleri. Meraculous: kısa eşleşmiş uçlu okumalarla de novo genom birleştirme. PloS One, 6(8):e23501, 2011.
7. Yupeng Chen, Bertil Schmidt ve Douglas L. Maskell. Hibrit bir kısa okuma eşleme hızlandırıcısı. BMC Bioinformatics, 14(1):67, 2013. doi:10.1186/1471-2105-14-67.
8. Rayan Chikhi, Antoine Limasset ve Paul Medvedev. Dizileme verilerinden de Bruijn grafiklerini hızlı ve düşük bellek kullanımıyla sıkıştırma. Bioinformatics, 32(12):i201–i208, 2016.
9. Zbigniew J. Czech, George Havas ve Bohdan S. Majewski. Mükemmel hashing. Theoretical Computer Science, 182(1):1–143, 1997.
10. Michael L. Fredman ve János Komlós. Ayırıcı sistemlerin ve mükemmel hash fonksiyonu ailelerinin boyutu üzerine. SIAM Journal on Algebraic Discrete Methods, 5(1):61–68, 1984.
11. Marco Genuzio, Giuseppe Ottaviano ve Sebastiano Vigna. (Minimal Perfect Hash) Fonksiyonlarının hızlı ve ölçeklenebilir oluşturulması. Springer International Publishing içinde, sayfa 339–352, 2016.
12. Yi Lu, Balaji Prabhakar ve Flavio Bonomi. Ağ uygulamaları için mükemmel hashing. IEEE International Symposium on Information Theory içinde, sayfa 2774–2778, 2006.
13. George Marsaglia ve diğerleri. Xorshift RNG'ler. Journal of Statistical Software, 8(14):1–6, 2003.
14. Kurt Mehlhorn. Mükemmel ve evrensel hash fonksiyonlarının program boyutu üzerine. Foundations of Computer Science içinde, sayfa 170–175. IEEE, 1982.
15. Michael Mitzenmacher ve Salil Vadhan. Basit hash fonksiyonları neden çalışır: veri akışındaki entropiden yararlanma. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms içinde, sayfa 746–755, 2008.
16. Ingo Müller, Peter Sanders, Robert Schulze ve Wei Zhou. Parmak izi kullanarak erişim ve mükemmel hashing. Springer International Publishing içinde, sayfa 138–149, 2014.

Ek

MPHF Boyutu ve Oluşturma İçin Gerekli Belleğin İspatları

γ = 1 için MPHF boyutu

[ \sum_{d \ge 0} |A_d| = N ]

[ = \frac{N}{1 - (1 - e^{-1})} ]

Çünkü

[ \lim_{d \to +\infty} (1 - e^{-1})^d = 0 ]

şunu elde ederiz

[ \sum_{d \ge 0} |A_d| = eN ]

Herhangi bir γ ≥ 1 kullanarak MPHF boyutu

γ ≥ 1 ile:

[ |A_d| = \gamma |A_{d-1}| (1 - e^{-1/\gamma}) ]

Dolayısıyla,

[ |A_d| = \gamma N (1 - e^{-1/\gamma})^d ]

ve

[ \sum_{d \ge 0} |A_d| = \gamma N \sum_{d \ge 0} (1 - e^{-1/\gamma})^d ]

Çünkü

[ 0 < 1 - e^{-1/\gamma} < 1 ]

şunu elde ederiz

[ \sum_{d \ge 0} |A_d| = \frac{\gamma N}{1 - (1 - e^{-1/\gamma})} ]

Bu ispatın γ > 0 olan herhangi bir değer için geçerli olduğunu belirtmek gerekir; ancak γ < 1 olduğunda hem teorik hem de pratik MPHF boyutları, γ sıfıra yaklaştıkça üstel olarak artar.

Lemma 1

m(d) düzey d sırasında gerekli olan bellek olsun ve R, MPHF oluşturulması sırasında gerekli olan en büyük bellek ile S ile gösterilen MPHF toplam boyutu arasındaki oran olsun.

[ R = \max_{d \ge 0} \frac{m(d)}{S} ]

Öncelikle şunu ispatlarız:

[ \lim_{d \to \infty} \frac{m(d)}{S} = 1 ]

şu ifade ile

[ m(d) = \sum_{i<d} |A_i| + 2|A_d| ]

Devam etmeden önce şu ifadeyi hesaplayalım:

[ m(d+1) - m(d) ]

bu da şu sonuca götürür

[ \gamma N (1 - e^{-1/\gamma})^d (1 - 2e^{-1/\gamma}) ]

Şimdi şunu ispatlarız:

• γ ≤ 1 / log(2) olduğunda R ≤ 1
• γ > 1 / log(2) olduğunda R < 2

Durum 1: γ ≤ 1 / log(2)

• m(0) / S = 2e^{-1/γ} ≤ 1
• m(d) artandır
• lim(d → ∞) m(d)/S = 1

Dolayısıyla R ≤ 1.

Durum 2: γ > 1 / log(2)

• m(0) / S = 2e^{-1/γ} > 1
• m(d) d ile birlikte azalır

Algoritmaların Sözde Kodları

Algoritma 1: MPHF Oluşturma

Veri: F₀ N anahtardan oluşan bir küme, tamsayılar γ ve last
Sonuç: bit dizilerinden oluşan dizi {A₀, A₁, …, A_last}, hash tablosu H

i = 0
while Fi not empty and i ≤ last do

    Ai = ArrayFill(Fi, γ)

    foreach key x of Fi do
        h = hashi(x) mod Ai.size()
        if Ai[h] == 1 then
            Fi+1.add(x)

    i = i + 1

Construct H using remaining elements from Flast+1
Return {A0, A1, …, Alast, H}

Pratikte i > 1 olan Fi kümeleri diskte saklanır (bkz. Bölüm 3.4). Hash tablosu H, Flast+1 içindeki elemanların çakışma olmadan şu aralıktaki tamsayılara eşlenmesini sağlar:

[|F₀| − |Flast+1| + 1, |F₀|]

Algoritma 2: ArrayFill

Veri: N anahtardan oluşan F dizisi, tamsayı γ
Sonuç: bit dizisi A

Zero-initialize A and C two bit arrays with γ * N elements

foreach key x of F do
    h = hash(x) mod (γ * N)

    if A[h] == 0 and C[h] == 0 then
        A[h] = 1

    else if A[h] == 1 and C[h] == 0 then
        A[h] = 0
        C[h] = 1

Delete C
Return A

A[h] == 1 ve C[h] == 1 durumunun hiçbir zaman gerçekleşmediğine dikkat edin.

Algoritma 3: MPHF Sorgusu

Veri: bit dizileri {A₀, A₁, …, A_last}, hash tablosu H, anahtar x
Sonuç: x'in tamsayı indeksi

i = 0
while i ≤ last do
    ...

Not: x, MPHF'nin anahtar kümesine ait bir eleman değilse algoritma yanlış bir tamsayı indeks döndürebilir.

Komutlar

Bu bölümde sunulan her sonuç için kullanılan komutlar açıklanmaktadır. Zaman ve bellek kullanımı /usr/bin/time --verbatim Unix komutu kullanılarak hesaplanmıştır. Disk kullanımı ise her 1/10 saniyede bir du -sk komutu ile dizin boyutunu ölçen ve en yüksek değeri kaydeden özel bir betik kullanılarak hesaplanmıştır.

BBhash kütüphanesi ve Bootest aracı şu adreste mevcuttur:

https://github.com/rizkg/BBHash

for ((gamma=1;gamma<11;gamma++)); do
    ./Bootest 1000000000 1 ${gamma} -bench
done

for ((gamma=1;gamma<11;gamma++)); do
    ./Bootest 1000000000 1 ${gamma} -bench
done

for keys in 10000000000 100000000000; do
    ./Bootest ${keys} 8 2 -bench
done

Bölüm 4.1 için kullanılan komutlar

1000000000 değerinin test edilen anahtar sayısını, 1 değerinin ise kullanılan çekirdek sayısını ifade ettiğini unutmayın.

Daha büyük anahtar kümeleri ve 8 iş parçacığı ile ek testler de yürütülmüştür.

Bölüm 4.2 için kullanılan komutlar

EMPHF, EMPHF MEM, CHD ve Sux4J için karşılaştırma (benchmark) kodu şu adreste bulunmaktadır:

https://github.com/rchikhi/benchmphf

BBhash komutları

for keys in 1000000 10000000 100000000 10000000000 \
10000000000 100000000000; do
    ./Bootest ${keys} 1 2 -bench
done

nodisk (Tablo 1) ile BBhash komutu:

./Bootest 1000000000 1 2 -bench -nodisk
./Bootest 1000000000 8 2 -bench -nodisk

sırasıyla tek ve sekiz iş parçacığı için.

EMPHF & EMPHF HEM komutları

for keys in 1000000 10000000 100000000 10000000000 \
10000000000 100000000000; do
    ./benchmphf ${keys} -emphf
done

EMPHF (sırasıyla EMPHF HEM) şu makro kullanılarak test edilmiştir:

#define EMPHF.SCAN
#define EMPHF.HEM

Disk boyutu ayak izini değerlendirmek için şu satır:

unlink(tmpl);

emphf/mmap_memory_model.hpp dosyasından yorum satırı haline getirilmiştir.

CHD komutları

for keys in 1000000 10000000 100000000 10000000000 \
10000000000 100000000000; do
    ./benchmphf ${keys} -chd
done

Sux4J komutları

Her boyut için şu dosya:

Sux4J/slow/it/unimi/dsi/sux4j/mph/LargeLongCollection.java

kullanılan boyutu belirtmek üzere değiştirilmiştir.

./run-sux4j-mphf.sh

Bölüm 4.4'te açıklandığı gibi keyStrings.txt dosyası, Google Books Ngram veri kümesinden (sürüm 20120701) çıkarılan n-gramlardan oluşmaktadır.

./BootestFile keyStrings.txt 10 2

Bölüm 4.4 için kullanılan komutlar