LH*—a scalable, distributed data structure
LH*—a scalable, distributed data structure
复制标题
DOI：
10.1145/236711.236713
复制
发表时间：
1996-12
期刊：
影响因子：
--
通讯作者：
W. Litwin;Marie-Anne Neimat;Donovan A. Schneider
中科院分区：
文献类型：
--
作者：
W. Litwin;Marie-Anne Neimat;Donovan A. Schneider
我们提出了一个可扩展的分布式数据结构LH*。LH*将线性哈希（LH）推广到分布式RAM和磁盘文件。LH*文件可以从具有主键的记录或具有oid的对象中创建，这些记录由任意数量的分布式和自治客户机提供。它不需要一个中心目录，并且通过每次拆分一个存储桶，可以优雅地扩展到几乎任意数量的服务器。无论文件大小如何，每次随机插入的消息数通常为1，在最坏的情况下为3。一般情况下，每个键搜索的消息数为2，最坏情况下为4。文件支持并行操作，例如哈希连接和扫描。在M个桶的文件上执行并行操作最多需要2M + 1个消息，并且需要1到O（log2）个消息轮。我们首先描述基本的LH*方案，其中协调器站点管理桶分割，并在每次发生碰撞时分割桶。我们表明，无论文件大小和桶容量如何，LH*文件的平均负载系数为65%-70%。然后，我们使用负载控制来增强方案，不需要额外的消息开销。然后平均负载系数增加到80-95%。这些值与LH大致相同，但LH*的负载系数变化更大。我们将定义没有协调器的LH*方案。我们展示了插入和搜索成本与基本方案相同。拆分成本平均会降低，但会变得更加多变，因为需要级联拆分来防止文件过载。接下来，我们将简要描述拆分策略的两种变体，它们使用并行拆分和预拆分，可以提高高性能应用程序的性能。总之，我们表明LH*文件可以有效地扩展到比单站点文件大几个数量级的文件。驻留在主存中的LH*文件也可能比单站点磁盘文件快得多。最后，LH*文件可能比任何具有集中式目录的分布式文件、静态并行文件或分布式哈希文件都更高效。
We present a scalable distributed data structure called LH*. LH* generalizes Linear Hashing (LH) to distributed RAM and disk files. An LH* file can be created from records with primary keys, or objects with OIDs, provided by any number of distributed and autonomous clients. It does not require a central directory, and grows gracefully, through splits of one bucket at a time, to virtually any number of servers. The number of messages per random insertion is one in general, and three in the worst case, regardless of the file size. The number of messages per key search is two in general, and four in the worst case. The file supports parallel operations, e.g., hash joins and scans. Performing a parallel operation on a file of M buckets costs at most 2M + 1 messages, and between 1 and O(log2 Mrounds of messages. We first describle the basic LH* scheme where a coordinator site manages abucket splits, and splits a bucket every time a collision occurs. We show that the average load factor of an LH* file is 65%–70% regardless of file size, and bucket capacity. We then enhance the scheme with load control, performed at no additional message cost. The average load factor then increases to 80–95%. These values are about that of LH, but the load factor for LH* varies more. We nest define LH* schemes without a coordinator. We show that insert and search costs are the same as for the basic scheme. The splitting cost decreases on the average, but becomes more variable, as cascading splits are needed to prevent file overload. Next, we briefly describe two variants of splitting policy, using parallel splits and presplitting that should enhance performance for high-performance applications. All together, we show that LH* files can efficiently scale to files that are orders of magnitude larger in size than single-site files. LH* files that reside in main memory may also be much faster than single-site disk files. Finally, LH* files can be more efficient than any distributed file with a centralized directory, or a static parallel or distributed hash file.