4.3 Hash-Based Sync

Node 3 is a node that has previously been connected to this Graph, and the Graph Database at the time it was last connected to the Graph was persisted to disk. Prior to connecting to the Graph, Node 3 loads its persisted Database.

Node 3 knows the address and port of Node 2, and establishes a connection just like Node 2 connected to Node 1 above.

Because Node 3 has an older copy of the Graph Database, it performs a Time-based Sync rather than a Sync All. Time-based Sync looks very similar to Sync All above, so this exchange is not shown. Following the Time-based Sync, Node 3 performs a Hash-based Sync.

Performing a Hash-based Sync includes the following steps:

• Node 3 divides its database into ranges of 10 Records each. In this Database, there are only five Records, so it has a single range.

• Node 3 calculates an MD5 hash of the Record IDs and Record Versions in the range.

• Node 3 sends Node 2 a SOLICIT_HASH message containing the range and hash calculated above.

• Node 2 calculates an MD5 hash of the Record IDs and Record Versions of all the Records in its Database for each range specified by Node 3.

• Node 2 notices that the hashes it generated in step 4 differ from the hashes sent in the SOLICIT_HASH message, and sends an ADVERTISE message containing all the Record IDs and Record Versions in the ranges that differ.

• Node 3 sees that the ADVERTISE message contains information about two Records that it does not have (3 and 6), and sends a REQUEST message for those two Records. Node 3 also sees that the ADVERTISE message does not contain information about Records 4 and 7, and remembers this for use below.

• Node 2 responds to the REQUEST message by sending FLOOD messages for Records 3 and 6.

• Node 2 sends a SYNC_END after flooding all the requested Records.

• Having noticed in step 6 that Node 2 was missing Records 4 and 7, Node 3 now sends FLOOD messages for Records 4 and 7.

• After synchronizing, Node 3 now begins listening just as Node 2 did above. Upon listening, Node 3 performs Graph Maintenance. Because there are now three Nodes in the Graph, Node 3 is able to find a Node that it is not already connected to. Node 3 establishes a connection to Node 1, as above. At this point, all three Nodes are interconnected.