CN105009111A - 使用键值存储系统的分布式sql查询处理 - Google Patents

Abstract

分布式存储器系统通过利用层叠在事务性键值系统(存储组件)上面的SQL库(SQL执行组件)来支持SQL，同时还提供可缩放性和容错。SQL库包括在客户端上运行的解析器和执行引擎，而存储组件包括用于存储数据的键值系统。SQL库解析从客户端应用接收到的SQL查询，并将它们映射到键值系统上的事务。键值系统存储通过键来标识的数据项，并提供处理并发事务的并发性控制机制。键值系统可以是带有数个存储服务器的分布式系统，每一个存储服务器都附接到一个或多个存储设备。

Description

使用键值存储系统的分布式SQL查询处理

背景技术

大规模的基于web的应用可以使用分布式存储系统来存储应用数据，诸如关于其用户、顾客、内部状态等等的数据。用于基于web的应用的现有的存储系统既包括一般以使用标准查询语言(SQ)为特色的传统的数据库系统，也包括不使用SQL的“NoSQL”存储系统。SQL是已知的并且广泛使用的查询接口，通过使用声明性语言提供强大功能，该声明性语言比命令式编程语言更简洁，使得几行SQL可等同于用于使用NoSQL系统来实现相同功能的几百行代码。

一般而言，使用SQL的传统的数据库系统扩展起来困难并且昂贵，因为它们使用昂贵的特殊硬件和/或具有高开销(例如，对数据进行分区以及调节性能的昂贵的系统管理员)。然而，在过去的十年，开发和使用大规模的Web应用的许多公司将传统的SQL数据库系统替换为不带有SQL的专业化的定制的存储系统，这类存储系统具有更好的性能、更好的可缩放性和降低的成本(不论是硬件还是开销)。然而，这些“NoSQL”存储系统只提供在传统的SQL数据库系统中可用的功能的子集。例如，NoSQL存储系统可能缺乏联接、子查询、辅助键、聚集、及由SQL所提供的其他特征。

因此，使用需要此缺失的功能的NoSQL存储系统的Web应用必须自己提供它，这又会增大开发这样的用于与NoSQL存储系统一起操作的应用的工作量和成本。此外，NoSQL存储系统一般具有自定义界面和专属于该存储系统的查询语言(即，是非标准并且专用的)；结果，被开发使用一个特定NoSQL系统的web应用在不对这样的web应用作出重大的更改以使它们与由其他NoSQL存储系统所特有的定制界面和查询语言兼容的情况下可能不与其他NoSQL存储系统一起工作。

发明内容

此处所公开的各种实现涉及支持SQL同时还提供可缩放性和高容错的存储系统。这些实现以层叠在事务性键值系统(数据存储组件)上面的SQL库(SQL执行组件)为特色。更具体地，SQL库包括在客户机上运行的解析器和执行引擎，而存储组件包括实现用于存储数据的键值系统的一个或多个存储服务器。客户端侧的SQL库解析从客户端应用接收到的SQL查询，并将这些SQL查询映射到键值系统上的操作(例如，事务)，该键值系统执行这些操作，以读取和写入通过键来标识的数据项(没有任何模式)。键值系统支持事务，并进一步提供处理并行事务的并行性控制机制。键值系统可以使用提供可缩放性和容错的数种技术中的任何一种来实现。对于数种这样的实现，键值系统可以是带有数个存储服务器的分布式系统，每一个存储服务器都附接到一个或多个本地存储设备。

一些实现涉及分布式SQL查询处理系统，包括：用于存储键值对象的键值服务器；通信地耦合到所述键值服务器的至少一个客户端；用于处理对所述键值对象中的一个的操作的键值库；以及用于从应用接收SQL查询并将所述SQL查询转换为对于要处理的所述键值库的事务的SQL库。

提供本发明内容是为了以精简的形式介绍将在以下详细描述中进一步描述的一些概念。本发明内容并不旨在标识所要求保护的主题的关键特征或必要特征，也不旨在用于限制所要求保护的主题的范围。

附图简述

当结合附图阅读时，可以更好地了解前面的摘要，以及下面的对说明性实现的详细描述。为了说明各实现，在图形中示出了各实现的示例结构；然而，各实现不仅限于所公开的特定方法和所公开的手段。在附图中：

图1是解说表示此处所公开的各种实现的示例性分布式SQL查询处理系统的框图；

图2是解说此处所公开的各种实现所使用的图1的SQL库、键值库，以及键值服务器的示例性结构的框图；

图3是用于在可以由此处所公开的各种实现使用的事务键值数据存储系统上执行SQL查询的示例性方法的流程图；

图4是表示可以由此处所公开的各种实现用于执行SQL查询的示例性方法的流程图，SQL查询使用计算出的并存储在临时表中的中间结果；以及

图5是可以与示例实现和各方面结合使用的示例计算环境的框图。

具体实施方式

传统的分布式数据库系统(再强调一遍，它们扩展起来困难并且昂贵)一般分成两个类别：共享磁盘的系统和无共享系统。在共享磁盘的系统中，数据库服务器共享一个或多个磁盘(或其他存储设备)，并且彼此协调，以通过使用锁定或同步协议，来控制对这些共享设备的并发访问。然而，此方法的缺点是由这些协议施加的开销，这会限制可缩放性，并会使这些系统的设计复杂化。另一方面，无共享系统不共享磁盘，而是替代地跨各种服务器对数据进行分割，每一个服务器存储数据的一部分。为在这些系统中执行数据库查询，查询被分解成在合适的服务器上执行的子查询，以产生被组合以回答查询的结果。然而，此方法的缺点是，它要求高效地跨服务器对数据进行分割，并高效地查询存储的数据，其中，实现这些效率涉及由管理专家进行相当大的手动调节。

为克服上文所描述的SQL和NoSQL系统的缺点，一些解决方案(此处被称为“两层方法”)尝试将存储系统划分为两个不同的并且分离的层，“事务层”位于“数据层”之上，其中，事务层协调事务执行，并负责并发控制，而数据层存储数据。然而，与现有的两层方法不同，此处所公开的各种实现的两个组件(SQL执行和数据存储)的不同之处在于，数据存储层中具有事务，并且负责并发控制。换言之，此处所公开的各种实现的数据存储组件有效地包括事务层和数据层两者，而SQL执行提供额外的事务功能(由SQL提供)，否则该功能是数据存储组件的事务能力所没有的。

其他解决方案(此处被称为“记录管理系统”)为每一个自定义数据库系统使用事务记录管理器，其中，事务被写入到共享的全局日志中，以允许每一个定制数据库系统重播每一个事务(即，其他定制数据库系统上的事务)，以便构建其自己的数据库状态的副本。然而，这些记录管理系统没有被实现为用于关系数据库，而是仅限于事务性键值系统。相比之下，此处所公开的各种实现是为关系数据库系统实现的，虽然数个这样的实现确实包括事务性键值系统作为其组件，但是，存储系统本身是关系数据库。

在任何情况下，在传统的SQL数据库系统中处理查询是在数据库服务器中与存储和管理数据一起进行。然而，除数据库服务器昂贵之外，向共享磁盘的数据库系统添加更多数据库服务器会显著地增大允许数量增多的数据库服务器访问共享的数据所需的协调开销。同样，在无共享数据库系统中，添加更多服务器要使用昂贵的并且资源密集的操作来在数量增多的可用的服务器之间在较细粒度对数据进行重新分割。类似地，对于传统的SQL数据库系统中的并发控制机制，事务协调器还位于服务器上，但是，由于上文给出的同样的理由，服务器难以扩展。

此处所公开的各种实现的增强的可缩放性(与现有的数据库系统相比)源于允许查询处理和并发控制相对于存储服务器独立地缩放。例如，查询处理和并发控制可以在客户端执行。以此方式，处理更多SQL查询的能力与客户端的数量成正比。结果，增大客户端的数量会提供额外的硬件来处理SQL查询。此增加的硬件还提供用于可缩放的并发地控制的增大的处理能力。由于在事务性键值系统上运行的并发控制机制构成简单服务——仅仅存储键值对——当客户端充当它们自己的事务的协调器时，如由此处所公开的各种实现所特有的，它们可以被高效地扩展。

相应地，此处所公开的各种实现涉及数据库系统，该数据库系统支持SQL，但是具有相当于现有的NoSQL系统的、并且在没有昂贵的专业化的硬件和大量的手动系统管理的情况下不能由传统的SQL数据库实现的性能和可缩放性。这些各种实现高效地将SQL查询映射到存储在键值系统上的键值对象上的操作，其中大多数简单SQL查询被映射到相对较小数量的操作。更具体而言，SQL查询处理系统包括：用于存储多个键值对象的键值服务器，通信地耦合到所述键值服务器的至少一个客户端，用于处理对所述键值对象的操作的键值库，以及，用于从应用接收SQL查询并将所述SQL查询转换为对于要处理的所述键值库的操作的SQL库。

当然，尽管此处所公开的各种实现可以包括位于客户端中的键值库和SQL库，但是也预料了各种替代的实现。例如，各种替代的实现可以包括SQL库和维护在与客户端分开的第二机器(并可能与键值服务器分开)中的键值库，在这样的情况下，客户端生成SQL查询，并将它发送到第二机器上的SQL库。其他替代实现可以包括在客户端机器处的SQL库和在第二机器处的键值库，其中，客户端可以生成SQL查询并在本地处理它(因为SQL库位于同一个机器上)。然后，客户端生成键值操作，该键值操作被发送到键值库所在的第二机器，随后，第二机器处的键值库将键值操作发送到键值服务器。在又一些其他替代实现中，SQL库可以位于第二机器处，而键值库位于第三机器处。在此设置中，客户端在客户端(第一机器)处生成SQL查询，并将它发送到第二机器处的SQL库，该第二机器又生成键值操作，随后，该键值操作被发送到第三机器处的键值库，随后，该第三机器将键值操作发送到键值服务器。其他这类替代的实现也是可以的。相应地，对此处的各种实现的描述可以假设，SQL库和键值库位于客户端处，但是，这不是限制性的，因为其他替代方案也是可以预期的。

图1是解说表示此处所公开的各种实现的示例性分布式SQL查询处理系统100的框图。在下面的描述中，在一种情况下使用“n”不一定等同于在另一种情况下“n”的使用的相同数量或计数。在附图中，分布式SQL查询处理系统100包括一组客户端机器110a…110n(也被称为客户端或客户端机器110)，每一个都运行能够生成一个或多个SQL查询的应用112a…112n(被称为应用112)。应用112向此处所公开的各种实现的SQL处理系统120a…120n(被称为SQL处理系统120)提交(或发出)SQL查询。SQL处理系统120a…120n包括SQL库122a…122n(被称为SQL库122)和用于处理键值服务器上的操作(其中，操作可以是事务)并在每一个客户端机器110上运行的键值库124a…124n(被称为键值库124)。SQL处理系统120a…120n进一步包括通信地耦合到客户端机器110中的每一个的键值服务器132a…132n(被称为键值服务器132或简单地称为“服务器”)，其中键值服务器132(即，存储服务器)和键值库124一起构成SQL处理系统120的事务性键值系统130。在此事务性键值系统130中，键值服务器132包括键值存储(例如，在图2中被示为键值存储174)，而键值库124中每一个都包括表示键值服务器上的键值存储的本地键值存储(例如，在图2中，被示为本地键值存储162)。键值服务器132存储也被称为kv对象的键值对象(每一个都是键值对，如下面所讨论的)。

在操作中，SQL库122将从应用112接收到的SQL查询映射到键值系统130上的操作。键值系统130可以使用已知分布式系统技术来实现，在此设计中，系统架构100继承键值系统130的性能和可缩放性。

应该注意的是，尽管应用112a…112n在上文中被描述为不同的应用(或在不同的客户端上运行的相同应用的独立副本)，但是，对于各种替代的实现，应用112a…112n可以构成位于不同的客户端机器上但是一起构成单一应用的各个子组件。相应地，此处不意图将这样的实现的公开限制于任何单一形式，这些替代形式是可以预期的。

图2是解说各种实现所使用的图1的SQL库122、键值库124，以及键值服务器132的示例性结构的框图。SQL库122包括SQL解析器和执行引擎152、表/索引映射器154、以及分布式有序数据结构(DODS)156(在下文中更详细地描述DODS的功能)。键值库124包括本地键值存储162(其可包括键映射功能)和远程过程协议(RPC)客户端组件164。键值服务器132进一步包括RPC服务器组件172、键值存储174，以及日志176，其中，此处键值存储174可以是存储每一个键的值的可能的多个版本的多版本存储。

对于各种实现，事务键值存储系统存储此处被称为kv对象的键值对。键值系统进一步将kv对象分组为容器，这些容器类似于传统的文件系统中的目录，只是存在没有子目录的平的层次结构。对于这样的实现，每一个kv对象的键都包括与对象id串联的容器id。键值系统进一步支持操作(是事务)的执行，其中，事务操作可包括读取和写入键值对的数个操作，而同时提供事务的ACID(原子性、一致性、隔离性、持久性)属性。

对于这样的实现，键值系统的事务确保快照隔离属性，这会提供三个保证：(1)当事务开始时，事务从包含在开始时间戳之前提交的所有更新的快照中读取；(2)当事务提交时，其写入被一起应用以创建新快照；以及(3)如果两个并发事务向相同位置(目标或目的地)写入，则它们中的一个被中止以避免冲突。这样的事务性键值系统可以使用数种已知技术中的任何一个来实现。

图3是用于在可以由此处所公开的各种实现使用的分布式SQL查询处理系统100上执行SQL查询的示例性方法的流程图200。在210，在客户端上执行的SQL库122从在客户端上执行的应用接收SQL查询。在220，SQL库122在客户端处解析SQL查询，并将SQL查询转换为对存储在事务性键值系统上的键值对象的操作；这样的操作可在事务性键值系统130上执行。在230，这些操作经由RPC客户端组件164和RPC服务器组件172从客户端传递到服务器，在240，在键-值服务器132上执行操作。在250，将这些操作的结果(或操作的结果的句柄)返回到应用。

通过使用如前所述的事务性键值系统，此处所公开的各实现能够存储SQL对象，SQL对象包括但不限于表、索引，以及模式。

SQL表是一组行，每一行都具有多个列，其中一个列被指定为主键，并且没有两行具有相同值的主键。如果用户不指定主键，则系统可以提供包括与表中的该行(并且只有该行)相关联的整数的行id。例如，web应用中的用户表可以保留数字的用户id、用户名、密码、名字、姓氏、电子邮件地址，以及帐户选项，作为表中的单独的列，并且主键可以是用户id、用户名，或行id，只要这些条目将用于唯一地标识表内的对应的行。

对于此处所公开的实现，键值系统在事务性键值系统中的其自己的kv对象中存储每一个表行，其中，kv对象的容器是表id，而kv对象的对象id是行的主键。然而，此方法具有两个局限性。首先，尽管键值系统可以使用固定长度的键，但是，SQL表准许主键是任何长度(取决于模式)，本领域技术人员将理解，对主键进行散列，以获得固定长度键是可能的，但是有问题，因为可能会产生冲突。此外，如由数个这样的实现所特有的，使用对象键来确定放置——即，确定哪一个服务器将存储该kv对象——就局部性和负载平衡而言不一定会导致好的放置，并由此无意地但是负面地影响效率。

相应地，各种替代的实现可以使用行id作为主键(代替kv对象的id)，以将行映射到特定kv对象，并由此避免上文所描述的问题。由于行id是固定长度的整数，因此，它完全与kv对象的键兼容，即使是对于允许用户选择行id的那些实现(指示行将被插入到表中的哪里)而言。此外，对于某些这样的实现，键值系统可以使用行id的较高的位来确定用于存储kv对象的特定服务器，如果需要，将放置控制权给予用户，但是如果用户选择不这样做，则仍允许系统来确定放置。无论如何，如果表的主键是整数，则这样的实现可以使用主键来将表行映射到kv对象id。

对于SQL表，索引可以被用来基于选择的列、通过将索引的列的值(被称为索引键)映射到包含该特定值的行来高效地发现行。例如，用户表可以具有用户id、用户名、电子邮件、或多列(例如，姓氏和名字)的串联的索引。如此，索引支持对于插入、删除、范围搜索(例如，查找小于或等于给定值的最大的键)、以及有序的遍历(例如，给定一个键，查找键序列中的下一键或前一键)的高效的SQL操作。然而，由于三个原因，不可能将这些操作直接映射到事务性键值系统：(1)键值系统不支持范围搜索或有序的遍历；(2)虽然键值系统中的键唯一地标识每一个条目，但索引键不会；以及(3)键值系统中的键具有小的固定长度(128比特)，而索引键可以是可变长度，并且大得多。为克服这些缺点，此处所公开的各种实现使用建立在键值系统(此处比较详细地描述的)上的分布式有序数据结构(DODS)，执行SQL索引操作，并且索引被存储在此数据结构中。

在SQL系统中，每一个SQL表都具有模式(模式表示表中的每一列以及其类型)，并且模式存储在由SQL系统本身维护在较高的级别的抽象中的“主表”内。此主表又具有被硬线连接到SQL系统代码中的固定模式。此处所公开的实现类似地以主表为特色。

为了可缩放性，SQL表可以水平地或垂直地分割。水平分割将各行分布在跨多个存储位置，例如，对于用户的SQL表，用户的一个子集可以存储在一个位置，而另一子集可以存储在另一位置。另一方面，垂直分割将各列分布在跨多个存储位置(例如，将名称和电子邮件列存储在一个位置，而将帐户设置列存储到另一位置，在两个位置重复主键作为引用)。水平和垂直分割两者可以同时用于SQL系统中。

对于此处所公开的各种实现，可以提供一种或两种类型的分割。在此处所公开的各种实现中，通过将不同的行映射到不同的kv对象使得键值系统基于不同的kv对象的键，将这样的kv对象存储在不同的服务器上，来实现用于这样的实现的水平划分。另一方面，可以通过将表行存储在不同的服务器上的多个kv对象下来提供垂直划分，其中，每一个kv对象都不对应于行而是存储一个或多个列(即，垂直分割)，这样的kv对象的键可以包含与行id串联的分区id(小整数)供容易的引用。

SQL系统还支持多个数据库(其中，每一个数据库都是一组表)以允许某些应用使用不同的数据库，以便隔离它们的数据并避免表名称冲突。此处所公开的各种实现通过包括数据库id作为存储在事务键值系统中的对象的容器的前缀来提供类似的功能。例如，在一些实现中，kv对象的键可以是数据库id和表id的组合(一起形成64比特容器id)加行id(64比特对象id)。

在SQL系统中，SQL查询的执行常常生成保存在临时(或“短暂的”)表中的中间结果。此处所公开的各种实现也可以使用临时表来实现使用它们的SQL特征(诸如聚集、集合运算、子查询，以及排序)。例如，考虑下列SQL查询：

SELECT AVG(age)FROM users WHERE type IN

(SELECT type FROM usertypes WHERE privileged＝1)

如精通技术的人员将理解的，此查询是包括子查询(第二行SELECT)的聚合函数(AVG)。为模仿SQL系统功能，此处所公开的各种实现可以使用图4中所示出的方法。

图4是表示可以由此处所公开的各种实现用于执行SQL查询的示例性方法300的流程图，SQL查询使用计算出的并存储在临时表中的中间结果，这里，查询包括子查询。在310，系统首先计算子查询。相对于上文的示例查询，此计算选择具有指定的特权属性集的用户类型。在320，系统将结果存储到第一临时表中。

在330，系统选择对应于带有与临时表中发现的相同类型的表条目(例如，用户)的属性(例如，年龄)，在340，将这些属性(例如，年龄)存储到第二临时表中。在350，系统计算第二临时表中的行的平均值，然后，将该平均值作为查询的结果返回。另外，对于某些实现，为提高效率，临时表可以存储在客户端处(而不存储在键值服务器处)。

由于SQL是声明性语言——即，程序员不指出应该如何执行查询，而是仅仅指出希望什么结果的语言——必须由SQL系统评估SQL查询，以确定应该如何执行查询。相应地，SQL系统首先将查询解析为某种中间表示，从该中间表示，可以标识完成该查询的一系列单个执行步骤。SQL系统针对实际存储的数据执行这些特定步骤以返回结果。例如，考虑下列SQL查询：

SELECT userid FROM users WHERE email＝'ab.com'

SQL系统将首先将此查询解析为下列步骤(只为说明，这里以风格化形式表示)：

result＝range-search"ab.com"in email index of users

//get largest key<＝"ab.com"

whileresult.key＝"ab.com"do

tablerow＝fetch result.row from users table

outputtablerow.userid

result＝getnext//get next key in index

在一些SQL系统中，这样的查询可以在存储所需数据的特定服务器中被解析和执行，以便避免跨网络发送计算的中间结果。然而，尽管此技术貌似效率高，但是，它也是有局限性的，因为该系统要求由查询所需的所有数据驻留在单一服务器上。在数据被完美地分割(并且数据事实上可分割)的系统中，或在可以将查询分解为能够在多个服务器上独立地执行的子查询的系统中(虽然这样的分解可能难以或不可能发现，诸如当查询联接存储在不同的服务器(使得分解查询并在本地执行它不可能)中的表时)，这对于集中式数据库系统(其具有有限的可缩放性)是可能的。

出于通用性和简单性，此处所公开的各种实现在客户端处(而不像在SQL系统中那样在服务器处)解析并执行这样的查询。此方法的一个优点是，解析SQL不会变为可缩放性瓶颈，因为每一个客户端都执行其自己的查询，随着添加更多客户端，也有效地添加用于处理查询的更多容量。因此，可缩放性仅仅受底层的键值系统限制。

应该注意的是，此方法看起来带来两个挑战。首先，SQL解析和执行消耗客户端处的资源——特别是CPU——可能与客户端应用(或在客户端上执行的其他应用)竞争；然而，这样的竞争仅仅具有对总的客户端性能的可忽略的影响。其次，为了执行查询，客户端通过网络获取中间数据，对于每一个这样的对存储服务器的访问，这又会产生网络往返成本；然而，随着网络延迟缩小并且新网络设计跨数据中心的机器提供均匀的且高的带宽，此成本也变得可忽略。即使使用简单但是相对慢的以太网，此方法在许多常见的情况下也表现得好。

如之前所述，此处所描述的各种实现在分布式有序数据结构(DODS)中可能以存储在键值系统中的索引为特色。虽然一些这样的实现可以使用已知技术在B树中维护DODS索引，但是，各种这样的实现可以使用实现起来比B树比较简单并且更加容易的跳跃列表。

跳跃列表是通过“skey”(跳跃列表键)排序的越来越稀疏的链接列表的层次结构。我们使用术语skey来区别跳跃列表键与键值键。为在这样的实现中搜索跳跃列表，算法从跳跃列表层次结构中的最高级别链接的列表开始，当遍历即将超过目标skey时，下降到下一级别。此过程从链接列表持续到链接列表，直到到达最低级别，此时，该算法查找目标skey或者该skey本应所处的位置。

此处所描述的多个实现可以将跳跃列表存储在事务性键值系统中，并且因此可以变为分布式跳跃列表，只要键值系统是分布式的。无论如何，用于某些这样的实现的一种方法是作为一个kv对象来存储每一个跳跃列表节点，其中，跳跃列表节点指针是kv对象键。通常，这样的方法可以使用数个网络往返以遍历多个链接列表，这是过多的。某些这样的实现可能以减轻这些效果的两次优化为特色。首先，每一个跳跃列表节点都可以存储多个skey而不是只存储一个，以便改善遍历时间。其次，一些实现可能以存储每一个级别的查找skey的skey节点(skey节点是该级别中的下一节点的skey)为特色，这又会导致较少的kv对象获取，因为遍历不必如在传统的skiplist中那样超越目标skey(其中超越会在每个跳跃列表级别导致额外kv对象获取)。

此分布式跳跃列表方法支持多个客户端的并发访问和修改。因此，虽然集中式系统使用锁定来协调访问，但此处所公开的这样的实现使用的分布式跳跃列表通过键值系统的事务来协调访问。例如，客户端可以通过下列操作添加节点：(a)启动键值事务，(b)通过写入合适的kv对象来修改以前的节点以指向新节点，(c)写入包含新节点的kv对象，以及，(d)提交键值事务。在此方法中，如果另一客户端并发地修改跳跃列表的相同部分，则可以中止事务，在这样的情况下，客户端将在例如随机的指数式增大的退避时间长度之后，重试事务。

对于此处所描述的各种实现，有两种类型的客户端缓存可用，其中这两种类型的客户端缓存中的一种或两种可以用于特定实现。两种类型的缓存是：(1)键值缓存，该缓存将kv对象存储在客户端上的键值库124中，没有任何SQL语义归于它们，以及(2)SQL缓存，该缓存将带有SQL语义的项(行、索引，以及模式)存储在客户端的SQL库122中。这两种类型的缓存都可以是透写或回写(其中更新同步地或异步地传播到服务器)。然而，一方面，键值缓存比SQL缓存使用起来简单，因为它一致地对待所有数据，无需对于行、索引、模式，或其他SQL项而定制行为。另一方面，SQL缓存可以更有效率，因为其策略可以反映正在被缓存的项。因此，尽管某些实现可以只使用键值缓存，而其他实现可以使用SQL缓存，但是此处所公开的多个实现可以将SQL缓存用于表模式(其被频繁地读取，但是很少被修改)并将键值缓存用于所有其他目的(即，用于除缓存表模式以外的缓存目的)。

相对于SQL缓存，表模式是紧凑的，但是，常常用于解析大多数(如果不是所有的话)查询，如此，可以通过让客户端加载表的模式一次并无限地缓存该信息来获得高效率。然而，当表的模式改变时，在将更改提交到表之前，利用这些更改来更新客户端。为了高效地执行此操作，某些这样的实现使用的一种方法可以依赖于键值系统中的纪元编号(如本领域技术人员已知的，这是广泛地用于指示分布式系统中的配置的变化的常见的机制)。对于这样的实现，每一个键值服务器都可以具有纪元编号，并且客户端跟踪每一个这样的客户端与其进行交互的键值服务器的纪元编号。然后，客户端在向键值服务器的请求中搭载纪元编号，并且键值服务器检查以查看该纪元编号是否匹配其自己的当前编号。如果它不匹配，则键值服务器拒绝客户端的请求(因为其纪元编号过时)。

在操作中，当客户端改变模式时，它还更新主表(此处之前讨论的)，并递增存储该表的键值服务器的纪元编号。为了一致性，通过在键值服务器中将纪元编号当作特殊对象，并让事务修改那些对象，在同一个事务中执行更新主表的替换。如果客户端请求由于纪元不匹配而被键值服务器拒绝，则客户端中止涉及该键值服务器的正在进行的事务，并查询主表，以重新加载保留在该键值服务器中的表的模式。

相比之下，键值缓存的操作简单：当客户端在一个事务中读取或写入数据时，客户端保留该数据，用于相同事务中的后续读取。此技术不使用缓存一致性协议，因为处于快照隔离下的事务从不可改变的快照中读取。键值系统可以潜在地实现更复杂的缓存技术。

如本领域技术人员将理解的，并发控制是任何事务性的系统中的一个考虑事项，常常要就下列事项作出选择：(a)将什么机制用于并发控制(例如，悲观的、乐观的、多版本)，以及，(b)该机制应该在什么级别操作(例如，相对于此处所公开的各种实现，kv对象还是SQL项)。

已知有数种用于并发控制的机制。悲观的并发控制使用锁，其中，对象被锁定无法读取或写入，以防止并发事务执行冲突的访问。乐观的并发控制允许事务自由地访问任何对象，但是一旦提交，就检查被访问的项是否被其他事务更改，如果是，则事务被中止。多版本并发控制保留对象的多个版本，以便尽管由事务读取的对象不必被锁定或检查，但是在提交时，检查被写入的对象，以防止写入冲突。尽管此处所公开的某些实现可以使用这些并发控制机制中的任何一种，但是，数个这样的实现使用多版本并发，因为此机制更有效率地执行只读事务，因为这样的事务不会中止并且不使用任何锁定。

进一步应该注意的是，类似于缓存，并发控制也可以在键值系统级别或者SQL的级别实现。当在键值系统级别实现时，事务协调对kv对象的并发访问。当在SQL级别实现时，事务协调对SQL行和表的并发访问。

此处所公开的某些实现专门在键值系统级别使用并发控制，因为这些实现已经使用以可缩放的并且有效的方式提供带有多版本并发控制的事务的键值系统。此外，对于SQL项目实现带有多版本并发控制的事务是困难并且昂贵的，因为客户端必须跟踪行的许多版本，每一个版本都存储在不同的kv-对象中，并且必须每次判断要访问哪一个版本。尽管如此，虽然这样的实现可以在键值级别运行事务，但是这些事务仍将它们的ACID语义遗留给用户观察到的更高级别的SQL事务。例如，SQL事务可以更新数个表，这会更新许多kv对象，并且那些更新是全部一起作为一个键值事务提交的，以便它们被其他用户以原子方式观察到。

图5是可以与示例实现和各方面结合使用的示例计算环境的框图。计算系统环境仅为合适的计算环境的一个示例，并非旨在对使用范围或功能提出任何限制。

可以使用很多其他通用和专用计算机系统、环境或配置。适合使用的公知计算系统、环境和/或配置的示例包括但不限于个人计算机(PC)、服务器计算机、手持式或膝上型设备、多处理器系统、基于微处理器的系统、网络PC、小型机、大型计算机、嵌入式系统、包括以上系统或设备的任一个的分布式计算环境等等。

可以使用由计算机执行的诸如程序模块之类的计算机可执行指令。一般而言，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等。可以使用在其中任务由通过通信网络或其他数据传输介质链接的远程处理设备执行的分布式计算环境。在分布式计算环境中，程序模块及其他数据可以位于包括存储器存储设备在内的本地和远程计算机存储介质中。

参考图5，用于实现此处所描述的各方面的示例性系统包括计算设备，诸如计算设备500。在其最基本配置中，计算设备500通常包括至少一个处理单元502和存储器504。取决于计算设备的确切配置和类型，存储器504可以是易失性的(如随机存取存储器(RAM))、非易失性的(如只读存储器(ROM)、闪存等等)或两种类型的某种组合。该最基本配置在图5中由虚线506来示出。

计算设备500可具有附加特征/功能。例如，计算设备500可包括附加存储(可移动和/或不可移动)，包括但不限于磁盘、光盘或磁(光)带。在图5中通过可移动存储508和不可移动存储510示出了这样的附加存储。

计算设备500通常包括各种计算机可读介质。计算机可读介质可以是可以被设备500访问的任何可用的介质，并包括易失性和非易失性介质，以及可移动的和不可移动的介质两者。

计算机存储介质摂包括以用于存储诸如计算机可读指令、数据结构、程序模块或其他数据之类的信息的任何方法或技术实现的易失性和非易失性介质、以及可移动和不可移动介质。存储器504、可移动存储508和不可移动存储510都是计算机存储介质的示例。计算机存储介质包括，但不限于，RAM、ROM、电可擦除可编程只读存储器(EEPROM)、闪存或其他存储器技术、CD-ROM、数字多功能盘(DVD)或其他光存储、磁带盒、磁带、磁盘存储或其他磁性存储设备、或可用于存储信息且可以由计算设备500访问的任何其他介质。任何这样的计算机存储介质可以是计算设备500的一部分。

计算设备500可包含允许该设备与其它设备通信的通信连接512。计算设备500也可包括输入设备514，如键盘、鼠标、笔、语音输入设备、触摸输入设备等等。也可包括输出设备516，如显示器、扬声器、打印机等等。所有这些装置在本领域中都是众所周知的，因此不必在此详细讨论。

计算设备500可以是通过网络互连的多个计算设备500中的一个。可以理解，网络可以是任何合适的网络，每一个计算设备500都可以通过通信连接512以任何合适的方式，与其连接，每一个计算设备500都可以以任何合适的方式，与网络中的其他计算设备500中的一个或多个进行通信。例如，网络可以是一个组织或数据中心或多个数据中心或家庭等等内的有线或无线网络，并可包括到诸如因特网等等之类的外部网络的直接或间接耦合。

应该理解，此处所描述的各种技术可以结合硬件或软件或，在适当的情况下，结合两者的组合来实现。因此，目前所公开的主题的过程和装置，或其某些方面或部分，也可以以在有形介质(如软盘、CD-ROM、硬盘驱动器，或任何其他机器可读存储介质)中实现的程序代码(即，指令)的形式来实现，其中当程序代码被加载到诸如计算机之类的机器中并由它们执行时，机器变为用于实施目前所公开的主题的装置。

在程序代码在可编程计算机上执行的情况下，计算设备一般包括处理器、可由处理器读取的存储介质(包括易失性和非易失性存储器和/或存储元件)、至少一个输入设备，以及至少一个输出设备。一个或多个程序可以实现或使用结合目前公开的主题所描述的过程，例如，通过使用API、可重用控件等等。这样的程序可以以高级别过程或面向对象编程语言来实现，以与计算机系统进行通信。程序也可以以汇编或机器语言来实现。在任何情形中，语言可以是编译语言或解释语言，且它可与硬件实现相结合。

虽然示例性实现可以在一个或多个独立计算机系统的上下文中适用，但是，主题不如此限制，而是可以与诸如网络或分布式计算环境之类的任何计算环境一起实现。更进一步，目前所公开的主题的各方面可以跨多个处理芯片或器件实现，并可以跨多个设备类似地实行存储。这样的设备可以包括，例如，PC、网络服务器、数据中心服务器，以及手持式设备。

尽管用结构特征和/或方法动作专用的语言描述了本主题，但可以理解，所附权利要求书中定义的主题不必限于上述具体特征或动作。相反，上述具体特征和动作是作为实现权利要求的示例形式公开的。

Claims (10)

1.一种分布式SQL查询处理系统，包括：

用于存储多个键值对象的键值服务器；

通信地耦合到所述键值服务器的客户端；

用于处理对所述多个键值对象中的一个的操作的键值库；以及

用于从应用接收SQL查询并将所述SQL查询转换为对于要处理的所述键值库的操作的SQL库。

2.如权利要求1所述的系统，其特征在于，对于要处理的所述键值库的所述操作是事务，而所述键值服务器以事务快照隔离为特色。

3.如权利要求1所述的系统，进一步包括在所述客户端上执行的用于向所述SQL库发出所述SQL查询的应用。

4.如权利要求1所述的系统，其特征在于，所述键值服务器进一步包括远程过程协议(RPC)服务器组件，并且所述键值库进一步包括RPC客户端组件，并且所述键值服务器使用多版本存储。

5.如权利要求1所述的系统，其特征在于，所述键值服务器包括键值存储，并且所述键值库包括表示所述键值服务器上的所述键值存储的本地键值存储。

6.如权利要求1所述的系统，其特征在于，所述键值库和所述SQL库位于所述客户端处。

7.如权利要求1所述的系统，进一步包括并发性控制。

8.一种用于分布式SQL查询处理的方法，包括：

在执行在客户端上的SQL库处接收来自应用的所述SQL查询；

在所述客户端上的所述SQL库处将所述SQL查询解析并转换为可在键值系统上执行的多个操作；

将所述多个操作转发到键值服务器。

9.如权利要求8所述的方法，其特征在于，所述SQL查询引用SQL表，并且所述系统使用行id来作为所述SQL表的主键，并作为所述事务键值数据存储系统的键。

10.一种包括用于使用事务性键值系统来执行SQL查询的计算机可读指令的计算机可读存储介质，所述计算机可读指令包括导致处理器在所述客户端上的SQL库处将所述SQL查询解析并转换为可在所述事务性键值系统上执行的多个操作的指令。