Kolize hashů pro mírně pokročilé

Hash tabulka je jedna ze základních datových struktur, byla vynalezena roku 1953 a všichni, kdo programování viděli aspoň z rychlíku, ji velice dobře znají. Hash tabulky (někdy také hashmapy nebo slovníky/dicti­onary) umí vyhledat, přidat nebo smazat hodnotu asociovanou s určitým klíčem v konstantním čase. Všechno je možné jen díky jednomu velice chytrému triku – použití hashovací funkce, která klíč, ať už je jakéhokoli typu a velikosti, zobrazí na číslo. To je potom využito k adresování do obyčejného plochého pole, které všichni známe a milujeme.

Tohle všechno funguje skoro až zázračně. Tedy aspoň do okamžiku, kdy to přestane. Pak se dostáváme do velkých problémů.

Všechno záleží na použité hashovací funkci. Ta by měla v ideálním případě být pseudo-náhodná – měla by produkovat hashe, které jsou rovnoměrně rozložené v oboru hodnot a které nezachovávají korelace mezi vstupními hodnotami, kdy např. hashe posloupnosti čísel také připomínají posloupnost. Jinými slovy: mělo by jít alespoň o jednu z rodiny univerzálních hashovacích funkcí.

Pokud hashovací funkce produkuje nadprůměrné množství stejných hashů pro různé hodnoty, nebo je předvídatelná a hodnoty s kolidujícími hashi může někdo, jehož záměry jsou méně než upřímné, snadno spočítat, hash-tabulky najednou začnou vykazovat patologické chování, kdy dříve konstantní operace potřebují lineární čas úměrný velikosti tabulky. Může tak jít o velice efektivní DOS útok.

Abych to osvětlil, musím se ponořit do krvavých detailů.


Hash tabulky mají tři základní varianty: chaining, probing a cuckoo hashing. Chaining a probing se také označují jako open hashing a open addressing, ale tohle označení nemám rád, protože si nikdy nemůžu vzpomenout, které je které.

Řetězící (chaining) varianta se zakládá na poli pointerů (buckets). Každý z nich ukazuje na spojový seznam, jehož každý článek obsahuje klíč, odpovídající hodnotu a pointer na následující článek (nebo null). Když chci vložit pár (key, value), spočítám hash klíče hash = ϝ(key) a z něj odpovídající pozici v poli pointerů index = hash % arraySize. Pokud je daná pozice prázdná, vytvořím článek a nastavím pointer na pozici index, aby na něj ukazoval. Pokud už je index obsazený, vytvořený článek připojím na konec seznamu.

Aby tohle fungovalo v konstantním čase, kolize musejí být nepravděpodobné. Pokud to platí, většina spojových seznamů obsahuje jen málo článků (v průměru n/m, kde m je velikost tabulky a n počet vložených elementů) a pole pointerů má délku úměrnou počtu položek v tabulce. V praxi jde o určitý malý násobek a je dovolené jen určité maximální zaplnění tabulky. Když je tato mez překročena, tabulka se zvětší na dvojnásobek, všechny klíče se rehashují na nové pozice a řetězy kolizí se zkrátí. Zvětšování o násobek garantuje amortizovaný konstantní čas operace vkládání.


Probing varianta typicky používá tři interní pole – jedno obsahuje klíče, druhé odpovídající hodnoty a třetí označuje smazané položky.

Pokud chci vložit klíč, stejně jako v minulém případě spočítám jeho hash a z něho odpovídající index v trojici stejně dlouhých polí. Když je odpovídající místo prázdné, klíč a hodnotu tam jednoduše vložím. Pokud je však místo už zabrané, vložím klíč a hodnotu o jedno místo doprava (linear probing), o 2i míst doprava (quadratic probing) nebo o počet míst vypočítaný jinou hashovací funkcí (double hashing). Pokud je plno i tam, zkouším další místa napravo dokud nenajdu volný flek.

Když chci najít určitý klíč, spočítám hash a z něho pozici, na které by se měl nacházet. Pokud se na tomto místě nachází, skončím s úspěchem. Pokud se tam nachází jiný klíč, zkusím to o jedno místo vpravo. Takto pokračuji, dokud nenajdu požadovaný klíč, smazaná místa ignoruji. Když narazím na prázdnou hodnotu, prohlásím, že klíč nebyl nalezen. Šipky v diagramu ukazují, kde se nachází další klíč se stejným hashem. Jak je vidět tento blok nemusí být spojitý a mezi klíči, které mají shodný hash, můžou být vklíněny klíče s jinými hashi. Záleží jen na pořadí vložení.

Pokud chci klíč smazat, pokusím se nalézt místo, kde se nachází (postup stejný jako v minulém odstavci) a potom, co ho objevím, ve třetím poli označím danou pozici jako smazanou (jde o pole boolů nebo o bitmapu). Kdybych klíče mazal tak, že bych odpovídající pozici v prvních dvou polích jen nastavil na null, rozbil bych hledání, protože bych tak do spojitých bloků vnesl díry a hledání by při nalezení této díry skončilo a nemuselo by se dostat ke správným hodnotám, které se můžou nacházet těsně za touto dírou.3

Konstantní čas pro všechny operace je zaručen opět tím, že hash funkce negeneruje kolize a rovnoměrně rozkládá hashe. V důsledku toho budou sekvence, které je potřeba projít při hledání klíčů, rozumně krátké. Tři zmíněná pole mají délku která je opět úměrná počtu položek v tabulce, i když bývají větší než u chainingu, protože efektivita probingu dramaticky degraduje, když se zaplnění tabulky blíží 100 procentům. Dlouhé běhy obsazených pozic, kam spadne mnoho hashů, která náhodou byly blízko sebe, se ještě více prodlužují a s nimi i počet míst, které je třeba projít. Nestačí jen jako v případě chainingu projít jeden spojový seznam odpovídající jednomu hashi, ale blok odpovídající několika hashům.

(Technicky vzato: Hashovací funkce použitá pro linear probing musí být aspoň 5-independent nebo musí jít o tabulation hashing, jinak není garantován konstantní čas. Více v tomto videu.)


Třetí variantou je takzvaný cuckoo hashing, který je založen na myšlence, že nepoužívám jednu hash funkci, ale dvě (a někdy i více). Výsledek každé funkce odpovídá jedné pozici v tabulce. Při vkládání se pokusím vložit na první pozici a když je obsazená, použiji druhou. Když je na této pozici jiný klíč, ten vezmu a přesunu ho na jeho druhou pozici a tak dále dokud nevystrčím klíč do neobsazeného místa. Pokud jsou hash funkce dobré, kolize řídké a nedojde k vytvoření smyček, počet přestěhovaných elementů při každém vložení je malý a to teoreticky garantuje konstantní časy jednotlivých operací (amortizované, když přihlédnu ke zvětšování tabulky, které probíhá, ne když je tabulka plná, ale když nemůžu vložit nový klíč). Cuckoo hashing se navíc chová rozumně i když je hash tabulka téměř plná a jeho výkon nedegraduje tak drasticky.

Podle toho co jsem četl, Cuckoo hashing se v praxi příliš nepoužívá, protože jeho výkon není z hlediska CPU cache nijak zázračný. Při vkládání musím načíst několik položek, které se nacházejí na prakticky náhodných místech v paměti (to je důsledek dobré hash funkce, která se chová jako PRNG), které s největší pravděpodobností nebudou v cache a z toho důvodu utrpím několik cache-miss. To samé platí při hledání klíče, jen počet načtených míst je v nejhorším případě stejný jako počet hash funkcí.

Chaining hash tabulka na tom také není nijak slavně: Nejprve musím načíst jeden pointer na prakticky náhodné pozici v paměti a pak postupně všechny objekty ze spojového seznamu. Protože články jsou dynamicky alokovány a lezí někde na haldě, každý pointer vede na nepředvídatelné místo v paměti. Pokud je tabulka větší než cache, s největší pravděpodobností toto místo nebude v cache. Navíc je načítání objektů spojového seznamu datově závislé: Musím načíst jeden objekt, abych zjistil pointer na ten další a teprve potom ho můžu načíst. Hardware nemá možnost paralelního přístupu k paměti. Některým z těchto nedostatků se dá předejít, když je spojový seznam částečně odrolovaný (jak je například použito v implementaci hashmap v Go).

Probing verze se vzhledem k hardwaru chová nejlépe ze všech. Sice také potřebuje načíst data ze tří prakticky náhodných míst paměti, ale tyto dotazy jsou nezávislé a hardware je může provést paralelně (paralelní fetch je demonstrován např zde). Změnami algoritmu a vnitřních datových struktur, je možné snížit počet interních polí na dvě nebo dokonce jen na jedno, což má za následek ještě lepší chování z hlediska CPU cache, jak ukazuje například tento článek. Navíc: Kolidující klíče nejsou ve spojovém seznamu, který skáče z místa na místo, ale jsou naskládány v paměti jeden vedle druhého (aspoň v případě lineárního probingu). S velkou pravděpodobností se budou nacházet na jedné cache-line, kterou procesor načte z paměti najednou. A když budu muset projít dlouhý seznam klidujících klíčů, prefetching se postará o to, abych měl data k dispozici včas a bez čekání na pomalou RAM. Počet kolizí může být velký, ale když hardware začne kouzlit, cena jedné kolize bude menší než v případě prolézání kratšího spojového seznamu.

Existují pochopitelně i další způsoby jak implementovat strukturu, která se chová jako asociativní pole. Ty jsou většinou založené na stromech a mají svoje specifické použití, jako například Hash Array Mapped Trie (také tady a tady).


Z předešlých odstavců je jasné, proč je útok na kolizi hashů (v literatuře se používá termín hash flooding) vůbec možný a jak efektivní může být. Všechny varianty hash tabulek se spoléhají na hashovací funkci, která musí být dobrá, rovnoměrná a produkovat málo kolizí. Když tyto předpoklady z nějakých důvodů přestane platit na horizontu se objeví čtyři jezdci apokalypsy a zátěž procesoru vyskočí na 100%. Jak se říká: Tvoje hash tabulka je jenom tak dobrá, jak dobrá je tvoje hash funkce.

Pokud do tabulky vkládám klíče, které mají stejný hash nastane právě takový apokalyptický scénář. A navíc stačí když je hash stejný modulo délka tabulky. V případě řetězení se nové klíče postupně vkládají na konec neustále rostoucího spojového seznamu a v případě probingu se musí projít čím dál tím větší blok obsazených pozic než je nalezeno volné místo, kam se může nováček vložit.

Například PHP pro hashování stringových klíčů používá velice jednoduchou a rychlou funkci DJBX33A, která vypadá takhle:

long DJBX33A(const unsigned char *key) {
  long hash = 5381;
  while(*key) hash = 33*hash + *key++;
  return hash;
}

Stačí chvíli střídavě zírat do kódu a do ASCII tabulky, než člověk přijde na několik krátkých stringů, které mají stejný hash. Jsou to například tyto tři: "~!", "}B", "|c"

Obecně platí, že stačí vybrat takové znaky, pro jejichž pozice v ASCII tabulce platí následující:

 a    * 33 +  b
(a+1) * 33 + (b-33)
(a+2) * 33 + (b-66)
     ...
(a+i) * 33 + (b-i*33)

Z toho, jak je DJBX33A napsána však vyplývá ještě jedna skutečnost: všechny stringy stejné délky poskládané z těchto střípků mají také stejný hash. Takže následující tři stringy mají také stejný hash:

"~!~!~!", "~!}B|c", "|c|cB|"

Najednou si můžu vygenerovat tolik stringů kolik si moje srdce žádá a ve velkém je začít posílat jako GET nebo POST argumenty a provést tak DOS útok nějaké PHP aplikace, jak bylo demonstrováno na Chaos Communication Congress v roce 2011 a 2012.

PHP tuto zranitelnost napravilo po svém a omezilo počet argumentů předaných jako POST nebo GET na něco kolem tisíce. Na(ne)štěstí v současnosti každá druhá webová služba poskytuje JSON API, které může útočník podstrčit speciálně připravený JSON dokument, který obsahuje jen a pouze zákeřné klíče. Když pak webová aplikace zavolá json_decode1, naparsuje JSON do PHP pole a sama se tak DOSne.

Pro představu jak velkou škodu může útok napáchat. Vytvoření pole se 100000 neškodnými klíči zabere (v PHP 5.6) 40 milisekund, se stejným počtem zákeřných klíčů 84000 milisekund.

V Javě/Scale jsem po rychlém experimentu v REPLu naměřil hodnoty: 27 ms a 20000 ms. Na konkrétních číslech však moc nezáleží, jde o to, že jedno roste lineárně, druhé kvadraticky.

V PHP verze 7 mají hash tabulky drasticky pozměněnou implementaci. Přešli z řetězu dynamicky alokovaných spojových seznamů na dvě před-alokovaná fixní pole, která má výkon velice podobný probingu. Stále však používají hashovací funkci DJBX33A. Útok je tedy stále možný, jen díky zvýšenému výkonu bude o něco málo méně účinný. Podle prvních nástřelů to vypadá, že je zhruba 10× méně nebezpečný.

A to nemluvím o tom, že celočíselné klíče se berou jako hash, což vede k možnosti útoků, které jsou triviální a zcela devastující.1

Jedinou skutečnou obranou proti tomuto útoku je použít randomizovanou hashovací funkci. Protože i když používám funkci, která rovnoměrně rozkládá hashe a není možné jednoduše před-počítat kolidující klíče a pak z nich poskládat mnohem víc delších klíčů, dostatečně odhodlaný útočník může brute-force metodou před-počítat dostatečné množství kolizí a pak je opakovaně posílat na cílový server. Přesně v duchu rčení pain is temporary, glory is ethernal.


Jak jsou na tom jiné jazyky/runtime?

HHVM standardně používá Murmur3 hash, ale když běží ne stroji, který podporuje SSE4.2, tak začne hashovat pomocí CRC32, která je implementována v hardware a tudíž velice rychlá (bohužel je rychlá i pro útočníky).

Java k hashování stringů používá funkci, která je velice podobná té z PHP:

public int hashCode() {
  int h = 0;
  for (char v : value) {
    h = 31 * h + v;
  }
  return h;
}

A stejně jako v případě PHP je zcela triviální vygenerovat kolidující stringy:

"1}" // 49 * 31 + 125 = 1644
"2^" // 50 * 31 + 94  = 1644
"3?" // 51 * 31 + 63  = 1644
"4 " // 52 * 31 + 20  = 1644

Integer se (zase podobně jako v PHP) hashuje na sebe sama. Na rozdíl od PHP se však tato slabina nedá tak jednoduše zneužít, protože int má malý rozsah. V javě má 4 bajty a něco přes 4 miliardy možných hodnot, takže v nejhorším případě do hash tabulky můžu vložit 65536 klíčů, jejichž hash je dělitelný 65536 a hash modulo velikost tabulky bude stejný.

Long se hashuje takto:

public static int hashCode(long value) {
  return (int)(value ^ (value >>> 32));
}

To vypadá rozumně, ale

(long) x << 32 | (long) x

je nula pro libovolné x. Když jsou horní a dolní čtyři bajty stejné, jejich xor je 0.

Zkuste si to sami a uvidíte jak se roztočí větrák na procesoru:

val map = new collection.mutable.HashMap[Long, Int]()

for (i <- 0 until 100000) {
  val h = (i.toLong << 32 | i.toLong)
  map.put(h, 1)
}

Problém může také nastat, když obě poloviny longu používají jen pár dolních bitů. Když používají jen 10 bitů (tedy čísla v rozmezí 0 – 1024), můžou reprezentovat milion kombinací, ale jejich hash je jen v onom desetibitovém rozmezí 0 – 1024. V takovém případě se bude hashovat jen do malé částí hash-tabulky a všechno bude (opět) velice pomalé. Tenhle případ jsem poznal na vlastní kůži, když jsem se snažil udělat něco chytrého.

Java v některé nedávné verzi přinesla jednu vychytávku: Pokud jeden slot obsahuje víc jak 8 kolizí, je spojový seznam přestavěn na binární red-black strom. Ten v patologických případech zredukuje lineární časovou složitost na logaritmickou za cenu nepříjemně komplikovaného kó­du.

C# podle všeho používá celkem jednoduchou multiplikativní funkci.

val hash1, hash2 = 5381
while (i < str.length) {
  hash1 = (hash1 * 33) + str(i)
  hash2 = (hash2 * 33) + str(i+1)
  i += 2
}

hash1 + (hash2 * 1566083941)

Když se nechci uchylovat k bruteforce řešení, je spočítání kolidujících stringů poměrně jednoduché. Například tyto dva kolidují: "*_O_", "+_n_".

Pokud se však zahledíte do odkazovaného kódu, uvidíte tam za několika IFDEFy nějaké ty XORy a možná i nějakou tu randomizaci. Těžko říct o co přesně tam jde.


Ať už je ale hash funkce libovolná, útočník může vždycky bruteforce vypočítat kolidující řetězce. Když jich zkusí moře, dostane pár kapek, a to může být víc než dost.

Jediným systematickým řešením je použít randomizovanou hash funkci. Taková funkce má několik skrytých argumentů (jsou např. vygenerovány na začátku běhu programu), které změní výstup hashovací funkce tak, že když s jedním argumentem mají dvě hodnoty stejný hash, s jiným mají vzájemně odlišné hashe.

Jako špatný příklad příklad uvedu PHP funkci DJBX33A. V té se na začátku vyskytuje magická konstanta 5381. Když bych randomizoval tuto konstantu, hashe budou jiné, ale jejich korelace zůstanou.

Pokud platí:

ϝ(a, 5381) = ϝ(b, 5381)

Tak bude také platit

ϝ(a, s) = ϝ(b, s)

Hashe se změní, kolize zůstanou.

Je nutné použít randomizovanou funkci, která tak byla navržena, jako je třeba SipHash (podrobně popsaná v tomto paperu). Ta je jednak rychlá (pomalejší než jednoduchá DJBX33A, ale mnohem rychlejší než třeba MD5) a zároveň poskytuje všechno dobré kolem randomizace. Útočník je schopný provést hash flood útok jen pokud zná náhodných 128 bitů, které SipHash používá jako seed, ale ty se můžou měnit každou minutu nebo při každém HTTP požadavku. Útočník jednak nemá jak zjistit tento seed a i kdyby ho zjistil 2, má jen limitované možnosti, jak ho uplatnit.

V případě PHP je změna hashovací funkce triviální, protože na rozdíl od světa Javy není součástí veřejného API a její změna nemůže rozbít kód, který na ní závisí.


Jako další ukázka proč jsou hashovací funkce důležité může posloužit příklad Bloom filtrů. Bloom filtr je pravděpodobnostní datová struktura pro test členství v množině, která interně používá několik hashovacích funkcí. Nedávno jsem psal vlastní maličkou implementaci bloom filtru do knihovny sketches a použil jsem stejné hashovací schéma jako v knihovně Breeze založené na MurMur3 hashi. Při testování se ukázalo, že výsledný filtr generuje 1000000000× více falešných pozitiv, než by statisticky měl. To byla velice špatná zpráva, protože to dělalo tuto strukturu mnohem méně přesnou a mnohem méně užitečnou. Později se ukázalo, že za tuto vadu může právě použití MurMur3 hashe, který očividně neprodukuje uniformní rozložení a nepatří tedy do rodiny univerzálních hashovacích funkcí. Když jsem použil dobrou univerzální hashovací funkci, problém zmizel.


Na závěr přidám dvě perličky:

Cache procesoru je také (překvapivě) organizována jako hash-tabulka – obsahuje několik slotů (řekněme 64) a každý slot může obsahovat 8 cache line (každá má 64 bajtů). Hashovací funkce vypadá takto: vezme fyzickou adresu, zahodí 6 nejnižších bitů a vezme 6 dalších. Výsledkem je index slotu v němž bude hledat nebo do něhož bude ukládat data.

Když program přistupuje na adresy s velice specifickým rozestupem, cache alising v podstatě udělá hash flood CPU cache, jak je ukázáno ve What Every Programmer Should Know About Memory nebo v Binary Search Is a Pathological Case for Caches. Následující graf pochází právě z WEPSKAM.

Za pozornost stojí také Robin Hood Hashing. Jde o variantu probing hashování, kde v nejhorším případě mají operace logaritmickou složitost. RH hashování toho docílí tím, že průměruje počet slotů, které je potřeba prohledat ve stylu Robina Hooda – bohatým bere (krátká probing cesta) a chudým dává (dlouhá cesta). Elementy v jenom běhu jsou tedy seřazeny podle délky probe cesty (nebo dokonce v některých variantách podle hashe samotnho), při vkládáná se tedy provádí inserion sort a hledání je možné předčasně ukončit i v případě, když element není v tabulce přítomen a dále to vede k velice jednoduchému a rychlému zvětšování tabulky a hromadnému vkládání, kterému předchází radix sort.

Tohle všechno znamená, že jsou všechny operace rychlé a tabulka se chová rozumně, i když je z velké části (klidně i 90%) zaplněná. Jak o tom teď píšu, napadá mě, že bych měl napsat vlastní implementaci ve Scale a přidat ji do sketches.


A to je všechno. Pokud jste se dočetli až sem, nejspíš toho víte o hash funkcích a jejich kolizích víc, než jste kdy chtěli vědět.


  1. Tady patří díky Janu-Sebastianovi Fabíkovi, který krátce potom, co jsem dopřednášel, přišel na to, že json_decode je částečně odolný nejtriviálnějšímu útoku, kdy se serveru pošle pole s speciálně připravenými numerickými klíči. Když json_decode bez extra parametrů narazí na JSON objekt, naparsuje ho jako PHP objekt. PHP objekty konvertují všechny atributy na string a tedy útok numerickými klíči nemá žádný dopad. Když se však json_decode předá druhý argument $assoc, tak JSON objekty naparsuje na pole a jsme zpátky odkud jsme vyšli. V obou případech je však zranitelný, když mu podstrčíme json s kolidujícími stringovými klíči.
  2. např. Python používal podobnou funkci, ale později se ukázalo, že je možné zjistit tajný seed.
  3. Přímo je možné smazat elementy na konci řady, tedy ty, které mají napravo neobsazenou pozici. Stejně tak je možné vložit element do smazané pozice. Tyto dvě zkratky nerozbijí hledání, protože nezpřetrhají řady obsazených pozic.

Dále k tématu:

Flattr this!

Posted in DS, Hashování, Java, PHP | Leave a comment

Střeva databází

Tenhle článek je mojí skromnou snahou si udělat pořádek v některých technikách a datových strukturách, které se používají uvnitř databází. Nejde o nijak kompletní nebo hluboký výčet, protože realita je vždycky mnohem komplikovanější a zdánlivé detaily (jako třeba konzistence) hrají vždycky větší roli, než se může na první pohled zdát.

Non-clustered index

Neclusterované indexy (jako například MyISAM morálně vycházející ze stařičkého ISAM) mají oddělený B-strom určený k navigaci a datový soubor obsahující data jednotlivých řádků. Listy B-stromu obsahují ukazatele do datového souboru a řádky se nacházejí v pořadí vložení, které nezaručuje, že bude odpovídat pořadí primárního klíče.

Důsledky tohoto uspořádání jsou jasné: Vkládání nových řádků je rychlé, protože stačí najít volné místo v datovém souboru, vložit klíč do B-stromů všech indexů (primárních i sekundárních), namířit pointer na řádek a voilà, data jsou uložená. Dotazování jednoho řádku je celkem nezajímavé, stačí najít klíč v příslušném B-stromu a skočit na pointer. Naproti tomu hledání rozsahů podle primárního klíče není tak růžové. Na rozdíl od clusterovaného indexu data nejsou uložena seřazená – je proto třeba najít požadovaný rozsah v B-stromu a dereferencovat všechny nalezené pointery, které můžou vést na nepředvídatelná místa v datovém souboru a náhodnému IO, které je katastrofální na rotujících discích, ale i na modernějších médiích je pomalejší než sekvenční čtení.

Clustered index

Jak je vidět z příjemně kryptického schématu, clusterovaný index3 (jako je například v InnoDB) obsahuje řádky seřazeném stejně jako primární klíč. Ty můžou být buď přímo v listech B-stromu nebo v jiném souboru, na který se listy B-stromu odkazují, ale který stále obsahuje řádky seřazené. Toto uspořádání přidává určitou režii pro vkládání nových záznamů, protože musí udržovat řazení, ale na druhou stranu vede k rychlým range select dotazům podle primárního klíče, protože stačí najít začátek a pak číst data dokud predikát dotazu platí.

Při hledání podle sekundárních indexů je třeba jedna úroveň nepřímosti navíc. B-strom sekundárního indexu v listech obsahuje primární klíč příslušného řádku, ten je třeba použít pro prohledání primárního B-stromu a získání samotného řádku. Protože jsou místo fyzických pointerů mířících do diskových bloků, použity virtuální identifikátory primárního klíče, je tento přístup výrazně flexibilnější a dovoluje přesouvat řádky bez toho, aby bylo třeba změnit všechny indexy, které na přestěhovaný řádek ukazují.

Tady se taky vyplatí zmínit covering index, který není to samé, co clustered index. Covering index (nebudu se snažit překládat) je takový index, který kompletně pokrývá všechny sloupce jednoho dotazu. Když tedy například sekundární index obsahuje všechny sloupce zmíněné v dotazu, není třeba hledat v B-stromu primárního indexu. Primární clustered index je z principu zároveň covering pokud dotaz hledá podle primárního klíče. Některé databáze (například TokuDB, pokud se nepletu) nabízejí možnost covering sekundárních indexů. V takovém případě listy B-stromu neobsahují primární klíč, ale všechny sloupce, které nejsou součástí klíče sekundárního indexu. Když se pak dotaz rozhodne použít sekundární covering index, má všechna data k dispozici.

Fractal trees

Fractal trees, používané v databázovém enginu TokuDB, jsou ve své podstatě obyčejné B-stromy, ve kterých je každý vnitřní uzel obohacený o buffer, do kterého směřují zápisy. Když se buffer naplní, změny jsou zatlačeny a propagovány do příslušných uzlů o úroveň níž. Díky tomuto uspořádání jsou všechny zápisy sekvenční, stejně jako IO, protože se vždy zapisuje sekvenčně do bufferu nebo se změny sekvenčně zapisují o úroveň níže. To vede k nízké write amplification a dobrému chování, když se kostra B-stromu nevejde do paměti. Není třeba pro každou aktualizaci dělat až log(n) náhodných IO operací, protože zápisy jsou amortizované a provede se jen pár sekvenčních IO operací.

Fraktální stromy, podobně jako LSMT, excelují velice rychlými inserty, ale na rozdíl od LSMT si stále zachovávají podobu B-stromů. Není tedy třeba na rozdíl od LSMT prohledávat log(n) seřazených souborů, ale jen jeden index o hloubce logb(n), kde b je nějaké relativně velké číslo + příslušné buffery.

Buffery se hodí na víc než jen na dočasnou akumulaci insert/update/de­lete operací. Dají se také využít pro odložené změny struktury tabulky. V typickém případě, když pomocí alter table přidám nebo odeberu sloupec, databáze musí přestavět celou tabulku, což může trvat velice dlouhou dobu. Ve fraktálním stromě můžu do bufferu vložit zprávu addcolumn, která se postupně propaguje k listům, jak je třeba, a když jich dosáhne, přidá požadovaný sloupec. Struktura tabulky se tedy nezmění hned, ale až někdy v budoucnosti, když se zápisy dostanou k listům B-stromu. Databáze přitom udržuje iluzi, že sloupec byl přidán a dotazy vrací správná data.

Log-structured merge-tree

LSMT (používané například v LevelDB nebo RocksDB) je interně uspořádané jako série seřazených polí/souborů. V nejjednodušším případě může jít o několik úrovní (0..k), z nichž k-tá má velikost 2k. Nový element je vložen do nulté úrovně. Pokud je prázdná, všechno skončí, pokud je plná, dvě pole nulté úrovně se sloučí do dvakrát většího seřazeného pole první úrovně1. Když je i ta úroveň obsazená, dochází rekurzivně ke slučování dokud nenarazí na prázdnou úroveň. Skutečně použitá schémata můžou být složitější, kdy v každé úrovni je několik souborů nebo se všechny soubory nacházejí v jedné úrovni a kandidáty na kompakci jsou vybírány heuristicky, mohou se také lišit tím, jestli je dovoleno, aby různé soubory ze stejné úrovně obsahovaly překrývající se rozsahy klíčů.

LSMT tedy má 1 až log(n) úrovní a všechny inserty do nejnižší z nich jsou velice rychlé, protože nejnižší úrovně zcela žijí v paměti2 a všechny IO operace zápisů jsou z podstaty věci sekvenční. Amortizovaná cena je také konstantní, jen někdy může zápis čekat, protože spustí kompakci. Slučování však může probíhat paralelně na pozadí a neblokovat probíhající čtení nebo jiné zápisy, protože seřazený soubor je efektivně neměnný. Problém ale může představovat situace, kdy slučování nestíhá, protože rychlost zápisu je limitovaná rychlostí kompakce a kompakce mezi úrovněmi vede k write aplification.

Při hledání je třeba procházet seřazené soubory jeden po druhém od nejnovějšího k nejstaršímu a pomocí binárního hledání v nich pátrat po požadovaném klíči a to má v jednoduchém schématu načrtnutém výše složitost něco jako log2(n). Pro range scan dotazy je nutné vždycky projít všechny soubory a není možné, jako v případě bodových dotazů, přestat, když je klíč nalezen.

Pro urychlení bodových dotazů může každý soubor obsahovat nějakou verzi Bloom filteru (nebo něco podobného) pro každý soubor. Pro range scan dotazy může mít bloom filter na prefixech klíčů nebo něco jako Adaptive Range Filter.

Fractional cascading

LSMT má složitost dotazů log2(n). Obsahuje log(n) úrovní a v každé je třeba provést binární hledání o složitosti ±log(n). Fractional cascading zlepšuje asymptoty hledání na log(n)+log(m) tím, že každá úroveň obsahuje ukazatele do hlubší úrovně na odpovídající rozsah klíčů. Jelikož odkazovaný rozsah v hlubší úrovni má konstantní velikost, je třeba udělat log(m) binární hledání v jedné úrovni a pak následovat pointery do malého výseku hlubší úrovně, ten prohledat a v případě nouze pokračovat hlouběji maximálně log(n) úrovní – tudíž log(n)+log(m). Na druhou stanu to přidává režii, která je potřeba k udržování a počítání těchto pointerů. Protože jsou často krajní hodnoty kopírovány z vyšší úrovně do té nižší, zvyšuje to o něco prostorové nároky.

Fractional cascading bylo použité v TokuDB jako první verze fraktálních stromů, než přešli na vylepšené B-stromy. To někdy vyvolává zmatek, protože některé články popisují jedno a některé to druhé.

  • fractional cascading se zmiňuje v kontextu datových struktur v paměti Kmett ve svých přednáškách.
  • Něco málo o COLA a fractional cascading tady a tady.

Dále k tématu:

Pozn:

  1. Použitý algoritmus je podstatě merge sort, jen je počítá s několika speciálními případy. Např. když je element v obou slučovaných úrovních, do výsledné kolekce zapíše jen ten nejnovější, když narazí na tombstone označující smazaný element, musí ho zapsat jen pokud nejde o slučování do nejvyšší úrovně, atd.
  2. Data v paměti se nacházejí ve struktuře, které se říká memtable (může být implementována jako skip list), seřazené soubory na disku se v některých implementacích označují sstfile.
  3. Dopad clusterovaných/ne-clusterovaných indexů na složitost operací a funkci plánovače je demonstrován v Access Path Selection in a Relational Database Management System.

Flattr this!

Posted in DB, DS | Leave a comment

I ve Scale se dá psát rychlý generický kód za použití typeclass

Nedávno jsem tu psal o tom, jak se dá rychle vypočítat Jaccardova podobnost. Rychle bylo klíčové slova a jediná věc na které skutečně záleželo. Právě kvůli rychlosti jsem do knihovny sketches přidal verzi této rutiny (a pár dalších funkcí) specializovanou pro jediný primitivní typ. Výsledek je na jednu stranu rychlý, ale na druhou stranu neflexibilní. Co když budu chtít udělat to samé, ale místo čtyřbajtových intů s osmibajtovými longy? V tom případě mám smůlu a musím duplikovat kód.

Naštěstí Scala nabízí dvě vlastnosti – typeclassy a specializaci, které přesně tento problém v kombinaci s chytrým a agresivním JITem dokážou vyřešit. S trochou snahy je možné psát kód, který je obecný a zároveň stejně rychlý jako verze ručně specializovaná pro každý primitivní typ.

Ručně specializovaná metoda vypadala takhle:

def intersectionSize(a: Array[Int], b: Array[Int]): Int = {
  var size, ai, bi = 0
  while (ai != a.length && bi != b.length) {
    val av = a(ai)
    val bv = b(bi)
    size += (if (av == bv) 1 else 0)
    ai   += (if (av <= bv) 1 else 0)
    bi   += (if (av >= bv) 1 else 0)
  }
  size
}

Když bych to přepsal na generickou verzi, se signaturou

def intersectionSize[T](a: Array[T], b: Array[T]): Int

pole Array[T] stále budou poli příslušných primitivních typů. V tomto případě generický typ nezpůsobí, že obsah polí bude boxován do objektů, ale k přístupu do nich budou použité statické metody array_apply a array_length ze třídy ScalaRunTime, které mají efektivitě velice daleko.

Ale na tom teď ale příliš nezáleží, protože to stejně nebude fungovat, protože bych v těle metody požíval porovnání ==, <=, >= na objektech generického typu T. T může být cokoli a tedy nemůže garantovat, že na něm budou tyhle operace definovány. To se dá vyřešit implicitním parametrem, který obsahuje implementaci těchto operací pro daný typ. Jde o takzvanou typeclass.

def intersectionSize[T](a: Array[T], b: Array[T])(implicit num: Num[T]): Int

Num je něco jako Numeric ze standardní knihovny. Při zavolání metody bez posledního bloku patametrů bude automaticky doplněn kompilátorem. V těle metody se to použije následovně:

size += (if (num.eq (av, bv)) 1 else 0)
ai   += (if (num.lte(av, bv)) 1 else 0)
bi   += (if (num.gte(av, bv)) 1 else 0)

Tohle už je správně a kompilátor si přestane stěžovat. I když jsem vyřešil problém genericity, problém s rychlostí stále zůstává. Každý element pole je autoboxován, jako objekt předán metodám třídy Num, které je rozbalí a provedou na něm jednu instrukci užitečné práce.

I když i v tomto případě není všechno ztraceno a JIT může trochu pomoct – když profilování ukáže, že se metoda volá jen pro jeden typ a je tedy použitá jedna a ta samá instance Num, JIT může metody eq, lte a gte inlinovat, po inlinování je možné odstranit zbytečný autoboxing a dostat něco, co vypadá celkem efektivně. Problém je v tom, že jde o velice křehkou rovnováhu sil. Takhle to funguje, když je Num argument vždycky instancí jedné třídy a callsite pro eq, lte a gte jsou monomorfní. Když intersectionSize používám v mnoha kontextech a s mnoha typy, JIT to s inlinováním přestane mít lehké, najednou musí počítat se všemi variantami, musí do kódu vkládat rozskoky, použít inline cache nebo použít klasické volání virtuálních metod. Výsledná binárka začne trpět a efektivita začne klesat.

Ale na druhou stranu, když se JIT rozhodne celou metodu intersectionSize inlinovat a tedy zkopírovat její tělo na místo odkud je volána, všechno může být zase dobré. Inlinováním se vytvoří nový kontext a nové callsite metod eq, lte a gte, které najednou nejsou uvězněné v těle metody a tedy sdílené pro všechna možná použití intersectionSize.

A tady do hry vstupuje specializace.

Je třeba specializovat jak typeclass Num, tak metodu, která ji používá:

trait Num[@specialized(Int, Long, Float, Double) T] {
  def eq (a: T, b: T): Boolean
  def gt (a: T, b: T): Boolean
  def gte(a: T, b: T): Boolean = !gt(b, a)
  def lt (a: T, b: T): Boolean =  gt(b, a)
  def lte(a: T, b: T): Boolean = !gt(a, b)
}

def intersectionSize[@specialized(Int, Long, Float, Double) T](a: Array[T], b: Array[T])(implicit num: Num[T]): Int = ???

Signatura metody specializované pro čtyři primitivní typy1 má na délku kilometr, ale každé písmeno za to stojí. Tady se totiž dostávám k jádru pudla.

Specializace vygenerovala nezávislou metodu pro každý typ zvlášť. Verze pro Int bude vypadat nějak takhle:

def intersectionSize$mIc$sp(a: Array[Int], b: Array[Int])(implicit num: Num[Int]): Int = {
  var size, ai, bi = 0
  while (ai != a.length && bi != b.length) {
    val av = a(ai)
    val bv = b(bi)
    size += (if (num.eq$mIc$sp (av, bv)) 1 else 0)
    ai   += (if (num.lte$mIc$sp(av, bv)) 1 else 0)
    bi   += (if (num.gte$mIc$sp(av, bv)) 1 else 0)
  }
  size
}

Jak je vidět, místo eq se teď volá metoda eq$mIc$sp specializovaná pro Int. Ta je nejen efektivní tím, že jako argument chce nahý primitivní int, ale také tím, že na jejím místě se vždycky za každých okolností volá jedna jediná implementace pocházející z jedné typeclassy Num[Int]. Konkrétní callsite je tedy zaručeně monomorfní, JIT s ní může zacházet jako se statickou metodu a velice snadno inlinovat její tělo. A v tomto případě jde o stabilní a garantovanou optimalizaci, kterou nerozbije zavolání metody intersectionSize v naprosto nesouvisející části programu.

JVM v tomto případě odvede tak dobrou práci, že výsledná binárka, kterou vyprodukoval JIT, je k nerozeznání od binárky ručně specializované ver­ze.

Ale zatímco tohle skvěle funguje pro typeclassy, nemusí to vůbec platit pro funkce vyšších řádů. Typeclass má typicky pro každý typ jednu implementaci a v metodě specializované pro jeden typ se použije právě jedna typeclassa. Funkce vyšších řádů fungují naproti tomu většinou přijímají spoustu různých funkcí jako argument a specializace tedy negarantuje dobré inlinování, jen eliminuje zbytečnou režii autoboxingu.


Dále k tématu:

Pozn:

  1. Používám jen čtyři nejčastější typy, abych omezil množství tříd a velikost bytekódu, kterou specializace vyprodukuje. Tohle je jedna ze slabých stránek specializace, protože je třeba vygenerovat všechny kombinace všech typů a parametrů pro které je specializováno. Z tohoto důvodu bylo navržena alternativa – tzv. miniboxing (viz & viz).

Flattr this!

Posted in JVM, Scala, VM | Leave a comment

Jaccardovo tajemství – jak počítat podobnost množin pomalu, jak ji počítat rychle a jak při výpočtu podvádět

Jaccardův index podobnosti je jednoduchá funkce, která udává míru podobnosti mezi dvěma množinami. Je definována jako velikost průniku vydělená velikostí sjednocení dvou množin.

J(A, B) = |A ∩ B| / |A ∪ B|

Funkce je to jednoduchá. Otázka je, jak ji implementovat, aby běžela rychle. V následujících odstavcích se vydám na cestu za největší efektivitou za každou cenu. A když říkám za každou cenu, myslím tím, že se skutečně před ničím nezastavím.

Když půjde všechno podle plánu, cestou se možná dostaví jeden nebo dva momenty osvícení.


Naivní implementace ve Scale by mohla vypadat nějak takhle:

def jacc(a: Set[Int], b: Set[Int]): Double = {
  val is = a.intersection(b).size
  val us = a.union(b).size
  if (us == 0) 0 else is.toDouble / us
}

Jednoduchý kód, strašlivý výkon. Problém spočívá v tom, že je třeba vytvořit dvě množiny jen proto, abych zjistit jejich velikost. Velikost sjednocení není třeba vůbec počítat, protože se dá jednoduše odvodit z principu inkluze a exkluze.

def jacc(a: Set[Int], b: Set[Int]): Double = {
  val is = a.intersection(b).size
  val us = a.size + b.size - is
  if (us == 0) 0 else is.toDouble / us
}

To je lepší, ale pořád je třeba vytvořit jednu množinu se všemi alokacemi a interními režiemi, které to obnáší. Logickým krokem je nic nealokovat a v jedné iteraci spočítat velikost průniku.

def jacc(a: Set[Int], b: Set[Int]): Double = {
  val small = (if (a.size < b.size) a else b
  val big   = (if (b.size < a.size) a else b
  val is = small.count { el => big.contains(el) }
  val us = a.size + b.size - is
  if (us == 0) 0 else is.toDouble / us
}

To je lepší, ale zdaleka ne ideální. Problém může představovat uspořádání dat a layout paměti. V případě JVM má generický HashSet celkem velkou režii a mizernou lokalitu3. Set[Int] neuchovává primitivní čtyřbajtové inty, ale reference na boxované Integer objekty. Kombinace ref+box může zabírat klidně 32 bajtů na 64-bitovém systému a musí udělat jednu dereferenci pointeru.

Tomu se dá vyhnout používáním jazyka/runtime, který dělá specializaci typů (reifikovaná generikav C# nebo C++ šablony) nebo kolekcemi specializovanými pro primitivní typy. Na JVM je k dispozici několik takových knihoven a jedna z nejlepších je Koloboke.

import net.openhft.koloboke.collect.set.hash.HashIntSet

def jacc(a: HashIntSet, b: HashIntSet): Double = {
  val small = (if (a.size < b.size) a else b
  val big   = (if (b.size < a.size) a else b

  var is = 0
  val cur = small.cursor
  while (cur.moveNext()) {
    if (big.contains(cur.elem)) {
      is += 1
    }
  }

  val us = a.size + b.size - is
  if (us == 0) 0 else is.toDouble / us
}

Kód je o něco delší, ale na druhou stranu může být mnohem rychlejší. Data jsou uložena v plochých polích a nepotřebují nahánět pointery.

Všechny předchozí změny představovaly pokrok v mezích zákona, pozvolné zlepšování jednoho řešení. Nešlo však o žádné radikální skoky vpřed. Těch můžu dosáhnout jedině, když to vezmu z druhého konce a začnu přemýšlet o tom, co je skutečně potřeba. V tomto případě mě zajímá jen Jaccardova podobnost, nic jiného. Všechny reprezentace množin, které jsem doteď používal byly založeny na hash tabulkách a nabízely tedy mnoho jiné funkcionality. Uměly například v konstantním čase zjistit, zdali se daný element nachází v množině. Já však potřebuji jen rychlý výpočet velikosti průniku. Když budu reprezentovat množinu seřazeným polem, dá se právě tahle veličina spočítat velice efektivně.

def jacc(a: Array[Int], b: Array[Int]): Double = {
  def intersectionSize(a, b) = {
    var ai, bi, size = 0
    while (ai < a.length && bi < b.length) {
      val av = a(ai)
      val bv = b(bi)
      size += (if (av == bv) 1 else 0)
      ai   += (if (av <= bv) 1 else 0)
      bi   += (if (av >= bv) 1 else 0)
    }
    size
  }

  val is = intersectionSize(a, b)
  val us = a.length + b.length - is
  if (us == 0) 0 else is.toDouble / us
}

Stačí velice jednoduchá smyčka, která udělá lineární průchod oběma poli a nepotřebuje dělat žádné hledání v interních hash tabulkách. Tři řádky ve tvaru x += (if (cond) 1 else 0) kompilátoru/JITu silně naznačují, aby místo podmíněných skoků použil cmov instrukce1. To odstraní potenciální nepředvídatelný skok v těle smyčky, který by všechno mohl výrazně zpomalit.

Tento kód je nejen velice rychlý, ale také překvapivě jednoduchý. Funguje tak, že hledá shodné prvky v poli. Když je najde, inkrementuje proměnnou size a i oba indexy. V ostatních případech inkrementuje index, který ukazuje na menší prvek. Jde o algoritmus velice podobný merge sortu.

Tělo smyčky obsahuje pouhých ±20 instrukcí a nepůjde zrychlit redukcí počtu operací v jedné iteraci, ale zmenšením počtu iterací.

Jedním způsobem jak toho dosáhnout, je dívat se n míst dopředu4 s tím, že když najdu element menší než ten hledaný, můžu přeskočit n míst a tím pádem i n iterací. Tělo smyčky se trochu zkomplikuje, výsledek však často je o pár desítek procent rychlejší a jen málokdy dojde ke zpomalení. Pokud je skok malý, kód přeskakuje jen malé úseky a neušetří příliš iterací. Na druhou stranu, když je skok velký, kód nemůže nic přeskočit a iteruje jako normální verze. Je potřeba najít nějaké přijatelné optimum.

while (ai < alen && bi < blen) {
  val av = a(ai)
  val bv = b(bi)
  val _ai = ai
  val _bi = bi
  size += (if (av == bv) 1 else 0)
  ai   += (if (av <= bv) (if (a(_ai+skip) < bv) skip else 1) else 0)
  bi   += (if (av >= bv) (if (b(_bi+skip) < av) skip else 1) else 0)
}

Pokud bych chtěl jít ještě dál, mohl bych pole předzpracovat a za každý element vložit předpočítanou bitmapu obsahující osm čtyřbitových čísel, které udávají, jak daleko může jeden index poskočit v závislosti na rozdílu porovnávaných hodnot. Za zmínku stojí, že kód obsahuje jen rychlé bitové operace a nepotřebuje žádný podmíněný extra skok. Je třeba jen něco přes 10 instrukcí navíc.

def intersectionSizeWithEmbeddedSkiplists(a: Array[Int], b: Array[Int]): Int = {
  var size, ai, bi = 0
  while (ai != a.length && bi != b.length) {
    val av = a(ai)
    val bv = b(bi)

    val s  = (if (av < bv) av else bv)
    val si = (if (av < bv) ai else bi)

    val d = java.lang.Math.abs(av - bv)
    val bits = 32 - Long.numberOfLeadingZeros(d)
    val slot = bits / 4

    val slotval = (s(si+1) >>> (slot * 4)) & ((1 << 4) - 1)
    val skip = slotval << (slot - 1)

    size += (if (av == bv) 1 else 0)
    ai   += (if (av <= bv) skip else 0)
    bi   += (if (av >= bv) skip else 0)
  }
  size
}

O kolik nebo jestli vůbec to zrychlí výsledek jsem ale netestoval, protože mi došla kuráž, když jsem začal přemýšlet jak napsat funkci, která vypočítá možné skoky.

Ale to stále není všechno. Na začátku jsem psal za každou cenu a pořád to myslím vážně.

Když zajdu do extrému, je možné implementovat Jaccarda pomocí AVX2 SIMD instrukcí2, které prohledávají vektor osmi hodnot paralelně. Jak takováto hrůza vypadá se můžete přesvědčit na vlastní oči v tomto gistu. Vektorizované řešení je v nejhorším případě, kdy nikdy není možné přeskočit několik iterací, 2× pomalejší než přímočará implementace (protože potřebuje vykonat víc instrukcí a každá iterace dělá víc práce), ale v nejlepším případě, kdy může často přeskakovat velký kus vstupního pole, až 4× rychlejší.

Pro další zrychlení je možné na začátku kontrolovat jestli je začátek jednoho pole větší než konec toho druhého. V takovém případě je jasné, že množiny nemají žádný společný prvek a Jaccardova podobnost bude vždycky 0. Ke stejnému účelu se dá použít bitmapa (např. 64 bitů) fungující jako maličký Bloom filtr. Když udělám logický and dvou bitmap a dostanu 0 (tj. dvě mapy nemají žádné společné bity), je jasné, že dvě množiny, ze kterých byly tyto bitmapy odvozeny nemají žádné společné prvky a Jaccardova podobnost bude opět nulová.

if (b(0) < a(a.length-1) ||
    a(0) < b(b.length-1) ||
    (aBitmap & bBitmap) == 0) {
  return 0.0
}

To ale stále není všechno. Když mě nezajímá přesná Jaccardova podobnost, ale vystačím si s odhadem, můžu použít MinHash. Ten produkuje jen přibližné výsledky5, ale může být výrazně rychlejší, protože nepočítá podobnost mezi celými množinami, ale jen jejich otisky, které mají fixní velikost.

MinHash a mnoho dalších skečů jsem implementoval v knihovně sketches. S ní se dá spočítat odhad podobnosti velice jednoduše:

val mh = atrox.sketches.MinHash(sets, 128)
mh.estimateSimilarity(i, j)

Když ani tohle nestačí, pomůže už jen locality sensitive hashing (LSH) (viz Mining of Massive Datasets, kapitola 3.3 a 3.4)6. LSH může výpočet podobnosti výrazně zrychlit, protože omezuje hledání jen na kandidáty, které jsou s velkou pravděpodobností podobné a zcela přeskočí ty, které jsou (opět s velkou pravděpodobností) nepodobné.

A knihovna sketches také obsahuje implementaci LSH.

val mh = atrox.sketches.MinHash(sets, 128)
val lsh = atrox.sketches.LSH(mh, bands = 32)
lsh.similarItems(i, similarityThreshold)

S vhodně nastavenou LSH je možné úlohu, která by trvala 24 hodin hrubou silou, spočítat za 24 vteřin s celkem rozumnou ztrátou přesnosti.

Myslím, že rychleji než tohle už to není možné.


Dále k tématu:


  1. Technicky vzato kompilátor může tento řádek přeložit na trojici instrukcí cmp, setX a add a ani nepotřebuje cmov.
  2. Síla SIMD operací je vidět v Někdy je nejchytřejší nedělat nic chytrého
  3. V případě neměnných kolekcí je to ještě horší, protože jsou interně implementované jako hash array mapped trie a to s sebou přináší další úrovně pointerů a referencí.
  4. viz Introduction to information retrieval, kapitola 2.3: Faster posting list intersection via skip pointers
  5. Někoho tady může napadnout, že když mi stačí odhady, můžu použít HyperLogLog k odhadnutí velikosti sjednocení a pak dopočítat průnik, před princip inkluze a exkluze. To funguje, ale není to příliš přesné, protože chyba je relativní vzhledem k velikosti sjednocení a nikoli k průniku, který může být mnohem menší.
  6. Když mluvím o LSH, měl bych se také zmínit, že existuje alternativní přístup hledání nejbližších sousedů, který není postavený na hashování, ale na binárních stromech. Přibližně to odpovídá rozdílu mezi hash tabulkami a binárními vyhledávacími stromy – hashování nabízí O(1) hledání, stromy hledají v čase O(log n), ale jejich obsah je seřazený. To v případě hledání nejbližších sousedů znamená, že si můžu říct o body, které jsou trochu dál, což LSH nedokáže.

Flattr this!

Posted in Algo, DS, Scala | 3 Comments

limit/offset stránkování nemusí být pomalé

Stará poučka říká, že implementace stránkování pomocí SQL dotazů s limit/offset klauzulemi je pomalá.

Když tuto zásadu nedávno zopakoval Filip Procházka na nedávné Poslední Sobotě, napadlo mě, že to nemusí být nutně pravda. Stačilo by, aby každý uzel interního B-stromu obsahoval informaci jak je velký jeho podstrom a limit/offset stránkování by mohlo být stejně rychlé jako stránkování pomocí jiných metod.

Problém spočívá v tom, že limit/offset stránkování obvykle neumí najít bod, kde stránka začíná. Databáze proto musí číst index, podle kterého se výsledky řadí, od začátku a počítat na kolik záznamů narazila. Když přeskočí offset položek, přečte limit záznamů a ty vrátí. Tohle je očividně lineární operace a když mám velkou databázi a v dotazu uvedu limit 10 offset 100000000 mám o zábavu postaráno, protože databáze musí proskenovat sto milionů řádků, než začne dělat něco užitečného. Když nám v tabulce jen pár tisíc řádků, tohle nepředstavuje velký problém. Ale když mám málo dat, nic nepředstavuje problém.

Následující obrázek ukazuje příklad, jak může vypadat kus B-stromu indexu se 150 záznamy. Pokud chci najít stránku limit 3 offset 147, musím projít všechno, protože nevím že začíná hodnotou 1257. Znám jen offset.

Místo toho se silně doporučuje tzv. seek metoda, která nepřeskakuje záznamy od začátku tabulky, ale v indexu přímo najde místo, kde stránka začíná (nebo předchozí končí) a od toho místa přečte počet záznamů uvedených v klauzuli limit. Velice jednoduché a efektivní. Když můžu použít index je nalezení záznamu velice rychlé (běží v logaritmickém čase) a protože mám index1, jsou záznamy seřazeny a tedy všechny potřebné záznamy budou vedle sebe.

Seek metoda má drobný problém v tom, že s ní nemůžu skočit na libovolnou stránku, ale musím se na ní postupně dostat. To ale nevadí, protože postupné stránkování dává větší smysl než skok na libovolnou stránku. Navíc je tato metoda stabilní a nerozhodí ji nové položky přidané na začátek tabulky.

Rozdíl mezi seek metodou a offset metodou je jen v tom, že jedna umí najít přesné místo, kde stránka začíná a druhá nikoli a proto musí skenovat všechno od začátku. Otázka zní: proč ho neumí najít?

Databáze typicky pracují s bloky dat, které mají pevně danou velikost a jeden uzel B-stromu, ať už kořen, interní nodus nebo list, zabírají jeden blok. Kdyby šlo o kompletní, vyvážený strom, kde každý záznam má stejnou délku, mohl bych najít každý záznam podle offsetu velice jednoduše. Situace ale není tak jednoduchá, protože záznamy mají proměnlivou délku a mechanismus vyvažování B-stromu zaručuje, že uzly budou z části prázdné. Uzly můžou být rozdělené nebo sloučené, když jejich velikosti přesáhly určité meze.

Tady se dostávám k jádru věci: Jak se zbavit nutnosti skenovat všechno od začátku? Řešení je triviální: Stačí, když do každého uzlu přidám informaci o velikosti celého podstromu, jak je naznačeno v následujícím schématu. Jde o stejný strom, jen každý vnitřní uzel nese jednu anotaci navíc.

Do podstromu musím sestoupit jen pokud je z jeho velikosti jasné, že se záznam, který potřebuji, nachází právě v něm, jinak ho přeskočím. Když bych položil dotaz s limit 3 offset 147 je jasné, že do prvního podstromu obsahujícího 18 záznamů vůbec nemusím vstoupit a celý ho přeskočím. Po tomhle kroku mi zbývá skočit přes 129 záznamů. Jestliže další podstrom obsahuje méně záznamů, přeskočím ho, pokud má více, vlezu do něj a celý postup budu opakovat o úroveň níž. S těmito změnami stránkování běží v logaritmickém čase místo lineárního, tedy stejně jako seek metoda. A dokonce to funguje i když mám v dotazu where klauzule, které pokrývají prefix indexu použitého k řazení – stejně jako seek metoda.

Jeden implementační problém tohoto přístupu představuje přidávání a mazání položek. Změna v listech se promítne do všech uzlů na cestě ke kořeni a to může vést k write amplification. To ale není nic, co by se nedalo vyřešit líným způsobem, kdy se změny zapisují do logu a jsou aplikovány na B-strom strom až později en masse. Ostatně relační databáze přesně tohle dělají už třicet let.

Aktualizace:

Když jsem začal přemýšlet, proč se tohle nepoužívá, napadlo mě vysvětlení, které je tak očividné, že se nelze divit, že jsem si ho neuvědomil dřív. Pod svícnem skutečně bývá největší tma.

Jde o to, že abych mohl dělat rychlé limit/offset stránkování popsané výše, potřebuji index. A když už nám index, můžu jednoduše použít seek metodu. Takže asi tak.


Dále k tématu:

  1. Tady předpokládám index postavený na B-stromu. Existují i jiné způsoby indexování, které data neřadí, jako například hashování. To teď neberu v úvahu, protože téměř všechny RDBMS standardně používají nějakou verzi B-stromu.

Flattr this!

Posted in DB, DS | 2 Comments