Particionamento

import crypto from "node:crypto";

// Os primeiros 8 bytes do SHA-256, como inteiro sem sinal: o mesmo valor em qualquer linguagem
const hash = (texto: string) =>
  crypto.createHash("sha256").update(texto).digest().readBigUInt64BE(0);

class Anel {
  private pontos: { posicao: bigint; servidor: string }[] = [];
  private virtuais: number;

  // Cada servidor ocupa várias posições no anel (nós virtuais), para dividir melhor as chaves
  constructor(servidores: string[], virtuais = 100) {
    this.virtuais = virtuais;
    for (const s of servidores) this.adicionar(s);
  }

  adicionar(servidor: string) {
    for (let v = 0; v < this.virtuais; v++) {
      this.pontos.push({ posicao: hash(`${servidor}#${v}`), servidor });
    }
    this.pontos.sort((a, b) => (a.posicao < b.posicao ? -1 : a.posicao > b.posicao ? 1 : 0));
  }

  // A chave vai para o primeiro ponto do anel a partir do hash dela, dando a volta no fim
  servidorDe(chave: string): string {
    const h = hash(chave);
    let ini = 0, fim = this.pontos.length;
    while (ini < fim) {
      const meio = (ini + fim) >> 1;
      if (this.pontos[meio].posicao < h) ini = meio + 1; else fim = meio;
    }
    return this.pontos[ini % this.pontos.length].servidor;
  }
}

// Teste: 100 mil chaves em 4 servidores, e quantas mudam ao entrar um quinto
const chaves = Array.from({ length: 100_000 }, (_, i) => `cliente:${i}`);
const anel = new Anel(["shard-0", "shard-1", "shard-2", "shard-3"]);
const antes = chaves.map((c) => anel.servidorDe(c));
const contagem: Record<string, number> = {};
for (const s of antes) contagem[s] = (contagem[s] ?? 0) + 1;
anel.adicionar("shard-4");
const mudouAnel = chaves.filter((c, i) => anel.servidorDe(c) !== antes[i]).length;
const mudouModulo = chaves.filter((c) => hash(c) % 4n !== hash(c) % 5n).length;
console.log("por servidor:", JSON.stringify(contagem));
console.log(`ao entrar o 5º servidor: anel ${mudouAnel} chaves mudaram, módulo ${mudouModulo}`);

import bisect
import hashlib
from collections import Counter


def hash_(texto: str) -> int:
    """Os primeiros 8 bytes do SHA-256, como inteiro sem sinal, igual em toda linguagem."""
    return int.from_bytes(hashlib.sha256(texto.encode()).digest()[:8], "big")


class Anel:
    # Cada servidor ocupa várias posições no anel (nós virtuais), para dividir melhor as chaves
    def __init__(self, servidores: list[str], virtuais: int = 100):
        self.virtuais = virtuais
        self.pontos: list[tuple[int, str]] = []
        for s in servidores:
            self.adicionar(s)

    def adicionar(self, servidor: str) -> None:
        self.pontos += [(hash_(f"{servidor}#{v}"), servidor) for v in range(self.virtuais)]
        self.pontos.sort()
        self.posicoes = [p for p, _ in self.pontos]

    def servidor_de(self, chave: str) -> str:
        """A chave vai para o primeiro ponto do anel a partir do hash dela, dando a volta no fim."""
        i = bisect.bisect_left(self.posicoes, hash_(chave))
        return self.pontos[i % len(self.pontos)][1]


# Teste: 100 mil chaves em 4 servidores, e quantas mudam ao entrar um quinto
chaves = [f"cliente:{i}" for i in range(100_000)]
anel = Anel(["shard-0", "shard-1", "shard-2", "shard-3"])
antes = [anel.servidor_de(c) for c in chaves]
print("por servidor:", dict(sorted(Counter(antes).items())))
anel.adicionar("shard-4")
mudou_anel = sum(anel.servidor_de(c) != a for c, a in zip(chaves, antes))
mudou_modulo = sum(hash_(c) % 4 != hash_(c) % 5 for c in chaves)
print(f"ao entrar o 5º servidor: anel {mudou_anel} chaves mudaram, módulo {mudou_modulo}")

package main

import (
	"crypto/sha256"
	"encoding/binary"
	"fmt"
	"sort"
)

// hash usa os primeiros 8 bytes do SHA-256, como inteiro sem sinal
func hash(texto string) uint64 {
	soma := sha256.Sum256([]byte(texto))
	return binary.BigEndian.Uint64(soma[:8])
}

type ponto struct {
	posicao  uint64
	servidor string
}

// Anel: cada servidor ocupa várias posições (nós virtuais), para dividir melhor as chaves
type Anel struct {
	pontos   []ponto
	virtuais int
}

func NovoAnel(servidores []string, virtuais int) *Anel {
	a := &Anel{virtuais: virtuais}
	for _, s := range servidores {
		a.Adicionar(s)
	}
	return a
}

func (a *Anel) Adicionar(servidor string) {
	for v := range a.virtuais {
		a.pontos = append(a.pontos, ponto{hash(fmt.Sprintf("%s#%d", servidor, v)), servidor})
	}
	sort.Slice(a.pontos, func(i, j int) bool { return a.pontos[i].posicao < a.pontos[j].posicao })
}

// ServidorDe: o primeiro ponto do anel a partir do hash da chave, dando a volta no fim
func (a *Anel) ServidorDe(chave string) string {
	h := hash(chave)
	i := sort.Search(len(a.pontos), func(i int) bool { return a.pontos[i].posicao >= h })
	return a.pontos[i%len(a.pontos)].servidor
}

func main() {
	// Teste: 100 mil chaves em 4 servidores, e quantas mudam ao entrar um quinto
	chaves := make([]string, 100_000)
	for i := range chaves {
		chaves[i] = fmt.Sprintf("cliente:%d", i)
	}
	anel := NovoAnel([]string{"shard-0", "shard-1", "shard-2", "shard-3"}, 100)
	antes := make([]string, len(chaves))
	contagem := map[string]int{}
	for i, c := range chaves {
		antes[i] = anel.ServidorDe(c)
		contagem[antes[i]]++
	}
	anel.Adicionar("shard-4")
	mudouAnel, mudouModulo := 0, 0
	for i, c := range chaves {
		if anel.ServidorDe(c) != antes[i] {
			mudouAnel++
		}
		if hash(c)%4 != hash(c)%5 {
			mudouModulo++
		}
	}
	fmt.Println("por servidor:", contagem)
	fmt.Printf("ao entrar o 5º servidor: anel %d chaves mudaram, módulo %d\n",
		mudouAnel, mudouModulo)
}

import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Anel {
    // Os primeiros 8 bytes do SHA-256; em Java, long tem sinal, então a comparação é sem sinal
    static long hash(String texto) throws Exception {
        var soma = MessageDigest.getInstance("SHA-256")
            .digest(texto.getBytes(StandardCharsets.UTF_8));
        return ByteBuffer.wrap(soma, 0, 8).getLong();
    }

    // TreeMap ordenado sem sinal: a chave é a posição no anel
    final TreeMap<Long, String> pontos = new TreeMap<>(Long::compareUnsigned);
    final int virtuais;

    // Cada servidor ocupa várias posições no anel (nós virtuais), para dividir melhor as chaves
    Anel(List<String> servidores, int virtuais) throws Exception {
        this.virtuais = virtuais;
        for (var s : servidores) adicionar(s);
    }

    void adicionar(String servidor) throws Exception {
        for (int v = 0; v < virtuais; v++) pontos.put(hash(servidor + "#" + v), servidor);
    }

    // A chave vai para o primeiro ponto do anel a partir do hash dela, dando a volta no fim
    String servidorDe(String chave) throws Exception {
        var proximo = pontos.ceilingEntry(hash(chave));
        return (proximo != null ? proximo : pontos.firstEntry()).getValue();
    }

    public static void main(String[] args) throws Exception {
        // Teste: 100 mil chaves em 4 servidores, e quantas mudam ao entrar um quinto
        var chaves = new ArrayList<String>();
        for (int i = 0; i < 100_000; i++) chaves.add("cliente:" + i);
        var anel = new Anel(List.of("shard-0", "shard-1", "shard-2", "shard-3"), 100);
        var antes = new ArrayList<String>();
        var contagem = new TreeMap<String, Integer>();
        for (var c : chaves) {
            var s = anel.servidorDe(c);
            antes.add(s);
            contagem.merge(s, 1, Integer::sum);
        }
        anel.adicionar("shard-4");
        int mudouAnel = 0, mudouModulo = 0;
        for (int i = 0; i < chaves.size(); i++) {
            if (!anel.servidorDe(chaves.get(i)).equals(antes.get(i))) mudouAnel++;
            long h = hash(chaves.get(i));
            if (Long.remainderUnsigned(h, 4) != Long.remainderUnsigned(h, 5)) mudouModulo++;
        }
        System.out.println("por servidor: " + contagem);
        System.out.printf("ao entrar o 5º servidor: anel %d chaves mudaram, módulo %d%n",
            mudouAnel, mudouModulo);
    }
}

using System.Buffers.Binary;
using System.Security.Cryptography;
using System.Text;

// Os primeiros 8 bytes do SHA-256, como inteiro sem sinal
static ulong Hash(string texto) =>
    BinaryPrimitives.ReadUInt64BigEndian(SHA256.HashData(Encoding.UTF8.GetBytes(texto)));

// Teste: 100 mil chaves em 4 servidores, e quantas mudam ao entrar um quinto
var chaves = Enumerable.Range(0, 100_000).Select(i => $"cliente:{i}").ToArray();
var anel = new Anel(["shard-0", "shard-1", "shard-2", "shard-3"], Hash);
var antes = chaves.Select(anel.ServidorDe).ToArray();
var contagem = antes.GroupBy(s => s).OrderBy(g => g.Key).Select(g => $"{g.Key}={g.Count()}");
anel.Adicionar("shard-4");
var mudouAnel = chaves.Where((c, i) => anel.ServidorDe(c) != antes[i]).Count();
var mudouModulo = chaves.Count(c => Hash(c) % 4 != Hash(c) % 5);
Console.WriteLine($"por servidor: {string.Join(", ", contagem)}");
Console.WriteLine(
    $"ao entrar o 5º servidor: anel {mudouAnel} chaves mudaram, módulo {mudouModulo}");

// Cada servidor ocupa várias posições no anel (nós virtuais), para dividir melhor as chaves
class Anel
{
    private readonly List<(ulong Posicao, string Servidor)> pontos = [];
    private readonly Func<string, ulong> hash;
    private readonly int virtuais;

    public Anel(IEnumerable<string> servidores, Func<string, ulong> hash, int virtuais = 100)
    {
        (this.hash, this.virtuais) = (hash, virtuais);
        foreach (var s in servidores) Adicionar(s);
    }

    public void Adicionar(string servidor)
    {
        for (var v = 0; v < virtuais; v++) pontos.Add((hash($"{servidor}#{v}"), servidor));
        pontos.Sort((a, b) => a.Posicao.CompareTo(b.Posicao));
    }

    // A chave vai para o primeiro ponto do anel a partir do hash dela, dando a volta no fim
    public string ServidorDe(string chave)
    {
        var h = hash(chave);
        int ini = 0, fim = pontos.Count;
        while (ini < fim)
        {
            var meio = (ini + fim) / 2;
            if (pontos[meio].Posicao < h) ini = meio + 1; else fim = meio;
        }
        return pontos[ini % pontos.Count].Servidor;
    }
}