一种以ID特征为依据的数据分片（Sharding）策略
2010-03-09 21:51 by 老赵, 19377 visits假如您有一个应用程序，随着业务越来越有起色，系统所牵涉到的数据量也就越来越大，此时您要涉及到对系统进行伸缩（Scale）的问题了。一种典型的扩展方法叫做“向上伸缩（Scale Up）”，它的意思是通过使用更好的硬件来提高系统的性能参数。而另一种方法则叫做“向外伸缩（Scale Out）”，它是指通过增加额外的硬件（如服务器）来达到相同的效果。从“硬件成本”还是“系统极限”的角度来说，“向外伸缩”一般都会优于“向上伸缩”，因此大部分上规模的系统都会在一定程度上考虑“向外”的方式。由于许多系统的瓶颈都处在数据存储上，因此一种叫做“数据分片（Database Sharding）”的数据架构方式应运而生，本文便会讨论这种数据架构方式的一种比较典型的实现方式。
简介
数据分片，自然便是将整体数据分摊在多个存储设备（下文统称为“数据分区”或“分区”）上，这样每个存储设备的数据量相对就会小很多，以此满足系统的性能需求。值得注意的是，系统分片的策略有很多，例如常见的有以下几种：
- 根据ID特征：例如对记录的ID取模，得到的结果是几，那么这条记录就放在编号为几的数据分区上。
- 根据时间范围：例如前100万个用户数据在第1个分区中，第二个100万用户数据放在第2个分区中。
- 基于检索表：根据ID先去一个表内找到它所在的分区，然后再去目标分区进行查找。
- ……
在这些数据分片策略之中没有哪个有绝对的优势，选择哪种策略完全是根据系统的业务或是数据特征来确定的。值得强调的是：数据分片不是银弹，它对系统的性能和伸缩性（Scalability）带来一定好处的同时，也会对系统开发带来许多复杂度。例如，有两条记录分别处在不同的服务器上，那么如果有一个业务是为它们建立一个“关联”，那么很可能表示“关联”的记录就必须在两个分区内各放一条。另外，如果您重视数据的完整性，那么跨数据分区的事务又立即变成了性能杀手。最后，如果有一些需要进行全局查找的业务，光有数据分片策略也很难对系统性能带来什么优势。
数据分片虽然重要，但在使用之前一定要三思而后行。一旦踏上这艘贼船，往往不成功便成仁，很难回头。在我的经验里，一个滥用数据分片策略而事倍功半的项目给我留下了非常深刻的印象（当然也有成功的啦），因此目前我对待数据分片策略变得愈发谨慎。
那么现在，我们便来讨论一种比较常见的数据分片策略。
策略描述
这里我先描述一个极其简单的业务：
- 系统中有用户，用户可以发表文章，文章会有评论
- 可以根据用户查找文章
- 可以根据文章查找评论
那么，如果我要对这样一个系统进行数据分片又该怎么做呢？这里我们可以使用上面提到的第一种方式，即对记录的ID取模，并根据结果选择数据所在的分区。根据后两条业务中描述的查询要求，我们会为分区策略补充这样的规则：
- 某个用户的所有文章，与这个用户处在同一数据分区内。
- 某篇文章的所有评论，与这篇文章处在用一数据分区内。
您可能会说，似乎只要保证“相同用户文章在同一个数据分区内”就行了，不是吗？没错，不过我这里让文章和用户在同一个分区内，也是为了方便许多额外的操作（例如在关系数据库中进行连接）。那么假设我们有4个数据分区，那么它们内部的条目可能便是：
| 分区0 | 分区1 |
|
|
| 分区2 | 分区3 |
|
|
在ID为0的分区中，所有对象的ID模4均为0，其他分区里的对象也有这样的规律。那么好，在实际应用中，如果我们需要查找“ID为2的用户”，便去第2分区搜索便是；如果要查找“ID为8的文章的所有评论”那么也只要去第0分区进行一次查询即可。既然查询不成问题，那么我们该如何添加新记录呢？其实这也不难，只要：
- 添加新用户时，随机选择一个数据分区
- 添加新文章时，选择文章作者所在分区（可根据Article的UserID求模得到）
- 添加新评论时，选择文章所在分区（可根据Comment的ArticleID求模得到）
但是，我们又如何保证新纪录的ID正好满足我们的分区规律？例如我们向第3分区添加的新数据，则它的ID必须是3、7、11等等。以前，我们可能会使用数据库的自增列作为ID的值，但这似乎不能满足我们“取模”的要求。以前我们可能还会使用GUID，但是我们如何生成一个“被4模于3”的GUID呢？其实我们还是可以使用自增ID来解决这个问题，只不过需要进行一些简单的设置。例如在SQL Server中，默认的自增ID属性为IDENTITY(1, 1)，表示ID从1开始，以1为间距自动增长。于是我们在创建数据分区的时候，每个自增列的属性则可以设置为：
- 分区0：IDENTITY(4, 4)
- 分区1：IDENTITY(1, 4)
- 分区2：IDENTITY(2, 4)
- 分区3：IDENTITY(3, 4)
这样，ID方面的问题便交由数据库来关心吧，我们的使用方式和以前并没有什么区别。
缺陷
那么这个数据分片策略有什么缺陷呢？当然缺陷还是有很多啦，只是大多数问题可能还是要和业务放在一起考虑时才会凸显出来。不过有一个问题倒和业务关系不大：如果数据继续增长，单个数据分区的数据量也超标了，怎么办？
自然，继续拆分咯。那么我们使用什么分区规则呢？和原先一致吗？我们举个例子便知。假设我们原有4个分区，有一个ID为1的用户落在第1分区里，他的文章也都在这个分区里，ID分别是1、5、9、13、17等等。于是在某一天，我们需要将分区数量提高到5个（财力有限，一台一台来吧），在重新计算每篇文章所在的分区之后，我们忽然发现：
- ID为1的文章，模5余1，处在分区1。
- ID为5的文章，模5余0，处在分区0。
- ID为9的文章，模5余4，处在分区4。
- ID为13的文章，模5余3，处在分区3。
- ID为17的文章，模5余2，处在分区2。
呼，5个分区都齐了！这说明，如果我们保持记录原来的ID不变，是没有办法直接使用之前的分区规则——无论您扩展成几个分区，（即便是从4个到8个）也只能“缓解”也不能“解决”这个情况。那么这时候该如何是好呢？例如，我们可以重新分配记录，改变原有ID，只是这么做会产生一个问题，便是外部URL可能也会随着ID一起改变，这样对SEO的折损很大。为此，我们可以制作一个查询表：例如在查询小于1234567的ID时（这是“老系统”的最大ID），假设是100，则根据查询表得知这条记录的新ID为7654321，再以此去数据源进行查找。解决这类问题的方法还有几种，但无论怎么做都会对新系统带来额外的复杂度。而且，一次扩展也罢，如果以后还要有所扩展呢？
有朋友可能会说，取模自然会带来这样的问题，那么为什么不用一致性哈希（Consistent Hash）呢？现在一致性哈希是个很流行的东西，和Memcached一样，如果不用上就会被一些高级架构师所鄙视。不过在这里一致性哈希也不能解决问题。一致性哈希的目的，是希望“在增加服务器的时候降低数据移动规模，让尽可能多的数据保留在原有的服务器”上。而我们现在的问题却是“在增加服务器的时候，让特征相同的数据同样放在一起”。两个目标不同，这并不是一致性哈希的应用场景。
我在以前的一个项目中曾经用过这样的方法：根据对访问量与数据量的预估，我们认为使用最多24个分区便一定可以满足性能要求（为什么是24个？因为它能被许多数字整除）。于是，从项目第一次在生产环境中部署时便创建了24个数据分区，只不过一开始只用了2台服务器，每台服务器放置12个数据分区。待以后需要扩展时，则将数据分区均匀地迁移到新的服务器上即可。我们团队当时便是用这种方法避免尴尬的数据分配问题。
没错，数据分区的数目是个限制，但您真认为，24个数据分区还是无法满足您的项目需求吗？要知道，需要用上24个数据分区的项目，一般来说本身已经有充分的时间和经济实力进行架构上的重大调整（也该调整了，几乎没有什么架构可以满足各种数据规模的需求）。此外，无论是系统优化还是数据分片都可以同时运用其他手段。
不过，我们目前还是想办法解决这个问题吧。
策略改进
我们之所以会遇到上面这个问题，在于我们没有选择好合适的策略，这个策略把一些重要的“要求”给“具体化”了，导致“具体化”后的结果在外部条件改变的时候，却无法重新满足原有的“要求”。还是以前面的案例来说明问题，其实我们“要求”其实是：
- 某个用户的所有文章，与这个用户处在同一数据分区内。
- 某篇文章的所有评论，与这篇文章处在用一数据分区内。
而我们“具体化”以后的结果却是：
- 某个用户的所有文章ID，与这个用户的ID模4后的余数相同。
- 某篇文章的所有评论ID，与这篇文章的ID模4后的余数相同。
之所以能如此“具体化”，这是因为有“4个分区”这样的前提条件在，一旦这个前提条件发生了改变，则杯具无法避免。因此，我们在制定规则的时候，其实不应该把前提条件给过分的“具体化”——具体化可以，但不能过度，得留有一定空间（这个稍后再谈）。打个比方，还是前面的条件（XX和XX处在同一数据分区内），但我们换一种具体化的方式：
- 某个用户的所有文章ID的前缀，便是这个用户的ID。例如，ID为1的用户的所有文章，其ID便可能是1-A1、1-A2、1-A3……
- 某篇文章的所有评论ID，与这个文章的ID使用相同前缀。例如，ID为3-A1的文章的所有评论，其ID便可能是3-C1、3-C2、3-C3……
使用这个策略，我们便可以保证与某个用户相关的“所有数据”都共享相同的“特征”（ID的前缀都相同），然后我们便可以根据这个特征来选择分区——例如，还是以“取模”的方式。此时，我们已经确保了“相同分区内的所有数据都具备相同的特征”，即便分区数量有所调整，我们也只需要根据特征重新计算分区即可，影响不大。而以前为什么不行？因为“模4的余数”只是“结果”而不是“特征”，这里的“特征”应该是“追本溯源后的用户ID相同”，而这一点已经体现在新的策略中了。
还是通过图示来说明问题吧。假设原有4个分区，使用“取模”的策略：
| 分区0 | 分区1 |
|
|
| 分区2 | 分区3 |
|
|
当分区数量调整为5个之后（为了避免分区3空缺，我又补充了一些对象）：
| 分区0 | 分区1 |
|
|
| 分区2 | 分区3 |
|
|
| 分区4 | |
|
是不是很合理？
值得一提的是，只要满足了“特征”这个要求，其实选择分区的方式并没有什么限制。例如，我们可以不用“取模”的方式，而是使用“一致性哈希”——没错，这里就是一致性哈希的使用场景了。在利用“一致性哈希”来选择分区之后，在添加服务器的情况下便可以相对减少数据的迁移数量了。
当然，在实现时还可以运用一些技巧。例如，我们的特征并非一定要“把用户ID作为前缀”——毕竟用户ID可能比较长，作为ID前缀还真有些难看（请想象把GUID作为ID前缀，再加上另一个GUID作为ID主体的情景）。此时，我们可以把前提条件先进行一定程度的“具体化”（但就像之前提到的，不能过度），例如我们可以把用户ID先进行取模，可能是1000万，便可以得到一个落在较大区间范围内的数字。然后，再把这个数字作BASE64编码，一下子前缀就缩小为4个字符以内了。而且，1000万这个区间范围，无论是使用取模还是一致性哈希的方式来选择分区都非常可行，一般不会造成什么问题。
总结
数据分片是系统优化的常用设计方式之一。正如前文所说的那样，数据分片的做法很多，本文提到的方式只是其中一种方式。这种根据ID特征的分片方式比较容易遇到的问题之一，便是在数据分区数量改变时造成的规则冲突，这也正是我这篇文章所讨论的主要内容。从这个角度看来，其他一些分片方式，如创建时间也好，查找表也罢，这样的问题反而不太常见。如果您有这方面的经验或是疑惑，也欢迎与我进行交流。
现在Web 2.0网站越来越热门了，此类项目的数据量也越来越大，从近几年的讨论形式可以看出，越来越多的人在强调什么大规模、高性能、或是海量数据。然后，似乎每个人都会横向切分、纵向切分、缓存、分离。我猜，再接下来，估计又会有许多人以用关系型数据库为耻了吧？但是，想想这样的问题：博客园和JavaEye都是国内技术社区的翘楚，它们都只用了1台数据库服务器。StackOverflow是世界上最大的编程网站（它是使用ASP.NET MVC写的，兄弟们记住这个经典案例吧），似乎也只用了1台还是2台数据库服务器（可能配置比较高）及SQL Server。因此，即便是单台服务器，即便是使用关系型数据库，它在性能方面的潜力也是非常之高的。
因此，数据分片应该只在需要的时候才做，因为它带来的复杂度会比中心存储的方式高出很多。这带来的结果是，可能您的应用程序还没有用足架构的能力就已经失败了，这样各种投资也已经浪费了。假如您一开始用最简单的方式去做，可能很快会带来成长所需要空间及资源，此时再做更多投资进行架构优化也不迟——架构不是一蹴而就，而是演变得来的。当然，第一次投入多少复杂度是个需要权衡的东西，这也是考验架构师能力的地方。架构不是空中楼阁，而是各种真实资源调配的结果。
好长 一时半会消化不了