Provably Good Randomized Strategies for Data Placement in Distributed Key-Value Stores
Provably Good Randomized Strategies for Data Placement in Distributed Key-Value Stores
复制标题
DOI：
10.1145/3572848.3577501
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Zhe Wang;Jinhao Zhao;Kunal Agrawal;Heyu Liu;Meng Xu;Jing Li
中科院分区：
文献类型：
--
作者：
Zhe Wang;Jinhao Zhao;Kunal Agrawal;Heyu Liu;Meng Xu;Jing Li
分布式存储系统在云，数据库和文件系统中广泛使用。这些系统在多个服务器上存储大量数据。当访问数据的请求进来时，将其路由到适当的服务器，排队并最终处理。如果服务器的队列已满，则可能会拒绝请求。因此，在设计将数据分配给服务器的算法时，一个重要的挑战是，请求模式可能是不平衡，不可预测的，并且可能会随着时间而变化。如果某些服务器得到了很大一部分请求，则将其重载，从而导致许多拒绝。在本文中，我们在对抗性假设下从理论上分析了这个问题。特别是，我们假设请求顺序是由对抗过程生成的，以最大程度地提高拒绝的数量，并根据拒绝的请求的分数来分析各种算法策略的性能。我们表明，没有确定性策略无法表现良好。另一方面，一种简单的随机策略可以确保最多持续不断的请求在预期中被拒绝。我们还表明，如果要拒绝一个很小的部分（1/m，m是服务器数），则至关重要。我们设计了一种随机化和数据传输的策略，以通过速度增强来实现此性能。最后，我们进行实验，并表明我们的算法在实践中表现良好。
Distributed storage systems are used widely in clouds, databases, and file systems. These systems store a large amount of data across multiple servers. When a request to access data comes in, it is routed to the appropriate server, queued, and eventually processed. If the server's queue is full, then requests may be rejected. Thus, one important challenge when designing the algorithm for allocating data to servers is the fact that the request pattern may be unbalanced, unpredictable, and may change over time. If some servers get a large fraction of the requests, they are overloaded, leading to many rejects. In this paper, we analyze this problem theoretically under adversarial assumptions. In particular, we assume that the request sequence is generated by an adversarial process to maximize the number of rejects and analyze the performance of various algorithmic strategies in terms of the fraction of the requests rejected. We show that no deterministic strategy can perform well. On the other hand, a simple randomized strategy guarantees that at most a constant fraction of requests are rejected in expectation. We also show that moving data to load balance is essential if we want to reject a very small fraction (1/m where m is the number of servers) of requests. We design a strategy with randomization and data transfer to achieve this performance with speed augmentation. Finally, we conduct experiments and show that our algorithms perform well in practice.