hash-rings

Crates.iohash-rings
lib.rshash-rings
version1.1.0
sourcesrc
created_at2018-04-05 06:44:31.119021
updated_at2019-10-11 03:23:00.301222
descriptionImplementations of various hash rings.
homepage
repositoryhttps://gitlab.com/jeffrey-xiao/hash-rings-rs
max_upload_size
id59030
size131,357
Jeffrey Xiao (jeffrey-xiao)

documentation

https://docs.rs/hash-rings

README

hash-rings-rs

hash-rings Documentation License: MIT License: Apache 2.0 Build Status codecov

hash-rings contains implementations for seven different hash ring algorithms: Cache Array Routing Protocol, Consistent Hashing, Multi-Probe Consistent Hashing, Rendezvous Hashing, Weighted Rendezvous Hashing, Maglev Hashing, and Jump Hashing. It also provides clients for Consistent Hashing, Rendezvous Hashing, and Weighted Rendezvous Hashing to efficiently redistribute items as nodes are inserted and removed from the ring.

Examples

Example Ring Usage

use hash_rings::consistent::Ring;
use std::collections::hash_map::DefaultHasher;
use std::hash::BuildHasherDefault;

type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;

fn main() {
    let mut r = Ring::with_hasher(DefaultBuildHasher::default());

    r.insert_node(&"node-1", 1);
    r.insert_node(&"node-2", 3);

    assert_eq!(r.get_node(&"point-1"), &"node-1");
}

Example Client Usage

use hash_rings::consistent::Client;
use std::collections::hash_map::DefaultHasher;
use std::hash::BuildHasherDefault;

type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;

fn main() {
    let mut c = Client::with_hasher(DefaultBuildHasher::default());
    c.insert_node(&"node-1", 1);
    c.insert_node(&"node-2", 3);

    c.insert_point(&"point-1");

    assert_eq!(c.get_node(&"point-1"), &"node-1");
    assert_eq!(c.get_points(&"node-1"), [&"point-1"]);
}

Usage

Add this to your Cargo.toml:

[dependencies]
hash-rings = "*"

and this to your crate root if you are using Rust 2015:

extern crate hash_rings;

Benchmarks

Benching carp hashing (10 nodes, 100000 items)
15848556381555908996 - Expected: 0.155015 | Actual: 0.155180 | Error: -0.001060
06801744144136471498 - Expected: 0.056593 | Actual: 0.056960 | Error: -0.006447
16730135874920933484 - Expected: 0.015944 | Actual: 0.016030 | Error: -0.005355
11802923454833793349 - Expected: 0.135407 | Actual: 0.134050 | Error:  0.010122
14589965171469706430 - Expected: 0.091974 | Actual: 0.093030 | Error: -0.011348
06790293794189608791 - Expected: 0.122949 | Actual: 0.123230 | Error: -0.002284
08283237945741952176 - Expected: 0.042317 | Actual: 0.042880 | Error: -0.013126
06540337216311911463 - Expected: 0.146495 | Actual: 0.145220 | Error:  0.008782
13241461372147825909 - Expected: 0.084205 | Actual: 0.084330 | Error: -0.001484
06769854041949442045 - Expected: 0.149100 | Actual: 0.149090 | Error:  0.000070

Total elapsed time:           1336.552 ms
Milliseconds per operation:  13365.519 ns
Operations per second:       74819.391 op/ms


Benching consistent hashing (10 nodes, 1611 replicas, 100000 items)
15848556381555908996 - Expected: 0.100000 | Actual: 0.102070 | Error: -0.020280
13987966085338848396 - Expected: 0.100000 | Actual: 0.102410 | Error: -0.023533
06801744144136471498 - Expected: 0.100000 | Actual: 0.102240 | Error: -0.021909
04005265977620077421 - Expected: 0.100000 | Actual: 0.100010 | Error: -0.000100
16730135874920933484 - Expected: 0.100000 | Actual: 0.098970 | Error:  0.010407
13195988079190323012 - Expected: 0.100000 | Actual: 0.099630 | Error:  0.003714
11802923454833793349 - Expected: 0.100000 | Actual: 0.102730 | Error: -0.026575
05146857450694500275 - Expected: 0.100000 | Actual: 0.099290 | Error:  0.007151
14589965171469706430 - Expected: 0.100000 | Actual: 0.098170 | Error:  0.018641
17291863876572781215 - Expected: 0.100000 | Actual: 0.094480 | Error:  0.058425

Total elapsed time:            417.016 ms
Milliseconds per operation:   4170.163 ns
Operations per second:      239798.789 op/ms


Benching jump hashing (10 nodes, 100000 items)
00000000000000000000 - Expected: 0.100000 | Actual: 0.098250 | Error:  0.017812
00000000000000000001 - Expected: 0.100000 | Actual: 0.100140 | Error: -0.001398
00000000000000000002 - Expected: 0.100000 | Actual: 0.100280 | Error: -0.002792
00000000000000000003 - Expected: 0.100000 | Actual: 0.100240 | Error: -0.002394
00000000000000000004 - Expected: 0.100000 | Actual: 0.101550 | Error: -0.015263
00000000000000000005 - Expected: 0.100000 | Actual: 0.099290 | Error:  0.007151
00000000000000000006 - Expected: 0.100000 | Actual: 0.100750 | Error: -0.007444
00000000000000000007 - Expected: 0.100000 | Actual: 0.100130 | Error: -0.001298
00000000000000000008 - Expected: 0.100000 | Actual: 0.098730 | Error:  0.012863
00000000000000000009 - Expected: 0.100000 | Actual: 0.100640 | Error: -0.006359

Total elapsed time:            191.231 ms
Milliseconds per operation:   1912.314 ns
Operations per second:      522926.543 op/ms


Benching maglev hashing (10 nodes, 100000 items)
15848556381555908996 - Expected: 0.100000 | Actual: 0.099670 | Error:  0.003311
13987966085338848396 - Expected: 0.100000 | Actual: 0.100700 | Error: -0.006951
06801744144136471498 - Expected: 0.100000 | Actual: 0.099130 | Error:  0.008776
04005265977620077421 - Expected: 0.100000 | Actual: 0.099960 | Error:  0.000400
16730135874920933484 - Expected: 0.100000 | Actual: 0.101340 | Error: -0.013223
13195988079190323012 - Expected: 0.100000 | Actual: 0.098740 | Error:  0.012761
11802923454833793349 - Expected: 0.100000 | Actual: 0.100650 | Error: -0.006458
05146857450694500275 - Expected: 0.100000 | Actual: 0.101050 | Error: -0.010391
14589965171469706430 - Expected: 0.100000 | Actual: 0.100660 | Error: -0.006557
17291863876572781215 - Expected: 0.100000 | Actual: 0.098100 | Error:  0.019368

Total elapsed time:            188.203 ms
Milliseconds per operation:   1882.027 ns
Operations per second:      531342.016 op/ms


Benching mpc hashing (10 nodes, 21 probes, 100000 items)
15848556381555908996 - Expected: 0.100000 | Actual: 0.096820 | Error:  0.032844
13987966085338848396 - Expected: 0.100000 | Actual: 0.098510 | Error:  0.015125
06801744144136471498 - Expected: 0.100000 | Actual: 0.103730 | Error: -0.035959
04005265977620077421 - Expected: 0.100000 | Actual: 0.093530 | Error:  0.069176
16730135874920933484 - Expected: 0.100000 | Actual: 0.103210 | Error: -0.031102
13195988079190323012 - Expected: 0.100000 | Actual: 0.083890 | Error:  0.192037
11802923454833793349 - Expected: 0.100000 | Actual: 0.096990 | Error:  0.031034
05146857450694500275 - Expected: 0.100000 | Actual: 0.111780 | Error: -0.105386
14589965171469706430 - Expected: 0.100000 | Actual: 0.098680 | Error:  0.013377
17291863876572781215 - Expected: 0.100000 | Actual: 0.112860 | Error: -0.113946

Total elapsed time:           1153.555 ms
Milliseconds per operation:  11535.552 ns
Operations per second:       86688.529 op/ms


Benching rendezvous hashing (10 nodes, 100000 items)
15848556381555908996 - Expected: 0.100000 | Actual: 0.099680 | Error:  0.003210
13987966085338848396 - Expected: 0.100000 | Actual: 0.100710 | Error: -0.007050
06801744144136471498 - Expected: 0.100000 | Actual: 0.100320 | Error: -0.003190
04005265977620077421 - Expected: 0.100000 | Actual: 0.099820 | Error:  0.001803
16730135874920933484 - Expected: 0.100000 | Actual: 0.099900 | Error:  0.001001
13195988079190323012 - Expected: 0.100000 | Actual: 0.100600 | Error: -0.005964
11802923454833793349 - Expected: 0.100000 | Actual: 0.098440 | Error:  0.015847
05146857450694500275 - Expected: 0.100000 | Actual: 0.099440 | Error:  0.005632
14589965171469706430 - Expected: 0.100000 | Actual: 0.101420 | Error: -0.014001
17291863876572781215 - Expected: 0.100000 | Actual: 0.099670 | Error:  0.003311

Total elapsed time:           1623.272 ms
Milliseconds per operation:  16232.719 ns
Operations per second:       61603.972 op/ms


Benching weighted rendezvous hashing (10 nodes, 100000 items)
15848556381555908996 - Expected: 0.155015 | Actual: 0.154470 | Error:  0.003531
06801744144136471498 - Expected: 0.056593 | Actual: 0.057320 | Error: -0.012687
16730135874920933484 - Expected: 0.015944 | Actual: 0.016210 | Error: -0.016400
11802923454833793349 - Expected: 0.135407 | Actual: 0.134700 | Error:  0.005248
14589965171469706430 - Expected: 0.091974 | Actual: 0.092940 | Error: -0.010391
06790293794189608791 - Expected: 0.122949 | Actual: 0.123490 | Error: -0.004385
08283237945741952176 - Expected: 0.042317 | Actual: 0.042200 | Error:  0.002776
06540337216311911463 - Expected: 0.146495 | Actual: 0.144770 | Error:  0.011918
13241461372147825909 - Expected: 0.084205 | Actual: 0.083530 | Error:  0.008080
06769854041949442045 - Expected: 0.149100 | Actual: 0.150370 | Error: -0.008443

Total elapsed time:           2233.020 ms
Milliseconds per operation:  22330.205 ns
Operations per second:       44782.393 op/ms

Changelog

See CHANGELOG for more details.

References

License

hash-rings-rs is dual-licensed under the terms of either the MIT License or the Apache License (Version 2.0).

See LICENSE-APACHE and LICENSE-MIT for more details.

Commit count: 79

cargo fmt