已分区的、可缩放的、并且可用的结构化存储中的分区管理的制作方法
专利名称：已分区的、可缩放的、并且可用的结构化存储中的分区管理的制作方法
已分区的、可缩放的、并且可用的结构化存储中的分区管理
背景技术：
包括服务器农场、web服务等的分布式系统对于提供巨大量的计算和存储资源已变得日益常见。例如，分布式存储系统被用来为各种应用存储并检索巨大量的数据。在一些情况下，存储系统利用结构化存储来更高效地存储、检索以及查询数据。结构化存储系统可以跨遍及网络的多个节点来存储数据。随着提供这样的存储所需的计算资源量的增加， 这样的存储系统可以通过添加附加计算设备而“扩展”，从而提供可以按需添加附加资源的灵活的拓扑结构。因此，结构化存储系统可例如从千万亿字节的存储数据扩展成百万万亿字节的存储数据。结果，管理这样的结构化存储系统内的数据以使得数据总是可供访问并且持久以防止数据丢失通常是复杂的。概述提供本概述是为了以简化的形式介绍将在以下详细描述中进一步描述的一些概念。本发明内容不旨在标识所要求保护的主题的关键特征或本质特征，也不旨在用于帮助确定所要求保护的主题的范围。本发明的各实施例涉及结构化数据存储系统中的分区管理。在该存储中，结构化数据被划分成可由不同的服务器提供的多个分区。使用分区图来跟踪这些分区的所在之处。更具体地，使用分区图，客户机可以找出哪一服务器正在提供特定数据段。跟踪各分区的详细负载信息。各分区可以在服务器之间移动，以跨各服务器来达到负载平衡。在一些实施例中，为了达到更好的负载平衡，标识具有高负载的分区来进行拆分。确定拆分该分区的位置，并且将该分区拆分以创建子分区，在一些实施例中，这些子分区可被卸载到另一服务器。更新分区图以反映该分区已被拆分成各子分区。在一些实施例中，标识两个或更多个分区来进行归并。归并这些分区并更新分区图来反映经归并的分区。结构化存储是在流系统的顶层构建的，该流系统呈现只可添加(append-only)的文件系统界面。流类似于只可添加的文件。每一分区具有与它相关联的一组流。该分区的所有持久状态都保持在与它相关联的这一组流中。在该组流中，存在该分区的元数据流，它包含到该分区的所有其他流的指针以及该分区的必要信息，该必要信息诸如是该分区中包括的所有行的分区键范围。附图简述下面参考附图详细描述本发明，附图中
图1是适用于实现本发明的各实施例的示例性计算环境的框图；图2描绘根据本发明的一实施例的表结构；图3是其中可以实现本发明的各实施例的示例性系统的框图；图4是根据本发明的一实施例的示出一个分区的框图；图5是根据本发明的一实施例的示出用于拆分一分区的方法的流程图；图6描绘根据本发明的一实施例的被拆分成两个子分区的父分区的示例；图7是根据本发明的另一实施例的示出用于拆分一分区的方法的流程图；图8是根据本发明的一实施例的示出用于将各分区归并成一个经归并的分区的方法的流程图；图9是根据本发明的一实施例的示出用于恢复破坏分区的方法的流程图；以及图10是根据本发明的一实施例的示出用于分区版本化和升级的方法的流程图。详细描述此处用细节来描述本发明的主题以满足法定要求。然而，该描述本身并非旨在限制本专利的范围。相反，发明人设想所要求保护的主题还可结合其他当前或未来技术按照其他方式来具体化，以包括不同的步骤或类似于本文中所描述的步骤的步骤组合。此外，尽管术语“步骤”和/或“框”可在此处用于指示所采用的方法的不同元素，但除非而且仅当明确描述了各个步骤的顺序，否则该术语不应被解释为意味着此处公开的各个步骤之中或之间的任何特定顺序。本发明的各实施例提供可缩放的、可用的、并且持久的结构化存储。该结构化存储由多个表来表示，这些表中的每一个包括多个行，每一行表示一数据实体。表被分成多个分区，每一分区包括来自该表的一定范围的行。各分区存储在表服务器上并且被使用表主机来进行管理。在一些实施例中，各分区是出于负载分布的目的来被拆分的。跟踪各表服务器和各分区的负载分布信息。基于该负载分布信息，表主机可以决定对各分区进行负载平衡，并将各分区重新分配给不同的节点以分布负载。另外，对于一些分区，表主机可以决定将拆分一分区以分布当前负载。表主机确定拆分比率，并查询提供该分区的表服务器以寻找用于定位该拆分的键信息。基于从表服务器接收到的键信息，表主机指令该表服务器拆分该分区。在接收到拆分请求后，表服务器卸载目标分区，创建子分区，并开始提供该子分区。在一些实施例中，子分区被分配给另一表服务器。更新分区图以反映提供子分区的表服务器。在一些实施例中，各分区被归并。同样，跟踪各表服务器和各分区的负载分布信息。基于该负载分布信息，标识两个或更多个分区来进行归并。提供这些分区的表服务器被指令停止提供这些分区。这些分区被归并，并且被加载到开始提供经归并的分区的表服务器，更新分区图以反映提供经归并的分区的表服务器。因此，在一个方面，本发明的一实施例针对由结构化存储系统内的一个或多个计算设备实现的方法，其中结构化存储由一个或多个表来表示，每一个表包括多个行，每一行表示由该结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分该多个行，每一分区包括来自该表内的多个行中的一定范围的行，其中该多个分区存储在多个表服务器上，并且其中表主机控制对多个表服务器的分区分配。该方法用于将一分区拆分成各子分区，并且包括基于分区的负载信息来标识要拆分的分区，其中该负载信息包括指定该分区的两个或更多个部分中的每一个部分上的负载的信息。该方法还包括由表主机基于该分区的两个或更多个部分中的每一个部分上的负载来确定用于拆分该分区的拆分比率。该方法还包括查询表服务器以寻找指示该分区内的与该分区比率相对应的实际位置的键信息。该方法还包括在表主机处从表服务器接收键信息，该键信息指示该分区内的与拆分比率相对应的实际位置。该方法还包括从表主机向表服务器发送拆分请求，该拆分请求指示基于键信息来拆分该分区。该方法还包括在与该键信息相对应的位置处拆分该分区，以创建子分区。该方法还包括通知表主机拆分已完成。该方法还包括基于被拆分成子分区的分区来更新分区图，分区图存储多个分区与提供该多个分区的多个表服务器之间的映射。在本发明的另一实施例中，一个方面针对存储用于执行一种方法的计算机可使用指令的一个或多个计算机存储介质，该方法用于管理由一个或多个表来表示的结构化存储系统，每一个表包括多个行，每一行表示由该结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分该多个行，每一分区包括来自该表内的多个行中的一定范围的行，其中该多个分区存储在多个表服务器上，并且其中表主机控制对多个表服务器的分区分配。该方法用于将该表的至少两个分区归并成经归并的分区，并且包括跟踪多个表服务器上的多个分区的负载信息。该方法还包括由表主机基于该负载信息来标识要归并的至少两个分区。该方法还包括由表主机创建该经归并的分区的元数据流。该方法还包括将该至少两个分区从提供该至少两个分区的至少一个表服务器上卸载。 该方法还包括由表主机将该经归并的分区分配给来自该多个表服务器的所选表服务器。该方法还包括在所选表服务器处加载并提供该经归并的分区。本发明的又一实施例针对存储用于执行一种方法的计算机可使用指令的一个或多个计算机存储介质，该方法用于管理由一个或多个表来表示的结构化存储系统，每一个表包括多个行，每一行表示由该结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分该多个行，每一分区包括来自该表内的多个行中的一定范围的行，其中该多个分区存储在多个表服务器上，并且其中表主机控制对多个表服务器的分区分配。该方法用于将该表的一分区拆分成至少两个子分区，并且包括跟踪多个表服务器上的多个分区的负载信息。该方法还包括由表主机基于该负载信息来标识要拆分的分区，其中该分区的负载信息标识该分区的不同部分上的不同负载。该方法还包括在表主机处确定用于拆分该分区的拆分比率，其中该拆分比率是基于负载信息来指定的并且表示该分区中的点，在该点处该分区的第一部分包括第一负载量并且该分区的第二部分包括第二负载量。该方法还包括从表主机向表服务器发送请求，该对键信息的请求标识该分区中的与拆分比率相对应的实际位置。该方法还包括由表服务器确定标识该分区中的与拆分比率相对应的实际位置的键信息，并将该键信息从表服务器传递给表主机。该方法还包括在表主机处构造各子分区中的每一个子分区的元数据流。该方法还包括从表主机向表服务器发送拆分请求，并且在表服务器处构建来自该分区的子分区。该方法还包括在该表服务器处停止提供该分区，并且在该表服务器处加载并提供子分区。该方法还包括从表服务器向表主机发送拆分完成通知。该方法还包括基于被拆分成子分区的分区来更新分区图，分区图存储多个分区与提供该多个分区的多个表服务器之间的映射。在简要描述了本发明各实施例的概览之后，以下描述其中可实现本发明的各实施例的示例性操作环境，以便为本发明各方面提供通用上下文。首先具体参考图1，示出了用于实现本发明的各实施例的示例性操作环境，并将其概括地指定为计算设备100。计算设备 100只是合适的计算环境的一个示例，并且不旨在对本发明的使用范围或功能提出任何限制。也不应该将计算设备100解释为对所示出的任一组件或其组合有任何依赖性或要求。本发明可以在由计算机或诸如个人数据助理或其他手持式设备之类的其他机器执行的计算机代码或机器可使用指令(包括诸如程序模块之类的计算机可执行指令)的一般上下文中描述。一般而言，包括例程、程序、对象、组件、数据结构等的程序模块指的是执行特定任务或实现特定抽象数据类型的代码。本发明可以在各种系统配置中实施，这些系统配置包括手持式设备、消费电子产品、通用计算机、专用计算设备等等。本发明也可以在其中任务由通过通信网络链接的远程处理设备执行的分布式计算环境中实施。参考图1，计算设备100包括直接或间接耦合以下设备的总线110 存储器112、一个或多个处理器114、一个或多个呈现组件116、输入/输出端口 118、输入/输出组件120、 和说明性电源122。总线110可表示一条或多条总线(诸如地址总线、数据总线、或其组合)。虽然为了清楚起见利用线条示出了图1的各框，但是实际上，各组件的轮廓并不是那样清楚，并且比喻性地来说，线条更精确地将是灰色的和模糊的。例如，可以将诸如显示设备的呈现组件认为是I/O组件。而且，处理器具有存储器。可以认识到，这是本领域的特性， 并且重申，图1的图示只是例示可结合本发明的一个或多个实施例来使用的示例性计算设备。诸如“工作站”、“服务器”、“膝上型计算机”、“手持式设备”等分类之间没有区别，它们全部都被认为是在图1的范围之内的并且被称为“计算设备”。计算设备100通常包括各种计算机可读介质。计算机可读介质可以是可由计算设备100访问的任何可用介质，而且包含易失性和非易失性介质、可移动和不可移动介质。作为示例而非限制，计算机可读介质可以包括计算机存储介质和通信介质。计算机存储介质包括以用于存储诸如计算机可读指令、数据结构、程序模块或其他数据的信息的任何方法和技术实现的易失性和非易失性、可移动和不可移动介质。计算机存储介质包括但不限于， RAM、ROM、EEPR0M、闪存或其他存储器技术、CD-ROM、数字多功能盘(DVD)或其他光学存储、 磁带盒、磁带、磁盘存储或其他磁存储设备、或能用于存储所需信息且可以由计算设备100 访问的任何其他介质。通信介质通常以诸如载波或其他传输机制的已调制数据信号来体现计算机可读指令、数据结构、程序模块或其他数据，并包括任意信息传送介质。术语“已调制数据信号”指的是其一个或多个特征以在信号中编码信息的方式被设定或更改的信号。 作为示例而非限制，通信介质包括有线介质，如有线网络或直接线连接，以及诸如声学、RF、 红外及其他无线介质之类的无线介质。上述的任意组合也应包含在计算机可读介质的范围内。存储器112包括易失性和/或非易失性存储器形式的计算机存储介质。存储器可以是可移动的、不可移动的、或其组合。示例性硬件设备包括固态存储器、硬盘驱动器、光盘驱动器等。计算设备100包括从诸如存储器112或I/O组件120等各种实体读取数据的一个或多个处理器。呈现组件116向用户或其他设备呈现数据指示。示例性呈现组件包括显示设备、扬声器、打印组件、振动组件等等。I/O端口 118允许计算设备100在逻辑上耦合至包括I/O组件120的其他设备，其中某些设备可以是内置的。说明性组件包括麦克风、操纵杆、游戏垫、圆盘式卫星天线、扫描仪、打印机、无线设备、网络设备等等。高级数据模型根据本发明的各实施例，结构化存储由表来表示，其中表包含行集合。作为说明， 图2描绘根据本发明的一个实施例的表200的一部分。表200中的每一行(如行20 表示数据实体并包含在一系列列中标识的一组属性，该组属性包括属性204、206、以及208 (为简化和清楚起见，列208的数据值为空)。属性/列可以是例如名称、类型化值对、或名称到多个类型化值的映射。行和/或每一单独的属性可以版本化或可以不版本化。表本身可具有固定模式，其中该表中的每一行具有相同属性和相同类型，或可以不强制模式，其中每一行存储了不同的一组属性和类型。对结构化存储执行的标准操作集合包括插入、更新和删除表、行以及属性的能力。 另外，提供了对表、行以及属性进行扫描和查询以找出与该指定扫描/查询相匹配的一组表、行或属性的功能。分区划分(partitioning)表能长到数十亿或数万亿行以及万亿字节/千万亿字节的数据，并且表可能必须跨数千服务器分布以处理对表的不同部分的流量/负载。为了使结构化存储达到这一可缩放性，各实施例采用分区划分来将各表和各行分布在各服务器上。分区划分将表中的各行编组/断开成各分区，并且随后这些分区被分配给不同的服务器并从这些不同的服务器提供(提供对这些分区的读和写访问)。为了使表变得可缩放，表具有被称为属性的组成分区键的一个到多个键。例如，参考图2的表200，表200的第一列204包括每一行/实体的分区键。如果给定表存在超过一个分区键属性/列，则组合在一起的属性/列形成该表的合成分区键。一个行的分区键的值被用来标识该实体/行所属于的分区。具有相同分区键值的行被认为编组到同一分区中。除分区键之外，每一行具有零个到多个附加行键属性/列。例如，再次参考图2的表200，表200的第二列206包括每一行/实体的行键。行键表示分区内的行的唯一 ID。组合了行键的分区键表示该行/实体在该表中的主键(唯一 ID)。主键表示该表中的分区的主排序次序。如果没有行键，则分区键是主键并且必须唯一地标识该表中的每一实体。虽然下文的描述按照单个分区键和单个行键讨论了本发明的各实施例，但在使用多个分区键和/或行键时，同样的原理也适用。分区键被用来将具有相同分区键“值”的各行编组在一起，而行键表示行在分区内的唯一 ID。基于分区键值将表的各行断开在本文中被称为对表进行分区划分。这将表的各行编组/断开成各分区。分区是具有同一分区键值的行集合，所以具有同一分区键的所有这些行将总是被存储在同一分区中。因此，具有同一分区键值的两个行处于同一分区中， 并且不被拆分到跨两个分区。另外，在一些实施例中，分区的定义被扩展，以允许具有不同分区键值的多个行被编组在同一分区中，只要它们的键值在分区键名字空间中显得邻近即可。作为示例，参考图2的表200，示出了四个分区，第一分区(Pl 210)、第二分区(P2 212)、 第三分区(P3 214)以及第四分区(P4 216)。如图2所示，一些分区包括具有单个分区键值的各行，而其他分区包括具有多个分区键值的各行。作为前者的示例，Pl 210包括具有分区键值1的所有行，并且P2 212包括具有分区键值2的所有行。作为后者的示例，P3 214 包括具有分区键值3、4、或5的所有行，并且P4 216包括具有分区键值6或7的所有行。分区划分的优点包括但不限于(1)通过将表断开成各分区并基于数据的访问模式和流量需求以将这些分区分布在各服务器上来缩放对表的访问的能力，以及O)同一分区中的各行被编组在一起并且从同一表服务器访问，这允许在操作的作用域处于分区内时更高效地进行查询、扫描、以及高速缓存。对分区进行扫描更加高效，因为由于它是从该分区的单个表服务器访问，因此最多只需扫描各分区内的那些行，而非在查询时在没有指定分区键的情况下可能必须遍历整个表。高级体系结构
根据本发明的各实施例，一组服务器(本文中被称为“表服务器”)存储结构化存储系统并提供对它的访问。另外，一组服务器(本文中被称为“表主机”)管理这些表服务器。“表客户机”提供对该结构化存储系统的应用程序访问。现在参考图3，提供了示出根据本发明一实施例的系统300的高级体系结构的框图。应当理解，此处所描述的这一和其他安排仅作为示例来阐明。除了所示的安排和元素之外，或作为其替代，可使用其他安排和元素(例如，机器、接口、功能、次序、以及功能组等)， 并且可完全省略某些元素。此外，此处所描述的许多元素是可以实现为分立或分布式组件或结合其他组件来实现的、以及以任何合适的组合和在任何合适的位置的功能实体。此处被描述为由一个或多个实体执行的各种功能可由硬件、固件和/或软件来执行。例如，各种功能可由执行存储在存储器中的指令的处理器来执行。虽然未示出其他组件，但系统300 —般包括表主机302，表服务器304、306、308、 310，以及表客户机312。每一个都可以驻留在任何类型的计算设备上，诸如例如参考图1描述的计算设备100。系统300的组件可以经由网络彼此通信，网络包括但不限于一个或多个局域网(LAN)和/或广域网(WAN)。应当理解，虽然图3中只示出了单个表主机、四个表服务器、以及单个表客户机，但在本发明的各实施例的范围内，在系统300中可以使用任何数量的表主机、表服务器、表客户机。表主机302负责(1)将各分区分配给表服务器304、306、308、310 ； (2)快速确定一分区何时由于故障而没有被提供并将该分区重新分配给不同的表服务器；C3)控制各分区在表服务器304、306、308、310之间的负载平衡；以及(4)监视表服务器304、306、308、 310的健康。表服务器304、306、308、310中的每一个负责提供对表主机分配给自己的分区的读和写访问。表服务器304、306、308、310中的每一个可以主存零个到多个分区。在图3的示例中，TSl 304(表服务器1 304)主存分区Pl和P4，TS2 306主存分区P2和P7，TS3 308 主存分区P3，以及TS4 310主存分区P5和P6。表客户机312被链接到应用程序，并且被用来向由表服务器304、306、308、310维护的分区发出命令。表客户机312使用分区图来确定提供该分区的表服务器，并且它将命令发送到该表服务器。表客户机312还从表服务器接收回结果并将它们传递给应用程序。 分区图是特殊的表，它存储各分区与提供它们的表服务器之间的映射，并且由表主机302 来维护。如图4所表示的，在内部，在表服务器处提供的分区400包括三个主要部分更新日志402、一个到多个存储器表404、以及零个到多个文件表406。更新日志402跟踪对持久存储中的分区的新近变更。存储器表404是更新日志中的新近(增量)更新的存储器内版本。这些是对分区400的新近增量变更。在存储器表404变得足够大或其中具有了足够的变更的情况下，存储器表404被检查点记录(checkpoint)到持久存储在存储中的文件表 406。在这发生时，更新日志402中的直至被检查点记录的存储器表404的所有请求可以从更新日志402中移除。如上所述，分区具有存储其持久状态的一组流。更新日志402存储在这些流之一中，该流被称为更新日志流。所有文件表406被存储在这些流之一中，这条流被称为文件表流。在表服务器加载一分区时，该表服务器重放更新日志中的自最新近检查点以来的所有请求，以将存储器表重构回到正好在该分区被最后卸载之前的状态。在访问表服务器处的分区时，该表服务器首先查看存储器表中是否有匹配的行， 以查看所有新近的变更，并且如果没有匹配，则在它的页高速缓存和文件表中查找该数据。一分区可存在多个存储器表和多个文件表。可存在多个存储器表，因为在一个存储器表变满时，它需要被检查点记录到文件表。在这发生时，当前存储器表在被检查点记录时被设成只读的，并为该分区创建新存储器表以供写入。因此，分区总是具有用于新近(增量)更新的一个存储器表，并且它可以具有被懒散地进行检查点记录的一个或多个存储器表。一旦存储器表被检查点记录到文件表，它可被删除或被垃圾收集。由于对一分区做了所有检查点记录，因此该分区可存在多个文件表检查点。这意味着在需要从文件表中读取数据时，可能需要查看多个文件表，并且是以从最新近到最老的次序来查看它们。这是因为所写的最新近文件表包含该分区的最新近变更。在对一分区进行检查点记录了足够的文件表时，表服务器懒散地将这些文件表压缩/归并在一起成为新的经归并的文件表，以减少为了找出一分区的被查找的数据而必须被搜索的文件表的数量。可缩放的、可用的并且持久的结构化存储本发明的各实施例采用分区划分、负载平衡、以及扼流来提供可缩放的结构化存储系统。可缩放性通过以下来提供(1)将表拆分成各分区并将这些分区分布在数据中心中的多个服务器上；( 使用负载平衡来将分区从高负载的表服务器移动到较轻负载的表服务器；以及C3)进行扼流来丢弃对具有发送到它的过多流量的分区的请求或丢弃对具有被发送到它的过多流量的表服务器的请求。可缩放性是通过基于分区的不同部分的负载来将表自动地拆分成各分区并随后跨各个表服务器进行负载平衡来提供的。负载平衡使系统动态地适应工作负载，从而将负载分布在大量机器上，从而通过高效地利用所有物理资源而达到更好的可缩放性。另外，进行扼流保护该系统免于高负载，从而使该系统保持在高效/优化的制度中操作。表主机通过标识未被提供的分区、向它们分配不同的表服务器、以及更新分区图来提供可用性，这允许表客户机找到分区的新位置来对该分区进行访问。在节点/网络故障的情况下对分区进行快速重新分配保持了所有分区可用并且产生了高系统可用性。持久性是通过将分区数据的全部存储在复制的流层中来提供的。流层提供如接口之类的文件系统，用于向流(类似于文件)写入数据并从流读取数据，并且流层提供用于确保数据被复制的完整功能，总是在该系统中的各表服务器中的任一个上持久存储并可从中获得。因此，分区信息被存储在流层中，该分区信息包括分区图、更新日志以及文件表。高效的流层操作流层提供将流的一个区域高效地硬链接到另一条流的能力。流层处的每一条流包括被称为范围的数据块列表。该流中的数据事实上存储在这些范围内部。流是范围的有序列表。给定范围可以驻留在多条流中，或甚至在同一条流的有序范围列表中出现多次。流层提供接口，用于通过将驻留在一条流中的一组现有范围进行链接来合成另一条流。在这一过程中不涉及真实的数据复制，所以它是非常高效的。流层维护每一范围的引用计数。一旦范围没有了指向它的流，则流层将从该系统中对这一范围进行垃圾收集/删除。流层还支持在一个原子事务中具有多个流级操作的能力，如对流进行创建、删除、重命名、以及将范围硬链接到流。结构存储系统大量使用这些特征来高效地对一分区的各条流的过时部分进行垃圾收集。示例是一旦作出了一分区的检查点，更新日志中的在该检查点之前的所有消息不再被使用。这些特征被用来通过原子地创建与更新日志流相同名称的新流、将来自原始流的仍然使用的范围硬链接到该新流、并删除原始流，来高效地将更新日志截短。所有这些是在一个原子事务中完成的。这极大地简化了故障处理逻辑。类似方案也被用于分区的其他流，如文件表流和元数据流。结构化存储系统还大量使用这些特征来高效地实现分区的拆分和归并，如在稍后章节中描述的。更具体地，这些特征被用来将来自原始分区的数据高效地引用到从拆分/ 归并创建的子分区，而不必物理地复制或移动任何位。对分区进行拆分、归并以及负载平衡本发明的一些实施例在存储系统内的各表服务器之间对负载分布进行平衡。一般而言，表服务器跟踪每一分区的负载，并且向表主机周期性地报告这一信息。表主机通过在表服务器之间移动分区来作出负载平衡决定。这通过将目标分区从原始表服务器卸载并将该分区分配给其他表服务器来实现。作为优化，本发明的一些实施例可以使表主机在卸载分区之前或之时向表服务器发送“准备卸载请求”。在接收到这一请求后，表服务器将对分区进行检查点检查，以减少在再次加载该分区时需要重放的日志的量。提供这一点以满足用于提供该分区的可用性SLA。在单个分区具有相对较高负载的情况下，将该分区拆分成两个或更多个分区是合乎需要的，并且只有在该分区包含超过一个分区键值的情况下这才是可能的。因此，子分区中的一个或多个可被卸载到不同的表服务器来达到负载平衡。对于负载分布跟踪，每一表服务器使用采样机制来跟踪每一分区内的细粒度的负载信息而不消费大量存储器。为了跟踪负载信息，分区被划分成多个分区键范围(在此称为“桶”)，并且跟踪与每一个桶相对应的负载。更具体地，表服务器在概率上对落入这些桶内的请求进行采样，并跟踪这些桶的负载分布。例如，参考图2的表200内的分区P3 214， 出于负载跟踪目的，该分区可以被划分成两个桶。第一个桶将包括具有分区键值3的行，第二个桶将包括具有分区键值4和分区键值5的行。在各实施例中，桶边界必须总是处于分区键值上。即，具有同一分区键值的行将总是处于同一个桶中。例如，出于负载跟踪以及拆分的目的，具有分区键值3的行可被拆分成两个桶。在一些实施例中，基于所收集的流量样本，桶边界可以动态地调整以更准确地跟踪跨一分区内的各键的流量分布。即，如果两个现有桶与其他桶相比不具有很大负载，则它们将被归并成单个桶；相反，如果一个桶包含比所有其他桶大得多的负载，则在可能的情况下，该桶可被拆分成两个。例如，在先前示例中，如果第二个桶与第一个桶相比包含过多负载，则它可被拆分成两个较小的桶，其中之一包含具有分区键值4的行并且其中的另一个包含具有分区键值5的行。此外，如果包含分区键值3的第一个桶具有很少负载，则它可与包含分区键值4的桶归并在一起。对桶大小的这一监视和调整全部是在进行中动态地完成的。除用来跟踪跨一个分区内的各分区键的负载分布的桶水平采样方案之外，表服务器还跟踪整个分区上的工作负载的总量。后者被传递给表主机。因此，在需要基于负载来拆分一分区时，相当准确的负载分布信息对表服务器和表主机确定应当在何处拆分该分区而言都是可用的。现在参考图5，提供了示出根据本发明的一实施例的用于拆分一分区的方法500 的流程图。在图5的实施例中，父分区Pl被拆分成两个子分区ΡΓ (被修改成只包括各行的子集的原始分区)和P2(包括其余各行的新分区)。虽然图5讨论了将一分区拆分成两个子分区，但应当理解，根据本发明的各实施例，一分区可被拆分成超过两个子分区。一开始，如在框502所示，跟踪表服务器、分区、和/或分区部分(即，“桶”)的负载分布信息。如上所述，通过在分区部分级跟踪细粒度的负载信息，可以作出关于在何处拆分一分区的判定。负载信息由表服务器来跟踪并被周期性地提供给表主机。在当前实施例中，发送到表主机的负载信息包括每一分区的总负载和每一表服务器的负载。一些其他实施例可以向表主机提供所有这些负载跟踪信息，包括桶级信息。从表服务器向表主机提供关于一分区的附加信息、约束、以及提示，以帮助进行负载平衡和拆分决策。例如，基于桶信息的分布，表服务器可以将一分区标记为带有某一严重性程度的“难以拆分”，其中“高”意味着表主机不应请求拆分该分区，因为表服务器不会拆分该分区，其中“中”意味着在某些情况下表服务器可选择不拆分该分区并且表主机可以不顾这一决定，并且其中“低”意味着表服务器将监听并采取表主机的指导。表主机使用该负载信息来作出负载分布决定，包括是否拆分分区、是否归并各分区、和/或是否在表服务器之间移动各分区。在图5的当前实施例中，表主机基于负载分布信息确定要拆分一分区(Pl)，如在框504所示。在框506，表主机确定用于拆分该分区的拆分比率。拆分比率表示用于确定应当在其中拆分该分区的位置的负载比率。例如，表主机可以决定在30% /70%负载点处拆分一分区。换言之，该分区应在以下点处拆分该分区第一部分的负载是30%并且该分区其余部分的负载是70%。在框508，表主机向主存被标识来拆分的分区的表服务器发送请求。 具体而言，表主机请求指定与该分区中的拆分比率相对应的位置的键信息。响应于该请求， 表服务器基于拆分比率来标识用于拆分该分区的实际分区键位置，如在框510所示。该实际位置尝试与拆分比率所指定的负载分布相匹配，但实际负载分布可能不同。例如，表主机所请求的拆分比率可以是30% /70%负载分布，但可以提供的最接近的匹配是35% /65% 负载分布。在一些实施例中，用于拆分的实际位置是使用分区键信息来标识的。例如，如果图 2的分区P3 214要在分区键值3和4之间进行拆分，则标识该拆分的键信息可以是分区键值3和/或分区键值4。任何及所有这样的变型都被构想为落在本发明的各实施例的范围内。表服务器将拆分比率的键信息返回给表主机，如在框512所示。表主机构造作为子分区之一的新分区(P2)的流，如在框514所示。分区的所有持久状态都保持在该分区的“流”中。存在该分区的元数据流，它包含到该分区的所有其他流的指针以及该分区的必要信息，该必要信息诸如是该分区中包括的所有行的分区键范围。 在该步骤中，表主机负责使用对应于拆分比率的正确的分区键范围信息来创建新分区(P2) 的元数据流。另外，在框516，表主机将拆分请求发送到表服务器。该拆分请求可以在下一心跳中从表主机提供给表服务器。在一些实施例中，写下适当的主日志以处理故障。表主机在每一步骤完成之后记录该对应步骤，使得在主机故障的情况下，这些日志可被重放并且表主机可以从它停止的地方继续进行拆分。在接收到拆分请求之后，表服务器停止提供原始分区并卸载原始分区(Pl)，如在框518所示。表服务器还从该原始分区中构建两个子分区(ΡΓ和P2)，如在框520所示。 表服务器基于原始分区(Pl)中的信息来构造新分区(P2)的流(除了元数据流之外)。更具体地，使用底层流层的特征，属于P2的键范围的数据部分将从分区Pl高效地被复制/硬链接到分区P2的流。子分区ΡΓ是通过调整Pl的键范围来“创建”的。子分区ΡΓ使用与原始分区Pl相同的一组流。改变ΡΓ的元数据以调整到该减少的键范围。如在框522所示，表服务器加载这两个子分区(ΡΓ和P2)并开始提供这些分区。 另外，表服务器向表主机通知拆分已完成，如在框5M所示。这一通知可以在下一心跳中从表服务器提供给表主机。响应于来自表服务器的拆分完成通知，表主机更新分区图以反映新分区，如在框5 所示。此时，表主机可以认为拆分已完成。表主机向表服务器发送包括新创建的子分区(P》的新分配，使得它与分区图相匹配，如在框5 所示。在一些实施例中，在拆分了一分区之后，表主机可以确定将子分区从原始分区所处的表服务器移动到另一表服务器。这允许表主机将负载高效地分布在整个网络上。分区移动是通过将分区从一个表服务器卸载并随后将它分配给另一表服务器来实现的。在本发明的其他实施例中，以上参考图5描述的拆分协议的性能可以通过在框 518处卸载原始分区之前创建新子分区来改进。对本领域技术人员而言，上述方法500的其他变型也显而易见并且处于本发明各实施例的范围内。图6示出根据本发明的一实施例的对图2的P3 214进行拆分的示例。具体而言， 图6示出图3的表主机(TM) 302与TS3 308 (表服务器3 308)之间的用于执行P3 214的拆分的交互，其中P3 214驻留在TS3 308上。一开始，如在602所示，表主机302向TS3 308 发送查询键信息的请求以标识拆分P3 214的位置。该请求指定0.3拆分比率，指示表主机希望在接收到P3 214上的负载的30%的P3 214的一部分与接收到该负载的70%的剩余部分之间的位置处拆分P3 214。响应于来自表主机302的请求，TS3 308确定与表主机302所指定的拆分比率相对应的键信息。该键信息基于被表主机302指定为拆分比率的30% /70%负载分布来表示 P3 214的两部分之间的位置。在本示例中，TS3 308确定具有分区键值3的行上的负载大约具有负载的30%，而其余行上的负载大约具有负载的70%。如此，在本示例中，TS3 308 所确定的键信息是分区键值4。应当理解，在各实施例中，可以提供其他键信息来标识应当在其中拆分P3 214的位置。在606，TS3 214将键信息(即，分区键值4)传递给表主机302。在608，表主机 302构造新分区PN的流。另外，如在框610所示，表主机302将拆分请求发送到表主机。在本示例中，拆分请求指定子分区中的每一个的范围。具体而言，对于一个子分区P3’，拆分请求指定低分区键值3和高分区键值4，从而指示P3’包括具有分区键值3的行。对于另一子分区PN，拆分请求指示低分区键值4和高分区键值6，从而指示PN包括具有分区键值4的行以及具有分区键值5的行。在612，基于拆分请求，TS3停止提供原始分区P3 214。另外，TS3 308将P3拆分成P3，和PN，如在614所示，并开始提供P3，和PN，如在616所示。TS3 308随后向表主机 302发送拆分完成通知，如在618所示。在620，表主机302更新分区图以反映子分区。
现在转向图7，提供了示出根据本发明的另一实施例的用于拆分一分区的方法 700的流程图。在图7的实施例中，父分区Pl被拆分成两个新子分区P2和P3，其中每一子分区包括来自父分区Pl的各行的一部分。虽然图7讨论了将一分区拆分成两个子分区，但应当理解，根据本发明的各实施例，一分区可被拆分成超过两个子分区。与图5的方法500类似，一开始跟踪负载分布信息，如在框702所示。该负载分布信息允许表主机作出负载分布决定，包括是否拆分一分区、是否归并各分区、和/或是否在表服务器之间移动各分区。在图7的当前实施例中，表主机基于负载分布信息确定要拆分一分区(Pl)，如在框704所示。在框706，表主机确定用于拆分该分区的拆分比率。如上所述，拆分比率表示用于确定应当在其中拆分该分区的位置的负载比率。例如，表主机可以决定在30% /70%负载点处拆分一分区。在框708，表主机向主存被标识来拆分的分区的表服务器发送请求。具体而言，表主机请求指定与该分区中的拆分比率相对应的位置的键信息。响应于该请求，表服务器基于拆分比率来标识用于拆分该分区的实际位置，如在框710所示。表服务器将拆分比率的键信息返回给表主机，如在框712所示。表主机构造新分区(P2和P3)的元数据流，如在框714所示。在一些实施例中，写下适当的主日志以处理故障。表主机在每一步骤完成之后记录该对应步骤，使得在主机故障的情况下，这些日志可被重放并且表主机可以从它停止的地方继续进行拆分。另外，在框 716，表主机将拆分请求发送到表服务器。该拆分请求可以在下一心跳中从表主机提供给表服务器。响应于该拆分请求，表服务器从原始分区(Pl)中构建两个子分区(P2和P3)，如在框718所示。表服务器基于原始分区(Pl)来构造新分区(P2和P3)的流(除了元数据流之外)。更具体地，使用底层流层的特征，属于P2的键范围的数据部分将从分区Pl高效地复制/硬链接到分区P2的流。类似地，使用底层流层的相同特征，属于P3的键范围的数据部分将从分区Pl高效地复制/硬链接到分区P3的流。表服务器停止提供原始分区并卸载原始分区(Pl)，如在框720所示。另外，如在框722所示，表服务器加载这两个子分区(P2和P； )并开始提供这些分区。表服务器向表主机通知拆分已完成，如在框7M所示。这一通知可以在下一心跳中从表服务器提供给表主机。响应于来自表服务器的拆分完成通知，表主机更新分区图以反映新分区，如在框726 所示。此时，表主机可以认为拆分已完成。表主机向表服务器发送包括新创建的子分区(P2 和P； )的新分配，使得它与分区图相匹配，如在框7 所示。在一些情况下，表主机可以基于例如负载分布信息来确定将两个或更多个分区归并成单个分区。在一实施例中，归并是在两个相邻分区(即，在表中的行序列中相邻)具有相对低的负载时执行的。将各分区归并成单个分区有益于减少系统中分区的数量。因此，图8提供示出根据本发明的一实施例的用于归并各分区的方法800的流程图。如在框802所示，一开始跟踪负载分布信息。基于该负载分布信息，表主机确定两个分区(Pl和P2)应被归并成新分区(P3)，如在框804所示。在各实施例中，只有形成连续且未脱节的分区键范围的分区才能被归并。在表主机决定归并两个分区时，表主机向提供这两个分区的(诸)表服务器发送 (诸)‘准备归并’消息，如在框806所示。在一些情况下，这两分区可驻留在单个表服务器上，而在其他情况下，这些分区可以驻留在不同的表服务器上。‘准备归并’消息向表服务器给出了在归并之前对分区进行压缩以减少经归并的分区的加载时间的机会。在框808，表主机创建经归并的分区(P3)的元数据流，并且在框810，将两个父分区$1和1^)从这些父分区所处的(诸)表服务器上卸载。表主机随后更新分区图(原子地移除旧分区条目，并插入新分区条目)，如在框812所示。从表主机的观点来看，归并事务在此时完成，因为在表主机故障的情况下，新归并的分区将在引导期间在持久存储的分区图中找到。表主机将经归并的分区(P3)分配给表服务器，如在框814所示。向其分配经归并的分区的表服务器可以是系统中的任何表服务器。例如，所分配的表服务器可以是父分区之一或两者所处的表服务器或可以是系统中的不同的表服务器。在分配之后，表服务器加载经归并的分区，如在框816所示。从经归并的分区的元数据流中，表服务器获知这是经归并的分区，并且它通过使用来自底层流层的特征来高效地复制/硬链接来自父分区的数据来从父分区构造该经归并的分区的流。在构造完成之后，表服务器将这一事件记录在经归并的分区的元数据流中(以便下一次加载这一分区时，这些流将不会被再次构造)，并删除父分区的流。从破坏的分区状态恢复持久的结构化存储系统应当能够从系统状态的隐错中恢复。为了实现这一能力， 本发明的一实施例中的结构化存储系统是构建在只可添加的存储上的，并且将所有已删除数据保留到被认为足以发现系统中的任何错误的最小长度的时间。现在参考图9，提供了示出根据本发明的一实施例的用于将一分区从破坏的分区状态中恢复的方法900的流程图。最初，如在框902所示，标识破坏的分区。如果分区被破坏并且不能被提供，则发出警报，从而将该分区标记为未被提供。这可造成对该分区中的数据的可用性的临时丢失。如在框904所示，将破坏的分区恢复到一致的分区状态。系统可以从下述两项中任选其一 (a)修复该分区，因为对该分区的所有先前改变已被存储在只可添加的存储中， 这将在不丢失任何数据的情况下恢复该分区；或(b)将该分区回退到先前数据段，这可能造成在回退到的时间与故障的时间之间发生的改变的丢失。一旦修复了分区，则该分区可再次用来被提供，以供读出和写入结构化数据。在分区回退期间，该系统找出仍然处于有效状态的最新近的检查点，并使用该检查点连同对应的日志(如果它们仍然存在)来重建分区状态。在一些情况下，在分区回退期间，该分区的当前元数据和数据内容不足以恢复分区状态。在这些情况下，该系统使用来自其他相关分区的数据，包括在涉及目标分区的最新近拆分或归并期间的该目标分区的父分区。更具体地，该系统通过归并来自父分区和目标分区的最新近的有效检查点的状态来重构分区的状态。在恢复或重建了所有分区之后，修订分区图来匹配经重构系统中的所有分区的键范围，如在框906所示。这将系统带回到全局一致的状态。分区版本化和升级在执行表服务器代码的升级时，一次只对表服务器的一个子集执行该升级。如此， 表服务器被分成N个升级域，并且可以一次升级一个升级域。
参考图10，提供了示出根据本发明的一实施例的用于在升级期间进行分区版本化的方法1000的流程图。如在框1002所示，在升级过程期间，分区可以从接下来要被升级的目标升级域内的表服务器移出。将新表服务器代码版本部署到该目标升级域内的表服务器，如在框1004所示。在升级过程期间，可将分区分配给具有新表服务器代码版本的表服务器，并且开始用可能新的数据格式来修改该分区，如在框1006所示。在这一修改之后，分区可只由较新升级的表服务器来提供，并且可不由较老版本表服务器来提供。如此，一旦版本N的表服务器提供了一分区，则该系统确保分区只由版本N或更加新的版本(或其他兼容的表服务器版本)的表服务器来提供，如在框1008所示。在本发明的各实施例的范围内，这可以用多种不同方式来实现。例如，在一个实施例中，跟踪每一分区、表服务器和表主机的版本号。在升级发生时，如果提供该分区的表服务器是较高版本号，则该分区采用该版本号。自此时起，该分区可以只由该版本或更高版本的表服务器来提供。在另一实施例中，每一表服务器一经升级，该表服务器就与表主机进行通信以指示它的版本。表主机跟踪最新表服务器版本，并且待分配的分区可只被分配给具有最新版本(或其他兼容版本)的表服务器。在又一实施例中，分区版本与分区元数据一起持久存储。表服务器将分配给它们的分区的版本通知给表主机。表服务器还向表主机报告它们自己的版本号。表主机从而保持跟踪分区版本以及表服务器版本。以此方式，表主机确保分区可被分配给兼容版本的表服务器。结论参考各具体实施例描述了本发明，各具体实施例在所有方面都旨在是说明性的而非限制性的。在不偏离本发明范围的情况下，各替换实施例对于本发明所属领域的技术人员将变得显而易见。从前面的描述可以看出，本发明很好地适用于实现上文所阐述的所有目的和目标，并且具有对于该系统和方法是显而易见且固有的其他优点。也可理解特定的特征和子组合是有用的，并且可以加以利用而无需参考其他特征和子组合。这由权利要求所构想的， 并在权利要求的范围内。
权利要求
1.一种由结构化存储系统内的一个或多个计算设备实现的方法，其中结构化存储由一个或多个表来表示，每一个表包括多个行，每一行表示由所述结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在所述多个分区之间划分所述多个行，每一分区包括来自所述表内的多个行中的一定范围的行，其中所述多个分区存储在多个表服务器上，并且其中表主机控制对所述多个表服务器的分区分配，所述方法用于将一分区拆分成各子分区，并且包括基于分区的负载信息来标识(504)要拆分的分区，其中所述负载信息包括指定该分区中的两个或更多个部分中的每一个部分上的负载的信息；由所述表主机基于所述分区的两个或更多个部分中的每一个部分上的负载来确定 (506)用于拆分所述分区的拆分比率；查询(508)所述表服务器以寻找指示所述分区内的与所述分区比率相对应的实际位置的键信息；在所述表主机处从所述表服务器接收(510)键信息，所述键信息指示所述分区内的与所述拆分比率相对应的实际位置；从所述表主机向所述表服务器发送(516)拆分请求，所述拆分请求指示基于所述键信息来拆分所述分区；在与所述键信息相对应的位置处拆分(518、520、52幻所述分区以创建所述子分区；向所述表主机通知(524)拆分已完成；以及基于被拆分成所述子分区的分区来更新(526)分区图，所述分区图存储所述多个分区与提供所述多个分区的多个表服务器之间的映射。
2.如权利要求1所述的方法，其特征在于，该方法还包括在所述表主机处构造所述子分区中的至少一个的流。
3.如权利要求1所述的方法，其特征在于，拆分所述分区包括停止从所述表服务器提供所述分区；从所述分区构建所述子分区；以及从所述表服务器加载并提供所述子分区，其中停止提供所述分区包括为所述分区创建检查点，从而减少在分区重载期间要重放的日志的量，其中创建所述分区的检查点包括在检查点期间通过原子地执行以下步骤来高效地截短日志流创建新日志流，将所述检查点之后的范围从旧日志流硬链接到所述新日志流，删除所述旧日志流，以及将所述新日志流重命名成所述旧日志流的名称。
4.如权利要求3所述的方法，其特征在于，从所述分区构建所述子分区包括通过在没有昂贵的数据复制的情况下原子地硬链接来自所述分区的流的范围来高效地构造所述子分区的流。
5.如权利要求1所述的方法，其特征在于，所述方法还包括将所述子分区中的至少一个分配给第二表服务器，并且更新所述分区图以指示所述子分区中的该至少一个位于该第二表服务器处。
6.如权利要求1所述的方法，其特征在于，所述方法还包括出于负载监视目的，基于所述负载信息通过归并或拆分所述分区的两个或更多个部分的至少一个子集来调整所述分区的该两个或更多个部分的边界。
7.一个或多个存储用于执行一种方法的计算机可使用指令的计算机存储介质，所述方法用于管理由一个或多个表来表示的结构化存储系统，每一个表包括多个行，每一行表示由所述结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分所述多个行，每一分区包括来自所述表内的多个行中的一定范围的行，其中所述多个分区存储在多个表服务器上，并且其中表主机控制对所述多个表服务器的分区分配，所述方法用于将所述表的至少两个分区归并成经归并的分区，并且包括跟踪(80 所述多个表服务器上的多个分区的负载信息；由所述表主机基于所述负载信息来标识(804)要归并的至少两个分区；由所述表主机创建(808)经归并的分区的元数据流；将所述至少两个分区从提供该至少两个分区的至少一个表服务器上卸载(810)；由所述表主机将所述经归并的分区分配给(814)来自所述多个表服务器的所选表服务器；以及在所选表服务器处加载并提供(816)所述经归并的分区。
8.如权利要求7所述的一个或多个计算机存储介质，其特征在于，所述至少两个分区被存储在同一表服务器上。
9.如权利要求7所述的一个或多个计算机存储介质，其特征在于，所选表服务器包括在所述至少两个分区被归并成所述经归并的分区之前在其上驻留有该至少两个分区中的至少一个分区的表服务器。
10.如权利要求7所述的一个或多个计算机存储介质，其特征在于，所述方法还包括基于被归并成所述经归并的分区的所述至少两个分区来更新分区图，所述分区图存储所述多个分区与提供所述多个分区的多个表服务器之间的映射。
11.如权利要求7所述的一个或多个计算机存储介质，其特征在于，所述方法还包括从所述表主机向提供所述至少两个分区的至少一个表服务器发送准备归并消息，其中所述准备归并消息使得所述至少一个表服务器在归并所述至少两个分区之前压缩该至少两个分区以减少所述经归并的分区的加载时间。
12.—个或多个存储用于执行一种方法的计算机可使用指令的计算机存储介质，所述方法用于管理由一个或多个表来表示的结构化存储系统，每一个表包括多个行，每一行表示由所述结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分所述多个行，每一分区包括来自所述表内的多个行中的连续范围的行，其中所述多个分区存储在多个表服务器上，并且其中表主机控制对所述多个表服务器的分区分配，所述方法用于将所述表的一分区拆分成至少两个子分区，并且包括跟踪(70 所述多个表服务器上的多个分区的负载信息；由所述表主机基于所述负载信息来标识(704)要拆分所述分区，其中所述分区的负载信息标识该分区的不同部分上的不同负载；在所述表主机处确定(706)用于拆分所述分区的拆分比率，其中所述拆分比率是基于负载信息来指定的并且表示所述分区中的点，在该点处所述分区的第一部分包括第一负载量并且所述分区的第二部分包括第二负载量；从所述表主机向所述表服务器发送(708)请求，该对键信息的请求标识所述分区中的与所述拆分比率相对应的实际位置；由所述表服务器确定(710)标识所述分区内的与所述分区比率相对应的实际位置的键信息；将所述键信息从所述表服务器传递给(71 所述表主机； 在所述表主机处构造(714)所述子分区中的每一个子分区的元数据流； 将拆分请求从所述表主机发送到(716)所述表服务器； 在所述表服务器处从所述分区构建(718)所述子分区； 停止(720)在所述表服务器处提供所述分区； 在所述表服务器处加载并提供(72 所述子分区； 将拆分已完成通知从所述表服务器发送到(724)所述表主机；以及基于被拆分成所述子分区的分区来更新(726)分区图，所述分区图存储所述多个分区与提供所述多个分区的多个表服务器之间的映射。
13.如权利要求12所述的一个或多个计算机存储介质，其特征在于，所述方法还包括将所述子分区中的至少一个分配给第二表服务器；并且更新所述分区图以指示所述子分区中的该至少一个位于该第二表服务器处。
14.如权利要求12所述的一个或多个计算机存储介质，其特征在于，停止提供所述分区包括为所述分区创建检查点，从而减少在分区重载期间要重放的日志的量，其中创建所述分区的检查点包括在检查点期间通过原子地执行以下步骤来高效地截短日志流创建新日志流，将在所述检查点之后的范围从旧日志流硬链接到所述新日志流，删除所述旧日志流，以及将所述新日志流重命名成所述旧日志流的名称。
15.如权利要求12所述的一个或多个计算机存储介质，其特征在于，从所述分区构建所述子分区包括通过在没有昂贵的数据复制的情况下原子地硬链接来自所述分区的流的范围来高效地构造所述子分区的流。
全文摘要
提供了用于可缩放的结构化存储系统的分区管理。该存储系统提供有一个或多个表来表示的存储，这些表中的每一个包括表示数据实体的行。表被分成多个分区，每一分区包括连续范围的行。各分区由表服务器提供并且由表主机来管理。跟踪表服务器和分区的负载分布信息，并且表主机基于该负载分布信息来确定要拆分和/或归并各分区。
文档编号G06F15/16GK102197372SQ200980142662
公开日2011年9月21日 申请日期2009年10月23日 优先权日2008年10月24日
发明者A·E·绍尔斯沃德, B·G·卡尔德, D·巴德瓦杰, J·王, N·尼拉康特恩, S·斯里瓦斯塔瓦 申请人:微软公司
已分区的、可缩放的、并且可用的结构化存储中的分区管理
背景技术：
包括服务器农场、web服务等的分布式系统对于提供巨大量的计算和存储资源已变得日益常见。例如，分布式存储系统被用来为各种应用存储并检索巨大量的数据。在一些情况下，存储系统利用结构化存储来更高效地存储、检索以及查询数据。结构化存储系统可以跨遍及网络的多个节点来存储数据。随着提供这样的存储所需的计算资源量的增加， 这样的存储系统可以通过添加附加计算设备而“扩展”，从而提供可以按需添加附加资源的灵活的拓扑结构。因此，结构化存储系统可例如从千万亿字节的存储数据扩展成百万万亿字节的存储数据。结果，管理这样的结构化存储系统内的数据以使得数据总是可供访问并且持久以防止数据丢失通常是复杂的。概述提供本概述是为了以简化的形式介绍将在以下详细描述中进一步描述的一些概念。本发明内容不旨在标识所要求保护的主题的关键特征或本质特征，也不旨在用于帮助确定所要求保护的主题的范围。本发明的各实施例涉及结构化数据存储系统中的分区管理。在该存储中，结构化数据被划分成可由不同的服务器提供的多个分区。使用分区图来跟踪这些分区的所在之处。更具体地，使用分区图，客户机可以找出哪一服务器正在提供特定数据段。跟踪各分区的详细负载信息。各分区可以在服务器之间移动，以跨各服务器来达到负载平衡。在一些实施例中，为了达到更好的负载平衡，标识具有高负载的分区来进行拆分。确定拆分该分区的位置，并且将该分区拆分以创建子分区，在一些实施例中，这些子分区可被卸载到另一服务器。更新分区图以反映该分区已被拆分成各子分区。在一些实施例中，标识两个或更多个分区来进行归并。归并这些分区并更新分区图来反映经归并的分区。结构化存储是在流系统的顶层构建的，该流系统呈现只可添加(append-only)的文件系统界面。流类似于只可添加的文件。每一分区具有与它相关联的一组流。该分区的所有持久状态都保持在与它相关联的这一组流中。在该组流中，存在该分区的元数据流，它包含到该分区的所有其他流的指针以及该分区的必要信息，该必要信息诸如是该分区中包括的所有行的分区键范围。附图简述下面参考附图详细描述本发明，附图中
图1是适用于实现本发明的各实施例的示例性计算环境的框图；图2描绘根据本发明的一实施例的表结构；图3是其中可以实现本发明的各实施例的示例性系统的框图；图4是根据本发明的一实施例的示出一个分区的框图；图5是根据本发明的一实施例的示出用于拆分一分区的方法的流程图；图6描绘根据本发明的一实施例的被拆分成两个子分区的父分区的示例；图7是根据本发明的另一实施例的示出用于拆分一分区的方法的流程图；图8是根据本发明的一实施例的示出用于将各分区归并成一个经归并的分区的方法的流程图；图9是根据本发明的一实施例的示出用于恢复破坏分区的方法的流程图；以及图10是根据本发明的一实施例的示出用于分区版本化和升级的方法的流程图。详细描述此处用细节来描述本发明的主题以满足法定要求。然而，该描述本身并非旨在限制本专利的范围。相反，发明人设想所要求保护的主题还可结合其他当前或未来技术按照其他方式来具体化，以包括不同的步骤或类似于本文中所描述的步骤的步骤组合。此外，尽管术语“步骤”和/或“框”可在此处用于指示所采用的方法的不同元素，但除非而且仅当明确描述了各个步骤的顺序，否则该术语不应被解释为意味着此处公开的各个步骤之中或之间的任何特定顺序。本发明的各实施例提供可缩放的、可用的、并且持久的结构化存储。该结构化存储由多个表来表示，这些表中的每一个包括多个行，每一行表示一数据实体。表被分成多个分区，每一分区包括来自该表的一定范围的行。各分区存储在表服务器上并且被使用表主机来进行管理。在一些实施例中，各分区是出于负载分布的目的来被拆分的。跟踪各表服务器和各分区的负载分布信息。基于该负载分布信息，表主机可以决定对各分区进行负载平衡，并将各分区重新分配给不同的节点以分布负载。另外，对于一些分区，表主机可以决定将拆分一分区以分布当前负载。表主机确定拆分比率，并查询提供该分区的表服务器以寻找用于定位该拆分的键信息。基于从表服务器接收到的键信息，表主机指令该表服务器拆分该分区。在接收到拆分请求后，表服务器卸载目标分区，创建子分区，并开始提供该子分区。在一些实施例中，子分区被分配给另一表服务器。更新分区图以反映提供子分区的表服务器。在一些实施例中，各分区被归并。同样，跟踪各表服务器和各分区的负载分布信息。基于该负载分布信息，标识两个或更多个分区来进行归并。提供这些分区的表服务器被指令停止提供这些分区。这些分区被归并，并且被加载到开始提供经归并的分区的表服务器，更新分区图以反映提供经归并的分区的表服务器。因此，在一个方面，本发明的一实施例针对由结构化存储系统内的一个或多个计算设备实现的方法，其中结构化存储由一个或多个表来表示，每一个表包括多个行，每一行表示由该结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分该多个行，每一分区包括来自该表内的多个行中的一定范围的行，其中该多个分区存储在多个表服务器上，并且其中表主机控制对多个表服务器的分区分配。该方法用于将一分区拆分成各子分区，并且包括基于分区的负载信息来标识要拆分的分区，其中该负载信息包括指定该分区的两个或更多个部分中的每一个部分上的负载的信息。该方法还包括由表主机基于该分区的两个或更多个部分中的每一个部分上的负载来确定用于拆分该分区的拆分比率。该方法还包括查询表服务器以寻找指示该分区内的与该分区比率相对应的实际位置的键信息。该方法还包括在表主机处从表服务器接收键信息，该键信息指示该分区内的与拆分比率相对应的实际位置。该方法还包括从表主机向表服务器发送拆分请求，该拆分请求指示基于键信息来拆分该分区。该方法还包括在与该键信息相对应的位置处拆分该分区，以创建子分区。该方法还包括通知表主机拆分已完成。该方法还包括基于被拆分成子分区的分区来更新分区图，分区图存储多个分区与提供该多个分区的多个表服务器之间的映射。在本发明的另一实施例中，一个方面针对存储用于执行一种方法的计算机可使用指令的一个或多个计算机存储介质，该方法用于管理由一个或多个表来表示的结构化存储系统，每一个表包括多个行，每一行表示由该结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分该多个行，每一分区包括来自该表内的多个行中的一定范围的行，其中该多个分区存储在多个表服务器上，并且其中表主机控制对多个表服务器的分区分配。该方法用于将该表的至少两个分区归并成经归并的分区，并且包括跟踪多个表服务器上的多个分区的负载信息。该方法还包括由表主机基于该负载信息来标识要归并的至少两个分区。该方法还包括由表主机创建该经归并的分区的元数据流。该方法还包括将该至少两个分区从提供该至少两个分区的至少一个表服务器上卸载。 该方法还包括由表主机将该经归并的分区分配给来自该多个表服务器的所选表服务器。该方法还包括在所选表服务器处加载并提供该经归并的分区。本发明的又一实施例针对存储用于执行一种方法的计算机可使用指令的一个或多个计算机存储介质，该方法用于管理由一个或多个表来表示的结构化存储系统，每一个表包括多个行，每一行表示由该结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分该多个行，每一分区包括来自该表内的多个行中的一定范围的行，其中该多个分区存储在多个表服务器上，并且其中表主机控制对多个表服务器的分区分配。该方法用于将该表的一分区拆分成至少两个子分区，并且包括跟踪多个表服务器上的多个分区的负载信息。该方法还包括由表主机基于该负载信息来标识要拆分的分区，其中该分区的负载信息标识该分区的不同部分上的不同负载。该方法还包括在表主机处确定用于拆分该分区的拆分比率，其中该拆分比率是基于负载信息来指定的并且表示该分区中的点，在该点处该分区的第一部分包括第一负载量并且该分区的第二部分包括第二负载量。该方法还包括从表主机向表服务器发送请求，该对键信息的请求标识该分区中的与拆分比率相对应的实际位置。该方法还包括由表服务器确定标识该分区中的与拆分比率相对应的实际位置的键信息，并将该键信息从表服务器传递给表主机。该方法还包括在表主机处构造各子分区中的每一个子分区的元数据流。该方法还包括从表主机向表服务器发送拆分请求，并且在表服务器处构建来自该分区的子分区。该方法还包括在该表服务器处停止提供该分区，并且在该表服务器处加载并提供子分区。该方法还包括从表服务器向表主机发送拆分完成通知。该方法还包括基于被拆分成子分区的分区来更新分区图，分区图存储多个分区与提供该多个分区的多个表服务器之间的映射。在简要描述了本发明各实施例的概览之后，以下描述其中可实现本发明的各实施例的示例性操作环境，以便为本发明各方面提供通用上下文。首先具体参考图1，示出了用于实现本发明的各实施例的示例性操作环境，并将其概括地指定为计算设备100。计算设备 100只是合适的计算环境的一个示例，并且不旨在对本发明的使用范围或功能提出任何限制。也不应该将计算设备100解释为对所示出的任一组件或其组合有任何依赖性或要求。本发明可以在由计算机或诸如个人数据助理或其他手持式设备之类的其他机器执行的计算机代码或机器可使用指令(包括诸如程序模块之类的计算机可执行指令)的一般上下文中描述。一般而言，包括例程、程序、对象、组件、数据结构等的程序模块指的是执行特定任务或实现特定抽象数据类型的代码。本发明可以在各种系统配置中实施，这些系统配置包括手持式设备、消费电子产品、通用计算机、专用计算设备等等。本发明也可以在其中任务由通过通信网络链接的远程处理设备执行的分布式计算环境中实施。参考图1，计算设备100包括直接或间接耦合以下设备的总线110 存储器112、一个或多个处理器114、一个或多个呈现组件116、输入/输出端口 118、输入/输出组件120、 和说明性电源122。总线110可表示一条或多条总线(诸如地址总线、数据总线、或其组合)。虽然为了清楚起见利用线条示出了图1的各框，但是实际上，各组件的轮廓并不是那样清楚，并且比喻性地来说，线条更精确地将是灰色的和模糊的。例如，可以将诸如显示设备的呈现组件认为是I/O组件。而且，处理器具有存储器。可以认识到，这是本领域的特性， 并且重申，图1的图示只是例示可结合本发明的一个或多个实施例来使用的示例性计算设备。诸如“工作站”、“服务器”、“膝上型计算机”、“手持式设备”等分类之间没有区别，它们全部都被认为是在图1的范围之内的并且被称为“计算设备”。计算设备100通常包括各种计算机可读介质。计算机可读介质可以是可由计算设备100访问的任何可用介质，而且包含易失性和非易失性介质、可移动和不可移动介质。作为示例而非限制，计算机可读介质可以包括计算机存储介质和通信介质。计算机存储介质包括以用于存储诸如计算机可读指令、数据结构、程序模块或其他数据的信息的任何方法和技术实现的易失性和非易失性、可移动和不可移动介质。计算机存储介质包括但不限于， RAM、ROM、EEPR0M、闪存或其他存储器技术、CD-ROM、数字多功能盘(DVD)或其他光学存储、 磁带盒、磁带、磁盘存储或其他磁存储设备、或能用于存储所需信息且可以由计算设备100 访问的任何其他介质。通信介质通常以诸如载波或其他传输机制的已调制数据信号来体现计算机可读指令、数据结构、程序模块或其他数据，并包括任意信息传送介质。术语“已调制数据信号”指的是其一个或多个特征以在信号中编码信息的方式被设定或更改的信号。 作为示例而非限制，通信介质包括有线介质，如有线网络或直接线连接，以及诸如声学、RF、 红外及其他无线介质之类的无线介质。上述的任意组合也应包含在计算机可读介质的范围内。存储器112包括易失性和/或非易失性存储器形式的计算机存储介质。存储器可以是可移动的、不可移动的、或其组合。示例性硬件设备包括固态存储器、硬盘驱动器、光盘驱动器等。计算设备100包括从诸如存储器112或I/O组件120等各种实体读取数据的一个或多个处理器。呈现组件116向用户或其他设备呈现数据指示。示例性呈现组件包括显示设备、扬声器、打印组件、振动组件等等。I/O端口 118允许计算设备100在逻辑上耦合至包括I/O组件120的其他设备，其中某些设备可以是内置的。说明性组件包括麦克风、操纵杆、游戏垫、圆盘式卫星天线、扫描仪、打印机、无线设备、网络设备等等。高级数据模型根据本发明的各实施例，结构化存储由表来表示，其中表包含行集合。作为说明， 图2描绘根据本发明的一个实施例的表200的一部分。表200中的每一行(如行20 表示数据实体并包含在一系列列中标识的一组属性，该组属性包括属性204、206、以及208 (为简化和清楚起见，列208的数据值为空)。属性/列可以是例如名称、类型化值对、或名称到多个类型化值的映射。行和/或每一单独的属性可以版本化或可以不版本化。表本身可具有固定模式，其中该表中的每一行具有相同属性和相同类型，或可以不强制模式，其中每一行存储了不同的一组属性和类型。对结构化存储执行的标准操作集合包括插入、更新和删除表、行以及属性的能力。 另外，提供了对表、行以及属性进行扫描和查询以找出与该指定扫描/查询相匹配的一组表、行或属性的功能。分区划分(partitioning)表能长到数十亿或数万亿行以及万亿字节/千万亿字节的数据，并且表可能必须跨数千服务器分布以处理对表的不同部分的流量/负载。为了使结构化存储达到这一可缩放性，各实施例采用分区划分来将各表和各行分布在各服务器上。分区划分将表中的各行编组/断开成各分区，并且随后这些分区被分配给不同的服务器并从这些不同的服务器提供(提供对这些分区的读和写访问)。为了使表变得可缩放，表具有被称为属性的组成分区键的一个到多个键。例如，参考图2的表200，表200的第一列204包括每一行/实体的分区键。如果给定表存在超过一个分区键属性/列，则组合在一起的属性/列形成该表的合成分区键。一个行的分区键的值被用来标识该实体/行所属于的分区。具有相同分区键值的行被认为编组到同一分区中。除分区键之外，每一行具有零个到多个附加行键属性/列。例如，再次参考图2的表200，表200的第二列206包括每一行/实体的行键。行键表示分区内的行的唯一 ID。组合了行键的分区键表示该行/实体在该表中的主键(唯一 ID)。主键表示该表中的分区的主排序次序。如果没有行键，则分区键是主键并且必须唯一地标识该表中的每一实体。虽然下文的描述按照单个分区键和单个行键讨论了本发明的各实施例，但在使用多个分区键和/或行键时，同样的原理也适用。分区键被用来将具有相同分区键“值”的各行编组在一起，而行键表示行在分区内的唯一 ID。基于分区键值将表的各行断开在本文中被称为对表进行分区划分。这将表的各行编组/断开成各分区。分区是具有同一分区键值的行集合，所以具有同一分区键的所有这些行将总是被存储在同一分区中。因此，具有同一分区键值的两个行处于同一分区中， 并且不被拆分到跨两个分区。另外，在一些实施例中，分区的定义被扩展，以允许具有不同分区键值的多个行被编组在同一分区中，只要它们的键值在分区键名字空间中显得邻近即可。作为示例，参考图2的表200，示出了四个分区，第一分区(Pl 210)、第二分区(P2 212)、 第三分区(P3 214)以及第四分区(P4 216)。如图2所示，一些分区包括具有单个分区键值的各行，而其他分区包括具有多个分区键值的各行。作为前者的示例，Pl 210包括具有分区键值1的所有行，并且P2 212包括具有分区键值2的所有行。作为后者的示例，P3 214 包括具有分区键值3、4、或5的所有行，并且P4 216包括具有分区键值6或7的所有行。分区划分的优点包括但不限于(1)通过将表断开成各分区并基于数据的访问模式和流量需求以将这些分区分布在各服务器上来缩放对表的访问的能力，以及O)同一分区中的各行被编组在一起并且从同一表服务器访问，这允许在操作的作用域处于分区内时更高效地进行查询、扫描、以及高速缓存。对分区进行扫描更加高效，因为由于它是从该分区的单个表服务器访问，因此最多只需扫描各分区内的那些行，而非在查询时在没有指定分区键的情况下可能必须遍历整个表。高级体系结构
根据本发明的各实施例，一组服务器(本文中被称为“表服务器”)存储结构化存储系统并提供对它的访问。另外，一组服务器(本文中被称为“表主机”)管理这些表服务器。“表客户机”提供对该结构化存储系统的应用程序访问。现在参考图3，提供了示出根据本发明一实施例的系统300的高级体系结构的框图。应当理解，此处所描述的这一和其他安排仅作为示例来阐明。除了所示的安排和元素之外，或作为其替代，可使用其他安排和元素(例如，机器、接口、功能、次序、以及功能组等)， 并且可完全省略某些元素。此外，此处所描述的许多元素是可以实现为分立或分布式组件或结合其他组件来实现的、以及以任何合适的组合和在任何合适的位置的功能实体。此处被描述为由一个或多个实体执行的各种功能可由硬件、固件和/或软件来执行。例如，各种功能可由执行存储在存储器中的指令的处理器来执行。虽然未示出其他组件，但系统300 —般包括表主机302，表服务器304、306、308、 310，以及表客户机312。每一个都可以驻留在任何类型的计算设备上，诸如例如参考图1描述的计算设备100。系统300的组件可以经由网络彼此通信，网络包括但不限于一个或多个局域网(LAN)和/或广域网(WAN)。应当理解，虽然图3中只示出了单个表主机、四个表服务器、以及单个表客户机，但在本发明的各实施例的范围内，在系统300中可以使用任何数量的表主机、表服务器、表客户机。表主机302负责(1)将各分区分配给表服务器304、306、308、310 ； (2)快速确定一分区何时由于故障而没有被提供并将该分区重新分配给不同的表服务器；C3)控制各分区在表服务器304、306、308、310之间的负载平衡；以及(4)监视表服务器304、306、308、 310的健康。表服务器304、306、308、310中的每一个负责提供对表主机分配给自己的分区的读和写访问。表服务器304、306、308、310中的每一个可以主存零个到多个分区。在图3的示例中，TSl 304(表服务器1 304)主存分区Pl和P4，TS2 306主存分区P2和P7，TS3 308 主存分区P3，以及TS4 310主存分区P5和P6。表客户机312被链接到应用程序，并且被用来向由表服务器304、306、308、310维护的分区发出命令。表客户机312使用分区图来确定提供该分区的表服务器，并且它将命令发送到该表服务器。表客户机312还从表服务器接收回结果并将它们传递给应用程序。 分区图是特殊的表，它存储各分区与提供它们的表服务器之间的映射，并且由表主机302 来维护。如图4所表示的，在内部，在表服务器处提供的分区400包括三个主要部分更新日志402、一个到多个存储器表404、以及零个到多个文件表406。更新日志402跟踪对持久存储中的分区的新近变更。存储器表404是更新日志中的新近(增量)更新的存储器内版本。这些是对分区400的新近增量变更。在存储器表404变得足够大或其中具有了足够的变更的情况下，存储器表404被检查点记录(checkpoint)到持久存储在存储中的文件表 406。在这发生时，更新日志402中的直至被检查点记录的存储器表404的所有请求可以从更新日志402中移除。如上所述，分区具有存储其持久状态的一组流。更新日志402存储在这些流之一中，该流被称为更新日志流。所有文件表406被存储在这些流之一中，这条流被称为文件表流。在表服务器加载一分区时，该表服务器重放更新日志中的自最新近检查点以来的所有请求，以将存储器表重构回到正好在该分区被最后卸载之前的状态。在访问表服务器处的分区时，该表服务器首先查看存储器表中是否有匹配的行， 以查看所有新近的变更，并且如果没有匹配，则在它的页高速缓存和文件表中查找该数据。一分区可存在多个存储器表和多个文件表。可存在多个存储器表，因为在一个存储器表变满时，它需要被检查点记录到文件表。在这发生时，当前存储器表在被检查点记录时被设成只读的，并为该分区创建新存储器表以供写入。因此，分区总是具有用于新近(增量)更新的一个存储器表，并且它可以具有被懒散地进行检查点记录的一个或多个存储器表。一旦存储器表被检查点记录到文件表，它可被删除或被垃圾收集。由于对一分区做了所有检查点记录，因此该分区可存在多个文件表检查点。这意味着在需要从文件表中读取数据时，可能需要查看多个文件表，并且是以从最新近到最老的次序来查看它们。这是因为所写的最新近文件表包含该分区的最新近变更。在对一分区进行检查点记录了足够的文件表时，表服务器懒散地将这些文件表压缩/归并在一起成为新的经归并的文件表，以减少为了找出一分区的被查找的数据而必须被搜索的文件表的数量。可缩放的、可用的并且持久的结构化存储本发明的各实施例采用分区划分、负载平衡、以及扼流来提供可缩放的结构化存储系统。可缩放性通过以下来提供(1)将表拆分成各分区并将这些分区分布在数据中心中的多个服务器上；( 使用负载平衡来将分区从高负载的表服务器移动到较轻负载的表服务器；以及C3)进行扼流来丢弃对具有发送到它的过多流量的分区的请求或丢弃对具有被发送到它的过多流量的表服务器的请求。可缩放性是通过基于分区的不同部分的负载来将表自动地拆分成各分区并随后跨各个表服务器进行负载平衡来提供的。负载平衡使系统动态地适应工作负载，从而将负载分布在大量机器上，从而通过高效地利用所有物理资源而达到更好的可缩放性。另外，进行扼流保护该系统免于高负载，从而使该系统保持在高效/优化的制度中操作。表主机通过标识未被提供的分区、向它们分配不同的表服务器、以及更新分区图来提供可用性，这允许表客户机找到分区的新位置来对该分区进行访问。在节点/网络故障的情况下对分区进行快速重新分配保持了所有分区可用并且产生了高系统可用性。持久性是通过将分区数据的全部存储在复制的流层中来提供的。流层提供如接口之类的文件系统，用于向流(类似于文件)写入数据并从流读取数据，并且流层提供用于确保数据被复制的完整功能，总是在该系统中的各表服务器中的任一个上持久存储并可从中获得。因此，分区信息被存储在流层中，该分区信息包括分区图、更新日志以及文件表。高效的流层操作流层提供将流的一个区域高效地硬链接到另一条流的能力。流层处的每一条流包括被称为范围的数据块列表。该流中的数据事实上存储在这些范围内部。流是范围的有序列表。给定范围可以驻留在多条流中，或甚至在同一条流的有序范围列表中出现多次。流层提供接口，用于通过将驻留在一条流中的一组现有范围进行链接来合成另一条流。在这一过程中不涉及真实的数据复制，所以它是非常高效的。流层维护每一范围的引用计数。一旦范围没有了指向它的流，则流层将从该系统中对这一范围进行垃圾收集/删除。流层还支持在一个原子事务中具有多个流级操作的能力，如对流进行创建、删除、重命名、以及将范围硬链接到流。结构存储系统大量使用这些特征来高效地对一分区的各条流的过时部分进行垃圾收集。示例是一旦作出了一分区的检查点，更新日志中的在该检查点之前的所有消息不再被使用。这些特征被用来通过原子地创建与更新日志流相同名称的新流、将来自原始流的仍然使用的范围硬链接到该新流、并删除原始流，来高效地将更新日志截短。所有这些是在一个原子事务中完成的。这极大地简化了故障处理逻辑。类似方案也被用于分区的其他流，如文件表流和元数据流。结构化存储系统还大量使用这些特征来高效地实现分区的拆分和归并，如在稍后章节中描述的。更具体地，这些特征被用来将来自原始分区的数据高效地引用到从拆分/ 归并创建的子分区，而不必物理地复制或移动任何位。对分区进行拆分、归并以及负载平衡本发明的一些实施例在存储系统内的各表服务器之间对负载分布进行平衡。一般而言，表服务器跟踪每一分区的负载，并且向表主机周期性地报告这一信息。表主机通过在表服务器之间移动分区来作出负载平衡决定。这通过将目标分区从原始表服务器卸载并将该分区分配给其他表服务器来实现。作为优化，本发明的一些实施例可以使表主机在卸载分区之前或之时向表服务器发送“准备卸载请求”。在接收到这一请求后，表服务器将对分区进行检查点检查，以减少在再次加载该分区时需要重放的日志的量。提供这一点以满足用于提供该分区的可用性SLA。在单个分区具有相对较高负载的情况下，将该分区拆分成两个或更多个分区是合乎需要的，并且只有在该分区包含超过一个分区键值的情况下这才是可能的。因此，子分区中的一个或多个可被卸载到不同的表服务器来达到负载平衡。对于负载分布跟踪，每一表服务器使用采样机制来跟踪每一分区内的细粒度的负载信息而不消费大量存储器。为了跟踪负载信息，分区被划分成多个分区键范围(在此称为“桶”)，并且跟踪与每一个桶相对应的负载。更具体地，表服务器在概率上对落入这些桶内的请求进行采样，并跟踪这些桶的负载分布。例如，参考图2的表200内的分区P3 214， 出于负载跟踪目的，该分区可以被划分成两个桶。第一个桶将包括具有分区键值3的行，第二个桶将包括具有分区键值4和分区键值5的行。在各实施例中，桶边界必须总是处于分区键值上。即，具有同一分区键值的行将总是处于同一个桶中。例如，出于负载跟踪以及拆分的目的，具有分区键值3的行可被拆分成两个桶。在一些实施例中，基于所收集的流量样本，桶边界可以动态地调整以更准确地跟踪跨一分区内的各键的流量分布。即，如果两个现有桶与其他桶相比不具有很大负载，则它们将被归并成单个桶；相反，如果一个桶包含比所有其他桶大得多的负载，则在可能的情况下，该桶可被拆分成两个。例如，在先前示例中，如果第二个桶与第一个桶相比包含过多负载，则它可被拆分成两个较小的桶，其中之一包含具有分区键值4的行并且其中的另一个包含具有分区键值5的行。此外，如果包含分区键值3的第一个桶具有很少负载，则它可与包含分区键值4的桶归并在一起。对桶大小的这一监视和调整全部是在进行中动态地完成的。除用来跟踪跨一个分区内的各分区键的负载分布的桶水平采样方案之外，表服务器还跟踪整个分区上的工作负载的总量。后者被传递给表主机。因此，在需要基于负载来拆分一分区时，相当准确的负载分布信息对表服务器和表主机确定应当在何处拆分该分区而言都是可用的。现在参考图5，提供了示出根据本发明的一实施例的用于拆分一分区的方法500 的流程图。在图5的实施例中，父分区Pl被拆分成两个子分区ΡΓ (被修改成只包括各行的子集的原始分区)和P2(包括其余各行的新分区)。虽然图5讨论了将一分区拆分成两个子分区，但应当理解，根据本发明的各实施例，一分区可被拆分成超过两个子分区。一开始，如在框502所示，跟踪表服务器、分区、和/或分区部分(即，“桶”)的负载分布信息。如上所述，通过在分区部分级跟踪细粒度的负载信息，可以作出关于在何处拆分一分区的判定。负载信息由表服务器来跟踪并被周期性地提供给表主机。在当前实施例中，发送到表主机的负载信息包括每一分区的总负载和每一表服务器的负载。一些其他实施例可以向表主机提供所有这些负载跟踪信息，包括桶级信息。从表服务器向表主机提供关于一分区的附加信息、约束、以及提示，以帮助进行负载平衡和拆分决策。例如，基于桶信息的分布，表服务器可以将一分区标记为带有某一严重性程度的“难以拆分”，其中“高”意味着表主机不应请求拆分该分区，因为表服务器不会拆分该分区，其中“中”意味着在某些情况下表服务器可选择不拆分该分区并且表主机可以不顾这一决定，并且其中“低”意味着表服务器将监听并采取表主机的指导。表主机使用该负载信息来作出负载分布决定，包括是否拆分分区、是否归并各分区、和/或是否在表服务器之间移动各分区。在图5的当前实施例中，表主机基于负载分布信息确定要拆分一分区(Pl)，如在框504所示。在框506，表主机确定用于拆分该分区的拆分比率。拆分比率表示用于确定应当在其中拆分该分区的位置的负载比率。例如，表主机可以决定在30% /70%负载点处拆分一分区。换言之，该分区应在以下点处拆分该分区第一部分的负载是30%并且该分区其余部分的负载是70%。在框508，表主机向主存被标识来拆分的分区的表服务器发送请求。 具体而言，表主机请求指定与该分区中的拆分比率相对应的位置的键信息。响应于该请求， 表服务器基于拆分比率来标识用于拆分该分区的实际分区键位置，如在框510所示。该实际位置尝试与拆分比率所指定的负载分布相匹配，但实际负载分布可能不同。例如，表主机所请求的拆分比率可以是30% /70%负载分布，但可以提供的最接近的匹配是35% /65% 负载分布。在一些实施例中，用于拆分的实际位置是使用分区键信息来标识的。例如，如果图 2的分区P3 214要在分区键值3和4之间进行拆分，则标识该拆分的键信息可以是分区键值3和/或分区键值4。任何及所有这样的变型都被构想为落在本发明的各实施例的范围内。表服务器将拆分比率的键信息返回给表主机，如在框512所示。表主机构造作为子分区之一的新分区(P2)的流，如在框514所示。分区的所有持久状态都保持在该分区的“流”中。存在该分区的元数据流，它包含到该分区的所有其他流的指针以及该分区的必要信息，该必要信息诸如是该分区中包括的所有行的分区键范围。 在该步骤中，表主机负责使用对应于拆分比率的正确的分区键范围信息来创建新分区(P2) 的元数据流。另外，在框516，表主机将拆分请求发送到表服务器。该拆分请求可以在下一心跳中从表主机提供给表服务器。在一些实施例中，写下适当的主日志以处理故障。表主机在每一步骤完成之后记录该对应步骤，使得在主机故障的情况下，这些日志可被重放并且表主机可以从它停止的地方继续进行拆分。在接收到拆分请求之后，表服务器停止提供原始分区并卸载原始分区(Pl)，如在框518所示。表服务器还从该原始分区中构建两个子分区(ΡΓ和P2)，如在框520所示。 表服务器基于原始分区(Pl)中的信息来构造新分区(P2)的流(除了元数据流之外)。更具体地，使用底层流层的特征，属于P2的键范围的数据部分将从分区Pl高效地被复制/硬链接到分区P2的流。子分区ΡΓ是通过调整Pl的键范围来“创建”的。子分区ΡΓ使用与原始分区Pl相同的一组流。改变ΡΓ的元数据以调整到该减少的键范围。如在框522所示，表服务器加载这两个子分区(ΡΓ和P2)并开始提供这些分区。 另外，表服务器向表主机通知拆分已完成，如在框5M所示。这一通知可以在下一心跳中从表服务器提供给表主机。响应于来自表服务器的拆分完成通知，表主机更新分区图以反映新分区，如在框5 所示。此时，表主机可以认为拆分已完成。表主机向表服务器发送包括新创建的子分区(P》的新分配，使得它与分区图相匹配，如在框5 所示。在一些实施例中，在拆分了一分区之后，表主机可以确定将子分区从原始分区所处的表服务器移动到另一表服务器。这允许表主机将负载高效地分布在整个网络上。分区移动是通过将分区从一个表服务器卸载并随后将它分配给另一表服务器来实现的。在本发明的其他实施例中，以上参考图5描述的拆分协议的性能可以通过在框 518处卸载原始分区之前创建新子分区来改进。对本领域技术人员而言，上述方法500的其他变型也显而易见并且处于本发明各实施例的范围内。图6示出根据本发明的一实施例的对图2的P3 214进行拆分的示例。具体而言， 图6示出图3的表主机(TM) 302与TS3 308 (表服务器3 308)之间的用于执行P3 214的拆分的交互，其中P3 214驻留在TS3 308上。一开始，如在602所示，表主机302向TS3 308 发送查询键信息的请求以标识拆分P3 214的位置。该请求指定0.3拆分比率，指示表主机希望在接收到P3 214上的负载的30%的P3 214的一部分与接收到该负载的70%的剩余部分之间的位置处拆分P3 214。响应于来自表主机302的请求，TS3 308确定与表主机302所指定的拆分比率相对应的键信息。该键信息基于被表主机302指定为拆分比率的30% /70%负载分布来表示 P3 214的两部分之间的位置。在本示例中，TS3 308确定具有分区键值3的行上的负载大约具有负载的30%，而其余行上的负载大约具有负载的70%。如此，在本示例中，TS3 308 所确定的键信息是分区键值4。应当理解，在各实施例中，可以提供其他键信息来标识应当在其中拆分P3 214的位置。在606，TS3 214将键信息(即，分区键值4)传递给表主机302。在608，表主机 302构造新分区PN的流。另外，如在框610所示，表主机302将拆分请求发送到表主机。在本示例中，拆分请求指定子分区中的每一个的范围。具体而言，对于一个子分区P3’，拆分请求指定低分区键值3和高分区键值4，从而指示P3’包括具有分区键值3的行。对于另一子分区PN，拆分请求指示低分区键值4和高分区键值6，从而指示PN包括具有分区键值4的行以及具有分区键值5的行。在612，基于拆分请求，TS3停止提供原始分区P3 214。另外，TS3 308将P3拆分成P3，和PN，如在614所示，并开始提供P3，和PN，如在616所示。TS3 308随后向表主机 302发送拆分完成通知，如在618所示。在620，表主机302更新分区图以反映子分区。
现在转向图7，提供了示出根据本发明的另一实施例的用于拆分一分区的方法 700的流程图。在图7的实施例中，父分区Pl被拆分成两个新子分区P2和P3，其中每一子分区包括来自父分区Pl的各行的一部分。虽然图7讨论了将一分区拆分成两个子分区，但应当理解，根据本发明的各实施例，一分区可被拆分成超过两个子分区。与图5的方法500类似，一开始跟踪负载分布信息，如在框702所示。该负载分布信息允许表主机作出负载分布决定，包括是否拆分一分区、是否归并各分区、和/或是否在表服务器之间移动各分区。在图7的当前实施例中，表主机基于负载分布信息确定要拆分一分区(Pl)，如在框704所示。在框706，表主机确定用于拆分该分区的拆分比率。如上所述，拆分比率表示用于确定应当在其中拆分该分区的位置的负载比率。例如，表主机可以决定在30% /70%负载点处拆分一分区。在框708，表主机向主存被标识来拆分的分区的表服务器发送请求。具体而言，表主机请求指定与该分区中的拆分比率相对应的位置的键信息。响应于该请求，表服务器基于拆分比率来标识用于拆分该分区的实际位置，如在框710所示。表服务器将拆分比率的键信息返回给表主机，如在框712所示。表主机构造新分区(P2和P3)的元数据流，如在框714所示。在一些实施例中，写下适当的主日志以处理故障。表主机在每一步骤完成之后记录该对应步骤，使得在主机故障的情况下，这些日志可被重放并且表主机可以从它停止的地方继续进行拆分。另外，在框 716，表主机将拆分请求发送到表服务器。该拆分请求可以在下一心跳中从表主机提供给表服务器。响应于该拆分请求，表服务器从原始分区(Pl)中构建两个子分区(P2和P3)，如在框718所示。表服务器基于原始分区(Pl)来构造新分区(P2和P3)的流(除了元数据流之外)。更具体地，使用底层流层的特征，属于P2的键范围的数据部分将从分区Pl高效地复制/硬链接到分区P2的流。类似地，使用底层流层的相同特征，属于P3的键范围的数据部分将从分区Pl高效地复制/硬链接到分区P3的流。表服务器停止提供原始分区并卸载原始分区(Pl)，如在框720所示。另外，如在框722所示，表服务器加载这两个子分区(P2和P； )并开始提供这些分区。表服务器向表主机通知拆分已完成，如在框7M所示。这一通知可以在下一心跳中从表服务器提供给表主机。响应于来自表服务器的拆分完成通知，表主机更新分区图以反映新分区，如在框726 所示。此时，表主机可以认为拆分已完成。表主机向表服务器发送包括新创建的子分区(P2 和P； )的新分配，使得它与分区图相匹配，如在框7 所示。在一些情况下，表主机可以基于例如负载分布信息来确定将两个或更多个分区归并成单个分区。在一实施例中，归并是在两个相邻分区(即，在表中的行序列中相邻)具有相对低的负载时执行的。将各分区归并成单个分区有益于减少系统中分区的数量。因此，图8提供示出根据本发明的一实施例的用于归并各分区的方法800的流程图。如在框802所示，一开始跟踪负载分布信息。基于该负载分布信息，表主机确定两个分区(Pl和P2)应被归并成新分区(P3)，如在框804所示。在各实施例中，只有形成连续且未脱节的分区键范围的分区才能被归并。在表主机决定归并两个分区时，表主机向提供这两个分区的(诸)表服务器发送 (诸)‘准备归并’消息，如在框806所示。在一些情况下，这两分区可驻留在单个表服务器上，而在其他情况下，这些分区可以驻留在不同的表服务器上。‘准备归并’消息向表服务器给出了在归并之前对分区进行压缩以减少经归并的分区的加载时间的机会。在框808，表主机创建经归并的分区(P3)的元数据流，并且在框810，将两个父分区$1和1^)从这些父分区所处的(诸)表服务器上卸载。表主机随后更新分区图(原子地移除旧分区条目，并插入新分区条目)，如在框812所示。从表主机的观点来看，归并事务在此时完成，因为在表主机故障的情况下，新归并的分区将在引导期间在持久存储的分区图中找到。表主机将经归并的分区(P3)分配给表服务器，如在框814所示。向其分配经归并的分区的表服务器可以是系统中的任何表服务器。例如，所分配的表服务器可以是父分区之一或两者所处的表服务器或可以是系统中的不同的表服务器。在分配之后，表服务器加载经归并的分区，如在框816所示。从经归并的分区的元数据流中，表服务器获知这是经归并的分区，并且它通过使用来自底层流层的特征来高效地复制/硬链接来自父分区的数据来从父分区构造该经归并的分区的流。在构造完成之后，表服务器将这一事件记录在经归并的分区的元数据流中(以便下一次加载这一分区时，这些流将不会被再次构造)，并删除父分区的流。从破坏的分区状态恢复持久的结构化存储系统应当能够从系统状态的隐错中恢复。为了实现这一能力， 本发明的一实施例中的结构化存储系统是构建在只可添加的存储上的，并且将所有已删除数据保留到被认为足以发现系统中的任何错误的最小长度的时间。现在参考图9，提供了示出根据本发明的一实施例的用于将一分区从破坏的分区状态中恢复的方法900的流程图。最初，如在框902所示，标识破坏的分区。如果分区被破坏并且不能被提供，则发出警报，从而将该分区标记为未被提供。这可造成对该分区中的数据的可用性的临时丢失。如在框904所示，将破坏的分区恢复到一致的分区状态。系统可以从下述两项中任选其一 (a)修复该分区，因为对该分区的所有先前改变已被存储在只可添加的存储中， 这将在不丢失任何数据的情况下恢复该分区；或(b)将该分区回退到先前数据段，这可能造成在回退到的时间与故障的时间之间发生的改变的丢失。一旦修复了分区，则该分区可再次用来被提供，以供读出和写入结构化数据。在分区回退期间，该系统找出仍然处于有效状态的最新近的检查点，并使用该检查点连同对应的日志(如果它们仍然存在)来重建分区状态。在一些情况下，在分区回退期间，该分区的当前元数据和数据内容不足以恢复分区状态。在这些情况下，该系统使用来自其他相关分区的数据，包括在涉及目标分区的最新近拆分或归并期间的该目标分区的父分区。更具体地，该系统通过归并来自父分区和目标分区的最新近的有效检查点的状态来重构分区的状态。在恢复或重建了所有分区之后，修订分区图来匹配经重构系统中的所有分区的键范围，如在框906所示。这将系统带回到全局一致的状态。分区版本化和升级在执行表服务器代码的升级时，一次只对表服务器的一个子集执行该升级。如此， 表服务器被分成N个升级域，并且可以一次升级一个升级域。
参考图10，提供了示出根据本发明的一实施例的用于在升级期间进行分区版本化的方法1000的流程图。如在框1002所示，在升级过程期间，分区可以从接下来要被升级的目标升级域内的表服务器移出。将新表服务器代码版本部署到该目标升级域内的表服务器，如在框1004所示。在升级过程期间，可将分区分配给具有新表服务器代码版本的表服务器，并且开始用可能新的数据格式来修改该分区，如在框1006所示。在这一修改之后，分区可只由较新升级的表服务器来提供，并且可不由较老版本表服务器来提供。如此，一旦版本N的表服务器提供了一分区，则该系统确保分区只由版本N或更加新的版本(或其他兼容的表服务器版本)的表服务器来提供，如在框1008所示。在本发明的各实施例的范围内，这可以用多种不同方式来实现。例如，在一个实施例中，跟踪每一分区、表服务器和表主机的版本号。在升级发生时，如果提供该分区的表服务器是较高版本号，则该分区采用该版本号。自此时起，该分区可以只由该版本或更高版本的表服务器来提供。在另一实施例中，每一表服务器一经升级，该表服务器就与表主机进行通信以指示它的版本。表主机跟踪最新表服务器版本，并且待分配的分区可只被分配给具有最新版本(或其他兼容版本)的表服务器。在又一实施例中，分区版本与分区元数据一起持久存储。表服务器将分配给它们的分区的版本通知给表主机。表服务器还向表主机报告它们自己的版本号。表主机从而保持跟踪分区版本以及表服务器版本。以此方式，表主机确保分区可被分配给兼容版本的表服务器。结论参考各具体实施例描述了本发明，各具体实施例在所有方面都旨在是说明性的而非限制性的。在不偏离本发明范围的情况下，各替换实施例对于本发明所属领域的技术人员将变得显而易见。从前面的描述可以看出，本发明很好地适用于实现上文所阐述的所有目的和目标，并且具有对于该系统和方法是显而易见且固有的其他优点。也可理解特定的特征和子组合是有用的，并且可以加以利用而无需参考其他特征和子组合。这由权利要求所构想的， 并在权利要求的范围内。
权利要求
1.一种由结构化存储系统内的一个或多个计算设备实现的方法，其中结构化存储由一个或多个表来表示，每一个表包括多个行，每一行表示由所述结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在所述多个分区之间划分所述多个行，每一分区包括来自所述表内的多个行中的一定范围的行，其中所述多个分区存储在多个表服务器上，并且其中表主机控制对所述多个表服务器的分区分配，所述方法用于将一分区拆分成各子分区，并且包括基于分区的负载信息来标识(504)要拆分的分区，其中所述负载信息包括指定该分区中的两个或更多个部分中的每一个部分上的负载的信息；由所述表主机基于所述分区的两个或更多个部分中的每一个部分上的负载来确定 (506)用于拆分所述分区的拆分比率；查询(508)所述表服务器以寻找指示所述分区内的与所述分区比率相对应的实际位置的键信息；在所述表主机处从所述表服务器接收(510)键信息，所述键信息指示所述分区内的与所述拆分比率相对应的实际位置；从所述表主机向所述表服务器发送(516)拆分请求，所述拆分请求指示基于所述键信息来拆分所述分区；在与所述键信息相对应的位置处拆分(518、520、52幻所述分区以创建所述子分区；向所述表主机通知(524)拆分已完成；以及基于被拆分成所述子分区的分区来更新(526)分区图，所述分区图存储所述多个分区与提供所述多个分区的多个表服务器之间的映射。
2.如权利要求1所述的方法，其特征在于，该方法还包括在所述表主机处构造所述子分区中的至少一个的流。
3.如权利要求1所述的方法，其特征在于，拆分所述分区包括停止从所述表服务器提供所述分区；从所述分区构建所述子分区；以及从所述表服务器加载并提供所述子分区，其中停止提供所述分区包括为所述分区创建检查点，从而减少在分区重载期间要重放的日志的量，其中创建所述分区的检查点包括在检查点期间通过原子地执行以下步骤来高效地截短日志流创建新日志流，将所述检查点之后的范围从旧日志流硬链接到所述新日志流，删除所述旧日志流，以及将所述新日志流重命名成所述旧日志流的名称。
4.如权利要求3所述的方法，其特征在于，从所述分区构建所述子分区包括通过在没有昂贵的数据复制的情况下原子地硬链接来自所述分区的流的范围来高效地构造所述子分区的流。
5.如权利要求1所述的方法，其特征在于，所述方法还包括将所述子分区中的至少一个分配给第二表服务器，并且更新所述分区图以指示所述子分区中的该至少一个位于该第二表服务器处。
6.如权利要求1所述的方法，其特征在于，所述方法还包括出于负载监视目的，基于所述负载信息通过归并或拆分所述分区的两个或更多个部分的至少一个子集来调整所述分区的该两个或更多个部分的边界。
7.一个或多个存储用于执行一种方法的计算机可使用指令的计算机存储介质，所述方法用于管理由一个或多个表来表示的结构化存储系统，每一个表包括多个行，每一行表示由所述结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分所述多个行，每一分区包括来自所述表内的多个行中的一定范围的行，其中所述多个分区存储在多个表服务器上，并且其中表主机控制对所述多个表服务器的分区分配，所述方法用于将所述表的至少两个分区归并成经归并的分区，并且包括跟踪(80 所述多个表服务器上的多个分区的负载信息；由所述表主机基于所述负载信息来标识(804)要归并的至少两个分区；由所述表主机创建(808)经归并的分区的元数据流；将所述至少两个分区从提供该至少两个分区的至少一个表服务器上卸载(810)；由所述表主机将所述经归并的分区分配给(814)来自所述多个表服务器的所选表服务器；以及在所选表服务器处加载并提供(816)所述经归并的分区。
8.如权利要求7所述的一个或多个计算机存储介质，其特征在于，所述至少两个分区被存储在同一表服务器上。
9.如权利要求7所述的一个或多个计算机存储介质，其特征在于，所选表服务器包括在所述至少两个分区被归并成所述经归并的分区之前在其上驻留有该至少两个分区中的至少一个分区的表服务器。
10.如权利要求7所述的一个或多个计算机存储介质，其特征在于，所述方法还包括基于被归并成所述经归并的分区的所述至少两个分区来更新分区图，所述分区图存储所述多个分区与提供所述多个分区的多个表服务器之间的映射。
11.如权利要求7所述的一个或多个计算机存储介质，其特征在于，所述方法还包括从所述表主机向提供所述至少两个分区的至少一个表服务器发送准备归并消息，其中所述准备归并消息使得所述至少一个表服务器在归并所述至少两个分区之前压缩该至少两个分区以减少所述经归并的分区的加载时间。
12.—个或多个存储用于执行一种方法的计算机可使用指令的计算机存储介质，所述方法用于管理由一个或多个表来表示的结构化存储系统，每一个表包括多个行，每一行表示由所述结构化存储系统存储的数据实体并且包括用于标识该行的一个或多个键，在多个分区之间划分所述多个行，每一分区包括来自所述表内的多个行中的连续范围的行，其中所述多个分区存储在多个表服务器上，并且其中表主机控制对所述多个表服务器的分区分配，所述方法用于将所述表的一分区拆分成至少两个子分区，并且包括跟踪(70 所述多个表服务器上的多个分区的负载信息；由所述表主机基于所述负载信息来标识(704)要拆分所述分区，其中所述分区的负载信息标识该分区的不同部分上的不同负载；在所述表主机处确定(706)用于拆分所述分区的拆分比率，其中所述拆分比率是基于负载信息来指定的并且表示所述分区中的点，在该点处所述分区的第一部分包括第一负载量并且所述分区的第二部分包括第二负载量；从所述表主机向所述表服务器发送(708)请求，该对键信息的请求标识所述分区中的与所述拆分比率相对应的实际位置；由所述表服务器确定(710)标识所述分区内的与所述分区比率相对应的实际位置的键信息；将所述键信息从所述表服务器传递给(71 所述表主机； 在所述表主机处构造(714)所述子分区中的每一个子分区的元数据流； 将拆分请求从所述表主机发送到(716)所述表服务器； 在所述表服务器处从所述分区构建(718)所述子分区； 停止(720)在所述表服务器处提供所述分区； 在所述表服务器处加载并提供(72 所述子分区； 将拆分已完成通知从所述表服务器发送到(724)所述表主机；以及基于被拆分成所述子分区的分区来更新(726)分区图，所述分区图存储所述多个分区与提供所述多个分区的多个表服务器之间的映射。
13.如权利要求12所述的一个或多个计算机存储介质，其特征在于，所述方法还包括将所述子分区中的至少一个分配给第二表服务器；并且更新所述分区图以指示所述子分区中的该至少一个位于该第二表服务器处。
14.如权利要求12所述的一个或多个计算机存储介质，其特征在于，停止提供所述分区包括为所述分区创建检查点，从而减少在分区重载期间要重放的日志的量，其中创建所述分区的检查点包括在检查点期间通过原子地执行以下步骤来高效地截短日志流创建新日志流，将在所述检查点之后的范围从旧日志流硬链接到所述新日志流，删除所述旧日志流，以及将所述新日志流重命名成所述旧日志流的名称。
15.如权利要求12所述的一个或多个计算机存储介质，其特征在于，从所述分区构建所述子分区包括通过在没有昂贵的数据复制的情况下原子地硬链接来自所述分区的流的范围来高效地构造所述子分区的流。
全文摘要
提供了用于可缩放的结构化存储系统的分区管理。该存储系统提供有一个或多个表来表示的存储，这些表中的每一个包括表示数据实体的行。表被分成多个分区，每一分区包括连续范围的行。各分区由表服务器提供并且由表主机来管理。跟踪表服务器和分区的负载分布信息，并且表主机基于该负载分布信息来确定要拆分和/或归并各分区。
文档编号G06F15/16GK102197372SQ200980142662
公开日2011年9月21日 申请日期2009年10月23日 优先权日2008年10月24日
发明者A·E·绍尔斯沃德, B·G·卡尔德, D·巴德瓦杰, J·王, N·尼拉康特恩, S·斯里瓦斯塔瓦 申请人:微软公司
最新回复(0)