大数据算法开发方案讲解

大数据算法开发方案讲解，包括蓄水池抽样算法、限流算法漏斗和令牌桶区别、一致性Hash 算法等等。

大数据算法开发方案讲解

• LRU
  • 基于时间的算法.最近最久未访问 Least Frequently Used
  • 三种实现
    • 1.用一个数组来存储数据 给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
    • 2.利用一个链表来实现 每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。
    • 3. 利用链表和hashmap。同时维护链表和 map,map用来索引查找 当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项
  • Java实现
    • LinkedHashMap
  • 缺点
    • 当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
  • LRU-K算法
    • LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
    • 实现
      • LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史
      • 只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
      • 数据第一次被访问时，加入到历史访问列表，如果书籍在访问历史列表中没有达到K次访问，则按照一定的规则（FIFO,LRU）淘汰
  • LRU-2
    • 2Q将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。
    • 当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。
    • 避免了批量的查询对于缓存的破坏
  • Multi Queue
    • MQ算法根据访问频率将数据划分为多个队列，不同的队列具有不同的访问优先级，其核心思想是：优先缓存访问次数多的数据。详细的算法结构图如下，Q0，Q1....Qk代表不同的优先级队列，Q-history代表从缓存中淘汰数据，但记录了数据的索引和引用次数的队列
    • 新插入的数据放入Q0，每个队列按照LRU进行管理，当数据的访问次数达到一定次数，需要提升优先级时，将数据从当前队列中删除，加入到高一级队列的头部；为了防止高优先级数据永远不会被淘汰，当数据在指定的时间里没有被访问时，需要降低优先级，将数据从当前队列删除，加入到低一级的队列头部；需要淘汰数据时，从最低一级队列开始按照LRU淘汰，每个队列淘汰数据时，将数据从缓存中删除，将数据索引加入Q-history头部。如果数据在Q-history中被重新访问，则重新计算其优先级，移到目标队列头部。Q-history按照LRU淘汰数据的索引。
• FIFO
  • 先进先出页面置换算法
  • 维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾
  • 该算法不会对使用频率进行统计,仅仅根据一开始进入缓存的时间作为依据, 谁进入的最老谁最先被丢弃.
  • 该算法可能会将使用频率比较高的元素, 丢弃. 实际上 LRU 算法是 FIFO的优化,没新访问一次就将其放在缓存头部
• NRU
  • 最近未使用页面置换算法
  • 该算法关注 访问元素的状态位 ,每次清理时,只清理掉 未访问到的元素
  • 还需要一个定时机制能够 定期的清理 元素的标记位,将其标记为未访问
• 蓄水池抽样算法
  • 给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据
  • 特点
    • 数据流长度N很大且不可知，所以不能一次性存入内存。
    • 时间复杂度为O(N)。
    • 随机选取m个数，每个数被选中的概率为m/N。
  • 思路
    • 如果接收的数据量小于m，则依次放入蓄水池。
    • 当接收到第i个数据时，i >= m，在[0, i]范围内取以随机数d，若d的落在[0, m-1]范围内，则用接收到的第i个数据替换蓄水池中的第d个数据。
    • 重复步骤2。
  • 推导
    • 第i个接收到的数据最后能够留在蓄水池中的概率=第i个数据进入过蓄水池的概率*之后第i个数据不被替换的概率（第i+1到第N次处理数据都不会被替换）。
    • 思路: 分别证明 当i <=m,时, 进入蓄水池的概率和 不被后边值替换的概率 当i>m 时, 进入蓄水池的概率和 不被后边替换的概率 重要证明在下面
    • 当i<=m时，程序从接收到第m+1个数据时开始执行替换操作，第m+1次处理会替换池中数据的为m/(m+1)，会替换掉第i个数据的概率为1/m，则第m+1次处理替换掉第i个数据的概率为(m/(m+1))*(1/m)=1/(m+1)，不被替换的概率为1-1/(m+1)=m/(m+1)。依次，第m+2次处理不替换掉第i个数据概率为(m+1)/(m+2)...第N次处理不替换掉第i个数据的概率为(N-1)/N。所以，之后第i个数据不被替换的概率=m/(m+1)*(m+1)/(m+2)*...*(N-1)/N=m/N。
  • 分布式蓄水池
    • 思路: 1. 将N 分到k 个机器上,可以按照hash来分片 2. 单机分别蓄水池得到 m 个 值 3. 在[1,N]中随机取一个值, 若在N1(第一个机器上,如果用hash 直接就能根据hash 计算出来) 上,则从第一个蓄水池中,随机1/m取一个值
    • 假设有K台机器，将大数据集分成K个数据流，每台机器使用单机版蓄水池抽样处理一个数据流，抽样m个数据，并最后记录处理的数据量为N1, N2, ..., Nk, ..., NK(假设m<Nk)。N1+N2+...+NK=N。
    • 取[1, N]一个随机数d，若d<N1，则在第一台机器的蓄水池中等概率不放回地（1/m）选取一个数据；若N1<=d<(N1+N2)，则在第二台机器的蓄水池中等概率不放回地选取一个数据；一次类推，重复m次，则最终从N大数据集中选出m个数据。
    • 推导
      • 第k台机器中的蓄水池数据被选取的概率为m/Nk。
      • 从第k台机器的蓄水池中选取一个数据放进最终蓄水池的概率为Nk/N。
      • 第k台机器蓄水池的一个数据被选中的概率为1/m。（不放回选取时等概率的）
      • 重复m次选取，则每个数据被选中的概率为m*(m/Nk*Nk/N*1/m)=m/N
• 限流算法漏斗和令牌桶区别
  • 漏斗算法
    • 设置漏斗总容量即服务的最高并发级别
    • 设置漏斗的消耗速率,该速率是固定的
    • 漏斗默认是空的,请求进入到桶中.
    • 漏斗算法其实是悲观的，因为它严格限制了系统的吞吐量，从某种角度上来说，它的效果和并发量限流很类似。漏斗算法也可以用于大多数场景，但由于它对服务吞吐量有着严格固定的限制
    • 保证服务的最高并发次数,但是在瞬间流量增大情况下,表现不好
  • 令牌桶算法
    • 令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。
    • 令牌桶可以为空时,请求会被丢弃. 同时令牌按照1/r 速度向桶中存放令牌
• 一致性Hash 算法
  • 作用
    • 负载均衡
    • 处理分片,无分布式锁架构
  • 常见Hash 算法不能解决增减节点 缓存大量漂移失效情况
  • 如何处理漂移情况
    • 使用Hash环
    • 将请求路由到环中,漂移时将请求漂移给上一个顺时针上一个节点
  • 如何避免漂移后处理不均衡的情况
    • 使用虚拟节点.
      • 使用物理节点到虚拟节点的映射.将一个物理节点映射多个虚拟节点.
      • 虚拟节点的key 可以使用前缀+数字标记.这样根据虚拟节点字节可以定位到物理节点
      • 物理节点到虚拟节点的映射并不是严格的划片,而是完全随机的.
        • 当发生漂移时,该物理节点漂移到的节点完全随机,避免一个 物理节点完全漂移到另一个物理节点.造成负载失衡
  • 实际实现
    • 包括hash 环 add,remove和hash 节点的定位
    • 使用两个 Map
      • 一个treemap存储hash虚拟节点到物理节点的映射.同时key 是可以排序的, 给定hash 值可以定位到具体哪个虚拟节点应该处理,进而根据虚拟节点前缀 确定物理节点(key:hash value: 物理节点#index)
      • 存储 物理节点到虚拟节点的映射.其中 key 是物理节点,value 是对应的虚拟节点hash值.(查询 treemap 可以找到)
      • 当添加物理节点时,生成若干(可以定义)虚拟节点.存储在两个map 钟
      • 当删除物理节点时,查询物理节点对应的虚拟节点,开始执行漂移逻辑,将请求漂移到该节点的上一个节点 需要将虚拟节点的 treemap value修改为上一个key对应的 value.
      • 使用 murmur 将相似度非常高的key散列的足够均匀.随机性越好.此时 漂移就可以做的足够随机,实际物理节点负载不比较均匀
      • 具体的漂移逻辑由客户端自己实现
        • 添加时也需要漂移,以前由上一个节点处理的请求要被路由到本节点. 删除时,,本节点处理的请求要被转发出去
    • murmur
      • 非加密哈希算法