YOLO tree
Stará internetová moudrost říká "you only live once". Život je příliš krátký na jistoty a někdy to prostě musíme risknout. Jako třeba během konstrukce binárního vyhledávacího stromu (BST).
BST je super věc, všichni ho známe, milujeme a napíšeme si jeden nebo dva ještě před snídaní. Ale i přesto má určité vlastnosti, které, i když se zdají naprosto samozřejmé, nemusí zrovna být to, co by člověk chtěl. Konstrukce BST je striktně sekvenční a nedá se (přímo1 ) naivně paralelizovat. To znamená, že pokud chci nejmenší element nějaké sekvence, musím nejdřív postavit celý BST v čase O(n log(n)) a teprve potom z něj vyhmátnout minimum. V tom okamžiku je ale už pozdě, protože jsem udělal všechnu práci nutnou k seřazení sekvence. V ideálním případě bych udělal jen nezbytně nutné množství práce a konstrukci zbytku bych líně odložil na později.
Naproti tomu je quicksort (QS) nebo radix sort (RS) představuje potenciálně líné algoritmy. Když chci n-tý nejmenší prvek, tak si ho v jednoduše quickselectnu a cestou udělám lineární množství práce vstříc plně seřazenému stupu. Stejně tak jsou všechny QS/RS naivně paralelizovatelé. Jako všechny algoritmy, které vstup rekurzivně rozdělí a pak jednotlivé části nezávisle zpracovávají, se u nich dá triviálně dosáhnout logaritmického paralelního zrychlení.
BST se od QS/RS odlišuje tím, že výsledkem není jen seřazená sekvence, ale dynamická datová struktura, do které můžu přidávat nebo z ní odebírat prvky.
Když chci to nejlepší z obou světů, musím na to jít jako Abe a Aaron z Primeru:
They took from their surroundings what was needed and made of it something more.
Reifikací quicksortu můžu dostat BST, který je dynamický a vyvážený a jeho konstrukce je líná a naivně paralelizovatelná.
Jako při každé reifikaci začnu s nehmotným procesem a zhmotním ho do datové struktury. Když v QS vybírám pivot, reifikuji ho jako uzel stromu s tím, že všechny menší prvky přijdou doleva a ty větší doprava. Takhle postupuji rekurzivně k listům a, když si to moje srdce žádá, strom průběžně vyvažuji.
Strom je tvořen dvěma druhy uzlů - nerealizovanými a realizovanými. Ty nerealizované jsou jednoduché seznamy prvků, realizované uzly jsou pak tvořeny pivotem a dvěma podstromy.
Začnu s nerealizovaným seznamem:
[6, 8, 3, 1, 4, 2, 9, 5, 0, 7]
Vyberu pivot, udělám z něj jeden realizovaný uzel, rozdělím seznam na dva nerealizované seznamy a ty strčím jako podstromy. V tomto případě výběr probíhá v Hoarově stylu první dobrá, ale je možné použít i komplikovanější metody jako best-of-3 nebo quasi best-of-9.
(6) / \ [3, 1, 4, 2, 5, 0] [8, 9, 7]
(Nerealizované seznamy uvádím vždy v hranatých závorkách. Do kulatých píšu pivot realizovaného uzlu.)
Takhle můžu pokračovat, dokud budu chtít. Můžu třeba realizovat jen cestu k nejmenšímu prvku v průměrném lineárním čase:
(6) / \ (3) [8, 9, 7] / \ (1) [4, 5] / \ (0) [2]
Jak je vidět, velká část stromu vůbec nebyla vyhodnocena.
Stejně tak můžu strom postavit najednou (podstromy můžu potenciálně stavět paralelně) rekurzivní aplikací tohoto pravidla.
Tato QS inspirovaná konstrukce je úzce spjatá s BST. Knuth o tom psal v The Art of Computer Programming: Když jako pivot používám vždycky první element, je výsledný strom stejný jako když stavím binární strom bez vyvažování. Ve výsledku provedu stejná porovnání, jen v jiném pořadí.
Pokud strom nesplňuje moje požadavky na vyváženost, můžu ho průběžně balancovat.
V mém případě může být levý podstrom příliš velký:
(6) / \ [3, 1, 4, 2, 5, 0] [8, 9, 7]
Rotace si v tomto případě vynutí částečnou realizaci podstromu.
(6) / \ (3) [8, 9, 7] / \ [1, 0, 2] (4) \ [5]
Po rotaci to bude vypadat takhle:
(4) / \ (3) (6) / / \ [1, 0, 2] [5] [8, 9, 7]
Musel jsem realizovat jednu úroveň stromu. Tento proces může pokračovat rekurzivně až k listům v průměrném lineárním čase (a quicksortovské O(n2) v nejhorším případě).
K vyvažování se nehodí techniky z red-black nebo AVL stromů. Ty potřebují označit každý uzel (buď barvou nebo hloubkou) a to nutně vede k realizaci celého podstromu.
Když jsem o tom přemýšlel, nějakou dobu jsem nevěděl, jak tenhle problém vyřešit. Pak jsem ale v paperu Implementing sets efficiently in a functional language narazil na size balanced trees - tedy stromy vyvažované podle velikosti. Velikost podstromu je lokální vlastnost, kterou znám nehledě na to, zdali je podstrom realizovaný nebo ne. Balancování začne jen, když je jeden podstrom k-krát větší než ten druhý.
Vyvažování ale v principu nemusí být nutné, protože když vybírám pivot náhodně, v průměrném případě je výsledný strom vybalancovaný s průměrnou hloubkou 1.386 log(n). Takže místo balancování bych mohl jen randomizovat pořadí vstupu.
Quicksort styl konstrukce vede k lenosti. Teď jak na dynamické vlastnosti? Chci mít možnost do stromu přidávat a odebírat prvky a zachovat při tom jeho lenost a asymptoty.
Vkládání je triviální. Místo toho, aby byl uzel buď realizovaný nebo ne, může být realizovaný se seznam nerealizovaných změn.
Když například do tohohle stromu
(6) / \ (3) [8, 9, 7] / \ (1) [4, 5] / \ (0) [2]
vložím [ 1.47 4.7 47 ]
, dostanu
(6)-[1.47, 4.7, 47] / \ (3) [8, 9, 7] / \ (1) [4, 5] / \ (0) [2]
Když budu opět chtít získat minimum, všechny nerealizované seznamy, na které narazím cestou, zrealizuji:
(6) / \ (3) [8, 9, 7, 47] / \ (1) [4, 5, 4.7] / \ (0) [2, 1.47]
V tomto případě jsem jen přidával na konec nerealizovaných seznamů.
Mazání můžu vyřešit dvěma způsoby. Buď striktně nebo líně. Striktní varianta najde mazaný prvek ve stromu a hned ho odstraní. Cestou nutně realizuje všechny uzly (to by mělo být v nejhorším případě O(n) práce). Líná varianta do nerealizovaného seznamu jen přidá tombstone. Když se tento objekt eventuálně dostane do listu, odstaní daný element. Tohle řešení je líné, ale zase může vést k hromadění tombstone objektů v nikdy nerealizovaných částech stromu. To se dá vyřešit tak, že každý podstrom nejen sleduje svou velikost, ale také počet náhrobků.
A to by bylo všechno.
Do tohoto bodu jsem se dostal jenom tak, že jsem přemýšlel, kam až se dá výchozí myšlenka dotáhnout. Pak jsem si ale najednou uvědomil, že jsem už něco podobného viděl.
Fraktální stromy, používané v TokuDB, mají velice podobnou strukturu. Druhá verze fraktálních stromů jsou B-stromy, kde je ke každému vnitřnímu uzlu připnutý buffer akumulující změny. Ty jsou eventuálně (např. když se buffer naplní), propagovány o úroveň níž do bufferů v příslušných uzlech nebo přímo do listů s datovými položkami.
Fraktální stromy jsou podobné mým YOLO stromům, i když k této podobě došly z jiného úhlu. TokuDB se snažilo omezit náhodné IO operace a nahradit je sekvenčním zápisem. Když se buffer naplní, jeho čtení a zápis do nižších úrovní je striktně sekvenční. Já jsem se v případě YOLO stromů zajímal jen o líné zpracování a sledoval ho až do extrému. V obou případech to došlo k podobným závěrům.
Pokud jsou tedy YOLO/fraktal tree reifikacemi quicksortu (resp. multi-way quicksortu), musí existovat podobná konstrukce, která reifikuje merge sort. Ta skutečně existuje a co víc - používá se ve světě databází.
Jde o LSMT - Log Structured Merge Trees v kombinaci s tzv. fractional cascasing - reifikovaný merge sort, který je líný a má ty správné asymptoty jako například O(log(n)) hledání.
Shodou náhod na LSMT byla založena první verze fraktálních stromů z TokuDB.
Dále k tématu:
- Jak řadit v lineárním čase, křísit mrtvé a dosáhnout osvícení
- Jak rychle řadit a šetřit čas
- Mergeselect
- Střeva databází
- Three Beautiful Quicksorts
- Můžu paralelně postavit několik BST a pak je naivně sloučit s maximálně logaritmickým zrychlením.