7 个版本 (2 个稳定版)

1.1.0	2019年10月11日
1.0.0	2018年10月6日
0.3.0	2018年5月12日
0.2.3	2018年5月1日
0.1.0	2018年4月5日

在数据结构中排名 1165

每月下载量 32

MIT/Apache

125KB
2K SLoC

hash-rings-rs

hash-rings 包含七种不同的哈希环算法的实现：缓存数组路由协议、一致性哈希、多探测一致性哈希、 rendezvous 哈希、加权 rendezvous 哈希、 Maglev 哈希和跳跃哈希。它还提供了 Consistent Hashing、Rendezvous Hashing 和 Weighted Rendezvous Hashing 的客户端，以有效地在节点插入和从环中删除时重新分配项目。

示例

示例环使用

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");
}

示例客户端使用

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"]);
}

用法

将此添加到您的 Cargo.toml

[dependencies]
hash-rings = "*"

如果您使用 Rust 2015，请将此添加到您的 crate 根目录

extern crate hash_rings;

基准测试

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

变更日志

有关更多详细信息，请参阅变更日志。

参考文献

一种快速、内存占用最小的哈希算法

Lamping, John, 和 Eric Veach. 2014. “一种快速、内存占用最小的哈希算法。” CoRR abs/1406.2294. http://arxiv.org/abs/1406.2294.
缓存数组路由协议
一致性哈希和随机树：缓解万维网热点问题的分布式缓存协议

Karger, David, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, 和 Daniel Lewin. 1997. “一致性哈希和随机树：缓解万维网热点问题的分布式缓存协议。” 在 第29届 ACM 理论计算研讨会论文集，654–63. STOC ’97。纽约，美国纽约：ACM。doi:10.1145/258533.258660.
Maglev：一种快速且可靠的软件网络负载均衡器

Eisenbud, Daniel E., Cheng Yi, Carlo Contavalli, Cody Smith, Roman Kononov, Eric Mann-Hielscher, Ardas Cilingiroglu, Bin Cheyney, Wentao Shang, 和 Jinnah Dylan Hosein. 2016. “Maglev：一种快速且可靠的软件网络负载均衡器。” 在 第13届 Usenix 网络系统设计与实现研讨会（Nsdi 16），523–35. 圣克拉拉，加州。 https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/eisenbud.
多探测一致性哈希

Appleton, Ben, 和 Michael O’Reilly. 2015. “多探测一致性哈希。” CoRR abs/1505.00062. http://arxiv.org/abs/1505.00062.
使用基于名称的映射来提高命中率

Thaler, David G. 和 Chinya V. Ravishankar. 1998. “利用基于名称的映射来提高命中率。” IEEE/ACM Trans. Netw. 6 (1). Piscataway, NJ, 美国: IEEE Press: 1–14. doi:10.1109/90.663936.
加权分布式哈希表

Schindelhauer, Christian 和 Gunnar Schomaker. 2005. “加权分布式哈希表。”见《第十七届ACM算法与架构并行性年会论文集》，218–27. SPAA '05. 纽约，NY，美国: ACM. doi:10.1145/1073970.1074008.
具有有限负载的一致性哈希

Mirrokni, Vahab，Mikkel Thorup 和 Morteza Zadimoghaddam. 2018. “具有有限负载的一致性哈希。”见《第二十九届ACM-SIAM离散算法年会论文集》，587–604. SIAM.

许可证

hash-rings-rs根据MIT许可证或Apache许可证（版本2.0）的双重许可条款。

有关详细信息，请参阅LICENSE-APACHE 和 LICENSE-MIT.

依赖关系

~1.5MB
~22K SLoC