Roaring Bitmap: Skompresowana Bitseta Mocząca Szukanie Maszyn

Rozdzielenie zakresu liczb całkowitych na kawałki

Roaring Bitmap zaczyna od prostej idei wziętej z tego, jak komputery reprezentują liczby. Każdy nieujemny trzydziestycyliczny integer można podzielić na dwie półliczby szesnastocyfrowe: górską i dolną. Górna szesnastocyfrowa półliczba może przyjąć jedno z sześćdziesięciu pięci setki trzysta sześć różnych wartości, a więc jest używana do wyboru kawałka, czasem nazywanego grupą kontenerów, do którego należy liczba. Dolna szesnastocyfrowa półliczba, która również może przyjąć jedno z sześćdziesięciu pięci setki trzysta sześć różnych wartości, opisuje pozycję tej liczby wewnątrz swojego kawałka. Inaczej mówiąc, cały zakres liczb całkowitych o ponad czterysta miliony wartości jest podzielony na sześćdziesiąć pięć setki trzysta sześć naczyń, każde z nich odpowiadające dokładnie sześćdziesięciu pięci setku trzysta sześć możliwych wartości. Krytycznie, kawałek jest tworzony i przechowywany tylko wtedy, gdy przynajmniej jedna liczba należąca do niego jest rzeczywiście obecna w zbiorze. Jeśli Twoje dane używają tylko liczb całkowitych poniżej sto tysięcy, tylko pierwsze dwa kawałki będą potrzebować istnieć, a każdy inny kawałek zużywa zero pamięci. Ta oporna, na żądanie alokacja kawałków jest pierwszym dużym źródłem efektywności Roaring Bitmap: nigdy nie płaci kosztu pamięci za zakresy liczb, które są całkowicie puste. W każdym aktywnym kawałku liczby należące do niego, czyli ich dolne szesnastocyfrowe półliczby, muszą być gdzieś przechowywane, a format przechowywania jest wybierany niezależnie dla każdego pojedynczego kawałka. Dwa poziomy projektu, rzadki górny poziom identyfikatorów kawałków, podpierający niezależnie optymalizowane kontenery, to co pozwala Roaring Bitmap na adaptację do bardzo różnorodnych rozkładów liczb, od małych grup rozproszonych identyfikatorów do prawie ciągłych zakresów obejmujących miliony wartości, wszystko w jednym zintegrowanym strukturze.

Trzy typy kontenerów dla trzech rodzajów danych

W każdym bloku Roaring Bitmap przechowuje kontener, który zawiera najniższe szesnaście bitów każdego z wartości obecnych, a wybór między trzema formatami kontenera opiera się na ilości rzeczywistych wartości przechowywanych w tym bloku. Pierwszy to kontener tablicowy, używany przy brzemiennym bloku, co zwykle oznacza, że zawiera nie więcej niż około cztery tysiące wartości. Tablica ta po prostu lista wartości najniższych bitów w uporządkowanej kolejności, a każda z nich jest przechowywana kompaktowo, więc blok zawierający tylko kilka liczb z możliwych sześćdziesięciu pięćset trzydzieści sześć kosztuje prawie nic do przechowywania. Drugi to kontener bitmapowy, używany przy gęstym bloku. Allokowany jest stały blok o wielkości osiem tysięcy dziewięćset dwadzieścia dwóch bajtów, jedno bit dla każdej możliwej wartości w tym bloku, a bity są prosto odwracane lub ustawiane. Gdy blok zawiera więcej niż kilka tysięcy wartości, bitmapa nieprzetworzona staje się bardziej kompaktowa niż posortowana lista pojedynczych liczb, ponieważ koszt przechowywania dla każdego z indywidualnych wartości w kontenerze tablicowym zaczyna przekraczać stały koszt jednego bitu na możliwy pozycji. Trzeci to kontener kodowany długością sekwencji, używany przy bloku zawierającym długie ciągi nieprzerwanych liczb całkowitych. Zamiast przechowywać każdą wartość w sekwencji indywidualnie, przechowywane są tylko wartości początkowe i długości każdej sekwencji, więc blok reprezentujący, na przykład, dziesięć tysięcy kolejnych identyfikatorów dokumentów można opisać jednym małym pary liczbami zamiast dziesięciu tysięcy osobnych wpisów. Implementacja Roaring Bitmap ciągle estymuje i w wielu implementacjach dynamicznie konwertuje między tymi trzema reprezentacjami, która zajmuje najmniej miejsca dla rzeczywistych treści bloku, więc ogólna struktura nigdy nie płaci za format zbyt kosztowny, gdy bardziej ekonomiczny byłby dokładnie tak samo efektywny.

Dlaczego kontenery adpatywne przewyższają proste bitmapy i tablice

Motywacja dla trójwymiarowego projektu adpatacyjnego staje się jasna, gdy rozważamy błędy funkcjonowania dwóch prostszych alternatyw, które on zastępuje. Prosta, niewykompresowana bitmapa na pełnym zakresie trzydziestiościobitowym wymagałaby pięćset dwunastu megabajtów tylko do istnienia, niezależnie od tego, czy zestaw zawiera dziesięć liczb lub milion, ponieważ każdy możliwy wartość musi mieć zarezerwowany bit, nawet jeśli nie jest używany. Jest to ogromna, często niedopuszczalna, stała koszt reprezentacji rzadkich zbiorów, które są bardzo powszechnie spotykane w praktycznych obciążeniach, takich jak wyniki wyszukiwania pasujące do szerokiego filtru. Na drugiej strone, prosta posortowana tablica lub zestaw hash unika tego stałego kosztu i zapisuje tylko liczby rzeczywiście obecne, ale płaci inny cenę, gdy zestaw staje się duży lub kiedy potrzebujesz połączyć wiele zestawów. Obliczanie przecięcia lub sumy dwóch dużych posortowanych tablic zwykle wymaga porównywania i łączenia elementów jeden po drugim, operacji której koszt rośnie z całkowitej liczby elementów, a zestawy hash pogorsza sytuację, przestawiając porządek posortowany, który umożliwia szybkie łączenie. Bitmapa Roaring uniknie obu problemów, ponieważ nigdy nie stosuje jednej strategii na cały zakres. Rzadkie regiony przestrzeni liczb są obsługiwane przez kontener tablicy kompaktowej, więc nie jest zużywany żaden pamięci na puste miejsca. DENSE regions są obsługiwane przez kontener bitmapy niewykompresowanej, więc nie akumuluje się żadne koszty administracyjne dla każdego elementu. Regiony z długimi ciągami kolejnych wartości, powszechne w obciążeniach takich jak identyfikatory uporządkowane według czasu lub ciągi rzędów są obsługiwane przez kontener kodowany długością ciągu, który może reprezentować miliony wartości w niewielkim i stałym ilości pamięci. Ponieważ wybór jest dokonany niezależnie dla każdego fragmentu, pojedyncza bitmapa Roaring może jednocześnie zawierać niektóre fragmenty prawie puste, niektóre prawie pełne oraz niektóre długie ciągi nieprzerwanej wartości, każda zapisana w formacie najlepiej dopasowanym do niej, bez żadnego globalnego kompromisu.

Szybkie Operacje na Zestawach, Kontener za Kontenerem

Prawdziwy zysk wynikający z tej konstrukcji pojawia się w momencie potrzeby łączenia zestawów, co jest operacją, której wyszukiwarki i bazy danych wykonują regularnie. Na przykład, łączymy zestaw dokumentów zawierających jedno słowo szukane z zestawem dokumentów zawierających drugie. Roaring Bitmap wykonywała operacje unii, przecięcia lub różnicy, przeszukując identyfikatory fragmentów obu bitmaps w porządku posortowanym, podobnie jak łączenie dwóch list posortowanych, i przetwarzając pasujące fragmenty razem. Jeśli identyfikator fragmentu istnieje tylko w jednej z bitmaps, dla unii całe fragmenty mogą być prosto skopiowane bez zmian, a dla przecięcia można je pominąć całkowicie, ponieważ nie może tam być pasujących wartości. To samej samotnie eliminuje ogromne ilości niewykorzystanej pracy w porównaniu z podejściem bit po bitu lub element po elemencie, ponieważ całe fragmenty zawierające sześćdziesiąt pięć tysięcy trzysta trzydzieści sześć wartości są rozstrzygnięte jednym porównaniem. Gdy identyfikator fragmentu istnieje w obu bitmaps, dwie odpowiednie kontenery są łączone, a dokładny sposób zależy od typów kontenerów, które są używane. Dwa kontenery bitmap mogą być łączone przy użyciu bardzo szybkich instrukcji procesorowych logicznych działających na wielu bitach jednocześnie. Dwa kontenery tablicowe można łączyć podobnie jak dwa posortowane listy, w czasie proporcjonalnym do ichłącznej wielkości. Kontener kodowany długościami ciągów może być łączony z innym kontenerem porównując bezpośrednio ciągi i zakresy, często dotykając znacznie mniej pojedynczych wartości niż oba kontenery rzeczywiście reprezentują. Ponieważ każdy format kontenera zachowuje swoje zawartości w przewidywalnym, posortowanym porządku wewnętrznym, łączenia na poziomie kontenera nigdy nie muszą opierać się na wolnych porównaniach ogólnych, a koszt całościowej operacji śledzi rzeczywistą złożoność danych zamiast teoretycznej wielkości zakresu liczb. To pozwala systemom przetwarzającym miliardy identyfikatorów obliczać przecięcia i unieje zestawów w milisekundach.

Roaring Bitmap w rzeczywistych systemach

Roaring Bitmap został opisany po raz pierwszy w badawczym pracowni z 2016 roku i szybko przeniesiono go z idei akademickich do produkcji, gdzie jest używany w niektórych z najbardziej rozprzestrzenionych infrastruktur danych na świecie. Biblioteka wyszukiwania Apache Lucene, podstawowy element Elasticsearcha i Apache Solra, używa struktur typu Roaring do reprezentacji list docelowych, zestawów identyfikatorów dokumentów związanej z każdym indeksowanym terminem, co pozwala na szybką kombinację wyników wieloterminowego zapytania nawet w indeksach zawierających setki miliardów dokumentów. Apache Spark używa Roaring Bitmap do śledzenia, które podzbiory lub wiersze zostały już przetworzone podczas dużych skalarnych obliczeń rozproszonych, unikając zarówno pamięciowego nadmiaru standardowych bitmap, jak i kosztu scalania standardowych list. Bazy danych analityczne kolumnowe takie jak ClickHouse i Apache Druid używają go do reprezentacji indeksów bitmapowych nad kolumnami kategoryjnymi, gdzie zapytanie może musiało znaleźć wszystkie wiersze pasujące do wielu warunków filtrowania jednocześnie poprzez przecięcie kilku takich bitmap. W każdym z tych systemów podstawowa obciążona pracą ma tę samą formę: identyfikatory przychodzą po ogromnym zakresie numerycznym, ich rozkład jest nieprzewidywalny i może być bardzo rzadki lub bardzo gęsty, a system musi kombinować wiele takich zestawów pod strictym bugetem czasu. Adaptatywna kompresja na poziomie chunka oraz szybkie operacje nad kontenerami setowych bezpośrednio odpowiadają wszystkim trzem wymaganiom, co wyjaśnia, dlaczego stało się prawie standardowym wyborem w miejscach, gdzie potrzeba skutecznego indeksowania, przechowywania i kombinowania dużych zestawów liczb całkowitych, a nie techniką nischową ograniczoną do jednego produktu.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Roaring Bitmap: Compressed Sets for Fast Databases i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.