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
  • Contribution
  • Definitions
  • Construction
  • Implementation
  • 负载均衡
  • P2P 系统
  • 数据库分片
  • 参考
  1. Papers We Love

Consistent Hashing and Random Trees (1997)

Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web*

论文作者的贡献主要包含两部分:Consistent Hashing 和 Random Trees。Consistent Hashing 主要用于解决分布式哈希表 (Distributed Hash Table, DHT) 的桶增减带来的重新哈希问题;Random Trees 主要用于分布式缓存中的热点问题,它利用了 Consistent Hashing。下文主要关注 Consistent Hashing。

Contribution

在分布式环境下,单台机器的负载有限,我们需要将请求散列到不同的机器上,利用更多的机器实现服务的横向扩容。这时候就需要 Hash Function,好的 Hash Function 能够帮我们均匀地分布到不同的机器上。但传统的 Hash Function 通常是静态的,桶的数量固定。在多台机器组成的服务中,每台机器就是一个桶,但机器在运行的过程中很可能出现崩溃,在请求数量波动较大时,需要动态地增减机器。如果每次桶的数量发生变化时都需要重新散列所有请求,可能造成多方面影响:

  • 来自于同一个用户的请求在桶发生变化时将被打到不同的节点,可能导致数据不一致 (考虑monotonic consistency)

  • 所有的 Client 都需要知道当前最新的 Hash Function 配置,在网络中传播这个配置需要时间

Consistent Hashing 的提出就是希望能够缓解/解决这个问题,使得每次桶数量发生变化时不需要重新散列桶内的所有元素,而是将受影响的数量控制在很小的范围内。

Definitions

作者从四个方面讨论了好的 Consistent Hash Function 应该满足的性质:

  • Balance:元素应当尽量均匀地分布到不同的桶内 (with high probability)

  • Monotonicity:当增加新的桶时,元素只可能从旧桶移动到新桶,而不可能从旧桶移动到其它旧桶

  • Spread:在不同的用户眼里,相同的元素可能被散列到不同的桶中,我们称之为不同的观点。Spread 要求总的观点数量必须有一个上限。好的 Consistent Hash Function 应当让 spread 尽量小。

  • Load:类似 spread,Load 性质是针对不同的用户,但它规定的是单个桶中不同元素数量的上限,即每个桶中的,至少有一个用户认为其中含有的,元素数量存在上限。好的 Consitent Hash Function 应当让这个上限尽量小。

Construction

作者提出一种构建好的 Consistent Hash Function 的方法:

假设我们有两个随机的函数 rBr_{B}rB​ 和 rIr_{I}rI​ :

  • rBr_{B}rB​将 buckets 映射到区间 [0,1][0, 1][0,1] 上

  • rIr_{I}rI​将 items 映射到区间 [0,1][0, 1][0,1] 上

那么一个好的 Consistent Hash Function 可以定义为 fV(i)=min(∣rB(b)−rI(i)∣)f_{V}(i) = min(|r_B(b) - r_{I}(i)|)fV​(i)=min(∣rB​(b)−rI​(i)∣) ,即将 item 放在距离它最近的 bucket 中。这里的 V 代表着不同的观点,由于观点数量会随着 buckets 的增减而增加,每个观点的内容会随着 buckets 的增减而变化,因此这个 Consistent Hash Function 并不是一个静态的、固定的函数。

这里还有一点,rBr_{B}rB​ 通常需要将每个 bucket 映射到 [0,1][0, 1][0,1]区间的多个点上。假设整个区间上的 bucket 数量上限为 CCC ,那么 rBr_{B}rB​ 需要将每个 bucket 映射到 klog⁡Ck\log{C}klogC 个点上,其中 kkk 为常数,且 rBr_{B}rB​ 在映射单个 bucket 的不同点时,是相互独立的。

接着论文证明了上述函数满足 Monotonicity、Balance、Spread 和 Load 四个特性,这里简要说明一下证明的直觉:

  • Monotonicity:新增 bucket 时,新的 bucket 会被映射到 klog⁡Ck\log{C}klogC 个随机的点上,而这些点周围的 items 可能会被新的 bucket 抢过来,因为新的 bucket 离它们更近,但绝不会出现 items 被旧的 bucket 抢走的情况,因此 Monotonicity 被满足。

  • Balance:因为每个 bucket 的 klog⁡Ck\log{C}klogC 个点会随机分布在 [0,1][0, 1][0,1] 上,因此每个 bucket 将管辖不超过 O(1)V\frac{O(1)}{V}VO(1)​ 长度的区间 (with high probability)。由于 items 会被随机地、均匀地分布在整个区间上,因此 Balance 被满足。

  • Spread:假设某个 item 被 rIr_{I}rI​映射到 [0,1][0, 1][0,1]上的某个点,那么每个观点 VVV 中,最接近 item 的 bucket 只有一个。由于 buckets 会被 rBr_{B}rB​随机、均匀地映射到整个区间,因此即使随着 buckets 数量的增减,观点的数量会增加,但可以想象,不可能所有新 bucket 对应的映射点都在 item 周围,位于它周围的 bucket 映射点数量应当有个上限。因此 Spread 被满足。

  • Load:类似 spread 的推理,把 item 和 bucket 位置对调即可。即对于每个 bucket 来说,映射到它附近的 items 数量应当有个上限。因此 Load 被满足。

Implementation

Consistent Hashing 在许多场景下都有应用,比如:

  • 负载均衡

  • P2P 系统

  • 数据库分片

  • ...

尽管场景很多,但它们对 DHT 的要求不一样:

负载均衡

在云原生环境下,为了保证服务的扩展性和可用性,通常会同时启动一个服务的多个实例。如何把不同的请求合理地反向代理到不同实例,是负载均衡器需要解决的问题。

为了保证服务的数据单调一致性,一些服务要求同一个用户的请求必须被路由到同一个实例。这时候就需要对用户的身份标识数据做一次哈希操作,找到固定的实例。但在云原生环境下,同一个服务的实例数量以及地址可能常常发生变化,为使得因实例变动影响到的用户数量最小,就需要使用 Consistent Hashing。

和其它场景不同,Consistent Hashing 在负载均衡场景下,实例数量发生变化时,实际上没有主动重新哈希已有数据的过程,因为它不需要保持对应关系数据。

实现思路

材料:哈希函数: H(x):string→[0,max]H(x):string \to [0, max]H(x):string→[0,max]

方案:将每个节点哈希到区间 [0,max][0, max][0,max] 上随机的 kkk 个点,将所有节点的所有哈希值排序后保存在一个数组 AAA 中。每次新来一个请求,就将请求的 ID 哈希到区间 [0, max] 上的某个点,然后利用二分查找找到比 k 大的最小点,后者对应的节点就是目标实例。

算法复杂度分析:

操作

时间复杂度

AddNode

DelNode

Get

实现示例

P2P 系统

Pastry

  • video

  • paper

数据库分片

(TODO)

参考

PreviousConsistency & ConsensusNextDynamic Hash Tables (1988)

Last updated 5 years ago

。

O(klog(n))O(klog(n))O(klog(n))
O(klog(n))O(klog(n))O(klog(n))
O(logkn)O(logkn)O(logkn)
stathat/consistent
Routing in Distributed Hash Tables | Anne-Marie Kermarrec
Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems
Consistent Hashing and Random Trees