open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  • 摘要
  • 简介
  • Linear Hashing
  • Spiral Storage
  • 其它
  • Linear Hashing vs. Consistent Hashing
  • 参考
  1. Papers We Love

Dynamic Hash Tables (1988)

本文对比 in-memory 版本的 Linear Hashing 和 Spiral Storage

PreviousConsistent Hashing and Random Trees (1997)NextLFU Implementation With O(1) Complexity (2010)

Last updated 5 years ago

摘要

Linear Hashing 和 Spiral Storage 是两种动态哈希算法。这两种算法最初都是为了优化外部存储 (secondary/external storage) 数据访问而设计的。本文将这两种算法引入到内存中,即键值数据可以一次性读入内存的场景,对比、分析二者之间,以及与其它动态哈希算法的性能。实验结果表明:Linear Hashing 的性能上要优于 Spiral Storage,实现难度上要小于 Spiral Storage。其它纳入对比范围的动态哈希算法包括 Unbalanced Binary Tree 以及支持周期性 rehashing 版本的 Double Hashing。Linear Hashing 的查询时间与 Double Hashing 相当,同时远远优于 Unbalanced Binary Tree,即使在 tree 很小的场景上也如此;在载入键值数据的表现上,三者相当。总体而言,Linear Hashing 是一个简单、高效的动态哈希算法,非常适用于键空间未知的场景。

简介

许多为外部文件存储而设计的动态哈希算法在过去的若干年中被提出,这些算法允许外部文件根据内部存储的纪录数量而优雅地扩大和缩小。在外部文件存储场景中,外部存储比内存读写慢很多,它的特点总结如下:

  • 按块读写数据,如 4096 字节为 1 块

  • 倾向于读写连续块

  • 倾向于批量读写

  • 在每一层都设有缓存来优化性能

  • 根据磁盘中数据块的读写次数来衡量程序的性能

Linear Hashing 和 Spiral Storage 在上述场景中都已被验证有效。本文将介绍如何将二者引入到 Internal Hash Table 场景中,在数学上分析其预期性能,并通过实验验证预期。从实验结论上看,两种方法对于 Internal Hash Table 、键 (key) 空间未知的场景同样有效。其中 Linear Hashing 更快且更容易实现。

所有 Hashing 技术都有一个特点:当负载提高时,基本操作的复杂度,如插入、查询、删除,也将提高。如果希望 Hash Table 的性能维持在一个可接受的下限之上,我们必须通过某种方式为其分配新的空间。传统的方案是创建一个新的、更大的哈希表,然后将所有数据重新哈希到新的哈希表上。动态哈希算法的不同之处在于,它允许哈希表逐渐扩大,每次增加一个桶。当新桶加入到寻址空间时,只需要重新哈希原来的一个桶即可,而不需要将所有数据全部重新哈希。

Linear Hashing

通常在 Hash 算法中需要一个 Hash Function,将输入参数转化成一个整数:

f:x→h(x)f: x \to h(x)f:x→h(x)
func bucket(hash uint) uint {
    m := hash & ((1<<i)-1)
    if m < n {
        return m
    } else {
        return m ^ (1<<(i-1))
    }
}

增加新桶的具体图形化实例请看论文原文。

Spiral Storage

在使用 Linear Hashing 时,查询、插入、删除的预期成本存在抖动。假如 Linear Hashing 使用的 Hash Function 能够均匀地将键散列到不同的桶上,那么发生分裂时,当前分裂的桶、新桶以及其它桶内的数据将出现不均匀的现象。如果我们能够刻意在散列分布上制造一些不均匀,使得即将分裂的桶是数据最多的桶,那么就有可能减少操作的预期成本。

基本思想如下图所示:

将数据更多地散列到位置靠前的桶内,分裂时直接将最前面的桶中的数据分裂到两个新的桶上。

一个典型的分布例子如下所示:

其它

Linear Hashing vs. Consistent Hashing

Linear Hashing 允许桶顺序地往后添加、往前删除,而 Consistent Hashing 允许按任意顺序添加和删除桶。二者的使用场景并不相同。

参考

  • papers

  • blogs

  • web

  • implementations

Linear Hashing 的核心思想在于不使用 h(x)h(x)h(x) 中的所有 bit 信息。当表较小时,使用较少的 bit 信息;当表较大时,使用较多的 bit 信息。在下文中我们假设:

nnn :桶的数量

iii :使用的 bit 位数

rrr :记录的数量

Linear Hashing 将使用 h(x)h(x)h(x) 的后 log2(n)log_2(n)log2​(n) 位的数据作为实际使用的值。举例如下,假设两个键 :wizard 和 witch 作为 xxx 输入到 Hash Function 中得到:

h(wizard)→11002,h(witch)→11112h(wizard) \to 1100_2 , h(witch) \to 1111_2h(wizard)→11002​,h(witch)→11112​

若此时 n=2n = 2n=2 ,那么最终 wizard 的 Hash 值为 0,witch 的为 1。如下图所示:

当表的负载到达一定程度后,需要增加新桶时,则将桶的数量 nnn 加 1;如果 n>2in > 2^in>2i ,则将使用的 bit 位数 iii 加 1。因此确定某个 Hash 值将对应到哪个桶的过程如下:

Linear hashing: A new tool for file and table addressing
Spiral Storage: Incrementally augmentable hash addressed storage
Hackthology: Linear Hashing
Hackthology: An in Memory Go Implementation of Linear Hashing
Hashing Tutorial
Wikipedia: Consistent Hashing
timtadh: linhash