算法

---

近似判断值是否存在

• 布隆过滤器

  • 是用bitMap来存储值得hash，可以利用多个hash函数来增加精确度。 bitMap有则可能存在，没有则一定不存在。 (guava BloomFilterStrategies)

  • 缺点： 不支持删除元素，误算率随着数据量增加而增加

• 布谷鸟过滤器

  • 在布隆过滤器的基础上增加了删除功能，原理为布谷鸟鸠占鹊巢，新的值会占用旧的值的地方，旧的值也去占用别的值位置。每个值至少可以存在两个位置

  • 缺点： 数组必须是2的次幂，不能连续插入相同的值，可能导致循环占位，而后扩容占空间大

共识算法

• Paxos

  • 由 提案节点，决策节点，记录节点三种角色组成。 每个节点可以担任多个职位，并且遵守两个承诺一个应答原则。

• Multi-Paxos

  • 对Paxos存在的问题提出的一种优化算法，增加了选主来处理存在的活锁问题。

• Gossip

  • 流言算法、瘟疫算法， 每个节点将信息传播给与自己相连的节点，保证最终一致性