Design Data Intensive Applicat

何为SHARDING:

将大数据集分为多个块，存储在不同的服务器上

目的：

可扩展性: 不同的分片可以放在不同的服务器上，分散读请求
复杂查询可以并行的在不同的分片上执行
写请求分散到各个服务器上

问题1: 怎么分？

每个服务器上数据保持均匀,避免数据倾斜

• 随机分配:
  优点: 数据均匀
  缺点: 无法知道数据在哪个节点
• 每个分片保存主键一个范围内连续键值 (partition by key range)
  优点: 容易算出主键在哪个节点. 主键可有序存储，方便范围搜索
  缺点: 每个分片数据可能不均匀，需要调节分片边界 --> 手动或自动. 主键前缀解决分布问题
• 按主键HASH值分片: （riak, couchbase, voldemort）
  优点: 理论上数据均匀，取决于HASH算法. 容易算出数据在哪个节点
  缺点: 难以进行范围搜索
• 混合模式: 联合主键，先按主键第一个属性HASH，再按其他属性有序排列 (cassandra)
  适合处理一对多数据
  处理数据倾斜和热点键读写:
  需要应用层解决: 如对键值增加随机前后缀. 缺点: 同一个键值的数据分散在不同分片内，增加读取复杂度

  问题2: 如何查询数据?

  分片策略解决了写和主键查询的问题，但是如何解决其他查询条件查询？如何在数据分片的情况下建立二级索引?

• 本地索引: 每个分片单独维护二级查询条件到主键列表的字典映射
  优点：写数据时更新索引时容易
  缺点：查询必须在每个分片的二级索引中查找，再合并结果
• 全局索引: 一个独立的索引结构覆盖所有分片，索引本身也分片，按照索引对应的查询条件 （term partitioned)
  优点：查询索引落到单个分片,效率高，如果采用RANGE分片也支持范围查询
  缺点: 写入数据复杂，写操作会影响多个分片(数据分片和索引分片未必在同一个节点), 需要分布式事务支持, 或者采用异步方式，牺牲一致性,新写入的数据未必立刻在索引中可见.

  问题3: 集群扩容或者有宕机节点分片数据如何处理?

  分片数据需要从一个节点迁移到另一个节点 (partition rebalancing)

  数据重平衡需求:

  1. 迁移后负载必须保持均匀 (集群扩容)
  2. 迁移中集群必须可用，读写无影响
  3. 迁移必须最小化不必要的数据移动，减少集群IO开销

     数据重平衡策略:

• hash取模会导致扩容后大量分片所处节点发生变化, 不满足上述需求3
• 不直接把key映射到node，而是先把key映射到partition, 再把partition映射到node. partition的数量远大于node的数量, 这样新增node获取部分partition数据, 同时保持key到partition的映射不变 （riak, elasticsearch, couchbase, voldemort)
  优点: 最小化扩容过程中的数据移动
  缺点: partition数量是永远固定的，不可增减, 决定partition的数量很难，每个partition的数据量过大或者过小都会带来额外开销
• 动态主键范围分片: 数据分片按照主键排序, 当分片超过配置大小后自动分裂为两个分片, 当分片由于数据删除过小后和相邻的分片做合并. (hbase, rethinkDB)
  优点: 分片大小自动适配集群数据量
  缺点: 数据库刚初始化时仅有一个分片, 读写负载不能有效分散. 解决方案: 配置预分片.
  动态分片也可应用于HASH分片
• 分片数同比例于节点数: 即每个节点上分片数固定. 新节点加入时，随机选取一定数量的分片做等分，把一半数据移动到新节点. (cassandra, ketama)
  缺点：只支持HASH分片. 随机选取可能导致数据不均匀

  人工或自动平衡:

  自动重平衡
  优点：不需要人工干预
  缺点：分片数据移动是昂贵的操作，会对集群性能产生不可知影响，并容易引起雪崩效应
  人工重平衡
  优点：可控性强
  缺点：响应速度慢

请求路由：

重平衡之后客户端需要知道连接到哪个节点

• 客户端可连接到任何节点，如果分区存在则处理请求，否则由节点负责将请求发往分片所在节点
  优点：客户端不需要存储分片METADATA，
  缺点：请求roundtrip时间可能变长
• 单独的路由层负责接收客户端请求并转发，路由层需要了解分片存储METADATA
  优点：客户端不需要存储分片METADATA，
  缺点：请求roundtrip时间可能变长

• 客户端存储分片METADATA并直接路由到新节点
  优点：直接路由, 速度快
  缺点：客户端需要感知分片topology变化

  客户端感知路由变化是一个挑战性的问题. (网络延迟/分区等), 需要分布式一致性协议，或者用集中式路由METADATA存储如zookeeper等

并行QUERY执行:

分析型数据库需要将复杂的QUERY分解成可多个并发执行的分片和阶段，构成一个有向无环图

其他：

一般SHARDING和REPLICATION会一起使用，一个分片会保存在多个服务器上
一致性HASH: 主要解决CDN网络随机选择分片边界而不需要一个集中式的一致性协议，一般不太适合使用于数据库