数据分区与路由
为什么要进行数据分区与路由?
大数据集 ⟶ 扩展 ⟶ 数据分片 / 分区 ⟶ 1) 数据访问的路由 2) 可用性的副本
- 优点
- 可用性
- 读取(并行化,单次读取效率)
- 缺点
- 一致性
如何进行数据分区与路由?
路由抽象模型本质上只有两张地图:1) 键-分区图 2) 分区-机器图
哈希分区
-
哈希和取模
- (+) 简单
- (-) 灵活性(紧耦合两张地图:添加和移除节点(分区-机器图)会破坏现有的键-分区图)
-
虚拟桶:键--(哈希)-->虚拟桶,虚拟桶--(表查找)-->服务器
- 使用案例:Membase 也称为 Couchbase,Riak
- (+) 灵活性,解耦两张地图
- (-) 集中式查找表
-
一致性哈希和 DHT
- [Chord] 实现
- 虚拟 节点:用于异构数据中心的负载均衡
- 使用案例:Dynamo,Cassandra
- (+) 灵活性,哈希空间解耦两张地图。两张地图使用相同的哈希,但添加和移除节点==只影响后续节点==。
- (-) 网络复杂性,难以维护
范围分区
按主键排序,按主键范围分片
范围-服务器查找表(例如 HBase .META. 表)+ 本地基于树的索引(例如 LSM,B+)
(+) 搜索范围 (-) log(n)
使用案例:Yahoo PNUTS,Azure,Bigtable