Model

Keys moved by a membership change

Add or remove a node and only the keys between that node and its predecessor move.

moved_{ring} \approx \frac{K}{N}, moved_{mod N} \approx K \frac{N - 1}{N}

$K$: Keys; the number of keys
$N$: Nodes; nodes after the change

How it behaves

One input on the horizontal axis, the others held fixed.

modulo hashingconsistent hashing (ring)

Data table

Share of keys that move when one node is added
Nodes N	series	Keys moved
2	modulo hashing	50%
2.12	modulo hashing	52.8%
2.24	modulo hashing	55.4%
2.38	modulo hashing	57.9%
2.52	modulo hashing	60.3%
2.67	modulo hashing	62.5%
2.83	modulo hashing	64.6%
2.99	modulo hashing	66.6%
3.17	modulo hashing	68.5%
3.36	modulo hashing	70.2%
3.56	modulo hashing	71.9%
3.77	modulo hashing	73.5%
3.99	modulo hashing	74.9%
4.23	modulo hashing	76.3%
4.48	modulo hashing	77.7%
4.74	modulo hashing	78.9%
5.02	modulo hashing	80.1%
5.32	modulo hashing	81.2%
5.64	modulo hashing	82.3%
5.97	modulo hashing	83.3%
6.32	modulo hashing	84.2%
6.7	modulo hashing	85.1%
7.1	modulo hashing	85.9%
7.52	modulo hashing	86.7%
7.96	modulo hashing	87.4%
8.43	modulo hashing	88.1%
8.93	modulo hashing	88.8%
9.46	modulo hashing	89.4%
10	modulo hashing	90%
10.6	modulo hashing	90.6%
11.2	modulo hashing	91.1%
11.9	modulo hashing	91.6%
12.6	modulo hashing	92.1%
13.4	modulo hashing	92.5%
14.2	modulo hashing	92.9%
15	modulo hashing	93.3%
15.9	modulo hashing	93.7%
16.8	modulo hashing	94.1%
17.8	modulo hashing	94.4%
18.9	modulo hashing	94.7%
20	modulo hashing	95%
21.2	modulo hashing	95.3%
22.4	modulo hashing	95.5%
23.8	modulo hashing	95.8%
25.2	modulo hashing	96%
26.7	modulo hashing	96.3%
28.3	modulo hashing	96.5%
29.9	modulo hashing	96.7%
31.7	modulo hashing	96.8%
33.6	modulo hashing	97%
35.6	modulo hashing	97.2%
37.7	modulo hashing	97.3%
39.9	modulo hashing	97.5%
42.3	modulo hashing	97.6%
44.8	modulo hashing	97.8%
47.4	modulo hashing	97.9%
50.2	modulo hashing	98%
53.2	modulo hashing	98.1%
56.4	modulo hashing	98.2%
59.7	modulo hashing	98.3%
63.2	modulo hashing	98.4%
67	modulo hashing	98.5%
71	modulo hashing	98.6%
75.2	modulo hashing	98.7%
79.6	modulo hashing	98.7%
84.3	modulo hashing	98.8%
89.3	modulo hashing	98.9%
94.6	modulo hashing	98.9%
100	modulo hashing	99%
106	modulo hashing	99.1%
112	modulo hashing	99.1%
119	modulo hashing	99.2%
126	modulo hashing	99.2%
134	modulo hashing	99.3%
142	modulo hashing	99.3%
150	modulo hashing	99.3%
159	modulo hashing	99.4%
168	modulo hashing	99.4%
178	modulo hashing	99.4%
189	modulo hashing	99.5%
200	modulo hashing	99.5%
2	consistent hashing (ring)	50%
2.12	consistent hashing (ring)	47.2%
2.24	consistent hashing (ring)	44.6%
2.38	consistent hashing (ring)	42.1%
2.52	consistent hashing (ring)	39.7%
2.67	consistent hashing (ring)	37.5%
2.83	consistent hashing (ring)	35.4%
2.99	consistent hashing (ring)	33.4%
3.17	consistent hashing (ring)	31.5%
3.36	consistent hashing (ring)	29.8%
3.56	consistent hashing (ring)	28.1%
3.77	consistent hashing (ring)	26.5%
3.99	consistent hashing (ring)	25.1%
4.23	consistent hashing (ring)	23.7%
4.48	consistent hashing (ring)	22.3%
4.74	consistent hashing (ring)	21.1%
5.02	consistent hashing (ring)	19.9%
5.32	consistent hashing (ring)	18.8%
5.64	consistent hashing (ring)	17.7%
5.97	consistent hashing (ring)	16.7%
6.32	consistent hashing (ring)	15.8%
6.7	consistent hashing (ring)	14.9%
7.1	consistent hashing (ring)	14.1%
7.52	consistent hashing (ring)	13.3%
7.96	consistent hashing (ring)	12.6%
8.43	consistent hashing (ring)	11.9%
8.93	consistent hashing (ring)	11.2%
9.46	consistent hashing (ring)	10.6%
10	consistent hashing (ring)	9.98%
10.6	consistent hashing (ring)	9.42%
11.2	consistent hashing (ring)	8.89%
11.9	consistent hashing (ring)	8.39%
12.6	consistent hashing (ring)	7.92%
13.4	consistent hashing (ring)	7.48%
14.2	consistent hashing (ring)	7.06%
15	consistent hashing (ring)	6.67%
15.9	consistent hashing (ring)	6.29%
16.8	consistent hashing (ring)	5.94%
17.8	consistent hashing (ring)	5.61%
18.9	consistent hashing (ring)	5.3%
20	consistent hashing (ring)	5%
21.2	consistent hashing (ring)	4.72%
22.4	consistent hashing (ring)	4.46%
23.8	consistent hashing (ring)	4.21%
25.2	consistent hashing (ring)	3.97%
26.7	consistent hashing (ring)	3.75%
28.3	consistent hashing (ring)	3.54%
29.9	consistent hashing (ring)	3.34%
31.7	consistent hashing (ring)	3.15%
33.6	consistent hashing (ring)	2.98%
35.6	consistent hashing (ring)	2.81%
37.7	consistent hashing (ring)	2.65%
39.9	consistent hashing (ring)	2.51%
42.3	consistent hashing (ring)	2.37%
44.8	consistent hashing (ring)	2.23%
47.4	consistent hashing (ring)	2.11%
50.2	consistent hashing (ring)	1.99%
53.2	consistent hashing (ring)	1.88%
56.4	consistent hashing (ring)	1.77%
59.7	consistent hashing (ring)	1.67%
63.2	consistent hashing (ring)	1.58%
67	consistent hashing (ring)	1.49%
71	consistent hashing (ring)	1.41%
75.2	consistent hashing (ring)	1.33%
79.6	consistent hashing (ring)	1.26%
84.3	consistent hashing (ring)	1.19%
89.3	consistent hashing (ring)	1.12%
94.6	consistent hashing (ring)	1.06%
100	consistent hashing (ring)	0.998%
106	consistent hashing (ring)	0.942%
112	consistent hashing (ring)	0.889%
119	consistent hashing (ring)	0.839%
126	consistent hashing (ring)	0.792%
134	consistent hashing (ring)	0.748%
142	consistent hashing (ring)	0.706%
150	consistent hashing (ring)	0.667%
159	consistent hashing (ring)	0.629%
168	consistent hashing (ring)	0.594%
178	consistent hashing (ring)	0.561%
189	consistent hashing (ring)	0.53%
200	consistent hashing (ring)	0.5%

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Data Movement
How do records cross between two systems that have independent rates, independent availability and independent lifetimes, and what are you willing to lose when the assumption underneath the crossing breaks?
$K / N not K \cdot (N - 1) / N$
Read it in place →
Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
$(N - 1) / N remapped with modulo$
Read it in place →