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 — k47

Funk­ci­o­nální pro­gra­mo­vání je horké téma po­sled­ních let. Co to je, proč je to dobré, co to při­náší a proč o tom všichni mluví právě teď? Od­po­vědi na tyto otázky jsou ná­sle­du­jící: Pro­gra­mo­váníre­fe­renčně transpa­rent­ními funk­cemi6 , zlep­šuje to mož­nosti kom­po­zice, po­ro­zu­mění pro­gra­mům, což v ide­ál­ním pří­padě vede k lepším pro­gra­mům s menším počtem chyb.

Jedním z hlav­ních pilířů funk­ci­o­nál­ního pro­gra­mo­vání je fakt, že všechny datové struk­tury jsou ne­měnné. Když něco jednou vy­tvo­řím, už to nikdy nemůžu mo­di­fi­ko­vat. Jediný způsob, jak něco změnit, je vy­tvo­řit novou verzi struk­tury, která v sobě po­ža­do­va­nou změnu za­hr­nuje .

„Ale to bude příliš drahá ope­race…“ může vás těď na­pa­dat.

Není to tak docela pravda. Je fakt, že kdyby bylo nutné při každé změně udělat kom­pletní kopii celé datové struk­tury, funk­ci­o­nální pro­gra­mo­vání by, i přes všechny te­o­re­tické i prak­tické výhody, ne­stálo za tu námahu. Pro­gram by vždycky běžel příliš pomalu. Na­štěstí od­vážní lidé z FP gangů za po­slední po­lo­vinu sto­letí přišli na mnoho způ­sobů, jak im­ple­men­to­vat datové typy, které jsou jednak ne­měnné, okážou rychle vy­tvá­řet změ­něné verze, a všechny ope­race nad nimi mají asympto­tic­kou slo­ži­tost, která je velice blízká efemér­ním va­ri­an­tám.

Hlavní myš­lenka těchto tak­zva­ných per­si­s­tent­ních da­to­vých struk­tur je jed­no­du­chá: Sdílet co nej­větí množ­ství struk­tury s před­chozí verzí a ko­pí­ro­vat jen nejmenší možnou část ob­sa­hu­jící změnu (toto je také ozna­čo­váno jako structu­ral sha­ring). Per­si­s­tentní v tomto kon­textu ne­zna­mená ulo­žený na disku, ale trvalý, pro­tože všechny verze dané struk­tury pře­žijí.

Jako pří­klad uvedu strom A, jehož po­slední list změním z 4 na αω a vý­sled­kem bude strom B.

Jak je vidět oba stromy sdílí vět­šinu dat (modré uzly), zko­pí­ro­vána byla jen cesta od změ­ně­ného listu ke kořeni stromu (tak­zvaná path copy8 ). Ope­race tedy nemá cenu O(n), ale jen O(log(n)) a to je něco s čím se už dá reálně pra­co­vat. Vy­vá­žený strom s 232 ele­menty (±4 mi­li­ardy) má hloubku 31 a je tedy po­třeba zko­pí­ro­vat jen 31 uzlů, což sice není kon­stantní množ­ství práce, ale na druhou stranu ani není nijak gi­gan­tické.

Prin­cip je to krásně jed­no­du­chý, jak na něm však po­sta­vit efek­tivní per­si­s­tentní da­to­vou struk­turu, která má ty správné asymptoty, je otázka na dlouhé zimní večery (na­pří­klad amor­ti­zace je v per­si­tent­ním pro­středí po­ně­kud zrádná). Ale když se to povede, ote­vírá se před námi země ne­če­ka­ných mož­ností: S per­si­s­tent­ními struk­tu­rami mám k dis­po­zici všechny verze – update nikdy ne­zničí starý stav, vy­tvoří nový a já můžu bez sta­rosti při­stu­po­vat k oběma, sdílet je, po­rov­ná­vat je a číst a od­vo­zo­vat z nich nové verze vrásek i ve ví­ce­vlák­no­vých pro­gra­mech. Pro­tože data jsou po vy­tvo­ření za­fi­xo­vána a zmra­zena v čase, ne­mu­sím se ničeho bát, ne­mu­sím za­my­kat, ko­or­di­no­vat nebo mezi sebou syn­chro­ni­zo­vat vlákna. Ne­měn­nou da­to­vou struk­turu je vždycky bez­pečné číst, ne­mu­sím se bát, že za­tímco jsem pře­četl jednu část, někdo jiný mi pod rukama změnil zbytek struk­tury a já teď nemám kon­zis­tentní stav. Ne­měnná struk­tura se chová jako hod­nota, jako sta­bilní fakt, jako věc, o které se můžeme bavit a ne­hrozí nám, že na ní každý má jiný pohled.

Že to je vše­o­becně dobrý nápad uka­zuje třeba kniha Ef­fective Java1 , kde Josh Bloch do­po­ru­čuje i v Javě po­u­ží­vat ne­měnné třídy, jak to je jen možné, právě proto, že to zjed­no­duší uva­žo­vání o kódu a od­straní jednu celou ka­te­go­rii sta­rostí. Když to není možné, tak radí při­stou­pit k de­fen­ziv­nímu ko­pí­ro­vání (které však není do­ko­na­lým ře­še­ním, pro­tože jednak mi během ko­pí­ro­vání někdo jiný může zdro­jový objekt změnit pod rukama2 a druhak při­náší ur­či­tou (a často zby­teč­kou) režii).

In­tu­i­tivně je jasné, že vy­tvá­ření mo­di­fi­ko­va­ných verzí per­si­s­tent­ních DS je dražší než in-place mo­di­fi­kace běž­ných DS.5 Při každé změně musím něco nového alo­ko­vat, někdy jeden objekt (jako v pří­padě Cons-Nil se­znamů) jindy log<sub>b</sub>(n) ob­jektů (jako v pří­padě stromů, pro nějaký základ lo­ga­ritmu b). I když je alo­kace vět­ši­nou levná, bouře alo­kací se přesto může po­de­psat na výkonu a v nej­hor­ším pří­padě může způ­so­bit, že vý­sle­dek je li­mi­to­ván pro­pust­ností paměti. Exis­tují určité tech­niky jak se alo­kací zbavit, nebo je aspoň čás­tečně omezit, jako na­pří­klad escape ana­ly­sis nebo de­fo­restation, ale ani ty nejsou do­ko­nalé.3

Ve funk­ci­o­nál­ním pro­středí se navíc prak­ticky nedá obejít bez gar­bage collec­toru, který sle­duje všechny re­fe­rence a jakmile nějaká verze per­si­s­tentní DS není po­u­ží­vána, od­straní data, která jí patří a nejsou sdí­lena s ostat­ními živými ver­zemi. Díky GC je im­ple­men­tace per­si­s­tent­ních DS velice jed­no­du­chá.

Skoro4 všechny funk­ci­o­nální struk­tury jsou im­ple­men­to­vané pomocí stromů právě proto, že stromy umož­ňují snadné a levné ko­pí­ro­vání cest. Nejde jen o zjevné stromy jako Red-BlackALV, ale také o ra­fi­no­vané vnitřní de­taily kom­pli­ko­va­ných struk­tur, které se cho­vají jako mapy, mno­žiny, pole, fronty nebo obou­stranné fronty.

Nechci tady však vy­svět­lo­vat, jak jsou různé per­si­s­tentní datové struk­tury im­ple­men­to­vané, jak vy­pa­dají a jaké mají cha­rak­te­ris­tiky. Jde o příliš roz­sáhlé téma, o němž se dá najít spousta dob­rých zdrojů, které všechno vy­světlí lépe, než bych já kdy dovedl. Místo toho sem jen vysypu seznam odkazů s drob­nými ano­ta­cemi a půjdu od toho.


Skvělá před­náška, ve které Daniel Spiewak vy­světlí im­ple­men­taci ně­ko­lika zá­klad­ních per­si­s­tet­ních DS (se­znamy, fronty, deque, red-black stromy, vek­tory).

Chris Oka­saki na pro­storu dvou set stran této le­gen­dární knihy vy­světlí mnohem víc, než jste kdy chtěli vědět o funk­ci­o­nál­ních da­to­vých struk­tu­rách – jak je napsat v čistě funk­ci­o­nál­ním jazyku (autor po­u­žívá ML, ale v do­dat­cích jsou ukázky pře­psané do Haskellu) a jak ana­ly­zo­vat jejich asympto­tic­kou slo­ži­tost. Každá ka­pi­tola vždy při­nese něco nového a ne­če­ka­ného, co člo­věka na­prosto ohromí (tedy aspoň mě to ohro­milo): Per­si­s­tence, líné vy­hod­no­co­vání, amor­ti­zace, amor­ti­zace v per­si­s­tet­ním pro­středí, eli­mi­nace amor­ti­zace, lazy re­bu­il­ding, datové struk­tury po­sta­vené na růz­ných nu­me­ric­kých re­pre­zen­ta­cích, bo­ot­stra­ping a další.

Na in­ter­netu se dá najít Oka­sa­kiho di­zer­tační práce, z níž po­sléze malými úpra­vami vznikla sa­motná kniha. Autor deset let od prv­ního vydání napsal malou re­ka­pi­tu­laci.

Tato před­náška z kurzu Advan­ced data structu­res vy­u­čo­va­ného na MIT vy­světlí, že s per­si­s­tent­ními da­to­vými struk­tu­rami je to o něco kom­pli­ko­va­nější, pro­tože ty funk­ci­o­nální nejsou jediné, které jsou. Kromě toho ještě exis­tují par­ti­ally (čás­tečně), fully (plně) a con­flu­ent (sou­běžně?) per­si­s­tentní datové struk­tury, které při­pouš­tějí mož­nost mo­di­fi­ko­vat exis­tu­jící data, ale stále ta­ko­vým způ­so­bem, že jsou všechny před­chozí verze za­cho­vány a můžu k nim při­stu­po­vat a číst je. Čás­tečně per­si­s­tentní DS do­vo­lují mo­di­fi­ko­vat jen nej­ak­tu­ál­nější verzi.

Tyto dva články vy­světlí jak in­terně fun­guje Vector – stě­žejní li­ne­ární da­to­vou struk­turu z Clo­jure a ze Scaly. Vektor je velice široký strom, za­lo­žený na práci Phila Bagwella7 (Fast And Space Ef­fi­ci­ent Trie Sear­chesIdeal Hash Trees), do jeho sou­časné podoby ho pře­vedl Rich Hickey, ale poprvé ho im­ple­men­to­val Daniel Spiewak (pokud se ne­pletu).9

Bagwel­lův paper po­pi­su­jící Re­la­xed Radix Ba­lan­ced Trees – vy­lep­še­nou verzi vek­toru, která do­vo­luje spojit dva RRB-vek­tory v lo­ga­rit­mic­kém čase (na­místo li­ne­ár­ního, jak je běžné pro prostý Vector). RRB tak lookup, append, update pra­cu­jící v efek­tivně kon­stant­ním čase, roz­šíří o další efek­tivní ope­raci, bo­hu­žel za cenu drob­ného (kon­stant­ního) zpo­ma­lení všech ostat­ních ope­rací. Lidé ze Scala ko­mu­nity plá­no­vali, že by za­cho­vali sou­časný vektor a RRB stromy by se po­u­ží­valy jen, když dojde ke spo­jení dvou vek­torů nebo RRB stromů.

Ná­sle­duje ně­ko­lik před­ná­šek od Ed­warda Kmetta. Jde o po­ně­kud hut­nější ma­te­riál, ale pokud jste se pro­kou­sali skrz Oka­sa­kiho, nemělo by být ne­možné se za­kous­nout i do tohoto.


Ne­měn­nost dat po jejich vy­tvo­ření značně zjed­no­du­šuje ví­ce­vlák­nové pro­gra­mo­vání a syn­chro­ni­zaci (pro­tože žádní není po­třeba) a proto se těchto struk­tur vy­u­žívá i v ob­las­tech, kde by to člověk ne­če­kal: V datech na disku.

Cou­chDB – po­u­žívá sdí­lení struk­tury indexů na disku (data ko­pí­ruje celá). Když je nějaký do­ku­ment změněn, je na disk za­psána nová cesta ke kořeni do­ku­mentu, která od­ka­zuje na ne­změ­něné části. Stará verze je pak ně­ja­kou dobu stále do­stupná. Pokud se ne­mý­lím, nejde však o hlavní myš­lenku této da­ta­báze, ale jen o tech­niku, jak zrych­lit zápisy, umož­nit do­časné kon­zis­tentní okno a zlep­šit pa­ra­le­lis­mus. Staré verze struk­tur jsou even­tu­álně sma­zány gar­bage collec­to­rem.

Full­text search engine Lucene, který tvoří základ pro Elas­tic a Solr během in­de­xace také po­u­žívá im­mu­table pří­stup. Když za­in­de­xuje nějaké do­ku­menty, Lucene vy­tvoří seg­ment indexu, který je po vy­tvo­ření ne­měnný a ostatní pro­cesy ho můžou použít k hle­dání. Na pozadí jsou tyto seg­menty lo­ga­rit­micky slu­čo­vány do vět­ších seg­mentů (na prin­cipu Log-structu­red merge-tree, jako to třeba dělá Le­velDB viz: Do­mi­nic Tarr: The da­ta­base of the future: le­veldb, Inside Hy­per­Le­velDBCon­currency Im­pro­ve­ments in Hy­per­Le­velDB), a i když nejsou per­si­s­tentní, jsou stále ne­měnné. Jediné, co se mění, je seznam ur­ču­jící, které seg­menty jsou do­stupné a ak­tu­ální, a které už nikdo ne­po­u­žívá a budou sma­zány.

Ana­ly­tická da­ta­báze Druid.io také vy­tváří ne­měnné (ale ne per­si­s­tentní) seg­menty, které poté dis­tri­bu­uje na do­ta­zo­vací ser­very. O Druid.io do­po­drobna píše Lukáš Ha­vr­lant: Druid.io: dis­tri­bu­o­vaná im­mu­table da­ta­báze pro ana­ly­tické vý­po­čty, Ar­chi­tek­tura Druid.ioJak Druid.io agre­guje data.

Da­ta­báze Da­to­mic je na myš­lence ne­měn­nosti a per­si­s­tence po­sta­vená. To ji spolu s mo­de­lem sub­jekt-pre­di­kát-objekt-(trans­akce) ji umož­ňuje uklá­dat všechny verze všech faktů a efek­tivně tak pra­co­vat s časem. Ne­měn­nost vede k dis­tri­bu­o­va­ným uzlům, které data jen čtou, a striktní po­ža­davky na ACID pak mají za ná­sle­dek, že všechny trans­akce putují přes jeden uzel, tzv. tra­sac­tor. Více in­for­mací viz:

Bw-stromy, po­psané v The Bw-Tree: A B-tree for New Hard­ware Plat­forms, také po­u­ží­vají čás­tečně ne­měnná data. V tomto pří­padě proto, že je to ide­ální způsob, jak do­sáh­nout dob­rého výkonu na mno­ha­já­d­ro­vých pro­ce­so­rech. Bw-strom je va­ri­an­tou B-stromu, která změny za­zna­me­nává jako seznam delt. Když delta seznam do­sáhne určité délky, dojde k vy­tvo­ření ak­tu­a­li­zo­va­ného uzlu Bw-stromu, který v sobě ob­sa­huje všechny změny. Jediné, co se (ato­micky) změní je poin­ter, který začne uka­zo­vat na nový za­čá­tek delta se­znamu. Pro­tože delta ne­pře­pi­suje sdí­lená data uzlu, ne­do­chází k in­va­li­daci cache ostat­ních jader a eli­mi­nuje se tak množ­ství zpráv cache co­he­rency pro­to­kolu, což omezí ná­klad­nou im­pli­citní ko­mu­ni­kaci mezi jádry pro­ce­soru a vede v lep­šímu výkonu. K po­dob­ným zá­vě­rům došli i autoři Asyn­chro­ni­zed Con­currency: The Secret to Sca­ling Con­current Search Data Structu­resSta­ring into the Abyss: An Eva­luation of Con­currency Con­t­rol with One Thou­sand Cores.

Per­si­s­tentní datová struk­tura také leží v srdci rychlé a pa­ra­lelní fronty Sna­pQueue, která dokáže rychle dělat sna­pshoty v čase a spo­jo­vání dvou front. Má to však jeden háček – per­si­s­tentní DS (v tomto pří­padě Conc-Tree) není po­u­žita přímo, ale slouží jako kostra pro pole malých jed­no­rá­zo­vých front, které jsou po­cho­pi­telně mě­ni­telné. Sna­pQueue přímo ma­ni­pu­luje pouze s první a po­slední fron­tou (z první bere, do po­slední ukládá, když je první prázdná, vy­táhne si další, když je po­slední plná, vloží ji do kostry a vy­tvoří další). Více de­tailů v Sna­pQueue: Lock-Free Queue with Con­stant Time Sna­pshotsConc-Trees for Functi­o­nal and Pa­ral­lel Pro­gra­m­ming.

Per­si­s­tentní struk­tury jsou také po­u­žity v Gitu. Btrfs a další sys­témy sou­borů, které in­terně po­u­ží­vají Copy on Write B-stromy, udr­žují do­čas­nou formu per­si­s­tence. Pokud jsou za­lo­žené na append-only logu, musí řešit gar­bage collection a kom­pakci dat tím, že pře­su­nou data z ně­ko­lika téměř prázd­ných strá­nek do jedné plné. Jde o ne­chvalně známý pro­blém, pro­tože vede k tzv. write am­pli­fi­cation a může způ­so­bit, že disk nebude stíhat uvol­ňo­vat stránky. Více v Log-structu­red file sys­tems: There's one in every SSDStra­ti­fied B-trees and ver­si­o­ning dicti­o­na­ries.


Dále k tématu:


Pozn:

  1. Možná se za ně­ja­kou dobu do­čkáme nové edice Ef­fective Java ak­tu­a­li­zo­vané pro Javu 8 viz
  2. Tech­nicky vzato na JVM není bez syn­chro­ni­zace bez­pečné ko­pí­ro­vat ani long nebo double. Podle spe­ci­fi­kace 64bitové pri­mi­tivní typy nejsou ato­mické a za­tímco jedno vlákno přečte prv­ních 32 bitů, nějaké jiné vlákno může změnit zbý­va­jí­cích 32 bitů. Prak­ticky vzato však všechna sou­časná JVM im­ple­men­tují pri­mi­tivní typy jako ato­mické. To se však může změnit v ně­které z ná­sle­du­jí­cích verzí, když při­bu­dou value types.
  3. Jedna možná op­ti­ma­li­zace, jak zrych­lit pro­gram, je omezit alo­kace a ko­pí­ro­vání cest pro­střed­nic­tvím vkus­ného po­u­žití mutací. Pokud jsou všechny mutace stavu lo­kální nějaké funkci a nikdo jiný je nemůže po­zo­ro­vat, vůbec nevadí, jestli byly pro­ve­deny jako ně­ko­lik čistě funk­ci­o­nál­ních kroků nebo došlo k po­chyb­ným mu­ta­cím. Nějaká funkce zkon­stru­uje objekt in-place mu­ta­cemi, uvede ho do správ­ného stavu,, fi­na­li­zuje a zve­řejní jako od té doby ne­měnný objekt. V Clo­jure tomuto me­cha­nismu říkají tran­si­ents.
  4. A ten zbytek je za­lo­žený na spo­jo­vých se­zna­mech, které však nejsou nic víc než zde­ge­ne­ro­vané stromy.
  5. Nicméně čtení může být efek­tiv­nější. Jednak se ne­mu­sím stra­cho­vat se za­my­ká­ním a ko­or­di­nací vláken při čtení, ale také sdí­lení je bez­pro­blé­mové. Pro­tože struk­tura je fixní, každý ji může sdílet a všechny pro­ce­sory mají kopii ve své CPU cache a vesele si ji čtou. Kdyby do­chá­zelo ke změnám, pro­ce­sory by mezi sebou museli po­sí­lat zprávy cache co­ho­re­nece pro­to­kolu a in­va­li­do­vat změ­něné cache line v ostat­ních já­drech. – Navíc, když bych po­u­ží­val ke sdí­lení jednu ato­mic­kou re­fe­renci, která by uka­zo­vala na ne­měn­nou struk­turu, mohlo by do­chá­zet ke CAS hell, kdy se mnoho vláken na­jed­nou snaží ak­tu­a­li­zo­vat struk­turu, ale vy­hraje jen jedno, což vede k mnoha zprá­vám cache co­he­rency pro­to­kolu nebo zby­tečné práci. Ře­še­ním je stejně jako u sdí­lené paměti mi­ni­ma­li­zo­vat ko­mu­ni­kaci mezi pro­cesy a zbavit se míst, kde je běh pro­gramu se­ri­a­li­zo­ván.
  6. Equati­o­nal re­a­so­ning s re­fe­renčně transpa­rent­ním pro­gra­mem není jen zby­tečné aka­de­mické cvi­čení, ale sku­tečně uži­tečná věc, která se mi hodila, když jsem upra­vo­val svojí kni­hovnu Matcher na­psa­nou v PHP. Na­vzdory jazyku je Matcher čistě funk­ci­o­nální a proto je možné s pro­gra­mem jed­no­duše ma­ni­pu­lo­vat pomocí do­sa­zo­vaní a eli­mi­nace. Právě takto – do­sa­zo­vá­ním za ar­gu­menty a vy­hod­no­co­vá­ním – jsem upra­vil ně­ko­lik funkcí, které byly příliš slo­žité a ne­pře­hledné.
  7. Rich Hickey to sám zmi­ňuje v Clo­jure Con­currency
  8. Twigg et. al. v Stra­ti­fied B-trees and ver­si­o­ning dicti­o­na­ries zmi­ňují, že ko­pí­ro­vání cest v roce 1986 Dris­coll et al. (Making Data Structu­res Per­si­s­tent) navrhl jako obecný způsob, jak z li­bo­volné datové struk­tury za­lo­žené na poin­te­rech udělat per­si­s­tentní verzi. Nešlo však o funk­ci­o­nální per­si­s­tenci, ale na­vr­ho­vaný pří­stup po­vo­luje mo­di­fi­kace již vy­tvo­ře­ných ob­jektů. Ko­pí­ro­vání cest pro do­sa­žení funk­ci­o­nální per­si­s­tence bylo po­u­žito už v roce 1982. Planar Point Lo­cation Using lan Munro Editor Per­si­s­tent Search Trees ob­sa­huje odkazy na ně­ko­lik zdrojů je­jichž autoři více méně ne­zá­visle došli ke stej­ným zá­vě­rům: Myers – AVL dags, Myers – Ef­fi­ci­ent ap­pli­ca­tive data types, Krij­nen, Meer­tens – Making B-trees work for B, Reps, Te­i­tel­baum, Demers – In­cre­men­tal con­text de­pen­dent ana­ly­sis for lan­gu­age-based edi­tors a Swart – Ef­fi­ci­ent al­go­ri­thms for com­pu­ting ge­o­met­ric in­ter­secti­ons.
  9. I když v Op­ti­mi­zing Hash-Array Mapped Tries for Fast and Lean Im­mu­table JVM Collecti­ons se píše: „The first per­si­s­tent HAMT im­ple­men­tation can be at­tri­bu­ted to Rich Hickey, lead-de­ve­lo­per of Clo­jure.“
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články