《Disigning Data-Intensive Applications》 Part II(2)

上一篇讲了分布式系统中的复制,有了复制之后,我们已经可以解决很多问题了:错误容忍、跨地域延时、读性能扩展等。但是如果数据量太大,或者写压力太大,我们还需要借助另外一个重型武器:分区,partitions

分区

关于分区,有很多名字,比如shardregionvnodevbucket等,在后面的描述中,我们统一称为partition。分区数据库在1980s就开始有了。分区和复制是一对好基友,经常一起出现。

Partitioning of Key-Value Data

如果要把数据分区,那么面临的第一个问题就是分区规则的问题。如果分区不合理,可能会导致data skew或者query skew。如果某一个分区的负载过高,我们称之为hot spot

分区负载过高有时候并不是分区的规则不合理,而是业务访问就具备了这种特性,比如说对随机热点商品的访问。Tair MDB/RDB在处理分布式分区系统热点问题上有非常创新实用的解法,详见此处

Partitioning by Key Range

按照key范围进行分区的好处是对于范围扫描非常有利(分布式文件系统的元数据),但是同时也有很致命的,非常容易产生访问热点。

Partitioning by Hash of Key

使用key的哈希值来分区可以避免前面提到使用key范围分组的热点问题(当然,如果是针对某一个key的热点,还是需要像Tair使用的更加non-trivial的方法)。对于primary key的范围扫描,使用哈希分区的方法就比较困难了。RiakCouchbaseVoldemort中不支持对primary key的范围扫描。

Skewed Workloads and Relieving Hot Spots

这里介绍的是一种trivial的方法,通过预先把key拆分成多个子key来做。Tair的方法针对服务场景做了特殊的优化,是非常智能的解决方案。

Partitioning and Secondary Indexes

之前都是讨论的主键索引,但是二级索引也同样重要。在关系型数据库中,二级索引就是面包和黄油,文档数据库中也是需要的。像Hbase这样的键值存储因为实现的复杂性放弃了对二级索引的支持,但是二级索引对于应用来说是非常友好的,所以,依然有像Riak这样的键值存储支持了这个特性。

对于SlorElasticSearch这样的搜索系统来说,二级索引更加是必不可少的。

Partitioning Secondary Indexes by Document

这种对二级索引进行分区的方式是比较trivial的,每个分区上的二级索引只是针对本分区上的数据的。这种document-partitioned的索引也被称为local index的。如下图所示,这种索引方式下如果需要针对二级索引的列进行查询的话,需要把请求发送到所有的分区,把结果收集起来:

这种方式的好像是更新二级索引会是一个本地更新的操作,对于写请求来说是友好的,对于读请求来说,会有放大。如果我只是计算某一个secondary key的聚合值,比如说是否存在、有多少文档有这个值的话,依然需要把请求发送到所有的节点。

这种方式是使用得比较多的,Mongodb / Riak / Cassandra / ElasticSearch / SolrCloud / VoltDB 都是使用的这种方式,以至于我们会忘记另外一种方式的存在。

Partitioning Secondary Indexes by Term

上面的方式中,二级索引的存放完全依赖于主键的分区。这里要介绍一种global index的方式,对于二级索引,会选用一种自己的分区方式。二级索引针对 secondary key 来进行分区,这里分区可以是secondary key的范围也可以是哈希。

这种方式的劣势是,插入的时候可能会涉及到分布式事务,因为要更新的二级索引的条目和主键的条目可能不在一个分区。使用这种方式的时候如果同步地更新索引是会阻塞写入的,所以在DynamoDB使用了异步的方式对它的global secondary index进行更新。

Rebalancing Partitions

随着时间的变化 ,访问的吞吐量、数据大小会发生变化 ,集群的节点会失效,所以这样改变都会涉及到分区的重新均衡。合格的重新均衡算法至少需要满足:均衡完成之后,集群中的节点负载应该是相同的;在重新均衡的过程中,集群仍然可以提供读写;迁移的数据应该越少越好。

Strategies for Rebalancing

How not to do it: hash mod N

对节点数进行取模是一种典型的反面教材,这样会导致节点增加或减少之后,产生非常多不必要的数据迁移。

Fixed number of partitions

指定固定的分区数,这个值需要比集群中的节点数多得多。这是一种常见有效的方式,Tair的全线产品都这种方式。集群拓扑发生变化时,分区数和key与分区的对应关系是不变化的,唯一变化的是每个节点持有的分区,如下图所示:

使用这种方式的系统大多是不会改变分区数的,但是也有系统会支持分区的分裂和合并。分区数的选择是比较难的,如果太小的话,集群中的节点数会受制约;如果太大了的话,会带来额外的管理开销。

Dynamic partitioning

使用范围分区的系统通常是这样的,支持动态地均衡分区。当某一个分区的数据量太大的时候,会分裂出新的分区。Mongodb 2.4也支持哈希规则时进行动态分区。pre-splitting是需要支持的,要不然空集群的时候就只有一个节点会接收到请求。

Partitioning proportionally to nodes

在动态分区中,分区的数目和集群的数据量是成正比的,每个分区的数据量保持在一个区间内。对于固定分区数而言,每个分区的数据量和集群的数据量是成正比的。在这两种方式下,分区数目和集群中节点的数目都是没有关系的。

对于CassandraKetama而言(KetamaMemchached中使用的库),使用的方法是每个节点拥有固定的分区数,分区数目和节点的数目成正比。这种方式会导致不必要的split,但是每个节点的分区数比较多的时候,这个影响是可控的。Cassandra 3.0中引入了新的算法避免产生不必要的split

Operations: Automatic or Manual Rebalancing

在完全自动和完全手动的rebalancing之间还有很多gradient,比如CouchbaseRiakVoldemort会给出rebalancing的建议,真正的动作需要管理员来触发。作者很实诚地说:

For that reason, it can be a good thing to have a human in the loop for rebalancing.
It’s slower than a fully automatic process, but it can help prevent operational
surprises.

自动的rebalancing和自动的故障检测结合到了一起会有些惊喜发生,如果节点负载过高导致判活失败,可能会导致cascading的失败。这个就需要系统做得精细一些来保证了,必须要自动的rebalancing啊。

Request Routing

上面已经讲了服务端如何进行数据分区了,那么客户端怎么感知这个分区信息呢?如果分区发生了重新均衡,客户端是如何感知到的呢?

有几种方式解决第1个问题:

  1. 让客户端能连接到所有的节点。节点如果发现请求的分区自己没有持有,就转发到对应的节点,比如说redis cluster
  2. 客户端先把请求发送到一个routing tier,比如说Mongodbmongos
  3. 客户端能感知到分区信息,把请求发送到对应的节点,smart client的方案,Tair全系产品使用的这种方式

分区发生改变的时候如何通知客户端是一个比较难的问题,因为需要让分布式系统的所有参与方都达成一致。很多分布式系统使用ZooKeeper来管理集群的元信息,ZooKeeper会通知routing tier分区的变化。

Hbase / SolrCloud / Kafka 都是使用的这种方式,Mongodb也类似,只是它没有使用ZooKeeper,而是使用的自己的Config Server

CassandraRiak使用了第1种方法,使用gossip protocol来传递集群状态的变化。Couchbase不支持自动的重新均衡,所以需要依靠配置moxi来更新集群的状态。

Parallel Query Execution

我们目前关注的都是一些非常简单的查询 ,massively parallel processing的关系型数据库产品支持的查询类型是非常复杂的。MPP查询优化器会把复杂的查询分拆成多个执行阶段和分区,这些子查询可以并行地在集群中各个分区上执行。

最后

这一节介绍了分区相关的内容,如果客户端一个更新操作需要操作多个分区的数据,比如说跨行事务,这时候需要如何处理呢,且听下回分解,数据系统王冠上的明珠:事务。