用于支持分布式数据网格中的分布式数据结构的系统和方法

摘要

一种支持分布式数据网格中的分布式数据结构的系统和方法。该网格包括多个桶，其中每一个桶被配置为具有包含分布式数据结构的若干元素的容量。分布式数据网格包括状态所有者进程，该状态所有者进程被配置为保持分布式数据结构的状态信息以及向客户端进程提供分布式数据结构的状态信息。分布式队列可以包括存储在多个进程上的桶的队列，其中每一个桶被配置为包含分布式队列的若干元素。分布式队列可以包括已命名的队列，该已命名的队列保持分布式队列的状态信息的本地版本，其中状态信息的本地版本包含指向分布式数据网格中桶的队列的头指针和尾指针。

说明书

版权声明

本专利文档的公开内容的一部分包含受版权保护的材料。版权所有者不反对任何人对专利文档或专利公开内容按照在专利商标局的专利文件或记录中出现的那样进行传真复制，但是除此之外在任何情况下都保留所有版权。

技术领域

本发明一般而言涉及计算机系统，并且具体地涉及支持分布式数据网格。

背景技术

现代计算系统(尤其是较大的组织和企业所采用的那些)在规模和复杂性上持续增长。具体而言，在诸如互联网应用的领域中，期望数以百万计的用户能够同时访问该应用，这实际上导致用户所生成和消费的内容量以及牵涉该内容的事务量指数增长。这些活动也造成对数据库和元数据存储的事务调用的数量对应增长，数据库和元数据存储可能具有有限容量而难以容纳该需求。这是本发明的实施例旨在解决的一般领域。

发明内容

本文描述了支持分布式数据网格中的分布式数据结构的系统和方法。分布式数据网格包括多个桶(bucket)，其中每个所述桶被配置为具有包含分布式数据结构的若干元素的容量。此外，分布式数据网格包括状态所有者进程，状态所有者进程被配置为保持分布式数据结构的状态信息并且向客户端进程提供分布式数据结构的状态信息。

本文描述了支持分布式数据网格中的分布式队列的系统和方法。分布式数据网格包括多个桶，其中每个所述桶被配置为具有包含分布式数据队列的若干元素的容量。此外，分布式队列可以包括保持分布式队列的状态信息的本地版本的已命名的队列，其中所述状态信息的本地版本包含指向分布式数据网格中的桶的队列的头指针和尾指针。

附图说明

图1是根据本发明各种实施例的数据网格集群的示意图。

图2显示了根据本发明的实施例支持分布式数据网格中的分布式数据结构的示意图。

图3显示了根据本发明的实施例支持分布式数据结构中的桶的示意图。

图4显示了根据本发明的实施例使用客户端进程在分布式数据结构上执行操作的示意图。

图5示出了根据本发明的实施例用于支持分布式数据网格中的分布式数据结构的示例性流程图。

图6显示了根据本发明的实施例支持分布式数据网格中的分布式队列的示意图。

图7显示了根据本发明的实施例的分布式队列中的桶的示意图。

图8显示了根据本发明的实施例向分布式队列供给元素的示意图。

图9显示了根据本发明的实施例用于向分布式队列供给元素的交互框图。

图10显示了根据本发明的实施例向分布式队列中的桶供给元素的交互框图。

图11显示了根据本发明的实施例从分布式队列探询元素的示意图。

图12显示了根据本发明的实施例用于从分布式队列探询元素或者查看元素的交互框图。

图13显示了根据本发明的实施例用于从分布式队列中的桶探询元素或者查看元素的交互框图。

图14示出了根据本发明的实施例用于支持分布式数据网格中的分布式队列的示例性流程图。

具体实施方式

本文描述了能够支持分布式数据网格中的分布式数据结构的系统和方法。分布式数据网格包括多个桶，其中每一个桶被配置为具有包含分布式数据结构的若干元素的容量。此外，分布式数据网格包括状态所有者进程，状态所有者进程被配置为保持分布式数据结构的状态信息并且向客户端进程提供分布式数据结构的状态信息。

分布式数据网格

根据实施例，本文所指的“数据网格集群”或者“数据网格”是包括多个计算机服务器的系统，该多个计算机服务器一起工作以管理分布式环境内或者集群式环境内的信息和相关操作(诸如计算)。数据网格集群可以被用来管理跨服务器共享的应用对象和数据。优选地，数据网格集群应当具有低响应时间、高吞吐量、可预测的可扩展性、持续的可用性和信息可靠性。作为这些能力的结果，数据网格集群十分适合用于计算密集型的状态中间层应用中。数据网格集群的一些示例(例如Oracle Coherence数据网格集群)可以将信息存储在存储器中以实现更高的性能，并且可以在保有该信息的跨多个服务器同步的拷贝中采用冗余，从而确保在服务器故障的情况下系统的恢复力以及数据的可用性。例如，Coherence在可靠的、高度可扩展的点对点集群协议之上提供复制数据管理和分布式(分区)数据管理以及缓存服务。

存储器中的数据网格可以通过将数据分布在一起工作的若干服务器上来提供数据存储和管理能力。数据网格可以是与应用服务器运行在同一层或者运行在应用服务器之内的中间件。它可以提供数据的管理和处理，并且也可以将处理推送到网格中数据所位于的地方。此外，通过在服务器变得不工作或者从网络断开时自动地并且透明地故障转移以及重新分布其集群数据管理服务，存储器中的数据网格可以排除单点故障。当新的服务器被添加或者当故障的服务器重启时，它可以自动地加入集群，而服务可以故障恢复到它，从而透明地重新分布集群负载。数据网格也可以包括网络级别的容错特性以及透明的软重启能力。

根据实施例，数据网格集群的功能基于使用不同的集群服务。集群服务可以包括根集群服务、分区缓存服务以及代理服务。在数据网格集群内，每一个集群节点可以参与若干集群服务，就提供集群服务和消费集群服务两者而言。每一个集群服务具有在数据网格集群内唯一地标识该服务的服务名称以及限定该集群服务能够做什么的服务类型。除了运行于数据网格集群中每一个集群节点上的根集群服务，还可以有每一服务类型的多个已命名实例。服务可以或者由用户配置，或者作为默认的服务集合由数据网格集群提供。

图1是根据本发明的各种实施例的数据网格集群的示意图。如图1中所示，数据网格集群100(例如Oracle Coherence数据网格)包括多个集群成员(或者服务器节点)，诸如具有各种集群服务111-116运行其上的集群节点101-106。此外，缓存配置文件110可以被用来配置数据网格集群100。在实施例中，数据网格集群100是存储器中的数据网格集群，其通过将数据分布在一起工作的集群节点的存储器中来提供数据存储和管理能力。

分布式数据结构

根据本发明的实施例，分布式数据网格可以支持分布式数据结构。例如，分布式数据结构可以是分布式队列、分布式集合、分布式列表和/或分布式栈。

图2显示了根据本发明的实施例支持分布式数据网格中的分布式数据结构的示意图。如图2中所示，分布式数据结构201可以包括多个桶(例如桶211-216)，其中的每一个桶被配置为包含若干元素。在使用中，桶在不同时刻可能包含零个、一个或者多个元素。取决于分布式数据结构的应用，元素可以是包括例如数据单元、调用、请求、响应、消息、事务和/或事件的数据元素。

此外，集群200中的状态所有者进程202可以负责保持分布式数据结构201的状态203。分布式数据结构201可以在不同的桶211-216上分别执行不同的操作，而不是直接作用于单个元素上。

如图2中所示，进程的集群(诸如分布式数据网格200中的进程221-223)可以维护(或者拥有)多个桶211-216。例如，桶211-216可以跨进程221-223的集群均匀分布，每一个进程负责维护(或者拥有)一个或多个桶。因此，分布式数据结构201的总大小可以超过单个进程的最大存储容量，因为每一个进程221-223负责存储分布式数据结构201的内容的仅仅一部分。

根据本发明的实施例，分布式数据结构201允许多个用户进程同时在分布式结构201中的不同桶211-216上执行不同的操作。如图2所示，操作204可被执行于桶211上，同时另一操作206被执行于桶216上。因此，系统可以减少分布式数据结构201上的竞争，因为访问分布式结构201的需求可以被分散到多个桶上。

此外，分布式数据结构201可以确保在任意时刻只有一个进程能够访问单个桶中的元素。例如，系统可以将锁机制应用到处于竞争下的每一个单独的桶上。替代地，系统可以利用请求队列，请求队列允许不同的进程有序地等待处理。

如图2中所示，当操作204正被执行于桶211上时，桶211被锁定。在同一桶211上的其他操作(诸如操作205)可能需要等待直到完成锁定操作204。类似地，当操作206正被执行于桶216上时，桶216被锁定，并且在同一桶216上的其他操作(诸如操作207)可能需要等待直到完成锁定操作206。

图3显示了根据本发明实施例支持在分布式数据结构中的桶的示意图。如图3中所示，分布式数据网格300中的桶301被配置为包含若干元素并且可以包含用于分布式数据结构的一个或多个元素(例如内部数据结构310中的元素311-315)。此外，桶301可以维护各种桶状态303，其可被用于访问存储在桶301中的元素311-315。

根据本发明的实施例，桶301被配置为具有容量，容量是它可以包含的元素的最大数量。桶301因而被配置为包含分布式数据结构的若干元素。当在使用中时，桶301可以保持零个到多个元素(上至容量)。此外，桶301的容量可以被调节以支持不同的分布式数据结构(以便提高针对特定的数据访问模式的性能)。

此外，桶301可以被复制到分布式数据网格300中的其他节点。如图3中所示，包含一个或多个元素(例如内部数据结构320中的元素321-325)的备用桶302和关联的桶状态304可以在桶301丢失时接管。

图4显示了根据本发明的实施例使用客户端进程在分布式数据结构上执行操作的示意图。如图4中所示，分布式数据网格400中的分布式数据结构401可以包括多个桶，例如桶411-416。此外，状态所有者进程402可以负责保持分布式数据结构401的状态信息403。

此外，客户端进程404可以使用(或者包括)已命名的数据结构410，其保持分布式数据结构401的状态信息的本地拷贝405。例如，当客户端进程404首次连接到分布式数据结构401时，系统可以初始化状态信息405。

根据本发明的实施例，多个客户端进程可以同时访问分布式数据结构401。当另一客户端进程已经改变了分布式数据结构401的状态403时，客户端进程404上的状态信息的本地拷贝405可能变为过期的。

使用分布式数据结构401，已命名的数据结构410中的逻辑(即被客户端进程404所使用的)可以考虑到状态405可能是过期的。因此，不需要在每一个操作之前刷新状态信息405。

如图4中所示，当状态405变为过期时，(客户端进程404上的)已命名的数据结构410可以向状态所有者进程402发送消息以刷新状态405。在接收到消息之后，状态所有者进程402可以将新状态403发送回客户端进程404，客户端进程404继而可以经由进程421在桶416上执行操作420。

根据本发明的实施例，一旦创建了桶，则即使当桶变为空(即全部的元素已经被探询或者从桶移除)，该桶也可能不会从分布式数据结构401移除。这对于支持多个客户端进程的操作可以是有益的。

图5示出了根据本发明的实施例用于支持分布式数据网格中的分布式数据结构的示例性流程图。如在图5中所示，在步骤501处系统可以提供分布式数据网格中的多个桶，其中每一个所述桶被配置为具有包含分布式数据结构的若干元素的容量。在使用期间的不同点处，桶可以包含分布式数据结构的零个或者多个元素(上至容量)。此外，在步骤502处，状态所有者进程可以保持分布式数据结构的状态信息。随后，在步骤503处，状态所有者进程可以向客户端进程提供分布式数据结构的状态信息。

分布式队列

根据本发明的实施例，分布式数据网格可以支持分布式队列。例如，分布式队列是队列(或者桶)的队列，其中每一个桶是父队列中的子队列。

图6显示了根据本发明的实施例支持分布式数据网格中的分布式队列的示意图。如图6中所示，分布式队列601可以包括分布式数据网格600中的桶(例如桶611-616)的队列。多个桶(例如桶611-616)中的每一个桶被配置为包含若干元素。在使用中，在不同时刻桶可以包含零个、一个或者多个元素。取决于分布式数据结构的应用，元素可以是包括例如数据单元、调用、请求、响应、消息、事务和/或事件的数据元素。

此外，状态所有者进程602可以负责保持分布式队列601的状态603。例如，状态603可以包括指向分布式队列601中的当前头桶611的头指针以及指向分布式队列601中的尾桶616的尾指针。

根据本发明的实施例，客户端进程604可以从队列状态所有者602获得分布式队列601的当前状态603，以及在分布式队列601上执行各种操作(诸如供给操作和探询操作)。

如图6中所示，可被用户进程606-607访问的客户端进程604可以使用(或者包括)已命名的队列610。已命名的队列610可以维护队列状态的本地拷贝605，队列状态的本地拷贝605包括在它看来的头指针和尾指针。例如，队列状态605中的头指针可以指向头桶611，而队列状态605中的尾指针可以指向尾桶616。

当客户端进程604首次连接到分布式队列601时，队列状态605结构可以被初始化。此外，客户端进程604不需要在每次操作前刷新其队列状态605，因为(用于执行供给操作和探询操作的)已命名的610中的逻辑可以考虑到所维护的队列状态605可能是过期的。

根据本发明的实施例，客户端进程604可以通过向分布式队列601的尾桶616(即尾端)供给(或者添加)一个或多个元素来在分布式队列601上执行供给操作。另外，客户端进程604可以通过从分布式队列601的头桶611(即前端)探询(或者移除)一个或多个元素来在分布式队列601上执行探询操作。此外，客户端进程604可以在分布式队列601上执行查看操作以(在不从分布式队列601移除元素的情况下)获得一个或多个元素的值。

此外，不同的客户端进程可以尝试同时执行不同的操作。围绕分布式队列601的头桶611和尾桶616可能形成隐式事务以处置不同客户端进程的多个请求。系统可以在处于竞争下的头桶611和/或尾桶616上应用锁机制。替代地，系统可以利用请求队列，请求队列允许不同进程有序地等待处理。

图7显示了根据本发明的实施例的分布式队列中的桶的示意图。如图7中所示，分布式队列700中的桶701包含元素的队列，例如队列710中的元素711-715。

此外，桶701可以维护各种桶状态702，桶状态702可以被用于访问存储在桶701中的不同元素711-715。桶状态702可以包括指向桶701中的头元素711的指针以及指向桶701中的尾元素716的指针。

此外，可以使用(存储桶701的)同一进程来存储桶701中的元素711-715。当桶701首次创建时，指向头元素和尾元素的指针可以包含指示桶701为空的专门的值。另外，桶701可以包含指示桶701是否为队列中的最后的桶的标志。

图8显示了根据本发明的实施例向分布式队列供给元素的示意图。如图8中所示，分布式数据网格800中的分布式队列801可以包括桶(例如桶811-816)的队列，其中每一个桶可以被配置为具有保持若干元素的容量并且可以在使用期间保持零个或更多元素。此外，状态所有者进程802可以负责在分布式队列801的队列状态803中保持状态信息。

根据本发明的实施例，客户端进程804可以尝试向如已命名的队列810中的如队列状态805所指示的尾桶供给(或者添加)一个或多个元素。例如，客户端进程804可以假定桶815是尾桶，因为队列状态805中的尾指针指向桶815。相应地，客户端进程804可以向维护桶815的进程821发送(包含元素集合的)供给消息。

随后，客户端进程804可以接收对其消息的响应。响应的内容可以向客户端进程804表明供给操作是否成功。例如，如果响应为空，则所有被供给的元素被添加到了尾桶。另一方面，如果响应包含任意元素，则这些元素没有被供给给(添加到)桶。

系统未能向桶供给(或添加)一个或多个元素可能有不同的原因。例如，所认为的尾桶可能不再是当前的尾桶(即队列状态805是过期的)，在此情况下在响应中返回全部元素。替代地，当前的尾桶可能不具有足够的剩余容量来保持全部的供给的元素，在此情况下在响应消息中返回剩余元素。

在任一情况下，当对供给的响应包含未供给的元素时，客户端进程804可能需要知道下一个尾桶ID是什么。进程804可以向拥有队列状态803的状态所有者进程802发送消息，以通知状态所有者进程802队列状态803应当指向下一个尾桶。

当存在多个客户端进程时，客户端进程804可能不知道另一个客户端进程是否已经移动了尾部ID。系统可以将移动尾部ID的操作作为原子(atomic)比较和设置操作来执行。

如图8中所示，当客户端进程804请求状态所有者进程802增加尾部ID时，客户端进程804也可以向状态所有者进程802发送队列状态805中的尾部ID。

当队列状态805中的尾部ID与队列状态803中的当前尾部ID匹配时，系统可以通过将尾部移动到下一个桶ID来改变队列状态803。随后，系统可以向客户端进程804发送更新后的队列状态803中的尾部ID作为响应。

当队列状态805中的尾部ID与队列状态803中的当前尾部ID不匹配时，队列状态803可能或者已经通过此消息被增加，或者此前已经被增加过。随后，系统可以向客户端进程804发送当前队列状态803中的尾部ID作为响应。

例如，如果在客户端一侧上的尾部ID是10并且在所有者一侧的的尾部ID是10，则在所有者一侧的的尾部ID可以被移动到11，此值可以被返回给客户端。如果在客户端一侧上的尾部ID是10而在所有者一侧的的尾部ID已经是11，则队列状态所有者可以将值11返回给客户端。

如图8中所示，队列状态803指向新的尾桶816。在客户端进程804接收到正确的尾部ID之后，客户端进程804可以向拥有新的尾桶816的进程发送包含任何剩余的要被供给的元素的供给消息。

此外，新的尾桶816可能不能保持全部供给的元素。例如，另一个客户端进程可能已经填充了新的尾桶816，或者新的尾桶816不具有充足的容量来保持全部元素。随后，系统可以重复以上增加尾桶ID和供给剩余元素的过程，直到全部元素已被成功地供给(添加)到分布式队列801。

图9显示了根据本发明的实施例用于向分布式队列供给元素的交互框图。如图9中所示，客户端进程901可以使用已命名的队列902来向分布式数据网格中的分布式队列供给(或者添加)一个或多个元素。分布式数据网格包括集群成员905，集群成员905是拥有队列状态906的队列状态所有者905。

在步骤911处，已命名的队列902可以(例如从客户端进程901)接收向分布式队列的尾部供给新值的消息。与客户端进程901相关联的已命名的队列902可以维护队列状态903，队列状态903是分布式队列的队列状态906的本地版本。

已命名的队列902可以假定本地队列状态903中的信息是正确的。在步骤912-913处，已命名的队列902可以请求并接收来自本地队列状态903的队列的状态信息，诸如尾部ID以及队列版本号。

随后，与客户端进程901相关联的已命名的队列902可以向根据其本地视角拥有尾桶的集群成员发送供给消息。在步骤914处，已命名的队列902可以将接收到的值供给到基于接收自队列状态906的尾部ID而拥有尾桶的集群成员904。

如果该值成功地供给(添加)到尾桶，则在步骤915处，集群成员904可以返回空集合，并且在步骤916处，已命名的队列902可以向客户端进程901返回OFFER_ACCEPTED消息。

否则，该值未成功地供给(添加)到尾桶，例如由于或者该桶是满的或者队列状态版本中的不匹配。在步骤915处，集群成员904可以向已命名的队列902返回未供给的元素的集合。随后已命名的队列902可以再次尝试供给操作，例如通过向下一个尾桶发送消息。已命名的队列902可以尝试重复地(例如在循环910中)向分布式队列添加接收到的值，直到或者分布式队列为满的时候或者接收到的值成功地被供给(或者添加)。

在循环910内，如果此前的供给由于桶为满或者版本不匹配而失败，则已命名的队列902可能需要刷新或者更新在它看来的尾部ID和队列版本。

在步骤917处，已命名的队列902可以向本地队列状态903发送刷新尾部ID的请求。在步骤918处，本地队列状态903可以尝试从是队列状态906的所有者的集群成员905获得下一个尾部ID。例如，消息可以包含基于本地队列状态903中的这种信息的尾部ID和队列版本信息。

在步骤919-920处，集群成员905可以请求并获得队列状态906的所有者版本中的状态信息。因此，集群成员905可以确定队列状态是否应当被刷新，例如通过比较从本地队列状态903接收到的信息和从队列状态906接收到的信息。

例如，当本地队列状态903中的信息与所有者队列状态906中的信息不匹配时，本地队列状态903是过期的。在这种情况下，所有者队列状态906中的状态信息可以被返回到本地队列状态903(即本地队列状态903被刷新)。

当本地队列状态903中的信息与所有者队列状态906中的信息匹配时，在步骤921处，集群成员905可以更新队列状态906，例如通过将尾部移动到下一个桶ID。随后，在步骤922处，队列状态906可以向集群成员905提供更新后的队列的状态信息。例如，如果尾部ID通过回卷到第一个桶ID或者任何其他重复使用的桶而移动到下一个桶ID，则可以增加队列版本号。

此外，可以执行检查以确定队列是否为满。例如，如果增加尾部ID将使尾部ID等于当前头部ID，则队列为满。

如图9中所示，在步骤923-924处，集群成员905可以向队列状态903提供(刷新后或更新后的)队列的状态信息，队列状态903继而可以向已命名的队列902提供队列的状态信息。例如，这些状态信息可以包括或者QUEUE_FULL消息或者带有更新后的队列版本号的更新后的尾部ID。

在步骤925处，当分布式队列为满时，已命名的队列902可以向客户端进程901发送QUEUE_FULL消息。否则，在步骤926-927处，已命名的队列902可以请求并获得来自队列状态903的队列的状态信息。此外，在步骤928-929处，已命名的队列902可以向集群成员904(或者拥有带有更新后的尾部ID的桶的任何其他集群成员)供给(或者添加)值。

如图9中所示，已命名的队列902可以尝试重复地(例如在循环910中)向分布式队列供给(或添加)接收到的值，直到接收到的值被成功地添加。在步骤930处，已命名的队列902可以在接收到的值被成功地添加之后向客户端进程901发送QUEUE_SUCCESS消息。

图10显示了根据本发明的实施例用于向分布式队列中的桶供给元素的交互框图。如图10中所示，调用者(例如已命名的队列1001)可以被用于向分布式数据网格中的集群成员1002所拥有的特定桶1003供给(或添加)一个或多个元素。

在步骤1011处，已命名的队列1001可以基于状态信息(诸如桶ID和队列版本信息)向集群成员1002供给值。在步骤1012-1013处，如果具有特定桶ID的桶1003不存在，则可以创建新桶。

在步骤1014-1015处，集群成员1002可以检查桶1003是否为满。当桶为满时，在步骤1016处，集群成员1002可以向已命名的队列1001发送BUCKET_FULL消息。否则，在步骤1017-1018处，集群成员1002可以从桶1003获得状态信息。

在步骤1019处，如果在已命名的队列1001看来的队列版本信息不匹配与桶1003相关联的队列版本信息，则已命名的队列1001可以向已命名的队列1001发送OFFER_FAILED消息。

在步骤1010-1021处，已命名的队列1001可以将值添加到桶1003中。随后，在步骤1022处，已命名的队列1001可以向已命名的队列1001发送OFFER_SUCCESS消息。

图11显示了根据本发明的实施例从分布式队列探询元素的示意图。如图11中所示，分布式数据网格1100中的分布式队列1101可以包括桶的队列(例如桶1111-1116)，其中每一个桶可以包括一个或多个元素。此外，状态所有者进程1102可以负责保持分布式队列1101的队列状态1103的状态信息。

根据本发明的实施例，客户端进程1104可以在分布式队列1101的头桶上执行探询动作或者查看动作。例如，探询动作可以从分布式队列1101返回并移除元素(诸如头元素)。另一方面，查看动作可以在不移除头元素的情况下返回分布式队列1101的头元素的值。

如图11中所示，客户端进程1104假定桶1111为分布式队列1101中的头桶。为了从分布式队列1101探询，客户端进程1104向拥有头桶1111的进程1121发送消息。随后，客户端进程1104可以接收响应，

该响应或者包含来自分布式队列1101的头部的元素，或者包含桶1111为空的指示符。

如果该响应指示桶1111为空(假设分布式队列1101本身不为空)，则由已命名的队列1110维护的队列状态1105是过期的。因此，队列状态1105可能需要被刷新，使得头桶ID被更新到下一个头部ID。

如图11中所示，队列状态1104可以向拥有队列状态1103的状态所有者进程1102发送消息以指令队列状态1103增加头部ID。用于探询操作或查看操作的移动到下一个头部ID的操作(即更新队列状态1105)可以是原子比较和设置操作，其中只有在当前头部ID与客户端头部ID匹配时才改变队列状态1103。客户端进程1104可以随后接收到包含来自队列状态1103的头部ID的响应，该头部ID或者已经通过此消息被增加，或者此前已经被增加过。

最后，客户端进程1104可以向拥有新的头桶的进程重新发送探询/查看消息。

图12显示了根据本发明的实施例用于从分布式队列探询元素或者查看元素的交互框图。如图12中所示，客户端进程1201可以使用已命名的队列1202来在分布式数据网格中的分布式队列1200中的一个或多个元素上执行诸如探询动作或查看动作的动作。分布式队列1200包括集群成员1205，集群成员1205是拥有队列状态1206的队列状态所有者1205。

在步骤1211处，已命名的队列1202可以(例如从客户端进程1201)接收在分布式队列1200的头元素上执行探询动作或查看动作的消息。与客户端进程1201相关联的已命名的队列1202可以维护分布式队列1200的队列状态1203的本地版本。

在步骤1212-1213处，已命名的队列1202可以检查队列状态1203以获得关于分布式队列1200是否为空的信息。当分布式队列1200为空时，在步骤1214处，已命名的队列1202可以向客户端进程1201发送QUEUE_EMPTY消息。

此外，如果队列不为空，则客户端进程1201假定它具有当前头部ID和队列版本号。在步骤1215-1216处，已命名的队列1202可以请求并接收来自本地队列状态1203的状态信息，诸如头部ID和队列版本号。已命名的队列1202可以使用这些信息来在分布式队列1200的头元素上执行探询动作或查看动作。

随后，在步骤1217处，已命名的队列1202可以在基于接收到的头部ID而拥有头桶的集群成员1204上执行探询动作或者查看动作。

如果该工作在头桶上成功执行，则在步骤1218处，集群成员1204可以向已命名的队列1202返回一个或多个元素，并且在步骤1219处，已命名的队列1202可以向客户端进程1201返回这些元素。

否则，如果该动作未在头桶上成功执行，则在步骤1218处，集群成员1204可以向已命名的队列1202返回空集合。在这种情况下，客户端进程1201可能需要更新在它看来的头部ID和队列版本信息。

如图12中所示，已命名的队列1202可以尝试重复地(例如在循环1210中)在分布式队列1200的头部上执行探询动作或者查看动作，直到或者分布式队列1200为空的时候或者该动作被成功执行的时候。

在循环1210内，在步骤1220处，已命名的队列1202可以请求本地队列状态1203刷新头部ID和队列版本号，而在步骤1221处本地队列状态1203可以尝试从是队列状态1206的所有者的集群成员1205获得下一个头部ID。

在步骤1222-1223处，集群成员1205可以请求并获得队列状态1206中状态信息的所有者版本。例如，消息可以包含基于本地队列状态1203中的信息的头部ID和队列版本信息。因此，集群成员1205可以确定队列状态是否是过期的，例如通过比较从本地队列状态1203接收到的信息和从队列状态1206接收到的信息。

例如，如果本地队列状态1203中的信息与队列状态1206中的信息不匹配，则队列状态1203是过期的。在这种情况下，队列状态1206中的状态信息可以被返回到队列状态1203(即队列状态1203被刷新)。

当本地队列状态1203中的信息与队列状态1206中的信息匹配时，在步骤1224处，集群成员1205可以更新队列状态1206，例如通过将头部移动到下一个桶ID。随后，在步骤1225处，队列状态1206可以向集群成员1205提供更新后的队列状态1206的状态信息。此外，可以执行检查来确定该队列是否为空。例如，当头部ID与尾部ID相同时，分布式队列1200为空队列，在此情况下头部ID可以不在尾部ID之上增加。

在步骤1226-1227处，集群成员1205可以向队列状态1203提供(刷新后的或者更新后的)队列的状态信息，队列状态1203继而可以将该队列状态信息提供给已命名的队列1202。例如，这些状态信息可以包括或者QUEUE_EMPTY消息或者带有更新后的队列版本号的更新后的头部ID。

在步骤1228-1229处，已命名的队列1202可以检查队列状态1203以确定分布式队列1200是否为空(因为可以在分布式队列1200上执行多个操作)。在步骤1230处，当分布式队列1200为空时，已命名的队列1202可以向客户端进程1201发送QUEUE_EMPTY消息。

否则，在步骤1231-1232处，已命名的队列1202可以请求并获得来自队列状态1203的更新后的队列状态1203的状态信息。在步骤1233-1234处，已命名的队列1202可以在集群成员1204(或者拥有带有更新后的头部ID的桶的任何其他集群成员)上执行探询动作或者查看动作。

如图12中所示，已命名的队列1202可以尝试重复地(例如在循环1210中)在分布式队列1200的头部上执行探询动作或者查看动作，直到该动作被成功执行。在步骤1235处，已命名的队列1202可以向客户端进程1201返回元素。

图13显示了根据本发明的实施例从分布式队列中的桶探询元素或者查看元素的交互框图。如图13中所示，调用者(例如已命名的队列1301)可以被用于在分布式数据网格中的集群成员1302所拥有的桶1303上执行诸如探询操作或者查看操作的动作。

在步骤1311处，已命名的队列1301可以基于状态信息(诸如桶ID和队列版本号)在集群成员1302上执行探询动作或者查看动作。

在步骤1312-1313处，集群成员1302可以检查桶1303是否为空。在步骤1314处，如果桶1303为空，则集群成员1302可以向已命名的队列1301发送BUCKET_EMPTY消息。

在步骤1315-1316处，集群成员1302可以从桶1003获得桶的状态信息。

在步骤1317处，如果在已命名的队列1301看来的队列版本信息不匹配与桶1303相关联的队列版本信息，则集群成员1302可以向已命名的队列1301发送POLL_FAILED消息。

否则，在步骤1318-1324处，集群成员1302可以在桶1303上执行探询动作或者查看动作。例如，如果该动作是探询动作，则桶1303可以在移除或删除桶元素1304之前返回桶元素1304的值。此外，如果该桶在桶元素1304被移除或删除之后变为空，则该桶可以更新队列版本。随后，集群成员1302可以将该元素提供给已命名的队列1301。另一方面，如果该动作是查看动作，则桶1303可以在不移除或不删除桶元素1304的情况下返回桶元素1304的值。

图14示出了根据本发明的实施例用于支持分布式数据网格中的分布式队列的示例性流程图。如图14中所示，在步骤1401处，系统可以提供分布式数据网格中的多个桶。随后，在步骤1402处，系统可以将分布式队列的一个或多个元素存储在多个桶中。此外，在步骤1403处，系统可以使用已命名的队列来保持分布式队列的状态信息的本地版本，其中所述状态信息的本地版本包含指向分布式数据网格中的桶的队列的头指针和尾指针。

一种用于支持分布式数据网格中的分布式队列的系统，包括：一个或多个微处理器；运行在一个或多个微处理器上的分布式数据网格中的多个桶，其中被维护在队列中的多个桶被配置来存储分布式队列的一个或多个元素；以及保持分布式队列的状态信息的本地版本的已命名的队列，其中所述状态信息的本地版本包含指向分布式数据网格中的桶的队列的头指针和尾指针。

该系统还包括一种部件，其中已命名的队列与客户端进程相关联，该客户端进程被一个或多个用户进程用来访问分布式队列中的一个或多个元素。

该系统还包括一种部件，其中所述客户端进程被配置为基于分布式队列的状态信息的本地版本向桶的队列中的尾桶供给一个或多个元素。

该系统还包括一种部件，其中所述客户端进程被配置为当从拥有尾桶的进程接收到的消息包括一个或多个未供给的元素时确定队列状态为过期的。

该系统还包括一种部件，其中所述客户端进程被配置为从状态所有者进程获得刷新后的队列状态，其中刷新后的队列状态指示新的头桶。

该系统还包括一种部件，其中所述客户端进程被配置为基于分布式队列的状态信息的本地版本从桶的队列中的头桶探询元素或者查看元素。

该系统还包括一种部件，其中所述客户端进程被配置为当在分布式队列不为空时从拥有头桶的进程接收到的消息为空时，确定队列状态是过期的。

该系统还包括一种部件，其中所述客户端进程被配置为从状态所有者进程获得刷新后的队列状态，其中刷新后的队列状态指示新的头桶。

该系统还包括一种部件，其中每一个桶维护桶状态，桶状态包括指向当前头元素的指针以及指向当前尾元素的指针，并且当执行操作时桶是锁定的，其中在所述桶上的其他操作被配置为等待直到完成该操作。

一种用于支持分布式数据网格中的分布式队列的方法，包括：提供分布式数据网格中的多个桶，其中每一个桶被配置为存储分布式队列的一个或多个元素；将分布式队列的一个或多个元素存储在多个桶中；以及使用已命名的队列保持分布式队列的状态信息的本地版本，其中所述状态信息的所述本地版本包含指向分布式数据网格中桶的队列的头指针和尾指针。

该方法还包括一种部件，用于将已命名的队列与客户端进程相关联，该客户端进程被一个或多个用户进程用来访问分布式队列中的一个或多个元素。

该方法还包括一种部件，用于使用所述客户端进程以基于分布式队列的状态信息的本地版本向桶的队列中的尾桶供给一个或多个元素。

该方法还包括一种部件，用于使用所述客户端进程以在从拥有尾桶的进程接收到的消息包括一个或多个未供给的元素时确定队列状态是过期的。

该方法还包括一种部件，用于使用所述客户端进程以从状态所有者进程获得刷新队列状态，其中刷新后的队列状态指示新的头桶。

该方法还包括一种部件，用于使用所述客户端进程以基于分布式队列的状态信息的本地版本从桶的队列中的头桶探询元素或者查看元素。

该方法还包括一种部件，用于使用所述客户端进程以当在分布式队列不为空时从拥有头桶的进程接收到的消息为空时，确定队列状态是过期的。

该方法还包括一种部件，用于使用所述客户端进程以从状态所有者进程获得刷新后的队列状态，其中刷新后的队列状态指示新的头桶。

该方法还包括一种部件，用于使用每个桶维护桶状态，该桶状态包括指向当前头元素的指针以及指向当前尾元素的指针，并且其中当执行操作时桶时桶是锁定的，其中在所述桶上的其他操作被配置为等待直到完成该操作。

一种具有存储于其上的指令的非临时性机器可读存储介质，该指令用于支持分布式数据网格中的分布式队列，该指令被计算机系统执行时使得计算机系统执行包括以下各项的步骤：提供分布式数据网格中的多个桶，其中每一个桶被配置为存储分布式队列的一个或多个元素；将分布式队列的一个或多个元素存储在多个桶中；以及使用已命名的队列保持分布式队列的状态信息的本地版本，其中所述状态信息的所述本地版本包含指向分布式数据网格中桶的队列的头指针和尾指针。

一种用于支持分布式数据网格中分布式数据结构的装置，包括：用于提供分布式数据网格中的多个桶的部件，其中每一个所述桶被配置为具有包含分布式数据结构的若干元素的容量；用于经由状态所有者进程保持分布式数据结构的状态信息的部件，以及用于经由状态所有者进程向客户端进程提供分布式数据结构的状态信息的部件。

该装置还包括用于在分布式数据网格中的多个进程之间均匀分布所述多个桶的部件。

该装置还包括用于在与分布式数据结构相关联的不同桶上同时执行多个操作的部件。

该装置还包括用于在分布式数据结构改变时更新所述状态所有者进程分布式数据结构的状态信息的部件。

该装置还包括用于允许桶在操作被执行时被锁定的部件，其中所述桶上的其他操作被配置为等待直到完成该操作。

该装置还包括用于允许分布式数据结构为分布式队列、分布式集合、分布式列表或者分布式栈的部件。

该装置还包括用于允许每一个桶维护桶状态的部件，其中桶状态被用来访问所述桶中的一个或多个元素。

该装置还包括用于关联至少一个桶与备用桶的部件，备用桶包含被包含在所述至少一个桶中的一个或多个元素。

该装置还包括允许所述客户端进程进行以下操作的部件：存储分布式数据结构的状态信息的本地版本；仅当状态信息的本地版本变得过期时，基于状态所有者进程所保持的状态信息刷新存储在所述客户端进程中的状态信息的本地版本；以及在分布式数据结构中的桶中的一个或多个元素上执行操作。

使用一个或多个传统通用数字计算机或专用数字计算机、计算设备、机器、或者微处理器(包括根据本公开的教导编程的一个或多个处理器、存储器和/或计算机可读存储介质)，本发明可以方便地实现。如软件领域技术人员显而易见的，熟练的编程者基于本公开的教导可以容易地准备适当的软件编码。

在一些实施例中，本发明包括计算机产品，其是具有存储于其上/中的指令的存储介质或者计算机可读介质，该指令可被用来编程计算机以执行本发明的任何进程。存储介质可以包括但不限于任意类型的盘，包括软盘、光盘、DVD、CD-ROM、微驱动器以及磁光盘、ROM、RAM、EPROM、EEPROM、DRAM、VRAM、闪存存储器设备、磁卡或光学卡、纳米系统(包括分子记忆IC)或者适于存储指令和/或数据的任意类型的介质或设备。存储介质或者计算机可读介质可以是非临时性的。

为了示意和描述的目的，已经提供了本发明的以上描述。它不旨在穷举或者限制本发明为所公开的确切形式。对本领域技术人员而言，许多修改和变形是显而易见的。这些修改和变形包括所描述的特性的任意相关组合。实施例是为了最好地解释本发明的原理及其实际应用而选择和描述的，从而使得其他本领域技术人员能够理解各种实施例的本发明以及理解带有适用于所预期的特定用途的各种修改的本发明。本发明的范围旨在由以下权利要求及其等价物限定。