hash_rings/lib.rs
1//! # hash-rings-rs
2//!
3//! [](https://crates.io/crates/hash-rings)
4//! [](https://docs.rs/hash-rings)
5//! [](https://opensource.org/licenses/MIT)
6//! [](https://opensource.org/licenses/Apache-2.0)
7//! [](https://travis-ci.org/jeffrey-xiao/hash-rings-rs)
8//! [](https://codecov.io/gh/jeffrey-xiao/hash-rings-rs)
9//!
10//! `hash-rings` contains implementations for seven different hash ring algorithms: Cache Array
11//! Routing Protocol, Consistent Hashing, Multi-Probe Consistent Hashing, Rendezvous Hashing,
12//! Weighted Rendezvous Hashing, Maglev Hashing, and Jump Hashing. It also provides clients for
13//! Consistent Hashing, Rendezvous Hashing, and Weighted Rendezvous Hashing to efficiently
14//! redistribute items as nodes are inserted and removed from the ring.
15//!
16//! ## Examples
17//!
18//! ### Example Ring Usage
19//!
20//! ```rust
21//! use hash_rings::consistent::Ring;
22//! use std::collections::hash_map::DefaultHasher;
23//! use std::hash::BuildHasherDefault;
24//!
25//! type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
26//!
27//! fn main() {
28//! let mut r = Ring::with_hasher(DefaultBuildHasher::default());
29//!
30//! r.insert_node(&"node-1", 1);
31//! r.insert_node(&"node-2", 3);
32//!
33//! assert_eq!(r.get_node(&"point-1"), &"node-1");
34//! }
35//! ```
36//!
37//! ### Example Client Usage
38//!
39//! ```rust
40//! use hash_rings::consistent::Client;
41//! use std::collections::hash_map::DefaultHasher;
42//! use std::hash::BuildHasherDefault;
43//!
44//! type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
45//!
46//! fn main() {
47//! let mut c = Client::with_hasher(DefaultBuildHasher::default());
48//! c.insert_node(&"node-1", 1);
49//! c.insert_node(&"node-2", 3);
50//!
51//! c.insert_point(&"point-1");
52//!
53//! assert_eq!(c.get_node(&"point-1"), &"node-1");
54//! assert_eq!(c.get_points(&"node-1"), [&"point-1"]);
55//! }
56//! ```
57//!
58//! ## Usage
59//!
60//! Add this to your `Cargo.toml`:
61//!
62//! ```toml
63//! [dependencies]
64//! hash-rings = "*"
65//! ```
66//!
67//! and this to your crate root if you are using Rust 2015:
68//!
69//! ```rust
70//! extern crate hash_rings;
71//! ```
72//!
73//! ## Benchmarks
74//!
75//! ```text
76//! Benching carp hashing (10 nodes, 100000 items)
77//! 15848556381555908996 - Expected: 0.155015 | Actual: 0.155180 | Error: -0.001060
78//! 06801744144136471498 - Expected: 0.056593 | Actual: 0.056960 | Error: -0.006447
79//! 16730135874920933484 - Expected: 0.015944 | Actual: 0.016030 | Error: -0.005355
80//! 11802923454833793349 - Expected: 0.135407 | Actual: 0.134050 | Error: 0.010122
81//! 14589965171469706430 - Expected: 0.091974 | Actual: 0.093030 | Error: -0.011348
82//! 06790293794189608791 - Expected: 0.122949 | Actual: 0.123230 | Error: -0.002284
83//! 08283237945741952176 - Expected: 0.042317 | Actual: 0.042880 | Error: -0.013126
84//! 06540337216311911463 - Expected: 0.146495 | Actual: 0.145220 | Error: 0.008782
85//! 13241461372147825909 - Expected: 0.084205 | Actual: 0.084330 | Error: -0.001484
86//! 06769854041949442045 - Expected: 0.149100 | Actual: 0.149090 | Error: 0.000070
87//!
88//! Total elapsed time: 1336.552 ms
89//! Milliseconds per operation: 13365.519 ns
90//! Operations per second: 74819.391 op/ms
91//!
92//!
93//! Benching consistent hashing (10 nodes, 1611 replicas, 100000 items)
94//! 15848556381555908996 - Expected: 0.100000 | Actual: 0.102070 | Error: -0.020280
95//! 13987966085338848396 - Expected: 0.100000 | Actual: 0.102410 | Error: -0.023533
96//! 06801744144136471498 - Expected: 0.100000 | Actual: 0.102240 | Error: -0.021909
97//! 04005265977620077421 - Expected: 0.100000 | Actual: 0.100010 | Error: -0.000100
98//! 16730135874920933484 - Expected: 0.100000 | Actual: 0.098970 | Error: 0.010407
99//! 13195988079190323012 - Expected: 0.100000 | Actual: 0.099630 | Error: 0.003714
100//! 11802923454833793349 - Expected: 0.100000 | Actual: 0.102730 | Error: -0.026575
101//! 05146857450694500275 - Expected: 0.100000 | Actual: 0.099290 | Error: 0.007151
102//! 14589965171469706430 - Expected: 0.100000 | Actual: 0.098170 | Error: 0.018641
103//! 17291863876572781215 - Expected: 0.100000 | Actual: 0.094480 | Error: 0.058425
104//!
105//! Total elapsed time: 417.016 ms
106//! Milliseconds per operation: 4170.163 ns
107//! Operations per second: 239798.789 op/ms
108//!
109//!
110//! Benching jump hashing (10 nodes, 100000 items)
111//! 00000000000000000000 - Expected: 0.100000 | Actual: 0.098250 | Error: 0.017812
112//! 00000000000000000001 - Expected: 0.100000 | Actual: 0.100140 | Error: -0.001398
113//! 00000000000000000002 - Expected: 0.100000 | Actual: 0.100280 | Error: -0.002792
114//! 00000000000000000003 - Expected: 0.100000 | Actual: 0.100240 | Error: -0.002394
115//! 00000000000000000004 - Expected: 0.100000 | Actual: 0.101550 | Error: -0.015263
116//! 00000000000000000005 - Expected: 0.100000 | Actual: 0.099290 | Error: 0.007151
117//! 00000000000000000006 - Expected: 0.100000 | Actual: 0.100750 | Error: -0.007444
118//! 00000000000000000007 - Expected: 0.100000 | Actual: 0.100130 | Error: -0.001298
119//! 00000000000000000008 - Expected: 0.100000 | Actual: 0.098730 | Error: 0.012863
120//! 00000000000000000009 - Expected: 0.100000 | Actual: 0.100640 | Error: -0.006359
121//!
122//! Total elapsed time: 191.231 ms
123//! Milliseconds per operation: 1912.314 ns
124//! Operations per second: 522926.543 op/ms
125//!
126//!
127//! Benching maglev hashing (10 nodes, 100000 items)
128//! 15848556381555908996 - Expected: 0.100000 | Actual: 0.099670 | Error: 0.003311
129//! 13987966085338848396 - Expected: 0.100000 | Actual: 0.100700 | Error: -0.006951
130//! 06801744144136471498 - Expected: 0.100000 | Actual: 0.099130 | Error: 0.008776
131//! 04005265977620077421 - Expected: 0.100000 | Actual: 0.099960 | Error: 0.000400
132//! 16730135874920933484 - Expected: 0.100000 | Actual: 0.101340 | Error: -0.013223
133//! 13195988079190323012 - Expected: 0.100000 | Actual: 0.098740 | Error: 0.012761
134//! 11802923454833793349 - Expected: 0.100000 | Actual: 0.100650 | Error: -0.006458
135//! 05146857450694500275 - Expected: 0.100000 | Actual: 0.101050 | Error: -0.010391
136//! 14589965171469706430 - Expected: 0.100000 | Actual: 0.100660 | Error: -0.006557
137//! 17291863876572781215 - Expected: 0.100000 | Actual: 0.098100 | Error: 0.019368
138//!
139//! Total elapsed time: 188.203 ms
140//! Milliseconds per operation: 1882.027 ns
141//! Operations per second: 531342.016 op/ms
142//!
143//!
144//! Benching mpc hashing (10 nodes, 21 probes, 100000 items)
145//! 15848556381555908996 - Expected: 0.100000 | Actual: 0.096820 | Error: 0.032844
146//! 13987966085338848396 - Expected: 0.100000 | Actual: 0.098510 | Error: 0.015125
147//! 06801744144136471498 - Expected: 0.100000 | Actual: 0.103730 | Error: -0.035959
148//! 04005265977620077421 - Expected: 0.100000 | Actual: 0.093530 | Error: 0.069176
149//! 16730135874920933484 - Expected: 0.100000 | Actual: 0.103210 | Error: -0.031102
150//! 13195988079190323012 - Expected: 0.100000 | Actual: 0.083890 | Error: 0.192037
151//! 11802923454833793349 - Expected: 0.100000 | Actual: 0.096990 | Error: 0.031034
152//! 05146857450694500275 - Expected: 0.100000 | Actual: 0.111780 | Error: -0.105386
153//! 14589965171469706430 - Expected: 0.100000 | Actual: 0.098680 | Error: 0.013377
154//! 17291863876572781215 - Expected: 0.100000 | Actual: 0.112860 | Error: -0.113946
155//!
156//! Total elapsed time: 1153.555 ms
157//! Milliseconds per operation: 11535.552 ns
158//! Operations per second: 86688.529 op/ms
159//!
160//!
161//! Benching rendezvous hashing (10 nodes, 100000 items)
162//! 15848556381555908996 - Expected: 0.100000 | Actual: 0.099680 | Error: 0.003210
163//! 13987966085338848396 - Expected: 0.100000 | Actual: 0.100710 | Error: -0.007050
164//! 06801744144136471498 - Expected: 0.100000 | Actual: 0.100320 | Error: -0.003190
165//! 04005265977620077421 - Expected: 0.100000 | Actual: 0.099820 | Error: 0.001803
166//! 16730135874920933484 - Expected: 0.100000 | Actual: 0.099900 | Error: 0.001001
167//! 13195988079190323012 - Expected: 0.100000 | Actual: 0.100600 | Error: -0.005964
168//! 11802923454833793349 - Expected: 0.100000 | Actual: 0.098440 | Error: 0.015847
169//! 05146857450694500275 - Expected: 0.100000 | Actual: 0.099440 | Error: 0.005632
170//! 14589965171469706430 - Expected: 0.100000 | Actual: 0.101420 | Error: -0.014001
171//! 17291863876572781215 - Expected: 0.100000 | Actual: 0.099670 | Error: 0.003311
172//!
173//! Total elapsed time: 1623.272 ms
174//! Milliseconds per operation: 16232.719 ns
175//! Operations per second: 61603.972 op/ms
176//!
177//!
178//! Benching weighted rendezvous hashing (10 nodes, 100000 items)
179//! 15848556381555908996 - Expected: 0.155015 | Actual: 0.154470 | Error: 0.003531
180//! 06801744144136471498 - Expected: 0.056593 | Actual: 0.057320 | Error: -0.012687
181//! 16730135874920933484 - Expected: 0.015944 | Actual: 0.016210 | Error: -0.016400
182//! 11802923454833793349 - Expected: 0.135407 | Actual: 0.134700 | Error: 0.005248
183//! 14589965171469706430 - Expected: 0.091974 | Actual: 0.092940 | Error: -0.010391
184//! 06790293794189608791 - Expected: 0.122949 | Actual: 0.123490 | Error: -0.004385
185//! 08283237945741952176 - Expected: 0.042317 | Actual: 0.042200 | Error: 0.002776
186//! 06540337216311911463 - Expected: 0.146495 | Actual: 0.144770 | Error: 0.011918
187//! 13241461372147825909 - Expected: 0.084205 | Actual: 0.083530 | Error: 0.008080
188//! 06769854041949442045 - Expected: 0.149100 | Actual: 0.150370 | Error: -0.008443
189//!
190//! Total elapsed time: 2233.020 ms
191//! Milliseconds per operation: 22330.205 ns
192//! Operations per second: 44782.393 op/ms
193//! ```
194//!
195//! ## Changelog
196//!
197//! See [CHANGELOG](CHANGELOG.md) for more details.
198//!
199//! ## References
200//!
201//! - [A Fast, Minimal Memory, Consistent Hash Algorithm](https://arxiv.org/abs/1406.2294)
202//! > Lamping, John, and Eric Veach. 2014. “A Fast, Minimal Memory, Consistent Hash Algorithm.” _CoRR_ abs/1406.2294. <http://arxiv.org/abs/1406.2294>.
203//! - [Cache Array Routing Protocol](https://tools.ietf.org/html/draft-vinod-carp-v1-03)
204//! - [Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web](https://dl.acm.org/citation.cfm?id=258660)
205//! > Karger, David, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. 1997. “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.” In _Proceedings of the Twenty-Ninth Annual Acm Symposium on Theory of Computing_, 654–63. STOC ’97. New York, NY, USA: ACM. doi:[10.1145/258533.258660](https://doi.org/10.1145/258533.258660).
206//! - [Maglev: A Fast and Reliable Software Network Load Balancer](https://research.google.com/pubs/pub44824.html)
207//! > Eisenbud, Daniel E., Cheng Yi, Carlo Contavalli, Cody Smith, Roman Kononov, Eric Mann-Hielscher, Ardas Cilingiroglu, Bin Cheyney, Wentao Shang, and Jinnah Dylan Hosein. 2016. “Maglev: A Fast and Reliable Software Network Load Balancer.” In _13th Usenix Symposium on Networked Systems Design and Implementation (Nsdi 16)_, 523–35. Santa Clara, CA. <https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/eisenbud>.
208//! - [Multi-probe consistent hashing](https://arxiv.org/abs/1505.00062)
209//! > Appleton, Ben, and Michael O’Reilly. 2015. “Multi-Probe Consistent Hashing.” _CoRR_ abs/1505.00062. <http://arxiv.org/abs/1505.00062>.
210//! - [Using name-based mappings to increase hit rates](https://dl.acm.org/citation.cfm?id=276288)
211//! > Thaler, David G., and Chinya V. Ravishankar. 1998. “Using Name-Based Mappings to Increase Hit Rates.” _IEEE/ACM Trans. Netw._ 6 (1). Piscataway, NJ, USA: IEEE Press: 1–14. doi:[10.1109/90.663936](https://doi.org/10.1109/90.663936).
212//! - [Weighted Distributed Hash Tables](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.414.9353&rep=rep1&type=pdf)
213//! > Schindelhauer, Christian, and Gunnar Schomaker. 2005. “Weighted Distributed Hash Tables.” In _Proceedings of the Seventeenth Annual Acm Symposium on Parallelism in Algorithms and Architectures_, 218–27. SPAA ’05. New York, NY, USA: ACM. doi:[10.1145/1073970.1074008](https://doi.org/10.1145/1073970.1074008).
214//! - [Consistent Hashing with Bounded Loads](https://arxiv.org/abs/1608.01350)
215//! > Mirrokni, Vahab, Mikkel Thorup, and Morteza Zadimoghaddam. 2018. “Consistent Hashing with Bounded Loads.” In *Proceedings of the Twenty-Ninth Annual Acm-Siam Symposium on Discrete Algorithms*, 587–604. SIAM.
216//!
217//! ## License
218//!
219//! `hash-rings-rs` is dual-licensed under the terms of either the MIT License or the Apache License
220//! (Version 2.0).
221//!
222//! See [LICENSE-APACHE](LICENSE-APACHE) and [LICENSE-MIT](LICENSE-MIT) for more details.
223
224#![warn(missing_docs)]
225
226pub mod carp;
227pub mod consistent;
228pub mod jump;
229pub mod maglev;
230pub mod mpc;
231pub mod rendezvous;
232#[cfg(test)]
233mod test_util;
234mod util;
235pub mod weighted_rendezvous;