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.

The irmin-pack backend uses a generic library to solve this problem, inventively named 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 irmin-pack and hence to the whole Tezos blockchain.

Necessary skills

  • Non-trivial functional programming experience
  • Ability to read scientific publications and implement concepts described in them
For more information and to apply, please email clement@tarides.com.
← See all available internships