B-tree index for Irmin backend
Mentor: Clément Pascutto
Location: Tarides office, Paris
Irmin is an OCaml library for building mergeable, branchable distributed datastores. Datastores are parameterised on a user-supplied persistence layer, each of which have their own performance and compatibility trade-offs.
The most-recent Irmin backend,
irmin-pack, is optimised for low disk usage in
order to be used in the Tezos ledger. One of the major challenges with
implementing high-performance storage is indexing: providing low-latency access
to any block location, given the hash of its contents.
irmin-pack backend uses a generic library to solve this problem,
index, which creates a multi-level index tree structured
according to fixed-length prefixes of the hash. There are more exotic solutions
to the indexing problem, each with their own trade-offs regarding latency,
concurrency and disk-usage. In particular, Tarides has been experimenting with
functional B-tree indices as part of our prototype MirageOS file-system, Wodan.
This internship involves designing and implementing a generic B-tree index in
OCaml to be used for constructing high-performance datastores with minimal
kernel dependencies. This could be implemented as either an extension of Index
or an entirely new backend to Irmin, and should build on existing work. Any
performance improvements to Index are immediately applicable to
hence to the whole Tezos blockchain.
- Non-trivial functional programming experience
- Ability to read scientific publications and implement concepts described in them