Rendevouz hashing

Mix.install([
  {:combination, "~> 0.0.3"}
], consolidate_protocols: false)

Section

defmodule Rendezvous do
  @spec get_node(binary) :: binary
  def get_node key do
    [Node.self | Node.list]
    |> Enum.map(&to_string/1)
    |> get(key)
  end

  @spec list([any], binary) :: [any]
  def list(buckets, key) do
    buckets
    |> Enum.map(&get_bucket_with_hash(&1, key)) 
    |> Enum.sort_by(fn {_bucket, hash} -> hash end)
    |> Enum.map(fn {bucket, _hash} -> bucket end)
  end
  
  @spec get([any], binary) :: any
  def get(buckets, key) do
    buckets
    |> list(key)
    |> hd
  end

  @hash_algorith :md5

  defp get_bucket_with_hash(bucket, key) do
    {bucket, :crypto.hash(@hash_algorith, [to_string(bucket), key])}
  end
end

defmodule ComputeNode do
  defstruct [:region, :zone, :id]
end

defimpl String.Chars, for: ComputeNode do
  def to_string(%ComputeNode{region: region, zone: zone, id: id}) when is_integer(id) do    
    "#{region}-#{zone}-#{String.pad_leading(Integer.to_string(id), 4, "0")}"
  end
end

defmodule AllPermutations do
  def generate_all(set) do
    list = MapSet.to_list(set)
    
    Range.new(2, Enum.count(set))
    |> Enum.flat_map(fn subset_size ->
      list
      |> combinations(subset_size)
      |> Enum.flat_map(&permutations/1)
    end)
  end

  # Generate all combinations of size k from a list
  defp combinations(_, 0), do: [[]]
  defp combinations([], _), do: []
  defp combinations([h | t], k) do
    (for(tail <- combinations(t, k - 1), do: [h | tail])) ++ combinations(t, k)
  end

  # Generate all permutations of a list
  defp permutations([]), do: [[]]
  defp permutations(list) do
    for elem <- list, rest <- permutations(list -- [elem]), do: [elem | rest]
  end
end

datacenters = 
  for region <- ["AMS", "DUB"], 
    az <- ["A", "B"],
    id <- Range.new(1, 2) do
    %ComputeNode{region: region, zone: az, id: id}
  end
  # |> Enum.map(&to_string/1)

datacenters
|> Rendezvous.list("Joe")
|> Enum.map(&to_string/1)
|> Enum.join(" / ")

key = "Christian"

MapSet.new(datacenters)
|> AllPermutations.generate_all()
|> Enum.map(&Rendezvous.list(&1, key))
|> Enum.map(fn l -> Enum.map(l, &to_string/1) end)
|> Enum.map(&Enum.join(&1, " >> "))
|> Enum.uniq()
|> Enum.sort()
|> Enum.each(&IO.puts/1)

keys = 
  Range.new(1, 20)
  |> Enum.map(&Integer.to_string/1)
  |> Enum.map(fn x -> String.pad_leading(x, 4, "0") end)
  |> Enum.map(fn x -> "actor_#{x}" end)
  
keys
|> Enum.map(fn key ->
  order = 
    Rendezvous.list(datacenters, key)
    |> Enum.join(" / ")
  {key, order}
end)
|> Enum.map(fn {key, order} -> "#{String.pad_trailing(key, 15)}: #{order}" end)
|> Enum.each(&IO.puts/1)

histogram =
  Range.new(1, 1_000_000)
  |> Enum.map(&Integer.to_string/1)
  |> Enum.map(fn x -> String.pad_leading(x, 4, "0") end)
  |> Enum.map(fn x -> "actor_#{x}" end)
  |> Enum.map(fn key ->
    order = 
      datacenters
      |> Rendezvous.list(key)
    {key, order}
  end)
  |> Enum.group_by(fn {_key, order} -> order end)
  |> Enum.map(fn {k, vals} -> 
    vals =
      vals
      |> Enum.map(fn {k,_v} -> k end)
    {k, Enum.count(vals)}
  end)
  |> Map.new()

frequencies =
  histogram
  |> Enum.map(fn {order, count} -> {hd(order), count} end)
  |> Enum.reduce(%{}, fn {city, value}, acc ->
    Map.update(acc, city, value, &(&1 + value))
  end)

chgeuer/rendevouz_hashing.livemd

Rendevouz hashing

Section

chgeuer commented Jul 10, 2025

Uh oh!