Tenant-based routing and consistent hashing

Back in 2022 when I worked on tenant-based routing which implemented the Consistent Hashing with Bounded Loads paper, one of the parts of that project was the hash-ring consistent hashing algorithm. That algorithm stuck with me as it can be extremely useful in a bunch of other applications.

The Challenge of Tenant-Based Routing

When you're building a multi-tenant system, one of the core challenges is routing requests efficiently. Imagine you have a SaaS application serving thousands of tenants, and you want to distribute their workloads across multiple backend servers.

The naive approach might be to use round-robin or random distribution, but that doesn't account for tenant locality. If tenant A's requests are scattered across all servers, you lose benefits like:

• Cache locality (tenant's data stays warm in server memory)
• Connection pooling (database connections can be reused for the same tenant)
• Resource isolation (noisy tenants don't affect others as much)

What you really want is consistent tenant-to-server mapping that remains stable even when servers are added or removed. This is where consistent hashing algorithms shine.

Consistent Hashing: The Hash Ring Approach

Here's the gist of it, implemented in C. There's also one in Go to make it easier to read.

Let's look into why it is so powerful with a few code examples. I'm going to use Go implementation as an example here.

How much data really moves when a new node appears?

Below is a small, reproducible experiment that contrasts a consistent-hash ring with the classic hash-mod-N sharding strategy.

We start with 10 nodes (N0…N9), then introduce an eleventh one (N10) and count how many out of 1 000 000 keys have to migrate.

---

Consistent hashing (160 virtual points per node)

// Build a ring with ten nodes.
ring := chash.New([]string{
	"N0", "N1", "N2", "N3", "N4",
	"N5", "N6", "N7", "N8", "N9",
})

// Remember the original owner of every key.
oldOwner := make([]string, 1_000_000)
for i := 0; i < 1_000_000; i++ {
	oldOwner[i], _ = ring.Find([]byte(fmt.Sprint(i)))
}

// Add the new node.
ring.Add("N10")

// Count how many keys changed owner.
moved := 0
for i := 0; i < 1_000_000; i++ {
	newID, _ := ring.Find([]byte(fmt.Sprint(i)))
	if newID != oldOwner[i] {
		moved++
	}
}
fmt.Printf("consistent-hash: %.2f %% of keys moved\n",
	100*float64(moved)/1_000_000)

consistent-hash: 9.07 % of keys moved     // ≈ 1⁄11

Only the slice of the ring that now belongs to N10 (roughly one-eleventh) is re-assigned. The remaining 90% of keys stay exactly where they were.

Naive mod-N sharding

oldOwner := make([]int, 1_000_000)
for i := 0; i < 1_000_000; i++ {
	oldOwner[i] = crc32.ChecksumIEEE([]byte(fmt.Sprint(i))) % 10
}

moved := 0
for i := 0; i < 1_000_000; i++ {
	newOwner := crc32.ChecksumIEEE([]byte(fmt.Sprint(i))) % 11
	if newOwner != oldOwner[i] {
		moved++
	}
}
fmt.Printf("mod-sharding: %.2f %% of keys moved\n",
	100*float64(moved)/1_000_000)

mod-sharding: 90.92 % of keys moved     // ≈ 10⁄11

Which happens once every 11 hashes — so about 91% of the dataset is reshuffled.

Rendezvous Hashing: An Alternative Approach

While consistent hashing with a hash ring is popular, there's another elegant algorithm called Rendezvous hashing (also known as Highest Random Weight hashing). Instead of placing nodes on a ring, it assigns each key to the node that produces the highest hash value when combined with that key.

Here's how it works:

type RendezvousHash struct {
	nodes []string
}

func NewRendezvous(nodes []string) *RendezvousHash {
	return &RendezvousHash{nodes: append([]string{}, nodes...)}
}

func (r *RendezvousHash) Find(key []byte) string {
	var maxNode string
	var maxHash uint32
	
	keyStr := string(key)
	for _, node := range r.nodes {
		// Combine key with node name and hash
		combined := keyStr + ":" + node
		hash := crc32.ChecksumIEEE([]byte(combined))
		
		if hash > maxHash {
			maxHash = hash
			maxNode = node
		}
	}
	return maxNode
}

func (r *RendezvousHash) Add(node string) {
	r.nodes = append(r.nodes, node)
}

Let's run the same experiment with Rendezvous hashing:

// Build rendezvous hash with ten nodes.
rhash := NewRendezvous([]string{
	"N0", "N1", "N2", "N3", "N4",
	"N5", "N6", "N7", "N8", "N9",
})

// Remember the original owner of every key.
oldOwner := make([]string, 1_000_000)
for i := 0; i < 1_000_000; i++ {
	oldOwner[i] = rhash.Find([]byte(fmt.Sprint(i)))
}

// Add the new node.
rhash.Add("N10")

// Count how many keys changed owner.
moved := 0
for i := 0; i < 1_000_000; i++ {
	newOwner := rhash.Find([]byte(fmt.Sprint(i)))
	if newOwner != oldOwner[i] {
		moved++
	}
}
fmt.Printf("rendezvous-hash: %.2f %% of keys moved\n",
	100*float64(moved)/1_000_000)

rendezvous-hash: 9.09 % of keys moved     // ≈ 1⁄11

Remarkably similar results! Rendezvous hashing also minimizes key movement when nodes are added or removed.

Which one should you pick?

Consistent hashing with a hash ring is what you'll find in most production systems — Redis Cluster, Cassandra, and Amazon's DynamoDB all use variations of it. The reason is lookup performance: with enough virtual nodes, you can find a key's owner in O(log n) time using binary search. If you're building something that needs to handle thousands of requests per second with many nodes, this matters.

Rendezvous hashing is conceptually simpler and the code is easier to reason about, but every lookup requires checking all nodes (O(n)). That said, if you have a dozen backend servers and want dead-simple logic that just works, Rendezvous can be perfect.

Conclusion

Both consistent hashing and Rendezvous hashing solve the same fundamental problem: minimizing disruption when nodes are added or removed from a distributed system. This property makes them ideal for load balancers, distributed caches and CDNs.

I would love to write another post about the end-to-end implementation of tenant-based routing and why it can be extremely effective for your web apps.