Optimize HELL.PK for spatial and temporal data locality

renatomassaro commented 6 years ago

The problem

IDs are hard. Sequential IDs are prone to race condition. Completely random GUIDs are too sparse, losing both spatial and temporal data locality. Furthermore, GUIDs do not have human-readable information to figure out which object is represented by the ID.

Extended description of the problem.

The solution

After several months of background processing while showering / walking / sleeping, I've come up with the following format for our IPv6-based (128-bit) PK:

56 bits of inheritance information, from which 32 bits are for the object immediate parent (p) and 24 bits for the object grandparent (g).
28 bits holding information about the time the object was created (t)
40 bits of random digits for the object ID (o)
4 bits used to map the ID to an internal Helix domain (h)

which maps to something like:

gggg:ggpp:pppp:pptt:tttt:tooo:oooo:oooh

This gives us:

objects belonging to the same parent are grouped together, sorted by time
parents belonging to the same grandparent are grouped together
a 3-second granularity hashed timestamp, valid for ~25.5 years after "Helix epoch".
a human-readable last-digit useful to quickly identify the domain for which the PK belongs to.
enough room to, including parents and grandparents, not have collisions - hopefully :crossed_fingers:.

In fact, since the timestamp hash increments every 3 seconds, a collision would have to happen within this 3 second time frame, which is quite unlikely. In ~25.5 years we'll reach fffffff. It's probably a good idea to start worrying about this once we are near ff00000 :).

Some objects have no parent, e.g. Entities. These will have all but the last digit (h) available for random generation. Some objects have no grandparents, e.g. Servers. These will have all 56 bits of inheritance information reserved for the parent.

Practical example

Suppose we have Entities. These Entities have Servers. These Servers have Processes.

Process is the object (o). Server is the parent (p) and Entity is the grandparent (g). The proposed PK format allows us to reach for:

all Processes within a Server grouped together, sorted by creation time.
all Processes belonging to the same Entity grouped together.

This is a great locality + cache optimization for:

querying Processes within a Server (ProcessQuery.get_processes_on_server and ProcessQuery.get_custom)
querying all Processes on all Servers belonging to the Entity (during ServerJoin and ServerBootstrap)

Caveats / cons

Some extra, seemingly unnecessary GP/parent information queried at Action/Query level in order to feed the corresponding Model the required data.
Careful thought required to design the corect GP/P/O hierarchy. An object's GP/P must never change. As such, e.g. Server must not be the parent of hardware Components, since Components may be linked to other Servers.

So one could say Helix will expire sometime after 2043. Hopefully HE2 will have been released by then :smile:

renatomassaro commented 6 years ago

Note to self: when implementing this, use pg_repack to constantly CLUSTER the index (in a "CONCURRENTLY" fashion) so we get around the MVCC limitations.

Also optimize pg's fillfactor accordingly. Somewhere in between 80 and 90% seems OK for starters.

renatomassaro commented 6 years ago

Implemented at #408 with minor changes to the specs proposed at the issue description. See lib/id/id.ex for a definitive, up-to-date documentation.

HackerExperience / Helix