Check if there is interest in Rendezvous router

[ruslandoga]

👋

I learned recently that Cachex supports distributed caching, and when checking the implementation I saw that it uses consistent hashing. I wonder if there is any interest in implementing the approach described in https://en.wikipedia.org/wiki/Rendezvous_hashing?

Compared to https://github.com/discord/ex_hash_ring it doesn't require any 3rd party NIFs or keeping extra in-memory state.

defmodule Cachex.Router.Rendezvous do
  def route(key) do
    nodes = Node.list([:this, :visible])
    Enum.max_by(nodes, fn node -> :erlang.phash2({key, node}) end)
  end
end

Quick performance check

Using a slightly more optimized version:

defmodule Rendezvous do
  def route(key) do
    nodes = Node.list()
    node = Node.self()
    max_by_hash(nodes, key, node, :erlang.phash2({key, node}))
  end

  defp max_by_hash([node | nodes], key, max_node, max_hash) do
    hash = :erlang.phash2({key, node})

    # TODO needs a tie-breaker for hash collisions, otherwise it seems to depend on nodes order
    case hash >= max_hash do
      true -> max_by_hash(nodes, key, node, hash)
      false -> max_by_hash(nodes, key, max_node, max_hash)
    end
  end

  defp max_by_hash([], _key, node, _hash), do: node
end

Three nodes setup:

iex(alice@mac4)> Node.list([:this, :visible])
#==> [:bob@mac4, :eve@mac4, :alice@mac4]

iex(alice@mac4)> alias ExHashRing.Ring
iex(alice@mac4)> {:ok, ring} = Ring.start_link()
iex(alice@mac4)> for node <- Node.list([:this, :visible]), do: Ring.add_node(ring, node)
#==> [
#==>   ok: [bob@mac4: 512],
#==>   ok: [eve@mac4: 512, bob@mac4: 512],
#==>   ok: [alice@mac4: 512, eve@mac4: 512, bob@mac4: 512]
#==> ]

Quick performance check:

iex(alice@mac4)> :timer.tc fn -> Enum.each(1..10_000, fn i -> Ring.find_node(ring, i) end) end
#==> {21187, :ok}
iex(alice@mac4)> :timer.tc fn -> Enum.each(1..10_000, fn i -> Ring.find_node(ring, i) end) end
#==> {20669, :ok}
iex(alice@mac4)> :timer.tc fn -> Enum.each(1..10_000, fn i -> Ring.find_node(ring, i) end) end
#==> {20088, :ok}
iex(alice@mac4)> :timer.tc fn -> Enum.each(1..10_000, &Rendezvous.route/1) end
#==> {2096, :ok}
iex(alice@mac4)> :timer.tc fn -> Enum.each(1..10_000, &Rendezvous.route/1) end
#==> {2786, :ok}
iex(alice@mac4)> :timer.tc fn -> Enum.each(1..10_000, &Rendezvous.route/1) end
#==> {2891, :ok}

I know this is unfair because of the anonymous function but it shows that it's fast enough while being simpler :)

[ruslandoga]

If there is interest, I'd be happy to contribute!

[whitfin]

@ruslandoga hi! Sorry, I thought I'd replied to this 😅

I haven't spent too much time thinking about adding new routers; if you'd like to contribute I'd be happy to take a look at it. If you can, trying to match the same options as the Ring router would be good - makes it easier for people to swap between.

You could also publish as it's own package, so people can include it additionally to Cachex if they need it, then we could bake it in based on how much usage it seems to get (and I'm happy to link to it from the Cachex docs, to avoid visibility bias).

[ruslandoga]

👋 @whitfin

I'd like to try the PR route if still possible :) Creating a third party library kind of defeats the purpose: simplicity and fewer dependencies.