Persistentní datové struktury

Funkcionální programování je horké téma posledních let. Co to je, proč je to dobré, co to přináší a proč o tom všichni mluví právě teď? Odpovědi na tyto otázky jsou následující: Programováníreferenčně transparentními funkcemi6, zlepšuje to možnosti kompozice, porozumění programům, což v ideálním případě vede k lepším programům s menším počtem chyb.

Jedním z hlavních pilířů funkcionálního programování je fakt, že všechny datové struktury jsou neměnné. Když něco jednou vytvořím, už to nikdy nemůžu modifikovat. Jediný způsob, jak něco změnit, je vytvořit novou verzi struktury, která v sobě požadovanou změnu zahrnuje .

„Ale to bude příliš drahá operace…“ může vás těď napadat.

Není to tak docela pravda. Je fakt, že kdyby bylo nutné při každé změně udělat kompletní kopii celé datové struktury, funkcionální programování by, i přes všechny teoretické i praktické výhody, nestálo za tu námahu. Program by vždycky běžel příliš pomalu. Naštěstí odvážní lidé z FP gangů za poslední polovinu století přišli na mnoho způsobů, jak implementovat datové typy, které jsou jednak neměnné, okážou rychle vytvářet změněné verze, a všechny operace nad nimi mají asymptotickou složitost, která je velice blízká efemérním variantám.

Hlavní myšlenka těchto takzvaných persistentních datových struktur je jednoduchá: Sdílet co největí množství struktury s předchozí verzí a kopírovat jen nejmenší možnou část obsahující změnu (toto je také označováno jako structural sharing). Persistentní v tomto kontextu neznamená uložený na disku, ale trvalý, protože všechny verze dané struktury přežijí.

Jako příklad uvedu strom A, jehož poslední list změním z 4 na αω a výsledkem bude strom B.

Jak je vidět oba stromy sdílí většinu dat (modré uzly), zkopírována byla jen cesta od změněného listu ke kořeni stromu (takzvaná path copy8). Operace tedy nemá cenu O(n), ale jen O(log(n)) a to je něco s čím se už dá reálně pracovat. Vyvážený strom s 232 elementy (±4 miliardy) má hloubku 31 a je tedy potřeba zkopírovat jen 31 uzlů, což sice není konstantní množství práce, ale na druhou stranu ani není nijak gigantické.

Princip je to krásně jednoduchý, jak na něm však postavit efektivní persistentní datovou strukturu, která má ty správné asymptoty, je otázka na dlouhé zimní večery (například amortizace je v persitentním prostředí poněkud zrádná). Ale když se to povede, otevírá se před námi země nečekaných možností: S persistentními strukturami mám k dispozici všechny verze – update nikdy nezničí starý stav, vytvoří nový a já můžu bez starosti přistupovat k oběma, sdílet je, porovnávat je a číst a odvozovat z nich nové verze vrásek i ve vícevláknových programech. Protože data jsou po vytvoření zafixována a zmrazena v čase, nemusím se ničeho bát, nemusím zamykat, koordinovat nebo mezi sebou synchronizovat vlákna. Neměnnou datovou strukturu je vždycky bezpečné číst, nemusím se bát, že zatímco jsem přečetl jednu část, někdo jiný mi pod rukama změnil zbytek struktury a já teď nemám konzistentní stav. Neměnná struktura se chová jako hodnota, jako stabilní fakt, jako věc, o které se můžeme bavit a nehrozí nám, že na ní každý má jiný pohled.

Že to je všeobecně dobrý nápad ukazuje třeba kniha Effective Java1, kde Josh Bloch doporučuje i v Javě používat neměnné třídy, jak to je jen možné, právě proto, že to zjednoduší uvažování o kódu a odstraní jednu celou kategorii starostí. Když to není možné, tak radí přistoupit k defenzivnímu kopírování (které však není dokonalým řešením, protože jednak mi během kopírování někdo jiný může zdrojový objekt změnit pod rukama2 a druhak přináší určitou (a často zbytečkou) režii).

Intuitivně je jasné, že vytváření modifikovaných verzí persistentních DS je dražší než in-place modifikace běžných DS.5 Při každé změně musím něco nového alokovat, někdy jeden objekt (jako v případě Cons-Nil seznamů) jindy log<sub>b</sub>(n) objektů (jako v případě stromů, pro nějaký základ logaritmu b). I když je alokace většinou levná, bouře alokací se přesto může podepsat na výkonu a v nejhorším případě může způsobit, že výsledek je limitován propustností paměti. Existují určité techniky jak se alokací zbavit, nebo je aspoň částečně omezit, jako například escape analysis nebo deforestation, ale ani ty nejsou dokonalé.3

Ve funkcionálním prostředí se navíc prakticky nedá obejít bez garbage collectoru, který sleduje všechny reference a jakmile nějaká verze persistentní DS není používána, odstraní data, která jí patří a nejsou sdílena s ostatními živými verzemi. Díky GC je implementace persistentních DS velice jednoduchá.

Skoro4 všechny funkcionální struktury jsou implementované pomocí stromů právě proto, že stromy umožňují snadné a levné kopírování cest. Nejde jen o zjevné stromy jako Red-Black a ALV, ale také o rafinované vnitřní detaily komplikovaných struktur, které se chovají jako mapy, množiny, pole, fronty nebo oboustranné fronty.

Nechci tady však vysvětlovat, jak jsou různé persistentní datové struktury implementované, jak vypadají a jaké mají charakteristiky. Jde o příliš rozsáhlé téma, o němž se dá najít spousta dobrých zdrojů, které všechno vysvětlí lépe, než bych já kdy dovedl. Místo toho sem jen vysypu seznam odkazů s drobnými anotacemi a půjdu od toho.


Skvělá přednáška, ve které Daniel Spiewak vysvětlí implementaci několika základních persistetních DS (seznamy, fronty, deque, red-black stromy, vektory).

Chris Okasaki na prostoru dvou set stran této legendární knihy vysvětlí mnohem víc, než jste kdy chtěli vědět o funkcionálních datových strukturách – jak je napsat v čistě funkcionálním jazyku (autor používá ML, ale v dodatcích jsou ukázky přepsané do Haskellu) a jak analyzovat jejich asymptotickou složitost. Každá kapitola vždy přinese něco nového a nečekaného, co člověka naprosto ohromí (tedy aspoň mě to ohromilo): Persistence, líné vyhodnocování, amortizace, amortizace v persistetním prostředí, eliminace amortizace, lazy rebuilding, datové struktury postavené na různých numerických reprezentacích, bootstraping a další.

Na internetu se dá najít Okasakiho dizertační práce, z níž posléze malými úpravami vznikla samotná kniha. Autor deset let od prvního vydání napsal malou rekapitulaci.

Tato přednáška z kurzu Advanced data structures vyučovaného na MIT vysvětlí, že s persistentními datovými strukturami je to o něco komplikovanější, protože ty funkcionální nejsou jediné, které jsou. Kromě toho ještě existují partially (částečně), fully (plně) a confluent (souběžně?) persistentní datové struktury, které připouštějí možnost modifikovat existující data, ale stále takovým způsobem, že jsou všechny předchozí verze zachovány a můžu k nim přistupovat a číst je. Částečně persistentní DS dovolují modifikovat jen nejaktuálnější ver­zi.

Tyto dva články vysvětlí jak interně funguje Vector – stěžejní lineární datovou strukturu z Clojure a ze Scaly. Vektor je velice široký strom, založený na práci Phila Bagwella7 (Fast And Space Efficient Trie Searches a Ideal Hash Trees), do jeho současné podoby ho převedl Rich Hickey, ale poprvé ho implementoval Daniel Spiewak (pokud se nepletu).9

Bagwellův paper popisující Relaxed Radix Balanced Trees – vylepšenou verzi vektoru, která dovoluje spojit dva RRB-vektory v logaritmickém čase (namísto lineárního, jak je běžné pro prostý Vector). RRB tak lookup, append, update pracující v efektivně konstantním čase, rozšíří o další efektivní operaci, bohužel za cenu drobného (konstantního) zpomalení všech ostatních operací. Lidé ze Scala komunity plánovali, že by zachovali současný vektor a RRB stromy by se používaly jen, když dojde ke spojení dvou vektorů nebo RRB stromů.

Následuje několik přednášek od Edwarda Kmetta. Jde o poněkud hutnější materiál, ale pokud jste se prokousali skrz Okasakiho, nemělo by být nemožné se zakousnout i do tohoto.


Neměnnost dat po jejich vytvoření značně zjednodušuje vícevláknové programování a synchronizaci (protože žádní není potřeba) a proto se těchto struktur využívá i v oblastech, kde by to člověk nečekal: V datech na disku.

CouchDB – používá sdílení struktury indexů na disku (data kopíruje celá). Když je nějaký dokument změněn, je na disk zapsána nová cesta ke kořeni dokumentu, která odkazuje na nezměněné části. Stará verze je pak nějakou dobu stále dostupná. Pokud se nemýlím, nejde však o hlavní myšlenku této databáze, ale jen o techniku, jak zrychlit zápisy, umožnit dočasné konzistentní okno a zlepšit paralelismus. Staré verze struktur jsou eventuálně smazány garbage collectorem.

Fulltext search engine Lucene, který tvoří základ pro Elastic a Solr během indexace také používá immutable přístup. Když zaindexuje nějaké dokumenty, Lucene vytvoří segment indexu, který je po vytvoření neměnný a ostatní procesy ho můžou použít k hledání. Na pozadí jsou tyto segmenty logaritmicky slučovány do větších segmentů (na principu Log-structured merge-tree, jako to třeba dělá LevelDB viz: Dominic Tarr: The database of the future: leveldb, Inside HyperLevelDB a Concurrency Improvements in HyperLevelDB), a i když nejsou persistentní, jsou stále neměnné. Jediné, co se mění, je seznam určující, které segmenty jsou dostupné a aktuální, a které už nikdo nepoužívá a budou smazány.

Analytická databáze Druid.io také vytváří neměnné (ale ne persistentní) segmenty, které poté distribuuje na dotazovací servery. O Druid.io dopodrobna píše Lukáš Havrlant: Druid.io: distribuovaná immutable databáze pro analytické výpočty, Architektura Druid.io a Jak Druid.io agreguje data.

Databáze Datomic je na myšlence neměnnosti a persistence postavená. To ji spolu s modelem subjekt-predikát-objekt-(transakce) ji umožňuje ukládat všechny verze všech faktů a efektivně tak pracovat s časem. Neměnnost vede k distribuovaným uzlům, které data jen čtou, a striktní požadavky na ACID pak mají za následek, že všechny transakce putují přes jeden uzel, tzv. trasactor. Více informací viz:

Bw-stromy, popsané v The Bw-Tree: A B-tree for New Hardware Platforms, také používají částečně neměnná data. V tomto případě proto, že je to ideální způsob, jak dosáhnout dobrého výkonu na mnohajádrových procesorech. Bw-strom je variantou B-stromu, která změny zaznamenává jako seznam delt. Když delta seznam dosáhne určité délky, dojde k vytvoření aktualizovaného uzlu Bw-stromu, který v sobě obsahuje všechny změny. Jediné, co se (atomicky) změní je pointer, který začne ukazovat na nový začátek delta seznamu. Protože delta nepřepisuje sdílená data uzlu, nedochází k invalidaci cache ostatních jader a eliminuje se tak množství zpráv cache coherency protokolu, což omezí nákladnou implicitní komunikaci mezi jádry procesoru a vede v lepšímu výkonu. K podobným závěrům došli i autoři Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures a Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores.

Persistentní datová struktura také leží v srdci rychlé a paralelní fronty SnapQueue, která dokáže rychle dělat snapshoty v čase a spojování dvou front. Má to však jeden háček – persistentní DS (v tomto případě Conc-Tree) není použita přímo, ale slouží jako kostra pro pole malých jednorázových front, které jsou pochopitelně měnitelné. SnapQueue přímo manipuluje pouze s první a poslední frontou (z první bere, do poslední ukládá, když je první prázdná, vytáhne si další, když je poslední plná, vloží ji do kostry a vytvoří další). Více detailů v SnapQueue: Lock-Free Queue with Constant Time Snapshots a Conc-Trees for Functional and Parallel Programming.

Persistentní struktury jsou také použity v Gitu. Btrfs a další systémy souborů, které interně používají Copy on Write B-stromy, udržují dočasnou formu persistence. Pokud jsou založené na append-only logu, musí řešit garbage collection a kompakci dat tím, že přesunou data z několika téměř prázdných stránek do jedné plné. Jde o nechvalně známý problém, protože vede k tzv. write amplification a může způsobit, že disk nebude stíhat uvolňovat stránky. Více v Log-structured file systems: There's one in every SSD a Stratified B-trees and versioning dictionaries.


Dále k tématu:


Pozn:

  1. Možná se za nějakou dobu dočkáme nové edice Effective Java aktualizované pro Javu 8 viz
  2. Technicky vzato na JVM není bez synchronizace bezpečné kopírovat ani long nebo double. Podle specifikace 64bitové primitivní typy nejsou atomické a zatímco jedno vlákno přečte prvních 32 bitů, nějaké jiné vlákno může změnit zbývajících 32 bitů. Prakticky vzato však všechna současná JVM implementují primitivní typy jako atomické. To se však může změnit v některé z následujících verzí, když přibudou value types.
  3. Jedna možná optimalizace, jak zrychlit program, je omezit alokace a kopírování cest prostřednictvím vkusného použití mutací. Pokud jsou všechny mutace stavu lokální nějaké funkci a nikdo jiný je nemůže pozorovat, vůbec nevadí, jestli byly provedeny jako několik čistě funkcionálních kroků nebo došlo k pochybným mutacím. Nějaká funkce zkonstruuje objekt in-place mutacemi, uvede ho do správného stavu,, finalizuje a zveřejní jako od té doby neměnný objekt. V Clojure tomuto mechanismu říkají transients.
  4. A ten zbytek je založený na spojových seznamech, které však nejsou nic víc než zdegenerované stromy.
  5. Nicméně čtení může být efektivnější. Jednak se nemusím strachovat se zamykáním a koordinací vláken při čtení, ale také sdílení je bezproblémové. Protože struktura je fixní, každý ji může sdílet a všechny procesory mají kopii ve své CPU cache a vesele si ji čtou. Kdyby docházelo ke změnám, procesory by mezi sebou museli posílat zprávy cache cohorenece protokolu a invalidovat změněné cache line v ostatních jádrech. – Navíc, když bych používal ke sdílení jednu atomickou referenci, která by ukazovala na neměnnou strukturu, mohlo by docházet ke CAS hell, kdy se mnoho vláken najednou snaží aktualizovat strukturu, ale vyhraje jen jedno, což vede k mnoha zprávám cache coherency protokolu nebo zbytečné práci. Řešením je stejně jako u sdílené paměti minimalizovat komunikaci mezi procesy a zbavit se míst, kde je běh programu serializován.
  6. Equational reasoning s referenčně transparentním programem není jen zbytečné akademické cvičení, ale skutečně užitečná věc, která se mi hodila, když jsem upravoval svojí knihovnu Matcher napsanou v PHP. Navzdory jazyku je Matcher čistě funkcionální a proto je možné s programem jednoduše manipulovat pomocí dosazovaní a eliminace. Právě takto – dosazováním za argumenty a vyhodnocováním – jsem upravil několik funkcí, které byly příliš složité a nepřehledné.
  7. Rich Hickey to sám zmiňuje v Clojure Concurrency
  8. Twigg et. al. v Stratified B-trees and versioning dictionaries zmiňují, že kopírování cest v roce 1986 Driscoll et al. (Making Data Structures Persistent) navrhl jako obecný způsob, jak z libovolné datové struktury založené na pointerech udělat persistentní verzi. Nešlo však o funkcionální persistenci, ale navrhovaný přístup povoluje modifikace již vytvořených objektů. Kopírování cest pro dosažení funkcionální persistence bylo použito už v roce 1982. Planar Point Location Using lan Munro Editor Persistent Search Trees obsahuje odkazy na několik zdrojů jejichž autoři více méně nezávisle došli ke stejným závěrům: Myers – AVL dags, Myers – Efficient applicative data types, Krijnen, Meertens – Making B-trees work for B, Reps, Teitelbaum, Demers – Incremental context dependent analysis for language-based editors a Swart – Efficient algorithms for computing geometric intersections.
  9. I když v Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections se píše: „The first persistent HAMT implementation can be attributed to Rich Hickey, lead-developer of Clojure.“

Flattr this!

This entry was posted in DS, Funkcionální programování. Bookmark the permalink.

2 Responses to Persistentní datové struktury

  1. Jakub Vrána says:

    Existuje nějaký jazyk, který by dokázal využít situace, kdy neměnná datová struktura už není používaná a místo kopírování by ji přepsal? Např. pokud máme kód x = sort(x) a x není jinde používáno, tak by sort() mohl x přepsat, místo aby ho nejprve kopíroval jinam nebo alokoval novou strukturu stejné velikosti.

Leave a Reply

Your email address will not be published. Required fields are marked *