Consistent hashing in bifrost

After some research to choose sharding method for my key-value store, I still insist using consistent hashing from last version.

According from some references like this video, consistent hashing allows users to lookup where is the data by keys. If clients share the same server information, whenever or wherever the lookup occurs, it will always get a fixed result.

maxresdefault

Consistent hashing can also prevent large scale re-hashing occurred on server node membership changes which may lead to unacceptable amount of data migration across servers. The downside is lookup operations in traditional way only need to do one mod by hash codes, but consistent hash required to do a binary search on the ring.

The core data structure to consistent hashing is a sorted array, which should be considered as ring, like showed in the figure above. The element of the ring, is objects with node hash and node address. To construct the ring, clients should get know server address and their weights. Server nodes objects which is the element of the ring should be generated for each servers and the ratio for nodes  to each server should be determinate by weights, their hash code should be unique. Each node should use the same hash function, because different implementation may have different result ranges. Consistent hashing components should also listen to membership changes in order to regenerate the ring and inform member servers to do data migration.

In bifrost, consistent hashing system is built on it's client membership system. User need to register server to bifrost membership services, plus a weight service to inform clients how much loads it can take. For example, a on-memory key-value store, the weights should be set as how much memory the server has, in MB. Bifrost consistent hashing clients will generate a almost fix sized ring (around 2048 nodes in default) according the weights. Users don't need to normalize weights to prevent a very large or small ring that will impact on it's performances.

The ring will be updated automatically if membership changes occurred. Thanks to subscription feature in bifrost raft state machine, there is no polling but server pushes underneath. User can also watch changes for the whole or individual server to migrate data. In the server changes callback for individual member, user will get new key ranges the member belongs, to remove or load data from outer sources.

To use consistent hashing in bifrost, it is similar to client membership. Server, raft services, heartbeat service for membership should be load and prepared. Consistent hashing data structure are built in term of membership groups, this allows to distribute data to servers for different purpose with different lookup table. So, a member must join groups to be accessible in the consistent hashing lookup. As mentioned before, servers all need to specify it's weight. It need to be initialized in bifrost cluster raft service.

Weights::new(&raft_service);

In member server side, the shell of the service can be created to set weight for itself. Please be noticed in this stage ch is not capable of doing any lookup because the ring have not yet been generated.

let ch = ConsistentHashing::new(&group_1, &wild_raft_client).unwrap();

Weights can be set by

ch.set_weight(&server_1, 1);

After weights been set, ring can be generated by

ch.init_table().unwrap();

In clients that will only to lookup, ch and it's ring can be generated without additional steps by

let ch = ConsistentHashing::new_client(&group_1, &wild_raft_client).unwrap();

Now, ch should be functional and ready to deliver.

To lookup a string key:

let server = ch1.get_server_by_string(&k).unwrap();

The server variable should contain a consistent server name for the key.

If user already knows the hash code, it can be lookup directly by

let server = ch1.get_server(&key_hash).unwrap();

Users may also want to lookup by hashing a object, bifrost allow users to provide a object that implemented serde::Serialize. Bifrost will use bincode for serde to encode the object into binary data and use the same hash function for the consistent hashing to calculate the hash code, by:

let server = ch1.get_server_by(&M {a: 1, b: 2}).unwrap();

To watch key range changes it should responsible in specific server, it is as easy as what we meet in raft state machine subscription.

ch.watch_server_nodes_range_changed(&server_name, move |r| {
    println!("Server key range changed to {:?}", r.unwrap());
});

Users do not need to update the ring manually. When any member in the group leave or go offline, nodes to the server will be removed from the ring. When any member joined or go back online, the nodes to the server will also be added to the ring, automatically. There maybe some lag to be responsive, users need to handle short time inconsistency by themselves.

Consistent hashing in bifrost is managed to be easy to use and also self-contained without other dependices. Combining with it's client membership system, the efforts required to be take care of from users was reduced to minimum.

Leave a Reply

Your email address will not be published. Required fields are marked *