EdgeKV: Distributed Key-Value Store for the Network Edge

August 16, 2021

To avoid the communication bottleneck caused by cloud-centric data storage, the authors of this paper propose the general-purpose storage system EdgeKV as a decentralized alternative. Unlike other storage systems for the edge present in the current literature, EdgeKV provides strong consistency guarantees. The fundamental idea of EdgeKV is to store key-value pairs in a Distributed Hash Table (DHT) over various edge servers. These edge servers are referred to as gateway nodes. Each gateway node is uniquely connected to a single, separate nearby group of edge nodes, where each group is defined as a cluster of edge devices in close proximity to one another. Instead of storing key-value pairs on the gateway nodes directly, each gateway node stores its data on a Replicated State Machine (RSM) formed over the nodes of the group that the gateway node is connected to.

Two Layers

EdgeKV can be decomposed into two layers: the Local Layer and the Global Layer. The Local Layer contains the various groups of edge devices. Each group forms a RSM over that group’s nodes, implemented using etcd, which itself uses the Raft consensus protocol. Each group is uniquely connected to a single nearby gateway node. These gateway nodes form the Global Layer.

In the Global Layer, the various gateway nodes form a DHT. For $n$ gateway nodes, the DHT’s implementation uses consistent hashing, can reach any gateway node in $O(\log n)$ hops, and uses $O(\log n)$ space per node for storing routing information. Like many other DHT protocols (such as Chord), EdgeKV’s DHT assigns each gateway node a hash based on the node’s IP, which is used to decide which group a key-value pair should be placed on. This use of a DHT in the Global Layer over the groups in the Local Layer enables a fair distribution of keys over the various groups.

Five Modules

EdgeKV can also be viewed as a composition of five modules: the RPC Interface, the Storage layer, the Placement Protocol, the Resource Finder, and the Replication Manager.

The RPC interface defines how users interact with EdgeKV.
The Storage layer differentiates local and global storage of data.
The Placement Protocol determines which of the aforementioned storage methods should be used.
The Resource Finder decides which group should store a given key-value pair.
Finally, the Replication Manager ensures that all key-value pairs are properly replicated among nodes in the same group.

RPC Interface

The RPC Interface provides a “structured and efficient method” for users to communicate with EdgeKV, with the added benefit that it abstracts user code from EdgeKV’s implementation. The interface, implemented with gRPC, allows end nodes (i.e. users) to execute GET, PUT, and DELETE operations on EdgeKV to obtain, insert, update, and remove key-value pairs.

Storage Layer

The Storage layer defines two ways that data can be stored in EdgeKV. In addition to storing key-value pairs globally in the DHT, EdgeKV also allows data to be stored locally, visible only to edge nodes in the same group. These two storage methods are called the Global Store and the Local Store respectively. When data is stored in the Local Store, the key-value pairs are replicated among the nodes of the group, but the key-value pair is not visible through the DHT in the Global Layer.

Placement Protocol

After a user initiates a call from the RPC Interface, the next layer reached is the Placement Protocol. The Placement Protocol decides which of the two stores from the Storage Layer should be used. This protocol runs on the edge nodes, and is presumably invoked when a user makes a request to an edge node in a group. It is assumed that the request received by the edge node has three parameters: the key, the value, and the type. The key and value parameters form the key-value pair. The type parameter is either the value "local" or the value "global". This value indicates whether the key-value pair sent in the request should be stored in the Local Store or the Global Store.

The algorithm begins by checking if type == "local". If this is the case, then the algorithm checks if the current node is the group’s leader (as elected by the Raft consensus protocol). If not, then the request is sent to the leader. Once the request reaches the leader, the request is forwarded to the Replication Manager of the group. If instead type == "global", then the request is forwarded to the group’s gateway node, which uses its Resource Finder to determine where the request should be processed.

Resource Finder

When a gateway node receives a request from the Placement Protocol, the gateway node invokes the Resource Finder running on it to determine which group should store the given key-value pair. Following the typical pattern employed by DHTs, the Resource Finder hashes the key, determines which group is responsible for keys with the resulting hash, and routes the request to that group’s corresponding gateway node. The receiving gateway node (also running the Resource Finder) then passes this request to the Replication Manager running on its associated group.

Replication Manager

Regardless of the Placement Protocol’s decision to store data globally, forwarding the request to the Resource Finder, or locally, sending the request directly to the group’s leader, the request eventually reaches the Replication Manager. This protocol runs on each node in the group, and is responsible for maintaining the group’s RSM. After receiving a request, the Replication Manager replicates the received key-value pair among the group’s nodes, using the specified storage method from the Storage module. Although the authors’ particular implementation uses etcd for the RSM, they mention that since each gateway node provide an abstraction over its group, different groups can use different implementations.

Results

The authors’ experiments were conducted by simulating clients making requests to a single group. Its worth mentioning that these experiments only use the Local Store and do not demonstrate the full functionality of EdgeKV. The authors note that they hope to do a more comprehensive evaluation including the Global Store at a later time. Each experiment consists of an edge group of 7 servers and a single client node. The client node simulates multiple users by running multiple threads. The hardware used was from the Grid'5000 testbed, and the Distem Network emulator was used to simulate latencies between the nodes.

To compare the performance of cloud-centric storage to that of EdgeKV on the edge, the authors conducted their experiments using two different latency settings. For the cloud setting, they emulated a 50 ms latency between the client and the group nodes. In the edge setting, they emulated a 5 ms latency between all nodes.

After running experiments with several different workloads (read heavy, write heavy, read only, and read latest), the authors found that the edge simulations outperformed the cloud simulation in terms of latency and throughput for all workloads. They also found that the throughput of both simulations scaled roughly linearly in the number of clients.

Takeaways

While the results presented by the authors are interesting, there are a few things that should be kept in mind. First, it is not entirely clear how well these simulations reflect real-world scenarios. For example, consensus protocols (and Raft especially) are known to perform poorly in unreliable networks. It certainly isn’t farfetched to assume these kinds of network conditions may occur in the edge computing environment, especially for the use case of autonomous driving that was mentioned in the paper. While the authors simulate the latency, they don’t account for these other factors that may be present in a realistic situation. Second, since the authors did not test the Global Store, it is unclear how effective EdgeKV is overall. More specifically, depending on the number of gateway nodes and their distance, lookups in the the Global Store may be more costly than simply querying the cloud. Third, while the authors distinguished the edge and cloud settings by emulating different latencies, they still use EdgeKV on both. It may be useful to see how EdgeKV running on the edge compares to the competing cloud-centric solutions.

Overall, this paper introduces many interesting ideas. The abstraction provided by the gateway nodes allows different groups of edge devices to implement different types of key-value stores. This is particulary useful in the sense that some groups may have devices constantly entering and leaving the group (such as mobile phones), while the devices in other groups may be mostly static (such as a group of security cameras). The first case would need to ensure that the key-value store’s implementation could tolerate the volatility of the group, while the implementation of the second case’s key-value store wouldn’t necessarily need to be concerned with this issue. Additionally, providing key-value stores on the edge without any centralized data center is an interesting direction. While DHTs have been around for decades, there are clearly some very interesting problems when moving this design onto the edge.

Review