Smash: Flexible, Fast, and Resource-Efficient Placement and Lookup of Distributed Storage

2.1. Design objectives of smash.  We consider a large-scale object storage system, in which each object is uniquely identified by its ID. The objects are stored in storage servers called nodes, which may contain one or more storage devices, such as SSD or HDD. Each node also carries some limited computation, DRAM, and network resources. A block is a sequence of bytes on a node that is read or written at a time. The storage location of an object $i$ can thus be specified as $<N_i,B_i>$, where $N_i$ is the node’s network address and $B_i$ is the sequence number of the block that stores the object. Following Ceph, the block size in Smash is 4MB; however, the size can be configured freely. Each block may store one or more objects. If a file is larger than 4MB, it is split into multiple objects. When a node writes objects to its disk, it keeps writing objects to a block until the block is full. Each block contains a header, including the IDs of its objects and their location offsets. The objects are stored from the end of each block so the header and objects can grow toward the middle. Clients are authorized users to access the objects, which may or may not be in the same cluster of the storage system.

The design objectives of Smash include:

• Full placement flexibility. Smash must support the placement of objects to arbitrary nodes, based on the application requirements for implementing fault tolerance, load balancing, data locality, and exploiting parallelism.

• Low DRAM cost. Smash needs to minimize metadata storage overheads and DRAM footprint to provide a low total cost of ownership (TCO).

• Low latency. Smash needs to perform object operations such as put, get, and delete objects as well as adding and removing storage nodes with low latency.

• High scalability. When the system size increases, the extra resources to support object placement and the latency to perform lookup should increase at most linearly.

To our knowledge, there is no prior work that can achieve all of these goals.

Placement flexibility is important. There are various data-placement requirements of storage systems, depending on the applications of the data and the priorities of placement policies. We just name a few here:

• Failure tolerance. Some applications may require the replicas of some data to be in different failure domains to improve system robustness.

• Parallelism. Some applications may require the objects belonging to a big file or a set of files to be stored at different servers to improve accessing parallelism.

• Load balance. Placing data in different nodes such that no node is overwhelmed by requests for popular data is an important task in storage systems.²¹ This requirement is particularly crucial for nodes with heterogeneous capacities and speeds because slow devices will become the bottleneck of overall performance

• Data placement. Some workloads require special placement of data to optimize performance, such as those of high-performance computing.⁴ Hash-based and hybrid methods cannot enforce flexible placement and hence fail to guarantee fault tolerance. They also cause further problems, such as a high bandwidth cost for data migration under node addition and removal.

Table 1 shows the high bandwidth cost of adding one node in CRUSH—from 10TB to 80TB—causing traffic spikes while introducing hardware costs and network overprovisioning. Our results are consistent with the reported results in Wang et al.¹⁹ Smash can take any object-to-node placement as the input and does not need data migration under node dynamics.

RAM cost and scalability. Every storage system requires DRAM space to support data placement and lookups. Even in hashing-based methods, where clients use hash functions to compute object locations, DRAM resource is still necessary on every node for local indices to support ID to block address mappings. The proportion of space cost to store the IDs (or keys in some context) usually contributes to the majority of the DRAM cost, for example, greater than 80%.¹⁷ The reason is the sizes of IDs are usually much longer than those of locations—Ceph²⁰ uses 16-byte IDs, and Twitter’s average key length is around 40 bytes.²⁴ It could cost hundreds of GBs of DRAM for 10 billion ID-location mappings, and the majority proportion is used to store the IDs. For the methods that use directories, the directory and metadata servers introduce large DRAM overheads that need to be hosted by specific servers to support client queries and data management. Smash requires a number of maintenance units that can be run on either a server or storage nodes. Different from a large directory, most maintenance units can be stored on SSD because they are rarely queried or changed. Only one maintenance unit (a few hundred MBs) needs to be run in DRAM. Hence, the DRAM cost of Smash is scalable to support an extremely large number of storage objects.

2.2. Ludo hashing.  Allowing fully flexible placement means an object can be placed onto an arbitrary node. Hence it is essential that the system should support querying the locations of arbitrary objects from clients and remember all object-location mappings in DRAM for fast response. The biggest challenge is the DRAM cost to store the massive number of ID-to-location mappings. There is no way to avoid storing locations because they are necessary results for lookups. However, we argue that there is a way to avoid storing IDs, which contribute to a majority of the memory cost of storing ID-to-location mappings.

To enable flexibility while minimizing storage overheads, we use Ludo hashing¹⁷ and adapt it for serving large-scale storage systems. Ludo is not a hash function, but a key-value lookup engine: For any given key-value mapping, Ludo can build a space-compact data structure (called the lookup structure) to return the corresponding values when keys are queried. The Ludo lookup structure does not store the keys themselves and reduces the space cost by up to 90%, compared to state-of-the-art hash tables such as (4,2)-Cuckoo.¹⁴

The lookup structure. The lookup structure returns the value given a key—in our context key-value is ID-location. All key-value mappings are specified by the user when constructing the lookup structure, and there is no restriction on the key-to-value mapping. As shown in Figure 2, the lookup structure consists of two stages. The first stage is a classifier that returns a 1-bit value $b\in \{0,1\}$ by querying the key $i$. The data structure of the classifier is called a Bloomier filter.²⁵ Ludo selects one of two hash functions $h_0\left(\right)$ and $h_1\left(\right)$ based on the result of Bloomier filter $b$, where $b=0$ or 1 because we have two independent hashing functions. The result $h_b\left(i\right)$ maps to a bucket (row) of a table shown on the right of Figure 2. The bucket includes a seed value $s$ and four slots, and four elements are hashed into these four slots without collision by a seed computed by brute force. Ludo computes a hash function by including the seed value $s$ and $i$, $H_s\left(i\right)$, to produce a 2-bit result ranging from 0 to 3. The slot with the resulting number will be chosen and the value stored in the slot is the returned value—the object location in our context. The lookup structure is very compact and only introduces a cost of $3.76+1.05l$ bit per key-value pair where $l$ is the size of each value. The query time complexity is $O(\mathrm{1)}$.

The maintenance structure. The maintenance structure is used to construct the lookup structure. As shown in Figure 3, it uses a (4,2)-Cuckoo hash table¹⁴ to store all key-value mappings. Each key-value pair is stored in one of the two buckets determined by the hash result of $h_0\left(i_x\right)$ and $h_1\left(i_x\right)$. Each bucket contains four slots and a pair is stored in one of them. For each bucket, Ludo finds a seed $s$ using brute force, such that all results of $H_s\left(i\right)$ for the four keys in the bucket are different. Each seed is 5 bits long, and a very small portion of seeds longer than 5 bits are addressed in an overflowing table. The second stage of the lookup structure is a copy of this table with all keys being removed. Using a seed for each bucket is the key idea to perform lookups in the table without storing the keys, because the seed guarantees there is no collision for IDs mapped to the same bucket. The first stage of the lookup table is a classifier that maps each key to either 0 or 1, depending on which bucket each key is stored in. The time complexity of constructing a lookup structure is $O\left(n\right)$ for $n$ items in expectation and that of inserting, deleting, and changing one item is $O\left(1\right)$ in expectation.

4.1. System overview.  Smash consists of three main software components: a monitor, a number of maintenance units (an active one running in the DRAM and others stored in SSD), and a number of lookup units located in the DRAM of storage nodes. Smash separates the tasks required to manage and look up objects into these three components to enable flexible placement without requiring a large directory. In particular, the directory-less, decentralized lookup units find objects without storing the keys that contribute to the majority DRAM cost. Lookup units provide flexibility because objects can be stored at arbitrary nodes. We leverage Ludo to scale MPH to a large number of objects per node. The task of the maintenance units is to update the lookup units. In most cases, only one maintenance unit should be run in DRAM, and the others can be stored in SSD. The whole system costs very little resources: It requires one server to run the monitor and active maintenance unit and store the other maintenance units. The lookup units run in the DRAM of the storage nodes.

Suppose a large storage system includes $n=10$ thousand nodes, $k=10$ thousand shards, and each shard includes $\alpha =40$ million objects. Based on our analysis (presented later), the monitor costs 391MB, a maintenance unit costs 1.5GB, and a lookup unit costs 680MB. In this setting, a server with 4GB DRAM is sufficient to run the monitor and the maintenance units and each node only needs less than 1GB DRAM to run the lookup units.

Monitor. The monitor provides the following functions. It maintains the disk availability on all nodes at a coarse-grained level. Each node’s space is divided into bulks, each consisting of 1GB data. A bulk is further divided into blocks and each block is 4MB. A block stores one or more objects. These sizes may vary for different applications. Bulk-level management enables the monitor to track whether each bulk has been assigned to an existing maintenance unit, though it does not track whether a block has been used or not. Each maintenance unit performs block-level management, hence the monitor maintains a bitmap containing one bit for each bulk in the system and each bit representing whether a bulk has been assigned.

The monitor also tracks the resource load of every node, including disk space, network bandwidth, DRAM, and CPU. The granularity of these loads is user-specified.

Lastly, the monitor includes a load-balancing function, which can stop assigning bulks to nodes that are about to reach a high load. Therefore, it receives information about the top-$k$ most popular objects from high-load nodes, enabling load-balancing of the most frequently accessed objects among nodes. Any existing load-balancing algorithm, such as Won You et al.,²² is compatible with Smash because the placement is fully flexible.

Maintenance units. Maintenance units are responsible for constructing and updating lookup units, as well as for providing fine-grained storage resource management at the block level. Each maintenance unit is responsible for a limited number of objects, and the set of these objects is called a shard. When Smash enables a maintenance unit, it is resident in DRAM of one of the servers accepting new put requests. Get requests are directly served by the lookup units and require no maintenance-unit interaction, and Delete requests do not need to be processed by the maintenance unit. The maintenance unit determines the object-placement location (storage node) by optimizing the application requirements considering fault tolerance regions, load balancing goals, parallelism opportunities, and workload-specific requirements. The detailed optimizing algorithm is out of the scope of this paper. However, Smash can be adapted to support any algorithm. Next, the maintenance unit determines the bulk to house the object on the particular storage node. Therefore, it either reuses an existing bulk that has free storage capacity, or it claims a new bulk on that node from the monitor. The maintenance unit then tracks the storage capacity available within the bulk and stores the newly put object to an available block. It then adds the ID-location tuple $<i,lo{c}_i>$ to the Cuckoo table, which is stored as part of the maintenance unit. Note that $lo{c}_i$ is a tuple including both IP and block addresses. It constructs the lookup unit of all $<i,lo{c}_i>$ tuples and deploys the lookup unit to a node with sufficient DRAM resources. The lookup unit will be updated whenever additional objects are put into the system. When the number of objects within an active maintenance unit reaches a threshold, the maintenance unit is stored to the SSD and it becomes immutable (inactive). An inactive maintenance unit only needs to be accessed in the case of rare situations, such as large-scale object relocation. Performing put, get, modify, and delete operations no longer requires the access of an inactive maintenance unit. Hence, only one active maintenance unit is running in the DRAM of each server at a time.

Both the monitor and maintenance units are small enough to be hosted on different storage nodes as long as the nodes have available DRAM space. Replicated monitors and maintenance units can also be deployed in this way to achieve fault tolerance. For this, replicated copies of each object are stored in multiple nodes. The ID-location mapping is then extended to $<i,lo{c}_1,lo{c}_2,lo{c}_3>$ for three copies in three different locations.

Lookup units. Lookup units respond to clients’ object $\mathrm{get}$ and $\mathrm{modify}$ requests. Every lookup unit is resident in the DRAM of a storage node. It returns the physical location $lo{c}_i=<I{P}_i,bloc{k}_i>$ of the requested object $i$ and forwards the request to the corresponding node. For fault tolerance, replicated lookup units can run on multiple nodes.

Storage nodes. The storage space of a node is divided into blocks. When receiving a $\mathrm{get}$ request forwarded by one of the lookup units, the storage node returns the corresponding data to the client based on the block address $bloc{k}_i$. When receiving a $\mathrm{modify}$ request, the storage node sends a message to the client directly, indicating the update was successful. Storage nodes also respond to $\mathrm{put}$, $\mathrm{relocate}$, or $\mathrm{delete}$ requests to objects. For fault-tolerance, replicated copies of an object can be stored in multiple nodes.

Clients. A client may or may not be in the same datacenter with the storage. For example, the clients of the object database of a social network are the Web servers in the same cloud. Smash provides a client library for accessing the object storage system. Like the interfaces in existing key-value stores, the client can request the lookup units or maintenance units to $\mathrm{put}$, $\mathrm{get}$, $\mathrm{relocate}$, or $\mathrm{delete}$ objects.

4.2. System initialization.  Objects and nodes can be incrementally deployed to a system running Smash. The number of inactive maintenance units and lookup units depends on system size. The monitor and all maintenance units can be hosted by a server whose resources are not necessarily rich, possibly with one or two backup servers. The lookup units are hosted by the storage nodes with very little DRAM cost. When a storage node joins, the monitor notifies the active maintenance unit about the node’s IP address and may assign the node’s bulks to the active maintenance unit.

Smash sets the maximum number of objects per shard as $\alpha$. Each maintenance unit then contains a Cuckoo hash table with $\lceil \frac{1}{0.95\times 4}\alpha \rceil =\lceil 0.263\alpha \rceil$ buckets with each bucket containing four slots. The reason behind this is that the total number of slots is then $\frac{1}{0.95}\alpha$, which can store all $\alpha$ ID-location pairs with the table’s load factor up to 95%. According to theoretical studies,^5,9 insertions to a Cuckoo hash table of load factor up to 98.03% are asymptotically almost surely (a.a.s) successful. We use 95% to avoid hitting the tight threshold. The lookup unit has the same number of buckets.

Each client stores the mappings of every shard ID $s_i$ to the IPs of all nodes that host the lookup unit of shard $s_i$, which takes a few MBs. Storing IPs of the nodes is also necessary for all existing object stores such as Ceph⁷ and MapX.¹⁹

4.3. Operations of smash.  Smash supports operations to put, get, modify, relocate, and delete objects. We describe the operations in the following. For ease of presentation and illustration, we first show the operations on one copy of each object. We then extend the operations with replicated copies for fault-tolerance.

$\mathrm{Put}$. Figure 5a shows the steps of putting a new object $i$. The client registers the new object to the active maintenance unit (Step 1). The maintenance unit determines the location $lo{c}_i=<I{P}_i,bloc{k}_i>$ to store the object, based on the application requirements and node availability. It then tells the client the tuple $<i,lo{c}_i>$ (Step 2). The maintenance unit updates the lookup unit and tells the update to the node that hosts the lookup unit (Step 3). This update takes $O\left(1\right)$ time and $O\left(1\right)$ communication bits in expectation.¹⁷ At the same time, the client sends the object $i$ to $I{P}_i$, the IP of the node to store $i$. The node $I{P}_i$ will store $i$ to block address $bloc{k}_i$ (Step 3).

$\mathrm{Get}$. Figure 5b shows the steps of getting an object $i$. The client finds the shard ID $k$ from the ID $i$ of the object it wants to get. Recall that each client maintains the mapping of every shard ID $k$ to the IPs of nodes that host the lookup unit of shard $k$. It then sends a lookup request of $i$ to the lookup unit (Step 1). The lookup unit returns $lo{c}_i$ by looking up the ID $i$. Then, it forwards the lookup request to the node $I{P}_i$ that stores $i$ along with the block address $bloc{k}_i$ included in $lo{c}_i$ (Step 2). The node $I{P}_i$ gets the object from $bloc{k}_i$ and sends it to the client (Step 3).

$\mathrm{Delete}$. The process of deleting an object $i$ can reuse Steps 1 and 2 of $\mathrm{Get}$. The difference is that in Step 3, the node that stores $i$ just deletes $i$ and sends a confirmation message to the client. Note: This process does not need the involvement of the maintenance unit, and the lookup unit does not need to change. In the lookup unit, if $i$ has been removed and never been queried, the correctness of the lookup unit of MPH will not be affected. The maintenance unit needs to guarantee that an ID will not be assigned twice to different objects, which can be easily achieved.

$\mathrm{Modify}$. The process of modifying an object $i$ can reuse Step 1 of $\mathrm{Get}$. The difference is that in Step 2, when the lookup unit gets $lo{c}_i$, it does not forward the request to the node $I{P}_i$ but sends $lo{c}_i$ back to the client. Hence, the client can directly contact the node $I{P}_i$ to modify the content of $i$. This process does not need the involvement of the maintenance unit because the storage location of $i$ does not change. Note that a “$\mathrm{Modify}$” in Smash and an “update” in Ludo have completely different meanings. An “update” in Ludo means inserting, deleting, or changing a key-value pair. The correctness of insertion cannot be guaranteed without an active maintenance unit. A “$\mathrm{Modify}$” in Smash changes the content of an object. The key-value pair of this object from Ludo’s perspective is the ID-location pair, which does not change for such an update. Without an active maintenance unit, an update of Smash is still always successful.

$\mathrm{Relocate}$. A relocation happens rarely compared to the above operations. Each relocation is initiated by the monitor rather than the clients. It happens when the monitor wants to further optimize the placements based on application requirements, such as locality and load balance. Note that when each object is placed for the first time, its location is already optimized by the maintenance unit. Hence, relocation may happen once during a long time period (such as several days). A relocation might change the maintenance and lookup units in multiple shards and, hence, some inactive maintenance units may need to be loaded to DRAM and updated at this point. Since there are fewer relocations happening during a long time period, the monitor can process relevant objects in one shard after another. Since the latency of relocation is not sensitive, changing inactive maintenance units will not introduce much DRAM cost. This is the only case where an inactive maintenance unit needs to change.

4.4. Management elasticity.  So far, we assume each shard includes up to $\alpha$ objects, and $\alpha$ is also the number of objects that a standard node can store. For example, when the storage capacity of a node is 16TB and each object is 100KB, $\alpha =160$ million. Each shard has one maintenance unit, constructing one lookup unit that is responsible for the $\alpha$ objects. So, in expectation, each node will host one lookup unit.

In practice, node capacities may be heterogeneous and $\alpha$ can be any value, as objects of the same shard can spread across different storage nodes. For a smaller $\alpha$, each lookup unit costs smaller memory, hence we can allocate lookup units to nodes with available DRAM resources, with finer-grained management. However, smaller $\alpha$ also causes longer shard IDs and, hence, more bits in object IDs should be used for shard IDs, which indirectly increases the cost of maintenance units.

In addition, the maintenance unit of a shard can further make $\beta$ sub-shards and construct a lookup unit for each sub-shard. Which sub-shard an object belongs to can be determined by hashing the object ID.

5.1. Methodology.  Hardware. The testbed consists of eight servers from a public cloud: CloudLab.⁸ Each server is equipped with two Intel E5-2630 v3 8-core CPUs at 2.40GHz, 128GB ECC Memory, one Intel DC S3500 480GB 6G SATA SSDs, and a dual-port Intel X520-DA2 10Gb NIC. These machines run Ubuntu 18.04 LTS with Linux kernel 4.15. In fact, Smash can run on much cheaper nodes with weaker resources.

Testbed configuration. We denote the eight servers as $S_0,S_1,..,S_6,S_7$. $S_0$ serves as the server to host the monitor and maintenance units, $S_1,..,S_6$ serve as storage nodes, and $S_7$ serves as clients. Smash places the lookup units evenly on the six storage nodes, although in the design there is no limit to the number of lookup units running simultaneously on each storage node as long as resources permit. To test Ceph and MapX, we use $S_0$ as the administrator and monitor of the system, which monitors the nodes’ status. We use ceph-deploy to build the testing system first. For MapX, we separate the storage nodes $\{S_1,S_2,S_3\}$ and $\{S_4,S_5,S_6\}$ into two different layers. The number of placement groups is set to 128 as recommended in.¹⁹ For Ceph and MapX, we use the C++ interfaces released in librados⁷ to implement the operations, including putting, getting, updating, and deleting objects. In addition, we set the number of copies of each object in each storage system to 3. We set that each object ID has 320 bits and a shard ID has 20 bits unless otherwise stated.

Workloads. We use both uniform and Zipfian distribution object-query workloads, and the Zipfian workload is modeled after real-world access patterns observed at Facebook.² The queried objects in uniform workload are generated uniformly randomly without any bias. Correspondingly, the Zipfian workload is generated with a biased parameter $\alpha$ ($<$1), containing a few popular objects. In the evaluations, the client ($S_7$) will generate and store 10,000 objects first and put them to the storage nodes. In the following evaluations, each operation (such as $\mathrm{Put}$ and $\mathrm{Get}$) is conducted at least 1,000 times with different objects in different locations. In addition, half of the objects are with each of the two layers with different timestamps in MapX.

5.2. DRAM cost.  For Ceph and MapX, we show the DRAM cost of the local lookup engine in Ceph/MapX with the assumption that storage nodes only have DRAM as the fast-accessing memory layer. We also compare Smash with SmashSimple. We first compare the DRAM cost per node by varying the average size of objects—and hence the number of objects per node. Each node has a storage capacity of 4TB and the key length is 40 Bytes according to the results in Atikoglu et al.² Object size varies from 16KB to 1MB, because in practical key-value applications, such as those from Facebook and Twitter,^2,24 the sizes of most values are much smaller than 1MB, where around 30% of the values in the ETC workload of Facebook are smaller than 4KB.² Smash can even support smaller value sizes than 16KB, but other methods could exhaust DRAM. As shown in Figure 6, compared to Smash-Simple, Smash can reduce the DRAM cost per node by 80%. Specifically, when the value size is 16KB, the DRAM cost is reduced from more than 20GB to less than 5GB per node. When the value size is 64KB, the DRAM cost is reduced from 4.8GB to 1.1GB per node. The DRAM cost of Ceph is also significantly higher than that of Smash.

5.3. Latency of storage operations.  In this subsection, we show testbed evaluation results of storage operation latency, including $\mathrm{Put}$ and $\mathrm{Get}$ under different distribution workloads. We first put 10,000 objects in the cluster, and then the client issues 4,000 operations for putting/getting/modifying/deleting objects with a replication factor of 3. In addition, to demonstrate that multiple lookup units can run simultaneously on different machines together in Smash, we show the performance of Smash running one and two lookup units respectively.

$\mathrm{Get}$. Figure 7 shows the CDF of $\mathrm{Get}$ latency under the uniform (Figure 7a) and Zipfian (Figure 7b) workloads. Again, Smash achieves the smallest average and tail latency compared to Ceph and MapX, although all of them are quite fast. Ceph and MapX have similar $\mathrm{Get}$ latency. Their latency below the 30^th percentile is smaller than that of Smash. Note that in practice, the latency of all methods could be shorter due to DRAM caching, but we do not enable caching in this set of experiments. However, Ceph and MapX have a relatively long tail latency. The main reason is the iterations of calling the ‘select’ function of CRUSH. In Smash, the trailing delay shown in the picture is mainly caused by the fallback table of the lookup unit structure. The results for SmashSimple are similar to those of Smash, with SmashSimple slightly faster than Smash in high-percentile results.

$\mathrm{Put}$. Figure 8 shows the cumulative distribution (CDF) of $\mathrm{Put}$ latency for these three methods under the uniform workload.