数据管理-多结构化数据管理

</div>

</div>

• memcached
  • 分布式内存对象
  • 内存分配原理
    • Chunk，按照预先规定的大小，将分配的内存分割成
    • slab class，尺寸相同的Chunk分组
    • 分配到的内存不会释放，会自动重用（早期的频繁调用malloc，free导致系统负载过高）
    • Lazy Expiration
      • 记录超时不会释放已分配内存，直接在get的时候看是否过期
    • 替换策略
      • LRU
  • 分布函数
    • 过程
      • 求得key hash
      • 除以台数，根据其余数来选择服务器
      • 无法连接则rehash，再尝试连接
    • 优缺点
      • 方法简单，分散性好
      • 当添加或移除服务器时，缓存重组的代价大
  • 一致性hash（改进）
    • consistent hashing
      • 求出服务器的hash，配置到0-2^32的圆上，对应一个hash范围而不是hash值
      • 用相同 的方法求出key hash，映射到圆上
      • 从数据映射到的位置开始顺时针查找，将数据保存到找到的第一台服务器上
      • 如果超过2^32仍然找不到服务器，就保存到第一台服务器上
      • 如果有结点数据分配不均衡（利用率低），可以建立虚拟结点，代理到数据分布密集的地方
• DynamoDB（一致性hash的另一个应用）
  • 无中心master，对等集群
  • 数据传输使用gosip协议
  • 设计
    • 高拓展
    • 简单的key-value
    • 高可用
    • 服务器级别的协议保证
      • 在峰值每秒500个请求时，保证99.9%的可以在300ms内响应
  • 基本设计思想
    • 为了达到高可用，牺牲一致性
    • 读数据时处理数据不一致冲突
    • 根据不同需求，指定不同的NRW值，协调可用性和一致性
    • 去中心化的维护成员和故障信息，采用gossip同步
  • 改进策略
    • 将整个地址空间平均分成Q个虚拟结点，每个物理结点得到\frac{Q}{S}个虚拟结点
    • 进场，则其他每个结点分配给新来的结点
    • 离场，将虚拟结点给原来的虚拟结点
  • Sloppy quarum（草率仲裁，草率的法定人数）
    • 每个对象有N个副本，确保W+R>N保证数据正确
      • 选出一个coordinator
      • PUT收到W-1个确认
      • READ收到R-1个确认
    • vector clock（逻辑时钟）
      • 每个机器本地有个逻辑时钟LC_i
      • 每发生一个事件设置为LC_i + 1
      • i给j发送消息m，把LC_i存在消息里 今天23
      • 机器j收到信息m后，
        • LC_j = max(LC_j,m_timestamp) + 1，结果值作为收到消息m这个事件的时间戳
  • 临时失效
    • 暗示接力
  • 通过反熵协议（基于Gossip的一致同步）来保持副本同步
    • 采用Merkle Tree技术
      • hash tree，二叉树
  • 零知识证明
    • 满足特性
      • if true, 诚实的验证者将确信证明者的事实
      • if false，不排除有概率欺骗者可以说服诚实的验证者它是真的
    • 类似于bloom过滤器
  • 总结
    • 一致性hash
    • NRW读写协议
    • Vector Clock -- Lamport --paxos -- chubby, zookeeper -- BigTable
    • 永久性失效处理——Merkel Tree——区块链技术、BitTorrent文件传输（P2P ）
    • Gossip协议（P2P）
• Redis Cluster
  • RedisObject对象hash类型关注列表，粉丝列表skip list 跳跃表
    • 随机化的数据结构，基于并联，效率相当于二叉查找树。对于大多数操作需要O(log n)平均时间
    • 基本思想Level 3： -1 -> 21 -> 37 -> 1（index）
      Level 2： -1 -> 7 -> 21 -> 37 -> 71 -> 1（index）
      Level 1： -1 -> 7 -> 14 -> 21 ...（real data）
    • 不使用B+树的原因：主要是结点的分裂、合并，容易引起动荡持久化机制
    • RDB快照
      • 可靠性：当快照存成一个数据文件，写入临时文件，然后借助原子性系统调用rename将文件重命名为RDB文件
      • 生成时机：可以通过save指令配置RDB快照生成的时机
      • 可用性：代价不高，但是自上一次RDB文件生成到Redis停机这段时间的数据会丢失
    • AOF（Append Only File）日志
      • 追加写入，写入的内容为Redis标准指令
      • 优化策略
        • 提供AOF rewrite功能，重新生成一份AOF文件，文件中一条记录的操作只会有一次，去掉之前叠加的操作分布式存储
    • 集群
      • 采用了P2P机制，没有Proxy层
      • Client保存集群中nodes与keys的映射关系，并保存此数据的更新
      • Client与每个结点保持连接
      • 没有Proxy层，Client请求的数据无法在nodes间merge
    • 允许单点故障
    • 没有中心节点
    • 具有线性可伸缩的功能
    • 不支持scan等操作
    • Redis槽
      • HASH_SLOT = CRC16(key) mod 16384
      • 也就是最多支持16384个node
    • Gossip协议
      • MEET握手
        • 第一次ping、pong，会触发MEET
      • PING，随机选择2个邻居结点发
      • PONG，同上数据迁移
    • 要迁移的槽被分别标记为迁出中、导入中。如果是导入状态则会等待数据获取
    • 若不在node上，则产生MOVED。然后Client将请求更新SLOT表。集群数据结构
    • Cluster State
    • Cluster SLOT
    • Cluster Link
• Trinity
  • 基于分布式内存的云系统
  • 本身不含有复杂的图计算模型，只是一个分布式的key-value系统，但是提供灵活的数据定义和处理建模的能力
  • 节点：slave、proxy、client体系结构
  • Slave：
    • 存储一部分图数据，执行图计算任务。图计算任务包括向其他各类节点收发消息
  • Proxy
    • 没有数据。作为client和slave节点的中间层，也用作消息聚集节点，可汇总来自多个slave的消息
  • Client
    • 用户接口层，通过API和slave、proxy结点通讯分布式缓存key值为64位全球唯一标识符，value为任意长度的blob串建议了key-slave结点的映射机制
  • 通过一致性hash实现节点动态加入或离开内存云图计算模式
  • 在线查询
  • 离线分析
  • 使用restrictive模型，每次只和固定的邻居结点集合通讯消息优化
  • 分割子图
  • 理想情况下，对图分割后，每个vertex节点只需要来自同一个partition的节点消息，可对这些消息进行本地缓存，争取使这些消息只发出一次。
    • 但是可能会有点，连接了大量的邻居结点
      • 解决：将结点分为两类
        • Hub结点，非hub结点
          • 缓存一部分的hub结点信息，其余的进行+1预取
• Kad网络
  • 一种典型的结构化P2P覆盖网络
  • 信息的存储：以hash条目的形式分散存储到各个节点中
    • 全网构成一张巨大的分布式哈希表
  • 检索：使用kademlia协议，查询key值对应的value存储
  • 字典条目均分布式存储于参与Kad网络的各个节点中，其存储和交换无需集中索引服务器的参与
    • 提高了查询效率
    • 提高了文件交换系统的可靠性网络结点ID和距离
  • 每个结点有一个ID，160bit的整数，节点自己生成
  • 距离为两个ID的二进制异或值节点维护
  • 第一个结点均维护160个list，每个list称为一个k-bucket
    • 第i个k桶的内容：记录当前节点已知的与自身距离为2^i - 2^{i+1}的其他节点的网络信息。（NodeID，IP，UDP端口）
    • 一个k-bucket最多存放k个对端节点信息，bucket中结点信息按访问时间排序
    • k-bucket更新：
      • 已经在list中，将其移动到队尾（LRU取队首删除）
      • list未满，直接插入队尾
      • list已满，先检查队首结点仍有响应，如果没有就删除，将最新的移动到队尾寻找结点查找与目标节点网络距离最近的k个节点所对应的网络信息(NodeID，IP地址，UDP端口)。 1）发起者从自己的k-桶中选出若干距离目标ID最近的节点，并向它们同时发送异步查询请求； 2）被查询节点收到请求后，从自己的k-桶中找出自己所知的目标ID的若干近邻返回给发起者； 3）发起者收到返回信息后，再次从当前已知的近邻节点中选出若干未被请求的，并重复步骤1。 重复上述过程2）~3）直至无法获得k近邻的更新时停止。 在查询过程中没有及时响应的节点将立即被排除。

小结

• Memcached（缓存系统、chunk块/slab块集、client实现分布式、一致性hash+虚拟结点、无冗余、处理“键值”集合）
  • 没有服务器的
  • 分布式靠算法完成
• DynamoDB(一致性hash+虚拟结点+固定、NWR读写协议、Vector Clock、Merkel Tree、Gossip协议)
• Redis（缓存系统、持久化、node/client、slot槽、client缓存、多副本、P2P去中心化、无proxy、Gossip协议MEET/PING/PONG消息、ASKED/MOVED异常处理，处理五类Redisobject的键值集合）
• Trinity（slave/proxy/client、slot槽、槽key向量、全局寻址表（slot数组）、slot内部hash表、2/8原理，图分割，restrictive模型，异步消息，TFS分布式文件系统，leader节点一致性广播，处理图数据）
• Kad（ P2P覆盖网络、逻辑距离、近邻列表、查询即迭代和传播，处理文件）