布隆过滤器、一致性hash

hash

布隆过滤器：失误率

布隆过滤器：比特类型的数组 0 1

url--hash1.hash2..hashk  每次k个位置为1  

hash函数的大小不影响布隆过滤器的大小 m

布隆过滤器的长度：m=-(n*lnp)/(ln2)^2  p=0.0001;  n样本量

hash函数的个数：k=ln2*(m/n)=0.7*(m/n);

错误率：(1-e^(-n*k/m))^k;

一致性hash（负载均衡）

hash环  找到顺时针最近的一个服务器m

减少数据迁移的代价。加机器和减机器。

当服务器很少的时候，环可能不均匀。

一开始均匀，后期增删机器，数据迁移后就不均匀了。

解决方案

虚拟节点

给m1 复制1000个虚拟节点同理 m2 m3.。。。建立一个路由表，路由表对应虚拟节点和物理节点。

由增加机器后，仍然是均分的虚拟节点。增加节点同时增加同量的1000个虚拟节点。这1000个是

从m1 m2 m3 均摊出来的。 

布隆过滤器、一致性hash

原文：https://www.cnblogs.com/bowenqianngzhibushiwo/p/11631962.html