Jim Morrison died in 1971, I wasn’t even alive then. I didn’t learn about The Doors until the Val Kilmer film from the 90s. I was still too young to really understand them but I became a fan of the music nonetheless. In the last few months I’ve learned more about doors. I learned about this concept of one way and two way doors. The idea being that one way doors can only be broken through once, but if you don’t love the decision you made you can walk through the door two times and be back to where you started.
How does this work for software? Isn’t everything in software a two way door since we can just change it? I’d like to think so, but I tend to write “small” software. Software that you can rewrite easily or just throw away and start fresh. But having worked in a database company where “big” and long lived software gets made makes me question that belief. One door I am going to walk back through is allowing Nodes to have none, one, or more than one Label. In RageDB all nodes will have one and only type and all relationships will have one and only one type. So we’re dropping the “Labeled Property Graph” and going with “Typed Property Graph”.
Along with this single type, all Nodes must have a unique “key”. Whatever way the user decides to identify them. Almost all “things” in a graph are supposed to be unique, they are a special snowflake and proud of it. Having a unique Type and Key combination will force the user into thinking this way.
In the first proof of concept, the external id of a node or relationship contained their internal id and the shard id. This was required to know which shard owned that data. We are going to add the type to the external ids. We will use 64-bit identifiers, take the first 10 bits which allows us to store 0-1023 as our shard_id to store the core responsible for this object. We have 54 bits left over, so we’ll take 16 of them to represent the type. This will allow us to store 0-65535 types, but we’ll kill the 0 type and use that as an error marker instead. That leaves us with 38 bits for our ids which is just under 275 Billion ids and should be plenty. Let’s take a look at some code:
static const unsigned int SHARD_BITS = 10U;
static const unsigned int TYPE_BITS = 16U;
uint64_t Shard::externalToInternal(uint64_t id) {
return (id >> (TYPE_BITS + SHARD_BITS));
}
uint64_t Shard::internalToExternal(uint16_t type_id, uint64_t internal_id) const {
return (((internal_id << TYPE_BITS) + type_id) << SHARD_BITS) + shard_id;
}
To convert an external id to an internal id, we shift it right 26 bits. That’s easy, what about the other way. We take the internal id, shift it left 16 bits, then add the type_id, take that addition and shift it again 10 bits, then add the shard id. Looks pretty easy still. Let’s see how we get the type or shard id.
static const unsigned int TYPE_MASK = 0x0000000003FFFFFFU;
static const unsigned int SHARD_MASK = 0x00000000000003FFU;
uint16_t Shard::externalToTypeId(uint64_t id) {
return (id & TYPE_MASK) >> SHARD_BITS;
}
uint16_t Shard::CalculateShardId(uint64_t id) {
if(id < SHARD_MASK) {
return 0;
}
return id & SHARD_MASK;
}
To get the type id of an external id, we AND it with the 26 bit type mask and shift right 10 bits to drop the shard_id. We could have also shifted first and then AND with a 16 bit mask. I don’t think it makes a difference. To calculate the Shard Id, first we check to see if the number is less than 1024, which means it’s invalid and should go to zero to deal with it.
I am no expert in bit twiddling hacks but hopefully I did that right. No you know what, let’s go ahead and write some tests to make sure. When we copied this template it came bundled with Catch2 (a unit testing framework) not to be confused with Catch 22 (which is something else entirely).
SCENARIO( "Shard can handle internal and external id conversions", "[ids]" ) {
GIVEN("An empty shard") {
ragedb::Shard shard(4);
WHEN("we convert external ids to internal ones") {
THEN("we convert 67108864 to 1") {
REQUIRE(shard.externalToInternal(67108864) == 1);
}
...
WHEN("we convert external ids to type ids") {
THEN("we convert 67109888 to 1") {
REQUIRE(shard.externalToTypeId(67109888) == 1);
}
...
WHEN("we convert internal ids to external ones for shard_id:0") {
THEN("we convert 1, 1 to 67109888") {
REQUIRE(shard.internalToExternal(1, 1) == 67109888);
}
Tests pass so far, but how do we get an id in the first place? We’re supposed to be creating nodes with a type and a key? We’ll create a string combining the type and key, then hash it into a 64 bit number, then bucket that number into one of the CPUs we have.
uint16_t Shard::CalculateShardId(const std::string &type, const std::string &key) const {
uint64_t x64 = std::hash<std::string>()((type + '-' + key));
return (uint16_t)(((__uint128_t)x64 * (__uint128_t)cpus) >> SIXTY_FOUR);
}
One look at that return clause and you know I didn’t come up with that code. I stole it from Daniel Lemire. It was on one of his blog posts, but he has so many I can’t recall which one it was. Let’s go ahead and test these as well.
SCENARIO( "Shard can calculate shard ids", "[ids]" ) {
GIVEN("An empty shard") {
ragedb::Shard shard(4);
WHEN("we calculate shard ids on 4 cores") {
THEN("calculate shard id 0 for an invalid number") {
REQUIRE(shard.CalculateShardId(99) == 0);
}
THEN("calculate shard id 2 for 65538") {
REQUIRE(shard.CalculateShardId(65538) == 2);
}
...
THEN("calculate shard ids for type and key") {
REQUIRE(shard.CalculateShardId("User", "maxdemarzi") == 0);
REQUIRE(shard.CalculateShardId("User", "helene") == 1);
REQUIRE(shard.CalculateShardId("User", "alejandro") == 2);
REQUIRE(shard.CalculateShardId("User", "tyler") == 1);
REQUIRE(shard.CalculateShardId("User", "ronnie") == 1);
REQUIRE(shard.CalculateShardId("User", "penny") == 0);
Ok, so far we can make some numbers and they seem to check out, how do we tie this into our Graph? Let’s start by first creating a NodeTypes class to hold the maps for the string to type_id and the reverse. We’re going to start the type_ids from 1 and increment from there, so we have vector style access to everything else because in C++ there is only one God and its name is Vector.
class NodeTypes {
private:
std::unordered_map<std::string, uint16_t> type_to_id;
std::vector<std::string> id_to_type;
We have not built the http endpoint yet, but let’s keep things simple and assume we are able to create empty nodes. That is, nodes without any properties by a NodeAddEmpty method. We don’t know which shard will own this new node, so we start off in a Peered version of the method and calculate both the shard_id and the type_id for our new node. If the type already exists, we tell the shard which will control that node that it should go ahead and add it.
seastar::future<uint64_t> Shard::NodeAddEmptyPeered(const std::string &type, const std::string &key) {
uint16_t node_shard_id = CalculateShardId(type, key);
uint16_t node_type_id = node_types.getTypeId(type);
if (node_type_id > 0) {
return container().invoke_on(node_shard_id, [type, node_type_id, key](Shard &local_shard) {
return local_shard.NodeAddEmpty(type, node_type_id, key);
});
}
But what happens when it is a brand new type? We need to co-ordinate the creation of the type ids, so we will forward all new type requests to shard zero and ask it to figure out what the node_type_id should be and then tell that shard to go ahead and add it.
return container().invoke_on(0, [node_shard_id, type, key, this] (Shard &local_shard) {
return local_shard.NodeTypeInsertPeered(type).then([node_shard_id, type, key, this] (uint16_t node_type_id) {
return container().invoke_on(node_shard_id, [node_type_id, key](Shard &local_shard) {
return local_shard.NodeAddEmpty(node_type_id, key);
});
});
});
So what exactly happens inside NodeTypeInsertPeered? Shard 0 takes a lock, adds new node_type_id, makes sure all the other shards add this type id to their collection, drops the lock and returns the newly created node_type_id which as we saw above gets passed on the shard that owns that node.
this->node_type_lock.for_write().lock().get();
node_type_id = node_types.insertOrGetTypeId(type);
return container().invoke_on_all([type, node_type_id](Shard &local_shard) {
local_shard.NodeTypeInsert(type, node_type_id);
}).then([node_type_id, this] {
this->node_type_lock.for_write().unlock();
return seastar::make_ready_future<uint16_t>(node_type_id);
});
It’s hard to reason about multi-threaded work, so we’ll try to do as little of it as possible but the above will make sure that if we get two nodes of different new types at the same time, they end up at all the shards with the right node_type_id for each. Realistically most graphs have a handful of node and relationship types so we won’t see this very often.
Now you may be wondering just what is a seastar::future and what’s all this “.then()” stuff. It’s all explained in the Seastar documentation, but basically a Future is a result that may not be ready yet and a Continuation is what happens when the result is ready. You attach Futures to Continuations using “then” and can chain them together. We already talked about them in Part 2, but I know you didn’t dive in to them. We’ll see more examples as we continue so I need you to go click on this Seastar documentation link (and read it) so you can better understand what is going on and can help me build this thing. Stay tuned for part 4.
Max De Marzi 