Openhft Chronicle Map Data Store Specification

Design Overview

  • Each Chronicle Map is split into N completely independent, ordered segments

    • the number of segments is chosen during the Chronicle Map creation and is never changed.

    • each segment has an associated 3-level lock (the read, update and write levels).

  • Query Flow

    1. Compute the hash code of the queried key. Hash code length is 64 bits.

    2. Identify the segment that should hold the key, based on the hash code.

    3. Acquire the segment lock on the needed level.

    4. Search for the entry with the queried key in the segment.

    5. Perform the actual query operation on the entry, if the entry is found (e. g. read the value, update the value, etc.), or insert the entry, if the queried key was absent in the segment, and insertion of a previously absent entry is implied by the logic of the query being performed.

    6. Release the segment lock.

Lock implementation

Each lock is represented by two 32-bit words in the Chronicle Map memory

  • Count word: holds the numbers of threads holding the lock at the moment on the read, update and write levels.

  • Wait word: holds the number of pending threads, trying to acquire the lock on the write level, at the moment.

  • These two words are updated only via compare-and-swap operations.

The segment data structure

  • Segment tier A segment tier basically consists of two parts:

    • Hash lookup

    • entry space

  • Tier chaining

If a segment tier is filled up, i. e. on some entry insertion request entry space fails to allocate a memory block sufficient to place the new entry, a whole new segment tier is allocated and chained after the previous tier. All tiers, either first in their segments or chained, are identical.


Query Operations