| 316 | * @since 3.19.0 |
| 317 | */ |
| 318 | export const getShards = <A extends PrimaryKey.PrimaryKey>(self: HashRing<A>, count: number): Array<A> | undefined => { |
| 319 | if (self.ring.length === 0) { |
| 320 | return undefined |
| 321 | } |
| 322 | |
| 323 | const shards = new Array<A>(count) |
| 324 | |
| 325 | // for tracking how many shards have been allocated to each node |
| 326 | const allocations = new Map<string, number>() |
| 327 | // for tracking which shards still need to be allocated |
| 328 | const remaining = new Set<number>() |
| 329 | // for tracking which nodes have reached the max allocation |
| 330 | const exclude = new Set<string>() |
| 331 | |
| 332 | // First pass - allocate the closest nodes, skipping nodes that have reached |
| 333 | // max |
| 334 | const distances = new Array<[shard: number, node: string, distance: number]>(count) |
| 335 | for (let shard = 0; shard < count; shard++) { |
| 336 | const hash = (shardHashes[shard] ??= Hash.string(`shard-${shard}`)) |
| 337 | const [index, distance] = getIndexForInput(self, hash) |
| 338 | const node = self.ring[index][1]! |
| 339 | distances[shard] = [shard, node, distance] |
| 340 | remaining.add(shard) |
| 341 | } |
| 342 | distances.sort((a, b) => a[2] - b[2]) |
| 343 | for (let i = 0; i < count; i++) { |
| 344 | const [shard, node] = distances[i] |
| 345 | if (exclude.has(node)) continue |
| 346 | const [value, weight] = self.nodes.get(node)! |
| 347 | shards[shard] = value |
| 348 | remaining.delete(shard) |
| 349 | const nodeCount = (allocations.get(node) ?? 0) + 1 |
| 350 | allocations.set(node, nodeCount) |
| 351 | const maxPerNode = Math.max(1, Math.floor(count * (weight / self.totalWeightCache))) |
| 352 | if (nodeCount >= maxPerNode) { |
| 353 | exclude.add(node) |
| 354 | } |
| 355 | } |
| 356 | |
| 357 | // Second pass - allocate any remaining shards, skipping nodes that have |
| 358 | // reached max |
| 359 | let allAtMax = exclude.size === self.nodes.size |
| 360 | remaining.forEach((shard) => { |
| 361 | const index = getIndexForInput(self, shardHashes[shard], allAtMax ? undefined : exclude)[0] |
| 362 | const node = self.ring[index][1] |
| 363 | const [value, weight] = self.nodes.get(node)! |
| 364 | shards[shard] = value |
| 365 | |
| 366 | if (allAtMax) return |
| 367 | const nodeCount = (allocations.get(node) ?? 0) + 1 |
| 368 | allocations.set(node, nodeCount) |
| 369 | const maxPerNode = Math.max(1, Math.floor(count * (weight / self.totalWeightCache))) |
| 370 | if (nodeCount >= maxPerNode) { |
| 371 | exclude.add(node) |
| 372 | if (exclude.size === self.nodes.size) { |
| 373 | allAtMax = true |
| 374 | } |
| 375 | } |