<style> .reveal { font-size: 26px; } .slides { position: absolute; top: 0; left: 0; } </style> # Intoduction to Plebeia Lin Oshitani --- ## Backgound: Tezos context * Stores blockchain data in Unix-like directory+file system ```shell= .. /protocol ... /votes/current_quorem ... /contracts/index/<contract_id>/balance /contracts/index/<contract_id>/code ... ``` --- ## What is Plebeia? * Storage system built for Tezos * Provides a UNIX file system like interface. * Key-value store where the key is unix like file path (e.g.`{foo/bar="hello"}`) * Can generate merkle proofs * Implemented using a modified version of Merkle Patricia tree * Better speed/disk space performance compared to Irmin --- ## Example: Read/write ``` $ echo "hello world" > foo/bar $ cat foo/bar ``` ```OCaml let () = let module F = Fs.Make(Fs.Name8bits) in let* ctxt = Context.create "./tmp" in let open F.Op.Monad in let cur = F.empty ctxt in let f = F.Op.write ["foo"; "bar"] (Value.of_string "hello world") >>= fun () -> F.Op.cat ["foo"; "bar"] >>= fun content -> Printf.printf "content=%s\n" (Value.to_string content); return () in Lwt.return @@ ignore (f cur) # content = hello world ``` --- ## Example: Merkle proof ```ocaml= let () = ...(* Same as previos slide *)... let f = F.Op.write ["foo"; "bar"] (Value.of_string "hello world") >>= fun () -> F.Merkle_proof.make [["foo"; "bar"]] >>= fun (proof, _) -> Format.eprintf "proof:@.@[%a@]@." F.Merkle_proof.pp proof; return () in Lwt.return @@ ignore (f cur) # proof: tree= Bud Extender LRRLLRRLLRRLRRRRLRRLRRRRLLLLLLLL Bud Extender LRRLLLRLLRRLLLLRLRRRLLRLLLLLLLLL Leaf 68656c6c6f20776f...; paths= [LRRLLRRLLRRLRRRRLRRLRRRRLLLLLLLL; LRRLLLRLLRRLLLLRLRRRLLRLLLLLLLLL]; ``` --- ## Internal implementation * Disclaimer: The following slides explains a simplified version of Plebeia. The actual implementation can be different. --- ## Internal implementation * The path is converted into a sequence of `L`s and `R`s. For example something like: `foo/bar` -> `LRLLRLRR/RRLRLLRR` * A tree is defined as: ```ocaml= type node = | Leaf of value | Branch of node option * node option (* left node * right node *) | Bud of node option (* Directory, i.e. the "/" in the path *) ``` * `{RR="e"; L/L="f"; L/R="g"}` ```graphviz digraph G { { node [fontcolor=white] a [shape=circle] b [shape=folder] c [shape=circle] d [shape=circle] e [shape=note fontcolor=black] f [shape=note fontcolor=black] g [shape=note fontcolor=black] } a -> b [label=L] a -> c [label=R] b -> d c -> e [label=R] d -> f [label=L] d -> g [label=R] } ``` --- * Problem: Tree becomes very deep when the path is long * Solution: Introduce an *extender node* that "squashes" common prefixes ```ocaml= type side = L | R and key = side list type node = | Leaf of value | Branch of node option * node option | Bud of node option | Extender of key (* added this *) ``` * `{LLRLL="d"; LLRLR="e"; R="c"}` ```graphviz digraph G { { node [fontcolor=white] a [shape=circle] b [shape=doublecircle] c [shape=note fontcolor=black] d [shape=note fontcolor=black] e [shape=note fontcolor=black] } a -> b [label=LLRL] a -> c [label=R] b -> d [label=L] b -> e [label=R] } ``` --- * Problem: Tree is often too large to be stored in memory * Solution: Add `Disk` node to represent a subtree stored in disk ```ocaml= type side = L | R and key = side list type node = | Leaf of value * index (* `index` represents the address in external storage *) | Branch of node option * node option * index option | Bud of node option * index option | Extender of key * index option | Disk of index (* Nodes can be swapped with `Disk` based on `index` *) ``` ```graphviz digraph G { { node [fontcolor=white] a [shape=circle] b [shape=folder] c [shape=circle] d [shape=circle] e [shape=note fontcolor=black] f [shape=note fontcolor=black] g [shape=note fontcolor=black] } a -> b [label=L] a -> c [label=R] b -> d c -> e [label=R] d -> f [label=L] d -> g [label=R] { node [fontcolor=white] a2 [shape=circle] b2 [shape=cylinder] c2 [shape=circle] e2 [shape=note] } a2 -> b2 [label=L] a2 -> c2 [label=R] c2 -> e2 [label=R] } ``` --- * Plebeia nodes fit in 32 bit "cell"s  (ref: https://www.slideshare.net/camlspotter/plebeia-a-new-storage-for-tezos-blockchain-state) --- * Problem: We want to generate merkle proofs * Solution: Introduce `Hash` nodes to "squash" sibling nodes ```ocaml= type side = L | R and key = side list type node = | Leaf of value * index option * hash option | Branch of node option * node option * index option * hash option | Bud of node option * index option * hash option | Extender of key * index option * hash option | Disk of index | Hash of hash ``` * Proof that `f` exists in the tree: ```graphviz digraph G { { node [fontcolor=white] a [shape=circle] b [shape=folder] c [shape=circle] d [shape=circle] e [shape=note fontcolor=black] f [shape=note fontcolor=black] g [shape=note fontcolor=black] } a -> b [label=L] a -> c [label=R] b -> d c -> e [label=R] d -> f [label=L] d -> g [label=R] { node [fontcolor=white] a2 [shape=circle] b2 [shape=folder] c2 [shape=point] d2 [shape=circle] f_ [shape=note fontcolor=black] g2 [shape=point] } a2 -> b2 [label=L] a2 -> c2 [label=R] b2 -> d2 d2 -> f_ [label=L] d2 -> g2 [label=R] } ``` --- ## Benchmarks: Time  https://www.dailambda.jp/blog/2022-06-10-tezos-plebeia-benchmark/ --- ## Benchmarks: Disk size  https://www.dailambda.jp/blog/2022-06-10-tezos-plebeia-benchmark/ --- ## Things I did not cover about Plebeia * Uses [*zippers*](http://gallium.inria.fr/~huet/PUBLIC/zip.pdf) to enable `cd`ing into a subtree * Avoids the cost of traversing the tree from root on every access * Detailed on-disk representation of the nodes * A lot of thought have been put to efficiently store the nodes in disk --- ## References * https://arxiv.org/pdf/2106.04826.pdf * https://gitlab.com/dailambda/plebeia * https://www.dailambda.jp/blog/2020-05-11-plebeia/ * https://www.dailambda.jp/blog/2022-06-10-tezos-plebeia-benchmark/