Bilim Adamları Veri Depolama ve Zaman Arasında Optimum Dengeyi Buluyor | Quanta Dergisi

Yaklaşık 70 yıl önce IBM'de Hans Peter Luhn adlı bir mühendis bilgisayar biliminin gidişatını sessizce değiştirdi. Luhn'un halihazırda birçok patenti vardı; bunlardan biri bir kumaşın iplik sayısını ölçebilen bir cihaz, diğeri ise mutfağınızdaki malzemelerden hangi karışık içecekleri yapabileceğinizi belirleyen bir kılavuzdu. Ancak 1953'te IBM'in dahili bir makalesinde, bilgiyi depolamak ve almak için şu anda hemen hemen tüm hesaplama sistemlerinde yerleşik olan yeni bir teknik önerdi: karma tablosu.

Hash tabloları veri yapılarının önemli bir sınıfıdır. Devasa veritabanlarındaki bilgilere erişmek ve bunları değiştirmek için özellikle kullanışlı bir yöntem sunarlar. Ancak bu teknoloji kaçınılmaz bir ödünleşimi de beraberinde getiriyor.

Bir 1957 yılında kâğıt yayımlanan IBM Araştırma ve Geliştirme Dergisi, W. Wesley Peterson, karma tabloların ortaya çıkardığı temel teknik zorluğu belirledi: Hızlı olmaları gerekiyor, yani gerekli bilgileri hızlı bir şekilde alabilmeleri gerekiyor. Ancak aynı zamanda kompakt olmaları ve mümkün olduğunca az bellek kullanmaları gerekir. Bu ikiz hedefler temelde birbirine zıttır. Karma tablonun belleği daha fazla olduğunda, veritabanına erişim ve değişiklik daha hızlı yapılabilir; ve daha az yer kullanan karma tablolarda işlemler yavaşlar. Peterson bu zorluğu ortaya koyduğundan beri araştırmacılar zaman ve mekan arasındaki en iyi dengeyi bulmaya çalışıyorlar.

Bilgisayar bilimcileri artık en uygun dengeyi bulduklarını matematiksel olarak kanıtladılar. Çözüm birinden geldi çift son zamanlarda kâğıtlar yani birbirini tamamlıyordu. "Bu makaleler, mümkün olan en iyi uzay-zaman değiş tokuşları hakkında uzun süredir devam eden açık soruyu çözüyor ve gelecek yıllarda önemli bir etkiye sahip olmasını beklediğim son derece şaşırtıcı sonuçlar veriyor" dedi. Michael MitzenmacherHer iki çalışmaya da dahil olmayan, Harvard Üniversitesi'nden bir bilgisayar bilimcisi.

"Bunun kesinlikle önemli bir olay olduğunu söyleyebilirim" diye ekledi Rasmus PaghKopenhag Üniversitesi'nde bilgisayar bilimcisi. "Birçok kişi bu sorun üzerinde çalıştı, hem alanı ne kadar daraltabileceğinizi hem de zamandan tasarruf sağlayan işlemler gerçekleştirebileceğinizi görmeye çalıştı. Çözmeyi çok istediğim şey buydu.”

Bir Hash Yapmak

Hash tabloları günümüzde en eski, en basit, en hızlı ve en yaygın kullanılan veri yapıları arasındadır. Üç temel işlemi gerçekleştirmek üzere tasarlanmışlardır: veritabanına yeni öğeler ekleyen eklemeler; bir öğeye erişen veya onun var olup olmadığını kontrol eden sorgular; ve silmeler. Karma tablo geçici olabilir (yalnızca belirli bir program çalıştığı sürece var olabilir) veya bilgisayarınızın işletim sisteminin kalıcı bir parçası olabilir. Chrome veya Safari gibi bir web tarayıcısı, farklı türdeki verileri takip etmeye yönelik birden fazla yerleşik karma tablosuna sahip olabilir.

Karma tablosundaki girişler, öğenin (bilginin kendisi) bilgiyi tanımlayan bir anahtara bağlanmasıyla çiftler halinde saklanır. Karma tablonun sorgu algoritmasına bir anahtar taktığınızda, bu sizi doğrudan öğeye götürür. Bu çok sıra dışı gelmeyebilir, ancak çok büyük veritabanları için büyük bir zaman tasarrufu sağlayabilir.

Son derece basitleştirilmiş bir örnek vermek gerekirse, 600,000'den fazla kelimenin tanımına sahip olan Oxford İngilizce Sözlüğünü düşünün. Dijital baskı karma tablosuna dayanıyorsa, belirli bir kelimeyi anahtar olarak kullanabilir ve doğrudan tanıma geçebilirsiniz. Karma tablosu olmadan, sözlük büyük olasılıkla çok daha yavaş bir arama mekanizmasına dayanacak ve sonuçta istenen tanıma yakınsama için bir eleme süreci kullanacaktır. Bir karma tablosu herhangi bir kelimeyi sabit bir sürede (genellikle saniyenin çok küçük bir kısmı) bulabilirken, diğer yöntemlerin arama süresi sözlükteki kelime sayısı arttıkça artabilir. Hash tablosunun başka bir avantajı da vardır: Sözlüğü dinamik tutabilir, yeni kelimeler eklemeyi ve eski kelimeleri silmeyi kolaylaştırır.

Araştırmacılar, hızı en üst düzeye çıkarmaya ve belleği en aza indirmeye çalışan karma tablolar oluşturmak için onlarca yıl harcadılar. 20. yüzyılda çözümler yalnızca tek bir açıdan, zaman ve mekan açısından önemli kazanımlar sunma eğilimindeydi. Daha sonra 2003 yılında araştırmacılar gösterdi hem zamanda hem de mekânda eş zamanlı olarak büyük bir verimlilik sıçraması yapmanın teorik olarak mümkün olduğu ortaya çıktı. Ancak araştırmacıların ikisi arasındaki ideal dengeyi bulmaları bir yirmi yıl daha alacak.

Veri Karıştırma

Bu hedefe yönelik ilk büyük adım 2022'de atıldı. büyük bilgisayar bilimi konferansı Roma'da. Orada bir ekip, şimdiye kadar tasarlanan en iyi zaman ve alan verimliliği kombinasyonunu sunabilecek yeni özelliklere sahip bir karma tablo önerdi. Makalenin ilk yazarı (alfabetik olarak listelenmiştir) Stony Brook Üniversitesi'nden Michael Bender'dı, bu nedenle genellikle Bender ve diğerleri olarak anılır. karma tablosu. Ekip işleyen bir karma tablo oluşturmaya çalışmasa da, prensipte bu tablonun tanımladıkları özelliklerle oluşturulabileceğini kanıtladı.

Grup, ortaya çıkardıkları hash tablosunu değerlendirmek için bir takas eğrisi üretti; bir eksende işlem başına süreyi (ekleme veya silme), diğer eksende hafızanın kapladığı alanı gösteren bir grafik. Ancak bu grafik alanı özel bir şekilde tanımlar: Oluşturulma şekillerinden dolayı karma tabloları, belirli bir öğe kümesini depolamak için gereken minimum miktardan daha fazla belleğe ihtiyaç duyar. Bilgisayar bilimcileri, gerçekte israf edilmeseler ve bir dereceye kadar gerekli olsalar da, bu fazladan alanı "boşa harcanan parçalar" olarak adlandırıyorlar. Bir takas eğrisindeki boşluk ekseni, anahtar başına boşa harcanan bitlerin sayısını ölçer.

Araştırmacılar, bir değiş-tokuş eğrisini analiz ederek, belirli miktarda alan kullanan bir karma tablo için mümkün olan en hızlı süreyi bulabilirler. Ayrıca belirli bir operasyon süresi için mümkün olan en küçük alanı bulmak için soruyu tersine çevirebilirler. Genellikle bir değişkendeki küçük bir değişiklik diğerinde de küçük bir değişikliğe yol açacaktır, dedi. William KuszmaulHarvard'da teorik bilgisayar bilimcisi ve 2022 tarihli makalenin ortak yazarı. "Süreyi iki katına çıkarırsanız, belki anahtar başına boşa harcanan bit sayısını yarıya indirirsiniz."

Ancak tasarladıkları hash tablosunda durum böyle değil. Kuszmaul, "Süreyi biraz artırırsanız, anahtar başına boşa harcanan bitler katlanarak azalır" dedi. Takas eğrisi o kadar dikti ki kelimenin tam anlamıyla alışılmışın dışındaydı.

Ekip karma tablosunu iki parça halinde oluşturdu. Öğelerin hiçbir bit israfı olmadan depolandığı bir birincil veri yapısına ve bir sorgu isteğinin aradığı öğeyi bulmasına yardımcı olan ikincil bir veri yapısına sahiptiler. Grup, ikincil veri yapısı kavramını icat etmemiş olsa da, hiper verimli karma tablosunu mümkün kılan çok önemli bir keşifte bulundu: Yapının genel bellek verimliliği, birincil yapının depolanan öğeleri nasıl düzenlediğine bağlıdır.

Temel fikir, birincil yapıdaki her öğenin tercih edilen depolama konumlarına sahip olmasıdır - en iyi konum, ikinci en iyi konum, üçüncü en iyi konum vb. Bir öğe en iyi noktasındaysa ona 1 sayısı eklenir ve bu sayı ikincil veri yapısında saklanır. Bir sorguya yanıt olarak ikincil yapı, öğenin birincil yapıdaki tam konumunu belirten yalnızca 1 sayısını sağlar.

Öğe 100'üncü en iyi noktadaysa, ikincil veri yapısı 100 sayısını ekler. Sistem ikili kullandığından, 100 sayısını 1100100 olarak temsil eder. Elbette 1100100 sayısını depolamak 1'den daha fazla bellek gerektirir. — bir öğe en iyi noktada olduğunda ona atanan sayı. Örneğin bir milyon öğeyi saklıyorsanız, bunun gibi farklılıklar önemli hale gelir.

Böylece ekip, birincil veri yapısındaki öğeleri sürekli olarak daha çok tercih edilen konumlara kaydırırsanız, sorgu sürelerini artırmak zorunda kalmadan ikincil yapı tarafından tüketilen belleği önemli ölçüde azaltabileceğinizi fark etti.

Pagh, "Bu çalışmadan önce hiç kimse bilgiyi hareket ettirerek veri yapısını daha da sıkıştırabileceğinizi fark etmemişti" dedi. "Bender makalesinin büyük içgörüsü buydu."

Yazarlar, buluşlarının en verimli hash tabloları için yeni bir üst sınır oluşturduğunu, bunun da hem zaman hem de alan verimliliği açısından şimdiye kadar tasarlanmış en iyi veri yapısı olduğu anlamına geldiğini gösterdi. Ancak bir başkasının daha iyisini yapabilme ihtimali devam ediyordu.

Başarılı Olmak Zorundayız

Ertesi yıl liderliğindeki bir ekip Huacheng YuPrinceton Üniversitesi'nden bir bilgisayar bilimcisi olan Bender ekibinin karma tablosunu iyileştirmeye çalıştı. "Çok çalıştık ama başaramadık" dedi Renfei ZhouPekin'deki Tsinghua Üniversitesi'nde bir öğrenci ve Yu'nun ekibinin bir üyesi. "İşte o zaman onların üst sınırının da bir alt sınır olduğundan şüphelendik" - elde edilebilecek en iyi şey. "Üst sınır alt sınıra eşit olduğunda oyun biter ve cevabınızı alırsınız." Ne kadar akıllı olursanız olun, hiçbir hash tablosu bundan daha iyisini yapamaz.

Yu'nun ekibi bu önsezinin doğru olup olmadığını öğrenmek için ilk prensiplerden bir alt sınır hesaplayarak yeni bir strateji kullandı. İlk olarak, bir ekleme veya silme işlemini gerçekleştirmek için bir karma tablosunun (veya aslında herhangi bir veri yapısının) bilgisayarın belleğine birkaç kez erişmesi gerektiğini düşündüler. Alanı verimli kullanan bir karma tablosu için gereken minimum sayıyı bulabilirlerse, bunu erişim başına gereken süre (sabit) ile çarparak onlara çalışma süresi için bir alt sınır verebilirler.

Ancak karma tablosu hakkında hiçbir şey bilmiyorlarsa (yer tasarrufu sağlaması dışında), araştırmacılar belleğe erişim için gereken minimum sayıyı nasıl hesaplayacaklardı? Bunu, iki taraf arasında bilgi aktarımı için kaç bitin gerekli olduğunu inceleyen iletişim karmaşıklığı teorisi adı verilen görünüşte alakasız bir alanı kullanarak, tamamen teoriden elde ettiler. Sonunda ekip başardı: Bir veri yapısının, işlem başına belleğine kaç kez erişmesi gerektiğini buldular.

Bu onların en önemli başarısıydı. Daha sonra, alan açısından verimli herhangi bir karma tablosu için çalışma süresinde bir alt sınır oluşturmayı başardılar. Ve bunun Bender hash tablosuyla birebir eşleştiğini gördüler. Zhou, "İlk başta bunun geliştirilebileceğini düşündük" dedi. "Yanlış davrandığımız ortaya çıktı." Bu da Peterson'un sorununun nihayet çözüldüğü anlamına geliyordu.

Onlarca yıllık soruyu yanıtlamanın yanı sıra Kuszmaul, Yu kanıtının şaşırtıcı yanının genelliği olduğunu söyledi. "Alt sınırları, henüz icat edilmemiş olanlar da dahil olmak üzere tüm olası veri yapıları için geçerlidir." Bu, hiçbir veri depolama yönteminin bellek ve hız açısından Bender karma tablosunu asla yenemeyeceği anlamına gelir.

Geleceğe Hashing

Yeni hash tablosunun benzeri görülmemiş verimliliğine rağmen, yakın zamanda hiç kimsenin onu oluşturmayı denemesi pek mümkün görünmüyor. İnşa edilmesi çok karmaşık. Zhou, "Teoride hızlı olan bir algoritmanın pratikte mutlaka hızlı olması gerekmez" dedi.

Kuszmaul, teori ve pratik arasındaki bu tür boşlukların uzun süre devam etmesinin alışılmadık bir durum olmadığını, çünkü teorisyenlerin sabit faktörleri göz ardı etme eğiliminde olduğunu söyledi. Bir işlemi gerçekleştirmek için gereken süre tipik olarak bir sayıyla çarpılır; bu sayının kesin değeri teorik açıdan önemsiz olabilecek bir sabittir. "Fakat pratikte sabitler gerçekten önemlidir" dedi. “Gerçek dünyada 10 faktörü oyunun sonudur.”

Gerçek karma tabloları, teorik idealin çok gerisinde kalsalar bile, maddi açıdan hâlâ gelişiyor. Örneğin, yeni bir karma tablosu adı verildi BuzdağıHTBender, Kuszmaul ve diğerleri tarafından inşa edilen bina öncekilerden çok daha iyi. Kuszmaul'a göre, günümüzün alan açısından en verimli karma tablosundan iki kat daha hızlı ve en hızlı karma tablosundan üç kat daha az yer kullanıyor.

Mitzenmacher, 2023 sonucunun yakında başka bir tür fayda sağlayabileceğini umuyor: "Yeni bir alt sınır elde ettiğinizde, özellikle de bazı yeni teknikleri içeren bir alt sınır elde ettiğinizde, bunları ilgili problemler için kullanabileceğinize dair her zaman bir umut vardır."

Bilgisayar bilimci, aynı zamanda zor ve uzun süredir devam eden bir sorunu çözdüğünüzü bilmenin getirdiği entelektüel tatminin de olduğunu söyledi. Piotr Indyk Massachusetts Teknoloji Enstitüsü'nden. "Belirli veri yapılarının iyileştirilemeyeceğinden emin olduğunuzda, bu araştırma çabalarına odaklanmanıza yardımcı olabilir." Son olarak, veri araştırmacıları dikkatlerini Peterson'ın meydan okumasından uzaklaştırabilir ve teorik bilgisayar biliminde hiçbir sıkıntısı olmayan yeni problemlere odaklanabilirler.