数据分区与路由

为什么要进行数据分区与路由？

大数据集 ⟶ 扩展 ⟶ 数据分片 / 分区 ⟶ 1) 数据访问的路由 2) 可用性的副本

• 优点
  • 可用性
  • 读取（并行化，单次读取效率）
• 缺点
  • 一致性

如何进行数据分区与路由？

路由抽象模型本质上只有两张地图：1) 键-分区图 2) 分区-机器图

哈希分区

1. 哈希和取模

   • (+) 简单
   • (-) 灵活性（紧耦合两张地图：添加和移除节点（分区-机器图）会破坏现有的键-分区图）

2. 虚拟桶：键--(哈希)-->虚拟桶，虚拟桶--(表查找)-->服务器

   • 使用案例：Membase 也称为 Couchbase，Riak
   • (+) 灵活性，解耦两张地图
   • (-) 集中式查找表

3. 一致性哈希和 DHT

   • [Chord] 实现
   • 虚拟节点：用于异构数据中心的负载均衡
   • 使用案例：Dynamo，Cassandra
   • (+) 灵活性，哈希空间解耦两张地图。两张地图使用相同的哈希，但添加和移除节点==只影响后续节点==。
   • (-) 网络复杂性，难以维护

范围分区

按主键排序，按主键范围分片

范围-服务器查找表（例如 HBase .META. 表）+ 本地基于树的索引（例如 LSM，B+）

(+) 搜索范围 (-) log(n)

使用案例：Yahoo PNUTS，Azure，Bigtable