Talk

The H2O distributed K/V algorithm

  • In English
Presentation pdf

H2O includes a distributed Key / Value store with exact (JMM volatile) semantics — instead of the more common lazy semantics. The DKV is very fast:

  • All values can be cached locally; local reads require only a hashtable probe, typically ~100ns.
  • Remote reads without conflicting writes require a single UDP packet round-trip.
  • Writes without conflicting reads are either local (~100ns for a hashtable probe) or remote (UDP packet round-trip).
  • Reads/writes can be declared "NOT volatile" and then typically the return UDP packet can be lazy / pipelined.
  • Bulk remote reads and writes stream: all internal i/o is lazy and overlaps, until the end and then the whole stream operation is treated as exact.
  • Conflicting reads/writes will block on each other but always maintain JMM semantics, including non-volatile updates.
  • Individual Keys can update with atomic transactions with local retry as needed.

The DKV is well geared to support individual updates for H2O control logic, as well as bulk throughput for Big Data applications. Big Data streaming math operations can commonly include millions to billions of streaming key reads & writes, and this volume is handled fast and gracefully while maintaining exact semantics.

However, the best and fastest K/V operation is purely local. Thus the standard DKV hash function deterministically stripes the Big Data across the cluster, and the standard H2O work distribution sends the work to the data based on the hash function — and most work never requires a remote Key.

  • #algorithms
  • #lock-free-programming
  • #low level
  • #memory-model
  • #performance
  • #state machine

Speakers

Talks