This is the first step to move the mapreduce code to an AMPC model which will allow us to implement some distributed graph algorithms more efficiently. The main difference between the MPC and AMPC model is that we use a distributed key/value store for synchronization and to store the result for each round. This allows the algorithms to dynamically choose which segments of the previous rounds result it needs, and can therefore reduce the number of rounds needed overall.
The key/value store is a distributed BTreeMap<Vec<u8>, Vec<u8>> where the key is routed to the correct shard based on md5(key) % num_shards. Each shard uses raft based consensus for high availability. Shard rebalancing is currently not implemented, so adding/removing a shard will result in keys being routed to incorrect shards.
In the paper they use remote direct memory access which we don't use here, but we should be able to get close to the same average latency by batching requests from the algorithm implementation which will hopefully amortize the overhead enough.
This is the first step to move the mapreduce code to an AMPC model which will allow us to implement some distributed graph algorithms more efficiently. The main difference between the MPC and AMPC model is that we use a distributed key/value store for synchronization and to store the result for each round. This allows the algorithms to dynamically choose which segments of the previous rounds result it needs, and can therefore reduce the number of rounds needed overall.
The key/value store is a distributed
BTreeMap<Vec<u8>, Vec<u8>>where the key is routed to the correct shard based onmd5(key) % num_shards. Each shard uses raft based consensus for high availability. Shard rebalancing is currently not implemented, so adding/removing a shard will result in keys being routed to incorrect shards.In the paper they use remote direct memory access which we don't use here, but we should be able to get close to the same average latency by batching requests from the algorithm implementation which will hopefully amortize the overhead enough.