|
大数据基本算法与协议 抽样调查，分析数据 特点： 大量、高速、多样、低价值密度、真实性 一、数据分片 1.哈希分片(哈希取模法) 优点：简单 缺点：缺乏灵活性 负载均衡（一致性哈希：Hadoop、NGINX、MemerCache) 查找数据（二分法） N31 ← N25 ← N20 ←N14 ←N8 ← N5 ←N0 循环1，2，… ; 形成一个环状序列 使用虚拟节点目的： 1.解决机器节点映射位置的随机性导致的负载不均匀 2.让尽可能多的结点参与节点的新建 3.允许使用异质机器 虚拟桶（非一致性哈希：Redis、Redbase） 1、键值哈希 2、哈希到那台机器 2.范围分片 隐含条件：递增、有序、连续 a.键值(库少的情况) Q、1w条数据做分库？（键值【start，end】） 1~1000 … 9000~10000 b.冗余处理(库多的情况) 二进制取膜算法 二、一致性协议(Paxos) 角色：倡议者(Proposer)、接受者(Acceptor)、学习者(Learner) 少数服从多数人的决议，新入的机器也需要遵循之前统一定下的规则。 Multi Paxos执行过程： 一次请求，多次计算，选出领导者 三、常见算法 Bloom Filter(布隆过滤器) Q、检查一个数据是否在数据集中？ 1、建立多个哈希，做标记1 SkipList 一个跳表分几个层，第一层包含所有个元素， LSM树(Log-structured Merge-tree) 缺点：查找文件数大 Merkle树（区块链） Cuckoo哈希 CukooHash(布谷鸟散列)是为了解决哈希冲突问题而提出，利用较少的计算换取较大的空间。 MySQL（B-树）、MangoDB(B+树) 四、通信协议 Gossip 协议 “一传十，十传百”模式 交换信息方式 push模式 pull模式 分布是缓存 |
|
|
