funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Persistentní datové struktury

14. 8. 2016, aktualizováno: 14. 12. 2021

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í s 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 teď 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ždy 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é, dokážou rychle vytvářet změněné verze, a všechny operace nad nimi mají asymptotickou složitost velice blízkou 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ů. Nejde o 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 bez 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ždy 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é přesto nepředstavuje dokonalé řešení, 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čnou) 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 logb(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ě způsobit, že výsledek bude limitován propustností paměti. Existují určité techniky jak se alokací zbavit, nebo je aspoň částečně omezit (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 nějaké formy 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 červeno-černé 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 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 persistentní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 persistentní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é. 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ší verzi.

Tyto dva články vysvětlí jak interně funguje Vector - stěžejní lineární datovou strukturu z Clojure a 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 kdo se prokousal skrz Okasakiho, se jistě zakousne 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 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, vytvoří segment indexu, který je po zkompletování 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 dělá třeba 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) 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. Naopak striktní požadavky na ACID garance způsobí, ž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, čímž se omezí nákladná komunikace mezi jádry procesoru a zlepší se výkon. 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ů 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. (Podívejte, co jsem našel)
  2. Technicky vzato na JVM není bez synchronizace/volatile 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 může změnit v některé z následujících verzí, když projekt Valhalla přinese value types neboli primitivní objekty.
  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í v nějaké funkci a nikdo jiný je nemůže pozorovat, nevadí, jestli byly provedeny jako několik čistě funkcionálních kroků nebo došlo k pochybným mutacím. Určitá funkce zkonstruuje objekt in-place mutacemi, uvede ho do konzistentní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 tak 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."
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články