2.2 分布式存储

分布式存储是网络爬虫中的一个重要问题，抓取下来的URL要存放在分布式环境中。在云计算热潮风起云涌的今天，存储云的概念也被炒得沸沸扬扬。因此，如何在分布式网络环境中存储数据，也是分布式爬虫的重要课题。

2.2.1 从Ralation_DB到key/value存储

前几年，key/value这个词还是和Hash表联系在一起的。现在，程序员看见key/value这个词时，马上联想到的就是BigTable、Redis和云计算。当下，key/value存储（或者叫key/value Database、云存储等）是个非常时髦的词汇，越来越多的开发人员（特别是互联网企业）开始关注和尝试key/value的存储形式。

key/value形式的存储并不是凭空想象出来的。有两个原因导致了key/value存储方式的崛起。

1. 大规模的互联网应用

对于Google和eBay这样的互联网企业，每时每刻都有无数的用户在使用它们提供的互联网服务，这些服务带来的就是大量的数据吞吐量。同一时间，会并发出成千上万的连接对数据库进行操作。在这种情况下，单台服务器或者几台服务器远远不能满足这些数据处理的需求，简单地升级服务器性能的方式也不行，所以唯一可以采用的办法就是使用集群。使用集群的方法有很多种，但大致分为两类：一类仍然采用关系数据库管理系统（RDBMS），然后通过对数据库的垂直和水平切割将整个数据库部署到一个集群上，这种方法的优点在于可以采用RDBMS这种熟悉的技术，缺点在于它是针对特定应用的。由于应用的不同，切割的方法是不一样的。关于数据库的垂直和水平切割的具体细节可以查看相关资料。

还有一类就是Google所采用的方法，抛弃RDBMS，采用key/value形式的存储，这样可以极大地增强系统的可扩展性（scalability），如果要处理的数据量持续增大，多加机器就可以了。事实上，key/value的存储就是由于BigTable等相关论文的发表慢慢进入人们的视野的。

2. 云存储

如果说上一个问题还有可以替代的解决方案（切割数据库）的话，那么对云存储来说，也许key/value的存储就是唯一的解决方案了。云存储简单点说就是构建一个大型的存储平台给别人用，这意味着在这上面运行的应用其实是不可控的。如果其中某个客户的应用随着用户的增长而不断增长，云存储供应商是没有办法通过数据库的切割来达到扩展的，因为这个数据是客户的，供应商不了解这个数据自然就没法作出切割。在这种情况下，key/value的存储就是唯一的选择，因为这种条件下的可扩展性必须是自动完成的，不能有人工干预。这也是为什么目前几乎所有的云存储都是key/value形式的，例如Amazon的smipleDB，底层实现就是key/value，还有Google的GoogleAppEngine，采用的是BigTable的存储形式。

key/value存储与RDBMS相比，一个很大的区别就是它没有模式的概念。在RDBMS中，模式所代表的其实就是对数据的约束，包括数据之间的关系（relationship）和数据的完整性（integrity）。比如RDBMS中对于某个数据属性会要求它的数据类型是确定的（整数或者字符串等），数据的范围也是确定的（0～255），而这些在key/value存储中都没有。在key/value存储中，对于某个key，value可以是任意的数据类型。

在所有的RDBMS中，都是采用SQL语言对数据进行访问。一方面，SQL对数据的查询功能非常强大；另一方面，由于所有的RDBMS都支持SQL查询，所以可移植性很强。而在key/value存储中，对数据的操作使用的都是自定义的一些API，而且支持的查询也比较简单。

正如前面反复提及的，key/value存储最大的特点就是它的可扩展性（scalability），这也是它最大的优势。所谓可扩展性，其实包括两方面内容：一方面，是指key/value存储可以支持极大的数据存储。它的分布式架构决定了只要有更多的机器，就能够保证存储更多的数据。另一方面，是指它可以支持数量很多的并发查询。对于RDBMS，一般几百个并发的查询就可以让它很吃力了，而一个key/value存储，可以很轻松地支持上千个并发查询。

key/value存储的缺陷主要有三点：

● 由于key/value存储中没有schema，所以它是不提供数据之间的关系和数据的完备性的，所有这些东西都落到应用程序一端，其实也就是开发人员的头上。这无疑加重了开发人员的负担。

● 在RDBMS中，需要设定各表之间的关系，这其实是一个数据建模的过程（data modeling process）。当数据建模完成后，这个数据库对应用程序就是独立的，这就意味着其他程序可以在不改变数据模型的前提下使用相同的数据集。但在key/value存储中，由于没有这样一个数据模型，不同的应用程序需要重复进行这个过程。

● key/value store最大的一个缺点在于它的接口是不熟悉的，这阻碍了开发人员可以快速而顺利地用上它。当然，现在有种做法就是在key/value存储上再加上一个类SQL语句的抽象接口层，从而使开发人员可以用他们熟悉的方式（SQL）来操作key/value存储。但由于RDBMS和key/value存储的底层实现有着很大的不同，这种抽象接口层或多或少还是受到了限制。

2.2.2 Consistent Hash算法

分布式存储常常会涉及负载平衡的问题，由于有多个存储介质分布在不同的节点上。因此，当一个对象被保存的时候，它究竟应该保存在哪个存储介质上呢（存储介质可以是数据库、Berkeley DB等，甚至可以是内存数据结构）？这就是负载均衡的问题，如图2.1所示。

面对云计算的热潮，如何很好地分布存储数据是一个非常重要的话题。在分布式网络爬虫中，抓取的页面非常多（通常是数十亿级别），因此，分布式存储非常有意义。那么，如果抓取一个页面，究竟要存放到哪个数据库中呢？这就涉及负载平衡的问题。

如果你有N个数据存储服务器，那么如何将一个对象（object）映射到N个服务器上呢？你很可能会采用类似下面的通用方法来计算对象的hash值，然后均匀地映射到N个服务器上。

hash(object)%N

一切都运行正常，但是要考虑以下两种情况：

● 一个服务器m挂掉了（在实际应用中必须考虑这种情况），则所有映射到服务器m的对象都会失效。怎么办，需要把服务器m移除，这时候服务器为N-1台，映射公式变成了hash（object）%（N-1）。

● 由于访问加重，需要添加服务器，这时候服务器是N+1台，映射公式变成了hash（object）%（N+1）。

在上面两种情况下，突然之间几乎所有的服务器都失效了（请看下面单调性的解释）。对于服务器而言，这是一场灾难。

再来考虑第三个问题。由于硬件能力越来越强，你可能会想让后面添加的节点多干点活，显然上面的Hash算法做不到。

有什么方法可以改变这个状况呢，这就要用到Consistent Hashing算法。

Hash算法的一个衡量指标是单调性（Monotonicity），定义如下：

单调性是指如果已经有一些内容通过哈希分配到了相应的缓冲中，而又有新的缓冲加入到系统中，哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

上面的简单Hash算法hash（object）%N难以满足单调性要求。

Consistent Hashing是一种Hash算法，简单地说，在移除/添加一个服务器时，它能够尽可能小地改变已存在的key映射关系，尽可能地满足单调性的要求。下面就按照5个步骤简单讲讲Consistent Hashing算法的基本原理。

步骤一：环形Hash空间

考虑通常的Hash算法都是将value映射到一个32位的key值，即0～232-1的数值空间。我们可以将这个空间想象成一个首（0）尾（232-1）相接的圆环，如图2.2所示。

步骤二：把对象映射到Hash空间

接下来考虑4个对象object1～object4，通过Hash函数计算出的Hash值key在环上的分布如图2.2所示。

hash(object1) = key1;
…
hash(object4) = key4;

步骤三：把服务器映射到Hash空间

Consistent Hashing的基本思想就是将对象和服务器都映射到同一个Hash数值空间，并且使用相同的Hash算法。

假设当前有A、B和C共三台服务器，那么其映射结果将如图2.3所示。它们在hash空间中，以对应的Hash值排列。

hash（服务器A) = key A;
…
hash（服务器C) = key C;

步骤四：把对象映射到服务器

现在cache和对象都已经通过同一个Hash算法映射到Hash数值空间中，接下来要考虑的就是如何将对象映射到cache上面。

在这个环形空间中，如果沿着顺时针方向从对象的key值出发，直到遇见一个服务器，那么就将该对象存储在这个服务器上，因为对象和服务器的Hash值是固定的，因此这个服务器必然是唯一和确定的。这样不就找到了对象和服务器的映射方法了吗？

依然继续上面的例子（见图2.4），那么根据上面的方法，对象object1将被存储到服务器A上，object2和object3对应到服务器C，object4对应到服务器B。

步骤五：考察服务器的变动

前面讲过，通过Hash算法然后求余的方法带来的最大问题就在于不能满足单调性，当服务器有所变动时，服务器会失效，进而对后台服务器造成巨大的冲击，现在就来分析Consistent Hashing算法。

1）移除服务器

考虑假设服务器B挂掉了，根据上面讲到的映射方法，这时受影响的将只是那些沿cache B逆时针遍历直到下一个服务器（服务器C）之间的对象，也即是本来映射到服务器B上的那些对象。因此这里仅需要变动对象object4，将其重新映射到服务器C上即可，如图2.5所示。

2）添加服务器

再考虑添加一台新的服务器D的情况，假设在这个环形Hash空间中，服务器D被映射在对象object2和object3之间。这时受影响的仅是那些沿cache D逆时针遍历直到下一个服务器（服务器B）之间的对象，将这些对象重新映射到服务器D上即可。因此这里仅需要变动对象object2，将其重新映射到服务器D上，如图2.6所示。

考量Hash算法的另一个指标是平衡性（Balance），定义如下。

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中，这样可以使所有的缓冲空间都得到利用。

Hash算法并不能保证绝对的平衡，如果服务器较少，对象并不能被均匀地映射到服务器上。比如上面的例子，仅部署服务器A和服务器C的情况下，在4个对象中，服务器A仅存储了object1，而服务器C则存储了object2、object3和object4，分布是很不均衡的。

为了解决这种情况，Consistent Hashing引入了“虚拟节点”的概念，它可以如下定义：

虚拟节点（virtual node）是实际节点在Hash空间的复制品（replica），一个实际节点对应若干个“虚拟节点”，这个对应个数也称为“复制个数”，“虚拟节点”在Hash空间中以Hash值排列。

仍以仅部署服务器A和服务器C的情况为例，在图2.5中我们已经看到，服务器分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为2，这就意味着一共会存在4个“虚拟节点”，服务器A1和服务器A2代表服务器A；服务器C1和服务器C2代表服务器C，一种比较理想的情况如图2.7所示。

此时，对象到“虚拟节点”的映射关系为：

objec1->服务器A2；objec2->服务器A1；objec3->服务器C1；objec4->服务器C2。

对象object1和object2都被映射到服务器A上，而object3和object4被映射到服务器C上，平衡性有了很大提高。

引入“虚拟节点”后，映射关系就从{对象->节点}转换到了{对象->虚拟节点}。查询对象所在cache时的映射关系如图2.8所示。

“虚拟节点”的Hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设服务器A的IP地址为202.168.14.241。引入“虚拟节点”前，计算服务器A的Hash值：

Hash("202.168.14.241");

引入“虚拟节点”后，计算“虚拟节点”服务器A1和服务器A2的Hash值：

hash("202.168.14.241#1"); // cache A1
hash("202.168.14.241#2"); // cache A2

2.2.3 Consistent Hash代码实现

上一节讲述了Consistent Hash算法的原理，本节我们实现一个简单的Consistent Hash算法。

public class ConsistentHash<T> {
 private final HashFunction hashFunction;//Hash算法
 private final int numberOfReplicas;//虚拟节点数目
 private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
 public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
     Collection<T> nodes) {//物理节点
     this.hashFunction = hashFunction;
     this.numberOfReplicas = numberOfReplicas;
     for (T node : nodes) {
           add(node);
     }
 }

 public void add(T node) {
   for (int i = 0; i < numberOfReplicas; i++) {
     circle.put(hashFunction.hash(node.toString() + i), node);
   }
 }

 public void remove(T node) {
   for (int i = 0; i < numberOfReplicas; i++) {
     circle.remove(hashFunction.hash(node.toString() + i));
   }
 }

 public T get(Object key) {//关键算法
   if (circle.isEmpty()) {
     return null;
   }
   //计算hash值
   int hash = hashFunction.hash(key);
   //如果不包括这个Hash值
   if (!circle.containsKey(hash)) {
     SortedMap<Integer, T> tailMap = circle.tailMap(hash);
     hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
   }
   return circle.get(hash);
 }

本节内容详细讲述了有关分布式和云计算存储的相关问题，下面几节我们将讲述Google的分布式和云计算技术，以及它们在网络爬虫中的应用。