lib_context: optimise the memory usage of the snapshot export

Craig Fergusonrequested to merge
CraigFe/tezos:optimise-snapshot-export into master

Context

TL;DR: reduce memory usage of the snapshot export from ~10G to ~4G by optimising the data-structure used.

The memory requirements of the context-dump portion are increasingly prohibitive (~10GB when exporting a store at block 1,694,978). This is mostly due to a data-structure that is used to track which hashes have already been exported when traversing the context tree, so as to (a) avoid redundant work in exporting shared child nodes, and (b) ensure that the snapshot format is canonical.

This MR optimises the space used by this hash-tracking data-structure. Currently, we use a (hash, unit) Stdlib.Hashtbl.t. After resolving type aliases, this is equal to:

([ `Blob of string<32> | `Node of string<32> ], unit) pair_list array

Breaking down the space usage per binding:

  • 6 word string (header + 4 words data + null padding)
  • 3 word polymorphic variant (header + tag hash + string pointer)
  • 4 word list node (header + data pointer + unit + tail pointer)
  • ~0.5 word bucket slot (in the best case, there are ~2 bindings per bucket)

This is ~13.5 words per hash.

The new implementation does the following:

  • drop the unnecessary polymorphic variant wrapper: it's not possible for a node and a blob to have the same hash;
  • use a hash-set rather than a unit Hashtbl.t;
  • store the hash strings in a bigstring arena;
  • use a linked-list implementation that is optimised for small list sizes (avoiding a tail pointer & amortising the cost of the heap header).

The result is a data-structure that uses ~6 words per hash instead, reducing the memory usage of exporting a recent context from ~10G to ~4G. Looking at the cumulative effect of each optimisation applied in sequence:

image

A consequence of this is that the context dump is also a bit faster, going from 13.5mins to 8.5mins on my machine.

Manually testing the MR

Run a snapshot export, and inspect the memory usage with htop:

dune exec src/bin_node/main.exe -- snapshot export /tmp/snapshot-out --data-dir=... --rolling

Checklist

  • Document the interface of any function added or modified (see the coding guidelines)
  • Document any change to the user interface, including configuration parameters (see node configuration)
  • Provide automatic testing (see the testing guide).
  • For new features and bug fixes, add an item in the appropriate changelog (docs/protocols/alpha.rst for the protocol and the environment, the Development Version section of CHANGES.md for everything else).
  • Select suitable reviewers using the Reviewers field below.
  • Select as Assignee the next person who should take action on that MR

Merge request reports