1/**
2 * Assigns string inputs to nodes with weighted consistent hashing.
3 *
4 * A hash ring minimizes remapping when nodes are added, removed, or reweighted.
5 * This makes it useful for routing requests, partitioning keys, and
6 * distributing shards across service instances or storage backends. This module
7 * can create rings, add or remove nodes by `PrimaryKey`, route an input string
8 * to a node, and compute shard assignments.
9 *
10 * @since 4.0.0
11 */
12import { dual } from "./Function.ts"
13import * as Hash from "./Hash.ts"
14import { PipeInspectableProto } from "./internal/core.ts"
15import * as Count from "./internal/count.ts"
16import * as Iterable from "./Iterable.ts"
17import type { Pipeable } from "./Pipeable.ts"
18import { hasProperty } from "./Predicate.ts"
19import * as PrimaryKey from "./PrimaryKey.ts"
20
21const TypeId = "~effect/HashRing" as const
22
23/**
24 * A weighted consistent-hashing ring for assigning inputs to nodes with stable
25 * remapping as nodes are added or removed.
26 *
27 * **When to use**
28 *
29 * Use to maintain a mutable weighted hash ring for routing keys or shards to
30 * nodes identified by `PrimaryKey`.
31 *
32 * **Details**
33 *
34 * Nodes are identified by their `PrimaryKey` value and can be iterated from the
35 * ring.
36 *
37 * @category models
38 * @since 3.19.0
39 */
40export interface HashRing<A extends PrimaryKey.PrimaryKey> extends Pipeable, Iterable<A> {
41 readonly [TypeId]: typeof TypeId
42 readonly baseWeight: number
43 totalWeightCache: number
44 readonly nodes: Map<string, [node: A, weight: number]>
45 ring: Array<[hash: number, node: string]>
46}
47
48/**
49 * Checks whether a value is a `HashRing`.
50 *
51 * **When to use**
52 *
53 * Use to narrow an `unknown` value before treating it as a `HashRing`, such as
54 * values crossing an untyped boundary.
55 *
56 * **Details**
57 *
58 * The guard checks for the module's internal `TypeId` property and narrows to
59 * `HashRing<any>`.
60 *
61 * **Gotchas**
62 *
63 * This is a structural type-id check; it does not validate the ring's `nodes`,
64 * `ring`, or weight state.
65 *
66 * @see {@link HashRing} for the type narrowed by this guard
67 * @see {@link make} for creating an empty `HashRing`
68 *
69 * @category guards
70 * @since 3.19.0
71 */
72export const isHashRing = (u: unknown): u is HashRing<any> => hasProperty(u, TypeId)
73
74/**
75 * Creates an empty `HashRing`.
76 *
77 * **When to use**
78 *
79 * Use to create an empty weighted consistent-hashing ring with the default or
80 * custom virtual-point density.
81 *
82 * **Details**
83 *
84 * `baseWeight` controls how many virtual points are added for a node with
85 * weight `1`; it defaults to `128` and is clamped to at least `1`.
86 *
87 * @see {@link add} for registering one node after creation
88 * @see {@link addMany} for registering several nodes after creation
89 *
90 * @category constructors
91 * @since 3.19.0
92 */
93export const make = <A extends PrimaryKey.PrimaryKey>(options?: {
94 readonly baseWeight?: number | undefined
95}): HashRing<A> => {
96 const self = Object.create(Proto)
97 self.baseWeight = Math.max(options?.baseWeight ?? 128, 1)
98 self.totalWeightCache = 0
99 self.nodes = new Map()
100 self.ring = []
101 return self
102}
103
104const Proto = {
105 ...PipeInspectableProto,
106 [TypeId]: TypeId,
107 [Symbol.iterator]<A extends PrimaryKey.PrimaryKey>(this: HashRing<A>): Iterator<A> {
108 return Iterable.map(this.nodes.values(), ([n]) => n)[Symbol.iterator]()
109 },
110 toJSON(this: HashRing<any>) {
111 return {
112 _id: "HashRing",
113 baseWeight: this.baseWeight,
114 nodes: this.ring.map(([, n]) => this.nodes.get(n)![0])
115 }
116 }
117}
118
119/**
120 * Adds new nodes to the ring. If a node already exists in the ring, it
121 * will be updated. For example, you can use this to update the node's weight.
122 *
123 * **When to use**
124 *
125 * Use to register or update several nodes in a `HashRing` at the same weight.
126 *
127 * @category combinators
128 * @since 3.19.0
129 */
130export const addMany: {
131 <A extends PrimaryKey.PrimaryKey>(nodes: Iterable<A>, options?: {
132 readonly weight?: number | undefined
133 }): (self: HashRing<A>) => HashRing<A>
134 <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, nodes: Iterable<A>, options?: {
135 readonly weight?: number | undefined
136 }): HashRing<A>
137} = dual(
138 (args) => isHashRing(args[0]),
139 <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, nodes: Iterable<A>, options?: {
140 readonly weight?: number | undefined
141 }): HashRing<A> => {
142 const weight = Math.max(options?.weight ?? 1, 0.1)
143 const keys: Array<string> = []
144 let toRemove: Set<string> | undefined
145 for (const node of nodes) {
146 const key = PrimaryKey.value(node)
147 const entry = self.nodes.get(key)
148 if (entry) {
149 entry[0] = node
150 if (entry[1] === weight) continue
151 toRemove ??= new Set()
152 toRemove.add(key)
153 entry[1] = weight
154 } else {
155 self.nodes.set(key, [node, weight])
156 }
157 keys.push(key)
158 }
159 if (toRemove) {
160 self.ring = self.ring.filter(([, n]) => !toRemove.has(n))
161 }
162 addNodesToRing(self, keys, Math.round(weight * self.baseWeight))
163 updateTotalWeight(self)
164 return self
165 }
166)
167
168function addNodesToRing<A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, keys: Array<string>, weight: number) {
169 for (let i = weight; i > 0; i--) {
170 for (let j = 0; j < keys.length; j++) {
171 const key = keys[j]
172 self.ring.push([
173 Hash.string(`${key}:${i}`),
174 key
175 ])
176 }
177 }
178 // Break hash ties by node key to avoid insertion-order dependence.
179 self.ring.sort((a, b) => a[0] - b[0] || (a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0))
180}
181
182// Sum in key order to avoid history-dependent floating-point rounding.
183function updateTotalWeight<A extends PrimaryKey.PrimaryKey>(self: HashRing<A>) {
184 const keys = Array.from(self.nodes.keys()).sort()
185 let total = 0
186 for (let i = 0; i < keys.length; i++) {
187 total += self.nodes.get(keys[i])![1]
188 }
189 self.totalWeightCache = total
190}
191
192/**
193 * Adds a new node to the ring. If the node already exists in the ring, it
194 * will be updated. For example, you can use this to update the node's weight.
195 *
196 * **When to use**
197 *
198 * Use to register one node in a `HashRing` so lookups and shard assignments can
199 * return it, or update that node's weight.
200 *
201 * **Details**
202 *
203 * Nodes are matched by `PrimaryKey.value`. The weight defaults to `1` and is
204 * clamped to at least `0.1`.
205 *
206 * **Gotchas**
207 *
208 * This mutates and returns the same ring instance.
209 *
210 * @see {@link addMany} for adding or updating several nodes
211 * @see {@link remove} for unregistering a node
212 * @see {@link has} for checking primary-key membership
213 *
214 * @category combinators
215 * @since 3.19.0
216 */
217export const add: {
218 <A extends PrimaryKey.PrimaryKey>(node: A, options?: {
219 readonly weight?: number | undefined
220 }): (self: HashRing<A>) => HashRing<A>
221 <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, node: A, options?: {
222 readonly weight?: number | undefined
223 }): HashRing<A>
224} = dual((args) => isHashRing(args[0]), <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, node: A, options?: {
225 readonly weight?: number | undefined
226}): HashRing<A> => addMany(self, [node], options))
227
228/**
229 * Removes the node from the ring. No-op's if the node does not exist.
230 *
231 * **When to use**
232 *
233 * Use to remove a node that has left the pool so future lookups and shard
234 * assignments stop returning it.
235 *
236 * **Details**
237 *
238 * Removal matches by `PrimaryKey.value`, so any value with the same primary key
239 * removes the same ring member.
240 *
241 * **Gotchas**
242 *
243 * This mutates and returns the same ring instance.
244 *
245 * @see {@link add} for registering or updating a node
246 * @see {@link has} for checking membership by primary key
247 *
248 * @category combinators
249 * @since 3.19.0
250 */
251export const remove: {
252 <A extends PrimaryKey.PrimaryKey>(node: A): (self: HashRing<A>) => HashRing<A>
253 <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, node: A): HashRing<A>
254} = dual(2, <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, node: A): HashRing<A> => {
255 const key = PrimaryKey.value(node)
256 const entry = self.nodes.get(key)
257 if (entry) {
258 self.nodes.delete(key)
259 self.ring = self.ring.filter(([, n]) => n !== key)
260 updateTotalWeight(self)
261 }
262 return self
263})
264
265/**
266 * Checks whether the ring contains a node with the same `PrimaryKey` value.
267 *
268 * **When to use**
269 *
270 * Use when you need to know whether registering a node would update an existing
271 * ring member because another node already has the same primary-key identity.
272 *
273 * **Details**
274 *
275 * Membership is checked with `self.nodes.has(PrimaryKey.value(node))`, so
276 * matching is by primary key, not object identity or weight.
277 *
278 * @see {@link add} for registering or updating nodes
279 * @see {@link remove} for removing nodes by the same primary-key identity
280 * @see {@link get} for routing an input string to a node
281 *
282 * @category combinators
283 * @since 3.19.0
284 */
285export const has: {
286 <A extends PrimaryKey.PrimaryKey>(node: A): (self: HashRing<A>) => boolean
287 <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, node: A): boolean
288} = dual(
289 2,
290 <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, node: A): boolean => self.nodes.has(PrimaryKey.value(node))
291)
292
293/**
294 * Gets the node which should handle the given input. Returns undefined if
295 * the hashring has no elements with weight.
296 *
297 * **When to use**
298 *
299 * Use to route a single string input key to the current ring member responsible
300 * for that key.
301 *
302 * @see {@link getShards} for assigning fixed shard indexes instead of routing
303 * one input string at a time
304 *
305 * @category combinators
306 * @since 3.19.0
307 */
308export const get = <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, input: string): A | undefined => {
309 if (self.ring.length === 0) {
310 return undefined
311 }
312 const index = getIndexForInput(self, Hash.string(input))[0]
313 const node = self.ring[index][1]!
314 return self.nodes.get(node)![0]
315}
316
317/**
318 * Computes a balanced shard distribution across the nodes in the ring.
319 *
320 * **When to use**
321 *
322 * Use to precompute ownership for a fixed number of shard indexes across the
323 * current ring members.
324 *
325 * **Details**
326 *
327 * Finite fractional values of `count` are rounded down. `NaN` and non-positive
328 * values produce an empty shard distribution.
329 *
330 * @category combinators
331 * @since 3.19.0
332 */
333export const getShards = <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, count: number): Array<A> | undefined => {
334 if (self.ring.length === 0) {
335 return undefined
336 }
337 count = Count.normalize(count)
338
339 const shards = new Array<A>(count)
340
341 // for tracking how many shards have been allocated to each node
342 const allocations = new Map<string, number>()
343 // for tracking which shards still need to be allocated
344 const remaining = new Set<number>()
345 // for tracking which nodes have reached the max allocation
346 const exclude = new Set<string>()
347
348 // First pass - allocate the closest nodes, skipping nodes that have reached
349 // max
350 const distances = new Array<[shard: number, node: string, distance: number]>(count)
351 for (let shard = 0; shard < count; shard++) {
352 const hash = (shardHashes[shard] ??= Hash.string(`shard-${shard}`))
353 const [index, distance] = getIndexForInput(self, hash)
354 const node = self.ring[index][1]!
355 distances[shard] = [shard, node, distance]
356 remaining.add(shard)
357 }
358 distances.sort((a, b) => a[2] - b[2])
359 for (let i = 0; i < count; i++) {
360 const [shard, node] = distances[i]
361 if (exclude.has(node)) continue
362 const [value, weight] = self.nodes.get(node)!
363 shards[shard] = value
364 remaining.delete(shard)
365 const nodeCount = (allocations.get(node) ?? 0) + 1
366 allocations.set(node, nodeCount)
367 const maxPerNode = Math.max(1, Math.floor(count * (weight / self.totalWeightCache)))
368 if (nodeCount >= maxPerNode) {
369 exclude.add(node)
370 }
371 }
372
373 // Second pass - allocate any remaining shards, skipping nodes that have
374 // reached max
375 let allAtMax = exclude.size === self.nodes.size
376 remaining.forEach((shard) => {
377 const index = getIndexForInput(self, shardHashes[shard], allAtMax ? undefined : exclude)[0]
378 const node = self.ring[index][1]
379 const [value, weight] = self.nodes.get(node)!
380 shards[shard] = value
381
382 if (allAtMax) return
383 const nodeCount = (allocations.get(node) ?? 0) + 1
384 allocations.set(node, nodeCount)
385 const maxPerNode = Math.max(1, Math.floor(count * (weight / self.totalWeightCache)))
386 if (nodeCount >= maxPerNode) {
387 exclude.add(node)
388 if (exclude.size === self.nodes.size) {
389 allAtMax = true
390 }
391 }
392 })
393
394 return shards
395}
396
397const shardHashes: Array<number> = []
398
399function getIndexForInput<A extends PrimaryKey.PrimaryKey>(
400 self: HashRing<A>,
401 hash: number,
402 exclude?: ReadonlySet<string> | undefined
403): readonly [index: number, distance: number] {
404 const ring = self.ring
405 const len = ring.length
406
407 let mid: number
408 let lo = 0
409 let hi = len - 1
410
411 while (lo <= hi) {
412 mid = ((lo + hi) / 2) >>> 0
413 if (ring[mid][0] >= hash) {
414 hi = mid - 1
415 } else {
416 lo = mid + 1
417 }
418 }
419 const a = lo === len ? lo - 1 : lo
420 const distA = Math.abs(ring[a][0] - hash)
421 if (exclude === undefined) {
422 const b = lo - 1
423 if (b < 0) {
424 return [a, distA]
425 }
426 const distB = Math.abs(ring[b][0] - hash)
427 return distA <= distB ? [a, distA] : [b, distB]
428 } else if (!exclude.has(ring[a][1])) {
429 return [a, distA]
430 }
431 const range = Math.max(lo, len - lo)
432 for (let i = 1; i <= range; i++) {
433 let index = lo - i
434 if (index >= 0 && index < len && !exclude.has(ring[index][1])) {
435 return [index, Math.abs(ring[index][0] - hash)]
436 }
437 index = lo + i
438 if (index >= 0 && index < len && !exclude.has(ring[index][1])) {
439 return [index, Math.abs(ring[index][0] - hash)]
440 }
441 }
442 return [a, distA]
443}