◐
Written by Niels Moseley
on 

Memgraph graph storage

A look at Memgraph graph storage

Memgraph

Storage

Storage is the main container of a graph. It can store data in memory or on disk. Unique or shared data access is handled through the Accessor class, which provides iterators to Vertex and Edge. It also holds name to ID translation information for edges, verteces, labels and properties. In addtion, it has functions to create or drop indeces.

Delta and Transaction

The Delta and Transaction class as used to keep track of modifications to the data.

Small vector

The small_vector is a replacement for std::vector and has 16 bytes overhead instead of the 24 required by std::vector.

NameIdMapper

To facilitate named objects, the NAmeIdMapper offers a std::string_view to uint64_t id translation. The translation data is stored in two SkipList for accelerated access, one for name -> id and one for id -> name. An atomic counter variable is used to handle concurrent write access.

Vertex

Verteces as referenced by Gid and hold incoming and outgoing edges in a small_vector. Each vertex has a PropertyStore to store properties and a mutable RWSpinLock to allow concurrent access.

Edge

Edges as referenced by Gid and hold almost nothing. Each edge has a PropertyStore to store properties and a mutable RWSpinLock to allow concurrent access.

An Edge can be connected to a Vertex by using the EdgeMetadata struct. This holds a raw pointer to a Vertex and a Gid.

EdgeReg

A struct holding a Gid and a raw pointer to the Edge.

ModifiedEdgeInfo

Not sure what this does, but it holds Gids of a source and destination vertex, an edge type id and an EdgeRef.

Property store

The property store uses a custom allocator code to store data in the class’ buffer_ variable. Lots of memmoves.

Property value

A property value can store NUll, Bool, Int, Double, TemporalData, ZonedTemporalData, Enum, String, List and Map. The type of data stored in a value is kept in an enum rather than a std::variant or similar C++ standard type. Each type has a ValueXXX() getter function that throws an exception if the type held is not convertible. A boost::flat map is used to hold maps.

SkipList

Memgraph has its own thread-safe SkipList implementation to accelerate lookups.

RWSpinLock

A spin lock that waits for all readers to leave before letting a writer access a resource. New readers are held back until a writer gets access to avoid starvation.

SpinLock

Memgraph has its own read-write spinlock implementation based on the pthreads spinlock. The spinlock is a light-weight locking mechanism that doesn’t make any kernel calls.

Other classes

Other interesting classes to look at are: