Bilgisayar Veri Merkezi

Doğrusal yoklama karma tabloları üzerinde yeni çalışma İLE BİRLİKTE CSAIL, bilgisayarlarda daha verimli veri depolamasına ve alınmasına yol açabilir.

MIT’de bilgisayar bilimi doktora öğrencisi olan William Kuszmaul’un da aralarında bulunduğu üçlü bir araştırmacı, bilgisayarlarda daha verimli veri depolama ve erişime yol açabilecek bir keşif yaptı.

Ekibin bulguları, 1954’te tanıtılan ve günümüzde mevcut olan en eski, en basit ve en hızlı veri yapıları arasında yer alan “doğrusal araştırma karma tabloları” ile ilgilidir. Veri yapıları, en yaygın olarak kullanılan yaklaşımlardan biri olan hash tabloları ile bilgisayarlarda verilerin düzenlenmesi ve depolanması için yollar sağlar. Doğrusal araştırma karma tablosunda, bilgilerin depolanabileceği konumlar doğrusal bir dizi boyunca uzanır.

Örneğin, bir veri tabanının 10.000 kişinin Sosyal Güvenlik numaralarını depolamak için tasarlandığını varsayalım, diyor Kuszmaul. “Sosyal Güvenlik numaranızı x alıyoruz ve daha sonra size bir ile 10.000 arasında rastgele bir sayı veren x, h(x)’in karma işlevini hesaplayacağız.” Sonraki adım, bu rastgele sayı olan h(x) dizisindeki o konuma gitmek ve Sosyal Güvenlik numarası olan x’i o noktaya koymaktır.

O noktayı işgal eden bir şey varsa, Kuszmaul diyor ki, “bir sonraki serbest pozisyona ilerleyin ve onu oraya koyun. Açık bir nokta bulana kadar doğrusal olarak ilerlemeye devam ettiğiniz için ‘doğrusal sondalama’ terimi buradan gelir.” Daha sonra Sosyal Güvenlik numarası olan x’i almak için, sadece belirlenen h(x) noktasına gidersiniz ve orada değilse, x’i bulana veya serbest bir konuma gelene kadar ilerleyin ve x’in olduğu sonucuna varın. veritabanınızda değil.

Sosyal Güvenlik numarası gibi bir öğeyi silmek için biraz farklı bir protokol vardır. Bilgileri sildikten sonra karma tablosunda boş bir nokta bıraktıysanız, daha sonra başka bir şey bulmaya çalıştığınızda bu karışıklığa neden olabilir, çünkü boş nokta yanlışlıkla aradığınız öğenin hiçbir yerde bulunmadığını gösterebilir. veritabanı. Kuszmaul, bu sorunu önlemek için, “elementin kaldırıldığı noktaya gidebilir ve oraya ‘mezar taşı’ adı verilen küçük bir işaret koyabilirsiniz, bu da eskiden burada bir element olduğunu, ancak şimdi yok olduğunu gösterir.”

Bu genel prosedür yarım yüzyıldan fazla bir süredir takip edilmektedir. Ancak tüm bu zaman boyunca, doğrusal sondalama karma tablolarını kullanan hemen hemen herkes, bunların çok dolmasına izin verirseniz, uzun dolu dolu noktaların bir araya gelerek “kümeler” oluşturacağını varsaymıştır. Sonuç olarak, boş bir yer bulmak için gereken süre çarpıcı bir şekilde artacaktır – aslında ikinci dereceden olarak – pratik olamayacak kadar uzun sürecektir. Sonuç olarak, insanlar hash tablolarını düşük kapasitede çalıştırmak için eğitildi – bir şirketin satın alması ve bakımını yapması gereken donanım miktarını etkileyerek ekonomik bir bedel ödeyebilecek bir uygulama.

Ancak, uzun süredir yüksek yük faktörlerine karşı mücadele eden bu köklü ilke, Kuszmaul ve meslektaşları, Stony Brook Üniversitesi’nden Michael Bender ve Google’dan Bradley Kuszmaul’un çalışmalarıyla tamamen alt üst oldu. Ekleme ve silme sayısının yaklaşık olarak aynı kaldığı ve eklenen veri miktarının kaldırılan veri miktarına kabaca eşit olduğu uygulamalar için doğrusal yoklama karma tablolarının hızdan ödün vermeden yüksek depolama kapasitelerinde çalışabileceğini buldular.

Ek olarak, ekip, bir diziye yerleştirilen mezar taşlarının sayısını, boş noktaların yaklaşık yarısını işgal edene kadar yapay olarak artırmayı içeren “mezarlık karma” adı verilen yeni bir strateji geliştirdi. Bu mezar taşları daha sonra gelecekteki yerleştirmeler için kullanılabilecek alanlar ayırır.

Kuszmaul, insanlara geleneksel olarak yapmaları talimatı verilenlerin aksine çalışan bu yaklaşımın “doğrusal yoklama hash tablolarında optimum performansa yol açabileceğini” söylüyor. Veya, o ve yardımcı yazarlarının makalelerinde ileri sürdükleri gibi, “mezar taşlarının iyi tasarlanmış kullanımı, lineer problamanın nasıl davrandığına dair manzarayı tamamen değiştirebilir.”

Kuszmaul, bu bulguları Bender ve Kuszmaul ile bu yılın başlarında yayınlanan ve Şubat ayında Boulder, Colorado’daki Bilgisayar Biliminin Temelleri (FOCS) Sempozyumu’nda sunulacak bir makalede yazdı.

Kuszmaul’un doktora tez danışmanı, MIT bilgisayar bilimi profesörü Charles E. Leiserson (bu araştırmaya katılmamış), bu değerlendirmeye katılıyor. Leiserson, “Bu yeni ve şaşırtıcı sonuçlar, karma tablo davranışıyla ilgili en eski geleneksel bilgeliklerden birini alt üst ediyor” diyor. “Dersler hem teorisyenler hem de uygulayıcılar arasında yıllarca yankılanacak.”

Sonuçlarını uygulamaya çevirme konusunda Kuszmaul, “bir hash tablosu oluşturmaya yönelik pek çok düşünce var. Hikayeyi teorik açıdan önemli ölçüde ilerletmiş olsak da, olayların deneysel yönünü keşfetmeye yeni başlıyoruz.”

Referans: “Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering”, Michael A. Bender, Bradley C. Kuszmaul ve William Kuszmaul, 2 Temmuz 2021, Bilgisayar Bilimi > Veri Yapıları ve Algoritmalar.
arXiv:2107.01250





#MITdeki #Teorik #Atılım #Veri #Depolamayı #Artırabilir