社交网

现在，传统的互联网正在迈向一个一个全新的时代 ---- 社交服务网时代（ Social Networking Service ），从“人与机器”的时代迈向“人与人”的时代。互联网社交服务网站的发展验证了“六度分隔理论”（ Six Degrees of Separation ），即“人际关系脉络方面你必然可以通过不超出六位中间人间接与世上任意先生女士相识”。个体的社交圈会不断地扩大和重叠并在最终形成大的社交网络。无论是国外的 Facebook 、 MySpace 、 Twitter ，还是国内的开心网、人人网等一头扎进社交网，他们认定社交网必然掀起新一轮的互联网革命。

社交网其中一个的显著特点是支持巨大用户数，例如 Facebook 支持超过 3 亿的用户， Facebook 数据中心运行着超过万台的服务器，为这些遍布全球的用户提供信息通讯服务。另外，任何两个社交网用户都可能交互，也就是必须支持任何两个数据库用户的数据关联操作。这种情况下，对于服务端的数据库管理提出了极大的挑战。

 

关系数据库与 NoSQL 数据库

关系数据库使用者遵循一些数据库范式，这些范式是数据库设计中的一系列原理和技术，其目的是为了减少数据库中数据冗余，并增进数据的一致性。结构化查询语言 SQL ，大量使用多表连接操作， SQL 的通用性为数据库使用者带来很多方便。

随着越来越多如 Web 服务之类承受大规模工作负荷的应用的发行，其对可伸缩性的需求，首先有可能会改变得非常迅速，其次会变得无比庞大。

关系数据库的确能伸缩自如，但通常只能单台服务器节点上进行。 例如采用表分区技术，一个表格可以由多个物理文件组成，虽然表格的容量增大了，但该表格仍然只能由一数据库引擎管理。

一旦单节点的能力抵达上限，你就得通过多服务器节点来往外扩展来分发负载。这时候关系数据库的复杂性就开始影响其潜在的扩展规模了。 RDBMS 支持分区视图 (Partition View) 技术，也就是支持联邦数据库 (Federated Databases) 概念【图 1 】。一个分区视图可以由多个分布在不同的数据库节点服务器上的表格组合而成，数据库用户只看到是该视图，不关心多个物理表格。通过数据水平分割技术，分区视图把负载分担到多个数据库节点服务器上。扩容时，该方法除了需改动视图定义外，分区视图成为分布式数据库系统的中心，存在单点故障问题。另外，跨数据库节点之间多表格间连接操作的支持出现极大困难。

图 1. IBM 联邦数据库的体系结构

 

当试图扩展数据库系统到成百上千个节点，而不是几个，将导致不堪复杂性之重负，这一特点使得 RDBMS 在大型分布式系统平台市场里的生存能力被大幅削减。

为了能向客户提供的一个伸缩自如的空间去存放应用数据，供应商实际上只有一种真正的选择。他们不得不实现一种新型的关注于可扩性的数据库系统，而牺牲掉关系数据库所带来的其他好处。 NoSQL 是非关系型数据存储的广义定义。它打破了长久以来关系型数据库与 ACID 理论大一统的局面。 NoSQL 数据存储不需要固定的表结构，通常也不存在连接操作。在超大型数据存取上具备关系型数据库无法比拟的性能优势。该术语在 2009 年初得到了广泛认同。其中 key-value 数据模型是解决大型数据库系统扩充问题的一种可行的解决方案。

Berkeley DB Key-Value数据模型

Berkeley DB 是一种支持 key-value 数据模型的嵌入式数据库存储引擎。不支持 Client/Server 网络访问方式，程序通过进程内的 API 访问数据库。不支持 SQL 或者其他的数据库查询语言，不支持表结构和数据列。访问数据库的程序自主决定数据如何储存在记录里，一条记录由一个称为键 key 的数据块和一个称为值 value 的数据块组成。 Berkeley DB 不对记录里的数据进行任何包装。应用程序可通过一回调函数来定义不同键之间的大小关系。记录和它的键都可以达到 4G 字节的长度。尽管架构很简单， Berkeley DB 却支持很多高级的数据库特性，比如 ACID 数据库事务处理， 细粒度锁， XA 接口，热备份以及同步复制。 Berkley DB 为不同用户提供多种功能集（ Feature Set ） : 支持单个写线程的数据存储（ Data Store ）；支持多并发写线程的并发数据存储（ Concurrent Data Store ） ; 支持 ACID 和灾难恢复的事务数据存储（ Transactional Data Store ）；和通过复制支持容错的高可靠数据存储（ High Availability ）。

实际上，一个关系数据库系统由两个独立的部分组成，一是存储引擎，二是关系引擎。存储引擎负责记录存储，索引和事务处理。关系引擎基于存储引擎提供的服务，根据表格、视图的数据结构 (Schema) 和已建立的索引等信息， 负责分析 SQL 查询，制定查询执行计划。 Berkeley DB 是一种存储引擎。例如 MySQL 数据库可采用 MyISAM 、 InnoDB 、 Berkeley DB 等存储引擎【图 2 】。

 

图 2 ： MySQL 使用的多种存储引擎

 

Berkeley DB 支持平衡树（ BTree ）、哈希（ Hash ）、队列（ Queue ）和记录（ Record ）等数据集存储、索引方式。 Berkeley DB 支持根据 key-value 中的 key 创建集群索引（ Clustered Index ）。这样记录集的物理次序就根据 key 的大小来排列。如果要查询结果记录集的键值为给定的一个范围，该特性对于支持这种类型的快速查询起了很大作用。 Berkeley DB 的一个 key-value 记录集称为一个数据库，一个数据库存储在一单独文件中。 Berkeley DB 通过创建辅助数据库（ Secondary Database ）允许对记录集建立非集群索引（ Non-Clustered Index ）。非集群索引适用于结果为一条记录的查询，该记录的键值为给定的一个值。例如社交网用户数据集：

User <UID, First_Name, Last_Name, Icon, E-mail>

如果以 UID 作为主数据库的键，其他字段作为主数据库的值。可再创建一辅助数据库，以 E-mail 作为辅助数据库的键，辅助数据库的值为 E-mail 所对应的 UID ，也就是指向主数据库记录的指针。

若在一个 key-value 数据库查询，一般可根据查询条件创建成一键值，引擎返回一游标（ Cursor ），该游标指向等于或大于该键值的结果数据集。

不难看出 Berkeley DB 使用的索引技术与 SQL Server, Oracle 等高端数据库系统是一样的。

其中在 RDBMS 中经常使用的表格连接操作，在 Berkeley DB 中不再支持，需要应用程序去实现两个数据集的连接操作。这是 key-value 数据模型与关系数据模型典型的区别。

基于 key-value 数据模型，可把一个 value 数据块扩充成多个列，来支持列数据模型。

Berkeley DB 除了作为 MySQL 的存储引擎之外，还应用在 OpenLDAP 、 MemCache 等知名软件。

与 Berkeley DB 类似的数据库引擎还有 Tokyo Cabinet/ Tyrant 等。

社交网数据库系统 Cassandra DB

以 Facebook 用户数据集为例子，不大可能把 3 亿条这巨大的数据集存放在同一表格中、同一个文件或由同一台计算机处理，这要求系统能支持数据分区，把数据集分割在多台节点计算机中，每台计算机分担一部分负载，当用户增加到一定程度时，系统能允许加入新的节点计算机，并且尽可能地减少数据迁移。

2007 年 10 月 30 日， Amazon 的 CTO Werner Vogels 发表了一文章，讨论了一种基于 key-value 数据模型存储系统 Dynamo 。 Dynamo 系统支撑了不少 Amazon 自有的面向电子商务等关键性应用。 Dynamo 上采用的存储引擎是 Berkeley DB 事务数据存储（ Transactional Data Store ）。 Dynamo 系统主要为存储 1M 左右甚至更小的内容，如购物车、推荐列表等。 Dynamo 设计上有如下一些特点：

• 通过数据分区复制来支持高可靠性与高可伸缩性
• 始终可写
• 一致性与写入速度的折衷，不要求同步写入所有副本
•   对称，完全去中心化，人工管理工作很小。

Cassandra DB 最初由 Facebook 开发，后转变成了开源项目。它是一个为网络社交云计算设计的数据库。 Cassandra 的主要特点就是它不是一个数据库，而是由一堆数据库节点共同构成的一个分布 式网络服务，对 Cassandra 的一个写操作，会被复制到其他节点上去，对 Cassandra 的读操作，也会被路由到某个节点上面去读取。对于一个 Cassandra 群集来说，扩展性能 是比较简单的事情，只管在群集里面添加节点就可以了。

Cassandra 的用户包括 Facebook 、 Twitter 和 Digg 等。 Digg 工程副总裁 约翰 • 奎因 (John Quinn)说 ：“ Cassandra 采用了完全分散的模式，每个节点都一样，不会出现单一点的故障。其容错率也非常高，数据可以被复制到数据中心的多个节点中。 Cassandra 还非常具有弹性，随着新设备的加入，其读写吞吐量将呈线性增加。”

Cassandra 以 Amazon 专有的完全分布式的 Dynamo 为基础，结合了 Google BigTable 基于列族（ Column Family ）的数据模型。 P2P 去中心化的存储。很多方面都可以称之为 Dynamo 2.0 。

图 3 为 Cassandra 、 Dynamo 、 key-value 之间的关系及在社交网上的应用。箭头表示依赖关系。

 

图 3 ： Cassandra, Dynamo, key-value 关系图

 

分布式存储系统 Amazon Dynamo 原理

Dynamo 采用 Consistent Hashing 算法来实现数据分区。

Consistent Hashing 基本原理是：首先求出服务器（节点）的哈希值，并将其配置到 0 ～ 2^32 的圆上。然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过 2^32 仍然找不到服务器，就会保存到第一台服务器上。【图 4 】

 

图 4 ：数据分割到 4 个节点数据库

 

如果添加一台服务器。只有在圈上，增加服务器的地点逆时针方向的第一台服务器上的部分数据需要迁移到新的节点数据库【图 4 】。

图 5 ：添加 Node5 后需要迁移的数据

 

数据分区后，数据块被复制到 N 个节点上。复制时因为更新产生的一致性问题的维护采取类似拜占庭容错 Quorum 协议（ Byzantine Fault-tolerance Quorum ）的机制以及去中心化的复制同步协议。当一个存储节点被认为是拜占庭节点时 , 它的行为可能任意偏移 , 表现在 : 拒绝响应请求、发送错误消息、存储错误信息等。 Quorum 协议中除了 N 之外还有两个关键参数： R 与 W 。 R 代表一次成功的读取操作中最小参与节点数量， W 代表一次成功的写操作中最小参与节点数量。 R 和 W 直接影响性能、一致性。 R 和 W 值过小则影响一致性，过大则影响效率，这两个值要平衡。如果 W 设置 为 1 ，则一个实例中只要有一个节点可写就写成功，不会影响写效率；如果 R 设置为 1 ，只要有一个节点可读，就读成功，不会影响读效率。 (N,R,W) 的典型配置是 (3,2,2) ，同时考虑了一致性和效率。

Facebook 数据库查询语言 : FQL

Facebook 为开发者提供一套和 SQL 风格一致的数据库查询语言，称为 Facebook Query Language (FQL) 。 FQL 是一种基于列的数据查询语言。提供丰富的条件查询，甚至包括子查询。

例如，以下 FQL 查询已安装 Facebook 应用程序的用户 $app_user 的好友 ID 集合：

SELECT uid FROM user WHERE is_app_user = 1 AND uid IN (SELECT uid2 FROM friend WHERE uid1 = $app_user)

与 SQL 重要区别是 FQL 不支持

·         多表连接： JOIN 操作

·         结果集记录个数限制： LIMIT

·         分组统计： GROUP BY 操作

·         排序： ORDER BY 操作

随着技术发展，一部分基于列结构的 NoSQL 数据库开始支持分组、排序等复杂数据统计分析功能。

例子：查询好友信息

例如一个 Facebook 应用程序从以下两个数据集中查找一用户的好友数据集信息 :

 

User <UID,First_Name, Last_Name, Icon>

Friend_List <UID, Friend_UID>

注 Friend_UID 是一指向 User （ UID ）的外键。

 

RDBMS 应用程序可使用数据集连接操作实现：

 

SELECT f.UID, u.Friend_UID, u.First_Name, u.Last_Name, u.Icon

FROM Friend_List f, User u

WHERE f.Friend_UID = u.UID AND f.UID=@Input_UID

 

在社交网数据库系统中，由于 User 数据分布在多台服务器中，其连接操作和外键约束实际上不能支持。

 

在 Facebook 中查找一用户的好友信息，得分 A)B) 两步操作实现：

A)

SELECT Friend_UID

INTO @Out_Record_Set

FROM Friend_List f

WHERE f.UID=@Input_UID

 

B)

FOR EACH (Friend_UID in @Out_Record_Set)

     SELECT u.Friend_UID, u.First_Name, u.Last_Name, u.Icon

     FROM User u

     WHERE u.UID = Friend_UID

 

No-SQL: Not Only SQL

对于那些关系复杂的数据处理和分析统计， SQL 值得花钱。但是当数据库结构非常简单时， SQL 可能没有太大用处。如果能用普通文件存储代替数据库系统部分功能的话，应该优选普通文件存储。

考虑社交网，能够不受限制的扩展比更丰富的功能更加重要。建立大规模社交网成本的压力让很多社交网开发人员努力去寻找更高性价比的解决方案。研究表明基于普通廉价硬件的分布式存储解决方案甚至比现在的高端数据库更加可靠。当支持 SQL 的 RDBMS 不能解决所有问题的时候， NoSQL 不是简单的 No SQL ，其本质是 No Relational ，这时候 NoSQL 就成为 Not Only SQL 。

 

参考资料

• Dynamo: Amazon‘s Highly Available Key-Value Storag
• Amazon Dynamo: The Next Generation Of Virtual Distributed Storage
• Digg追随 Twitter弃用 MySQL数据库