Naukowcy odkryli optymalną równowagę przechowywania danych i czasu | Magazyn Quanta

Około 70 lat temu inżynier z IBM, Hans Peter Luhn, po cichu zmienił bieg informatyki. Luhn był już posiadaczem kilku patentów, w tym jednego na urządzenie mierzące liczbę nitek tkaniny i drugiego na przewodnik określający, jakie napoje mieszane można przygotować ze składników znajdujących się w kuchni. Jednak w wewnętrznej pracy IBM z 1953 roku zaproponował nową technikę przechowywania i wyszukiwania informacji, która jest obecnie wbudowana w niemal wszystkie systemy obliczeniowe: tablicę mieszającą.

Tabele skrótów są główną klasą struktur danych. Oferują szczególnie wygodną metodę dostępu i modyfikowania informacji w ogromnych bazach danych. Jednak technologia ta wiąże się z nieuniknionym kompromisem.

W 1957 papier opublikowane w IBM Journal of Research and Development, W. Wesley Peterson zidentyfikował główne wyzwanie techniczne, jakie stwarzają tabele mieszające: muszą być szybkie, co oznacza, że ​​mogą szybko uzyskać niezbędne informacje. Muszą jednak być również kompaktowe i zużywać jak najmniej pamięci. Te bliźniacze cele są zasadniczo sprzeczne. Dostęp do bazy danych i modyfikowanie jej można wykonać szybciej, gdy tablica mieszająca ma więcej pamięci; a operacje stają się wolniejsze w tabelach skrótów, które zajmują mniej miejsca. Odkąd Peterson postawił to wyzwanie, badacze próbowali znaleźć najlepszą równowagę między czasem i przestrzenią.

Informatycy udowodnili matematycznie, że znaleźli optymalny kompromis. Rozwiązanie przyszło od a đôi z ostatnich Papiery które się uzupełniały. „Artykuły te rozwiązują od dawna otwarte pytanie dotyczące najlepszych możliwych kompromisów czasoprzestrzennych, dostarczając głęboko zaskakujących wyników, które, jak oczekuję, będą miały znaczący wpływ przez wiele nadchodzących lat” – powiedział Michaela Mitzenmachera, informatyk z Uniwersytetu Harvarda, który nie brał udziału w żadnym z badań.

„Zdecydowanie powiedziałbym, że to wielka sprawa” – dodał Rasmus Pagh, informatyk na Uniwersytecie w Kopenhadze. „Wiele osób pracowało nad tym problemem, próbując zobaczyć, jak bardzo można wycisnąć przestrzeń, jednocześnie oszczędzając czas. To jest problem, który bardzo chciałbym rozwiązać.”

Robienie z tego haszu

Tabele skrótów należą obecnie do najstarszych, najprostszych, najszybszych i najczęściej używanych struktur danych. Przeznaczone są do wykonywania trzech podstawowych operacji: wstawiania, które dodają nowe pozycje do bazy danych; zapytania, które uzyskują dostęp do elementu lub sprawdzają, czy istnieje; i usunięcia. Tablica skrótów może być efemeryczna — istnieć tylko tak długo, jak działa określony program — lub może stanowić stałą część systemu operacyjnego komputera. Przeglądarka internetowa, taka jak Chrome lub Safari, może mieć wiele wbudowanych tabel skrótów przeznaczonych do śledzenia różnych rodzajów danych.

Wpisy w tablicy mieszającej są przechowywane w parach, przy czym element – ​​sama informacja – jest połączony z kluczem identyfikującym informację. Podłącz klucz do algorytmu zapytania tabeli mieszającej, a przeniesie Cię bezpośrednio do elementu. Może nie brzmi to tak nadzwyczajnie, ale w przypadku ogromnych baz danych może to być świetna oszczędność czasu.

Aby wziąć bardzo uproszczony przykład, rozważmy Oxford English Dictionary, który zawiera definicje ponad 600,000 XNUMX słów. Jeśli wydanie cyfrowe opiera się na tablicy mieszającej, możesz po prostu użyć danego słowa jako klucza i przejść od razu do definicji. Bez tablicy mieszającej słownik prawdopodobnie opierałby się na znacznie wolniejszym mechanizmie wyszukiwania, wykorzystującym proces eliminacji, aby ostatecznie uzyskać zbieżność z żądaną definicją. I chociaż tabela mieszająca może znaleźć dowolne słowo w stałym czasie (zwykle w niewielkim ułamku sekundy), czas wyszukiwania w przypadku innych metod może wzrosnąć wraz ze wzrostem liczby słów w słowniku. Tablica mieszająca ma jeszcze jedną zaletę: utrzymuje dynamikę słownika, ułatwiając wstawianie nowych słów i usuwanie nieaktualnych.

Naukowcy spędzili dziesięciolecia na tworzeniu tabel skrótów, które próbowały zmaksymalizować prędkość i zminimalizować pamięć. W XX wieku rozwiązania oferowały zazwyczaj znaczne korzyści tylko w jednym aspekcie – w czasie i przestrzeni. Następnie w 20 roku badacze pokazał że teoretycznie możliwe było dokonanie dużego skoku wydajności jednocześnie w czasie i przestrzeni. Jednak znalezienie idealnej równowagi między nimi zajęłoby badaczom kolejne dwie dekady.

Tasowanie danych

Pierwszy poważny krok w stronę tego celu nastąpił w 2022 r. o godz wielka konferencja informatyczna w Rzymie. Tam zespół zaproponował tabelę skrótów z nowymi funkcjami, które mogłyby zapewnić najlepszą kombinację efektywności czasowej i przestrzennej, jaką kiedykolwiek wymyślono. Pierwszym autorem pracy (w kolejności alfabetycznej) był Michael Bender ze Stony Brook University, stąd powszechnie określa się ją jako Bender et al. tablica mieszająca. Chociaż zespół nie próbował zbudować działającej tabeli skrótów, udowodnił, że w zasadzie można ją zbudować, korzystając z opisanych przez siebie funkcji.

Aby ocenić opracowaną tabelę skrótów, grupa stworzyła krzywą kompromisów — wykres przedstawiający czas operacji (wstawiania lub usuwania) na jednej osi i miejsce zajmowane przez pamięć na drugiej. Ale ten wykres definiuje przestrzeń w szczególny sposób: ze względu na sposób budowy tabele skrótów wymagają więcej pamięci niż tylko absolutne minimum wymagane do przechowywania danego zestawu elementów. Informatycy nazywają tę dodatkową przestrzeń „marnowanymi bitami”, mimo że w rzeczywistości nie są one zmarnowane, a w pewnym stopniu są konieczne. Oś przestrzenna na krzywej kompromisu mierzy liczbę zmarnowanych bitów na klucz.

Analizując krzywą kompromisów, badacze mogą określić najszybszy możliwy czas dla tabeli mieszającej zajmującej daną ilość miejsca. Mogą także odwrócić pytanie, aby znaleźć najmniejszą możliwą przestrzeń dla danego czasu operacji. Zwykle niewielka zmiana w jednej zmiennej prowadzi do niewielkiej zmiany w drugiej, mówi Williama Kuszmaula, informatyk teoretyczny na Harvardzie i współautor artykułu z 2022 roku. „Jeśli podwoisz czas, być może zmniejszysz o połowę liczbę zmarnowanych bitów na klucz”.

Ale tak nie jest w przypadku zaprojektowanej przez nich tabeli mieszającej. „Jeśli nieznacznie wydłużysz czas, liczba straconych bitów na klucz będzie wykładniczo spadać” – powiedział Kuszmaul. Krzywa kompromisów była tak stroma, że ​​dosłownie wykraczała poza schematy.

Zespół zbudował swoją tabelę skrótów składającą się z dwóch części. Miały pierwotną strukturę danych, w której elementy są przechowywane bez żadnych zbędnych bitów, oraz wtórną strukturę danych, która pomaga żądaniu zapytania znaleźć szukany element. Chociaż grupa nie wymyśliła pojęcia wtórnej struktury danych, dokonała kluczowego odkrycia, które umożliwiło stworzenie hiperwydajnej tablicy skrótów: ogólna wydajność pamięci struktury zależy od tego, jak struktura pierwotna organizuje przechowywane elementy.

Podstawową ideą jest to, że każdy przedmiot w strukturze podstawowej ma preferowane miejsca przechowywania — najlepszą lokalizację, drugą najlepszą, trzecią najlepszą i tak dalej. Jeśli element znajduje się w najlepszym miejscu, przypisana jest do niego liczba 1, a liczba ta jest przechowywana w wtórnej strukturze danych. W odpowiedzi na zapytanie struktura drugorzędna podaje tylko cyfrę 1, która określa dokładną lokalizację elementu w strukturze podstawowej.

Jeśli element znajduje się na 100. miejscu w rankingu, drugorzędna struktura danych dołącza liczbę 100. A ponieważ system używa systemu binarnego, reprezentuje liczbę 100 jako 1100100. Przechowywanie liczby 1100100 wymaga oczywiście więcej pamięci niż 1 — numer przypisany do przedmiotu, gdy znajduje się on w najlepszym miejscu. Takie różnice stają się znaczące, jeśli przechowujesz, powiedzmy, milion przedmiotów.

Zespół zdał sobie zatem sprawę, że jeśli stale będziesz przesuwać elementy podstawowej struktury danych do ich bardziej preferowanych lokalizacji, możesz znacznie zmniejszyć ilość pamięci zużywanej przez strukturę drugorzędną bez konieczności wydłużania czasu wykonywania zapytań.

„Przed tymi pracami nikt nie zdawał sobie sprawy, że można jeszcze bardziej skompresować strukturę danych poprzez przenoszenie informacji” – powiedział Pagh. „To był najważniejszy wniosek artykułu Bendera”.

Autorzy wykazali, że ich wynalazek ustanowił nową górną granicę dla najbardziej wydajnych tablic skrótów, co oznacza, że ​​była to najlepsza struktura danych, jaką kiedykolwiek opracowano, zarówno pod względem wydajności czasowej, jak i przestrzennej. Pozostała jednak możliwość, że ktoś inny poradzi sobie jeszcze lepiej.

Związany z sukcesem

W następnym roku zespół prowadzony przez Huacheng Yu, informatyk z Uniwersytetu Princeton, próbował ulepszyć tablicę skrótów zespołu Bender. „Pracowaliśmy naprawdę ciężko i nie mogliśmy tego zrobić” – powiedział Renfei Zhou, student Uniwersytetu Tsinghua w Pekinie i członek zespołu Yu. „Wtedy podejrzewaliśmy, że ich górna granica jest [również] dolną granicą” – najlepszą, jaką można osiągnąć. „Kiedy górna granica zrówna się z dolną granicą, gra się kończy, a ty masz odpowiedź”. Nieważne, jak mądry jesteś, żadna tabela skrótów nie będzie lepsza.

Zespół Yu zastosował nowatorską strategię, aby sprawdzić, czy to przeczucie było słuszne, poprzez obliczenie dolnej granicy na podstawie pierwszych zasad. Po pierwsze, doszli do wniosku, że aby dokonać wstawienia lub usunięcia, tablica skrótów – a właściwie dowolna struktura danych – musi uzyskać dostęp do pamięci komputera określoną liczbę razy. Gdyby udało im się obliczyć minimalną liczbę czasów potrzebnych do oszczędnej przestrzennie tabeli skrótów, mogliby pomnożyć ją przez czas wymagany na dostęp (stała), co dałoby im dolną granicę czasu wykonania.

Ale jeśli nie wiedzieli nic o tablicy mieszającej (z wyjątkiem tego, że zajmowała mało miejsca), w jaki sposób badacze mogli obliczyć minimalną liczbę razy wymaganą do uzyskania dostępu do pamięci? Wyprowadzili go wyłącznie z teorii, wykorzystując pozornie niepowiązaną dziedzinę zwaną teorią złożoności komunikacji, która bada, ile bitów potrzeba do przekazania informacji między dwiema stronami. W końcu zespołowi się udało: obliczyli, ile razy struktura danych musi uzyskać dostęp do swojej pamięci w ramach jednej operacji.

To było ich kluczowe osiągnięcie. Następnie udało im się ustalić dolną granicę czasu wykonania dowolnej tabeli skrótów oszczędzającej miejsce. I zobaczyli, że dokładnie pasuje do tabeli skrótów Bendera. „Początkowo myśleliśmy, że można to ulepszyć” – powiedział Zhou. „Okazało się, że się myliliśmy”. To z kolei oznaczało, że problem Petersona został wreszcie rozwiązany.

Kuszmaul powiedział, że poza odpowiedzią na pytanie sprzed kilkudziesięciu lat zadziwiającą cechą dowodu Yu jest jego ogólność. „Ich dolna granica dotyczy wszystkich możliwych struktur danych, także tych, które jeszcze nie zostały wynalezione.” Oznacza to, że żadna metoda przechowywania danych nie przebije tabeli skrótów Bendera pod względem pamięci i szybkości.

Haszowanie w przyszłość

Pomimo niespotykanej dotąd wydajności nowej tablicy mieszającej, prawdopodobnie nikt w najbliższym czasie nie będzie próbował jej zbudować. Jest po prostu zbyt skomplikowany w konstrukcji. „Algorytm, który jest szybki w teorii, niekoniecznie jest szybki w praktyce” – powiedział Zhou.

Nie jest niczym niezwykłym, że takie luki między teorią a praktyką utrzymują się przez długi czas, powiedział Kuszmaul, ponieważ teoretycy mają tendencję do ignorowania czynników stałych. Czas potrzebny na wykonanie operacji jest zwykle mnożony przez liczbę, pewną stałą, której dokładna wartość może być nieistotna z teoretycznego punktu widzenia. „Ale w praktyce stałe naprawdę mają znaczenie” – powiedział. „W prawdziwym świecie współczynnik 10 oznacza koniec gry”.

Rzeczywiste tabele skrótów wciąż ulegają istotnym zmianom, nawet jeśli znacznie odbiegają od teoretycznego ideału. Na przykład nowa tabela mieszająca o nazwie Góra lodowaHT, zbudowany przez Bendera, Kuszmaula i innych, jest znacznie lepszy od swoich poprzedników. Według Kuszmaula jest dwukrotnie szybszy niż najbardziej zajmująca obecnie przestrzeń tablica mieszająca i zajmuje trzy razy mniej miejsca niż najszybsza tablica mieszająca.

Mitzenmacher ma nadzieję, że wynik za 2023 r. może wkrótce przynieść inny rodzaj korzyści: „Za każdym razem, gdy pojawi się nowa dolna granica – zwłaszcza taka, która wymaga nowych technik – zawsze jest nadzieja, że ​​uda się ją wykorzystać… w przypadku powiązanych problemów”.

Jest też intelektualna satysfakcja wynikająca ze świadomości, że rozwiązano trudny i długotrwały problem – stwierdził informatyk Piotra Indyka Instytutu Technologii Massachusetts. „Gdy masz pewność, że pewnych struktur danych nie da się ulepszyć, może to pomóc w skoncentrowaniu wysiłków badawczych”. Wreszcie badacze danych mogą odwrócić swoją uwagę od wyzwania Petersona i skupić się na nowych problemach informatyki teoretycznej, których nie brakuje.