引导会合联盟的制作方法
专利名称：引导会合联盟的制作方法
引导会合联盟
背景技术：
计算机技术(例如，微处理器速度、存储器容量、数据传输带宽、软件功能等)的进步一般有助于各行业中的计算机应用的增长。通常提供常被配置为服务器阵列的甚至更强大的服务器系统来服务源自诸如万维网等外部源的请求。当可用电子数据的数量增长时，以便于用户友好和快速数据搜索和检索的可管理方式来储存这些数据也变得愈发重要。当今，一种常见的方法是将电子数据存储在一个或多个数据库中。典型的数据库可被称为其数据被结构化使得计算机程序可例如快速搜索和选择期望的数据的有组织的信息集合。此外，在此类环境中，联盟指的是彼此之间已建立了信任且在其间实现用户身份信息的共享的一组组织或服务提供商。例如，联合身份是识别在企业边界之间以递增的频度比率移动的个体的分布式计算构造。联合身份的实际应用由需要同时管理若干不同种类的系统的大型跨国公司来表示。一般而言，当发起联盟或环的第一节点(例如，超级种子节点)在实际上最初需要单个环之时会不经意地创建多个环时，会频繁地产生问题。此外，脑分裂(split-brain) 情形会造成进一步的复杂度，其中两个环同时存在而不知晓彼此。这会在底层通信信道不被认为可靠时进一步造成困难，且例如会促成网络中的分区。另外，常规系统采用手动过程，这通常要求管理员最初确保没有现有节点，且随后显式地指令种子节点充当超级种子节点。概述以下提出了简化概述以便提供对在此描述的某些方面的基本理解。本概述不是所要求保护的主题的详尽的概述。它既不旨在标识出所要求保护的主题的关键或重要的要素，也不描绘其范围。其唯一的目的是以简化形式呈现一些概念，作为稍后呈现的更详细描述的序言。本主题发明对分布式环境中的种子节点的选出成员(quorum)强制施行预定条件——经由环形成组件，以确保可在任何给定时间从种子节点形成恰好一个与一组节点相关联的单个环。这一环形成组件在节点的生命周期中促成条件作为“引导”阶段，以减轻脑分裂情况(例如，在两个环被同时生成却在网络中彼此不知晓时)的不利影响。例如，该组节点可与预定应用程序相关联和/或由用户定义。此外，在此引导阶段期间，如果找到现有环，则种子节点可按与非种子节点所进行的相同的方式加入现有环。然而，如果没有检测到环，则引导阶段尝试推选一种子节点作为“超级种子节点”，该超级种子节点可形成新环，其中此新的超级种子节点表示新环的第一节点。由此，超级种子节点表示具有开始新环的权限的种子节点。根据特定方面，环形成组件确保通过强制施行以下条件来确保单个环的创建和/ 或存在性即，1)在引导阶段期间，恰好一个种子节点被选择作为超级种子节点；2)由种子节点的选出成员来推选超级种子节点；以及幻超级种子节点可仅在其确保来自选出成员中的所有种子节点的全局权证已期满之后才形成新环。另外，本主题发明还在节点与一组指定种子节点之间建立全局租约——其中如果节点具有与种子节点的选出成员的活跃租约，则其可以存活。在相关方面中，诸种子节点可在它们之间通信以推选形成此环的第一节点。因此， 环的存在性可取决于与之相关联的全局租约。在一个方面，种子节点可生成两种类型的权证；即，全局权证和超级权证，它们服从以下约束1.存活时间(TTL)要求，其中相关联TTL 存在且在预定时段之后期满；幻行为要求，其中可从接收方节点和发起方种子节点保证行为(行为的类型由权证的类型来决定)；幻转移要求，其中权证可被从一个节点传递到另一个节点；4)恢复要求，其中每个权证在其被发出之前需要被保存，以使得其可幸免于节点的重新引导(例如，发出权证表示发出节点许诺负起特定责任且由此其通常必须记住其已提供了什么承诺)力)期满的次序的要求；其中权证在其于接收方节点上期满之后在发出节点上期满。根据又一方面，全局权证表示由发出种子节点对接收方节点的以下条件，即1) 种子节点不尝试形成新环，除非其确信联盟中不存在唯一性全局权证的选出成员；以及2) 一旦丢失全局权证的选出成员，则节点终止其自己并重新加入环。类似地，此类权证是当在创建新的环时，从种子节点发出到种子节点的且仅在引导阶段期间发出。在此引导阶段期间，节点通常仅被允许对该节点持有其超级权证的节点发出全局权证。由此，一旦转移了与之相关联的超级权证，节点就放弃其发出全局权证的权限。为实现上述及相关目的，在此结合以下描述和附图描述了所要求保护的主题的某些说明性方面。这些方面指示可实践本主题的各种方式，它们均落在所要求保护的主题的范围之内。当结合附图阅读以下详细描述时，本发明的其他优点和新颖特征将变得显而易见。附图简述
图1图解了根据本发明的一方面的具有联盟的多个种子/非种子节点的系统的框图。图2图解了根据本发明的一方面的结合多个节点采用权证(Ticket)的系统的框3图解了根据本发明的一方面的节点之间的权证的交换。图4图解了根据本发明的示例性方面的实现引导阶段的环形成组件。图5图解了根据本发明的一方面的示例性引导阶段。图6图解了根据又一方面的选出成员中的权证交换的方法。图7图解了根据本发明的又一方面的形成环的方法。图8图解了根据又一方面的消息交换的特定方法。图9图解了可结合本发明的一方面使用的复原组件。图10图解了用于实现本发明的各方面的示例性环境。图11是根据本发明的一方面的可用于节点形成的又一示例性计算环境的示意性框图。详细描述现在将参考附图描述本发明的各方面，全部附图中相同的标号指的是相同或相应的元素。然而应该了解，附图及其相关详细描述不旨在将所要求保护的主题限于所公开的具体形式。相反，其意图是覆盖落在所要求保护的主题的精神和范围内的所有修改、等效和替换方案。图1图解了采用环形成组件115来确保在任何时间可从与之相关联的种子节点确切地形成一单个环的系统100的框图。一般而言，这个环还表示由一组节点构成的联盟，这组节点在其间协作以形成其中可系统地且高效地散布并定位信息的动态且可伸缩的网络。例如，参与联盟的节点可包括使用自反的、反对称的、传递的、总的、以及在节点身份域上定义的二元关系的排序列表。例如，排序列表的两个端可被联结，由此自己形成环。 这规定列表中的每个节点将其自己视为处于排序列表的中间。作为另一示例，列表可被双链接，以使得节点可在任一方向上遍历列表。此外，可从节点身份的值域至节点自身定义一对一映射函数。此类映射函数解决在映射并不紧凑时值域中节点的稀疏性。在另一示例中，参与联盟的每个节点可被指派0与恰当选择的上限(含该上限) 之间的自然数，其中这个范围不必是连贯的——例如，在指派给节点的数字之间可存在间隙。指派给节点的数字进一步充当其在环中的身份。此外，映射函数通过将位于两个节点身份之间的数字映射到具有在数值上更接近该数字的身份的节点来解决数字空间中的间隙。 因此，通过向每一节点指派均勻分布的数字，可确保该环的所有段都被均勻填充。另外，指示后继者、前导者、和邻域计算的节点可使用模运算来高效地完成。系统100还允许所有节点(1到η，η是整数)与种子节点之间的租约——由全局租约101表示一的实现。由此，本主题发明要求联盟中的每个节点维护与每个种子节点的租约，其中联盟具有公知的一组种子节点(1到m，m是整数)。全局租约的最大持续期可进一步由全局租约超时时段G(例如，预定时间持续期)来指定。在相关方面，节点一剩下少于全局租约的选出成员，其通常就必须终止(例如，自杀)并尝试再次重新加入环。这通常确保一旦种子节点的选出成员终止，环就可在随后在间隔G内终止。因此，如果种子节点的选出成员决定形成新环，则这可在时段G期满之后来实现——同时确保先前环中的所有节点已离开。种子节点的这些选出成员可在随后推选一个种子节点作为超级种子并安全地形成环。图2示出根据本主题发明的又一方面的示例性系统200。如图所例示的，可由每个种子节点来发出两种类型的定时权证全局权证202和超级权证204。一般而言，每个权证遵从以下约束，即1)相关联TTL，在该TTL之后其期满；2)来自接收方节点和发起方种子节点的行为保证，其中行为的类型由权证的类型来决定；幻权证可被从一个节点传递到另一个节点；4)每个权证在其被发出之前需要被保存，以使得其可幸免于节点的重新引导 (例如，发出权证可指示发出节点许诺负起特定责任且由此其必须记住其已给出了什么承诺)；以及幻权证应当在其于接收方节点上期满之后在发出节点上期满。此外，且如图2中所例示的，种子节点可发出两种类型的权证1.全局权证每个种子节点向联盟中的所有节点发出全局权证。存在需要与全局权证相关联的两个保证。a)种子节点将不尝试形成新环，除非其确信联盟中不存在唯一性全局权证的选出成员。b)在丢失全局权证的选出成员时，节点将终止或自杀且重新加入环。2.超级权证此类权证是当在创建新环时从种子节点发出到种子节点的且仅在引导阶段期间发出(如下文中详细描述的)。在引导阶段期间，节点仅被允许对该节点持有其超级权证的节点发出全局权证。在传递其超级权证时，节点丢失其发出全局权证的权限。图3图解了根据本主题发明的一个特定方面的节点A 302与节点B 304之间的特定权证交换。为了确保发出节点上的期满在接收方节点上的期满之后的约束，可通过响应消息发送权证。例如，图3假定节点B期望从节点A获得权证。最初且在310，节点B可向节点A发送包含T·的请求消息，Tsfil表示节点B的时钟上该消息被发送的时间。节点A 在对B的响应消息中附连权证311连同T发送。当节点B接收到权证311时，其通过Tsti-T
来减去权证中的时间。由于自权证发出起的所流逝的时间被界定为Τ·-Τ·，因此，这可确保该权证在其于A上期满之前于B上期满。图4图解了根据本主题发明的特定方面的实现引导阶段412的系统400，该系统包括环形成组件402。此类引导阶段412可与种子节点的生命周期的起始相关联，以便确保在任何给定时间，仅存在一个环。此外，在此引导阶段412期间，如果找到现有环，则种子节点可如非种子节点所进行的方式那样加入现有环。否则，此阶段尝试选择种子节点来作为超级种子节点。可在随后以新的超级种子节点作为第一节点来形成新环。此外，为了确保仅一个环存在于系统中，强行以下条件la)在引导阶段期间，仅一个种子节点被选择作为超级种子节点。lb)超级种子节点可仅由种子节点的选出成员来推选。Ic)超级种子节点可仅在其确保来自选出成员中的所有种子节点的全局权证已期满之后才形成新环。类似地，在引导阶段之后，如果节点丢失全局租约的选出成员，则该节点必须终止自己并重新加入环。因此，在任何给定时间点，在系统中仅可存在一个环。例如，在第一引导阶段，不存在早前的环——因而推选仅一个超级种子节点可保证存在单个环(以上的约束la)。作为另一示例，在考虑后继引导阶段时，新环可仅在推选超级种子节点之后开始存在，因为其是加入环的第一节点。此外，超级种子节点可仅由种子节点的选出成员来推选 (约束lb)。如果种子节点中的选出成员已推选了超级种子节点，则这指示该选出成员已离开了先前的环。在超级种子节点创建新环之前，可确保自种子节点中的选出成员发出其最后的全局权证起已经过了时间G。另外，这可进一步确保环的先前实例死亡，由此指示最多存在一个环。引导阶段图5图解了助益强制施行以上详述的约束的示例性方法500。虽然该示例性方法此处被示出并描述为表示各种事件和/或动作的一系列框，但本发明并不受所示出的这些框的排序的限制。例如，根据本发明，除了在此示出的次序之外，某些动作或事件可以按不同的次序发生和/或与其他动作或事件同时发生。此外，不是所有示出的框、事件或动作都是实施根据本发明的方法所必需的。此外，将会认识到根据本发明的该示例性方法和其他方法可以与在此图示并描述的方法相关联地实现，也可与未示出或描述的其他系统和装置相关联地实现。一般而言，种子节点可总是在引导阶段中开始。在此阶段期间且在510，其通过在502向每个其他种子节点周期性地发送SEEDPING (种子查验)消息来保持对其他种子节点的状态的跟踪。每个种子节点将用SEEDPINGRESPONSE(种子查验响应)消息来作出响应，以传达其当前阶段。如果种子节点告知另一种子节点已加入联盟——如在530处确定的，则其将仅仅在540处离开引导阶段并进入加入阶段，在那里，作为加入环的消息交换的部分，其将发送JOIN(WA)消息。否则，在550，种子节点保留在引导阶段中。一般而言，每个种子节点也保持对其拥有的超级权证的跟踪。典型地，当超级节点进入引导阶段时，其将拥有其自己的超级权证——(例外的是在种子节点向其他种子节点发出超级权证并在随后在超级权证期满之前重新引导，其中在重新启动之后不再拥有任何超级权证，因为其超级权证已被授予其他种子节点。其在先前发出的权证期满之后将再次拥有超级权证。)此外，超级权证可被转移。当节点接收到SEEDPING消息时，如果其在引导阶段，且发送者的节点id小于其自己的节点id，则其将在答复发送者的SEEDPINGRESPONSE 消息中转移其拥有的所有超级权证(若有的话)。当超级权证被转移时，相应的全局权证的期满时间也被转移。类似地，当种子节点在610处确定其(例如，至少)拥有超级权证的选出成员，且在620由选出成员中的种子节点发出的每个全局权证已期满时，则在630其可离开引导阶段作为超级节点。在640，其还将代表选出成员中的每个种子节点发出全局权证，且期满时间被设置成相应的超级权证的期满时间(如图7的方法700的动作710中例示的)。在 720，其将接着形成环，并向每个其他种子节点发送通知消息，以使得它们可在在730离开引导阶段以及在740进入加入阶段。维护全局租约根据又一方面，节点无需在引导阶段和加入阶段具有全局租约。在加入阶段结束时，加入方节点将从J0INRESP0NSE(加入响应)消息接收全局租约。从此时开始，如果节点曾丢失全局租约的选出成员，则其必须终止或自杀。全局租约最初由种子节点生成且在随后被转移(直接或间接地)到其他节点。应当理解，发出活动超级权证的种子节点丢失其发出全局权证的权限。然而，这存在例外，其中如果种子节点接收到比由自己发出的最近的全局权证更新鲜的全局权证，且该全局权证也比其最后的超级权证的发出时间更新鲜(但在超级权证期满之前)，则种子节点可作出结论其超级权证必须被超级种子消费且该超级种子必须已代表该种子节点授予全局权证。在此情形中，种子节点可忽略其发出的超级权证，并授予全局权证，如同超级权证已期满那样。在没有此优化的情况下，保证存在充分小的时间窗，在该时间窗中，对于此种子节点，在整个环中不存在有效全局权证，且由此全局租约丢失是很可能的。以下讨论是关于在每个节点上如何续订全局租约。由于全局权证仅由种子节点发出，因此权证需要抵达联盟中的每个节点。在一个方面中，可强制施行蛮力选项以便使每个节点维护与每个种子节点的租约。根据进一步方面，可在现有消息上承载租约。此类消息可包括1.租约消息，在相邻节点之间交换以进行失败检测。2. UPDATE/UPDATERESPONSE (更新/更新响应)，节点必须发送该消息来更新其路由表。此外，响应消息可包含正从一个节点转移到另一个的权证。每个节点还可维护包含全局权证的表并使用消息来分送其权证。图8示出了根据本主题发明的一方面的节点之间的消息交换的特定方法800。最初且在810，每个ESTABLISH LEASE/RENEW LEASE/UPDATE (建立租约/续订租约/更新)消息可包含发送时间1^送。接着，一旦接收到ESTABLISH LEASE/RENEW LEASE/UPDATE消息并决定发送响应(LEASERESPONSE/UPDATERESPONSE (租约响应/更新响应))，节点就可在820 将其具有的权证以及Tsfil附连到响应消息。在830且一旦接收权证，节点B就通过Tsti-T 来减去权证中的时间。接着，在840，节点可针对现有种子节点检测现有权证。因此，如果新权证中的时间大于现有权证中的时间，则在860，由新权证替代现有权证。在相关方面，如果权证在其期限的内，则此节点可尝试从种子节点直接获得新权证。此外，如果在任何权证期限，节点发现其权证的选出成员期满，则其终止或死亡并尝试重新加入环。图9图解了根据本主题方面的附加方面的实现复原组件904的分布式应用程序框架的系统900。复原组件904可通过路由节点发起复原协议。探针消息可被逐跳地发送， 直至其抵达另一路由节点，后者可在随后再次逐跳地回应探针消息，直至其抵达始发者。此外，反向路径上的每个节点可增大其复原版本，以防止其自己接受在其获得回声之前转移的令牌。在此系统下，节点N声明对在其后继者S与前导者P节点之间的id范围的所有权 (其中S、N、P是整数)。可使用模运算将所有权范围确定为(N-(N-P)/2，N+(S-N)/2]。这可指示P、N和S节点必须协定保证仅一个节点接受发送到目标id的消息，其中此协定暗示环一致性。应当理解，单单环一致性不足以满足安全性特性——例如，因为经分区的环可以是各自一致的，可是违背安全性特性。本主题方面的各个方面通常阻止环分区从一开始就发展。每个节点901维护其令牌操作的序号。序号被初始化为“0”且对于每个令牌操作是递增的。令牌操作是令牌创建、令牌拆分、令牌合并、和令牌复原。所有令牌转移消息指定接收方节点可接受所转移的令牌的目标令牌序号。如果所指定的目标序号不匹配其当前令牌序号，则接收方节点不能接受所转移的令牌。例如，环中的最初种子节点对整个ID空间创建有效令牌，并自动成为路由节点。此外，任何其他加入方节点尝试从现有最靠近的路由节点获得其令牌，因为其拥有该加入方节点的ID。加入方节点通过将令牌请求消息路由到其自己的ID来定位最靠近的节点。当路由节点接收来自具有ID X(X为整数)的非路由节点的令牌请求时，其通过使用其自己的ID与χ的中点值作为分区点来将有效令牌拆分成两个，并将包含χ的令牌转移到加入方节点同时保留另一个令牌。每当路由节点找到具有ID χ的新后继者或前导者路由节点，其就可进行检查以验证其令牌是否包含更靠近该新节点的ID空间。若包含，则其通过使用其自己的ID与χ的中点值作为分区点来将其令牌拆分成两个，并将包含χ的令牌转移到新节点，同时保留另一个令牌。每个路由节点可与其直接相邻节点周期性对话，以使得其具有执行此动作的无限机会。另外，当路由节点想要离开环时，其通过使用前导者和后继者ID的中点值作为分区点来将它的令牌拆成两个部分，并将两个令牌分别转移给前导者和后继者节点。此外，如果节点不拥有令牌且传入令牌范围包含其自己的ID或其令牌与传入令牌毗邻，则节点可接受传入令牌。如果其不接受令牌，则其应当拒绝该令牌，且若有可能，则建议所知晓的与传入令牌范围相毗邻的节点。已从其后继者和前导者节点两者获得成功获得其令牌的路由节点此后被称为操作节点。应当理解，操作节点也是路由节点且其保持为操作节点直至其重新引导。如在本申请中所使用的，术语“组件”、“系统”旨在表示计算机相关的实体，其可以是硬件、硬件和软件的组合、软件、或者执行中的软件。例如，组件可以是但不限于在处理器上运行的进程、处理器、对象、可执行代码、执行的线程、程序和/或计算机。作为说明，运行在服务器上的应用程序和服务器都可以是组件。一个或多个组件可以驻留在进程和/或执行的线程内，且组件可以位于一台计算机上和/或分布在两台或更多的计算机之间。此外，本发明的全部或部分可以使用产生控制计算机以实现所公开的发明的软件、固件、硬件或其任意组合的标准编程和/或工程技术而被实现为方法、装置或制品。例如，计算机可读介质可以包括但不限于磁存储设备(例如，硬盘、软盘、磁带……)、光盘(例如，紧致盘(⑶)、数字多功能盘(DVD)……)、智能卡和闪存设备(例如，卡、棒、钥匙驱动器……)。另外，应该理解，可以使用载波携带计算机可读的电子数据，如那些在传输和接收电子邮件或在访问诸如因特网或局域网(LAN)之类的网络时所使用的。当然，本领域的技术人员将会认识到，在不背离所要求保护的主题的范围或精神的前提下可以对这一配置进行许多修改。为给所公开的主题的各方面提供上下文，图10和11以及以下讨论旨在提供可以在其中实现所公开的主题的各方面的合适的环境的简要、概括的描述。尽管以上在运行在一台和/或多台计算机上的计算机程序的计算机可执行指令的一般上下文中描述了本主题，但本领域的技术人员将认识到，本发明也可结合其他程序模块实现。一般而言，程序模块包括执行特定任务和/或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等。而且，本领域的技术人员可以理解，本发明的方法可用其他计算机系统配置实现， 包括单处理器或多处理器计算机系统、小型计算设备、大型计算机、以及个人计算机、手持式计算设备(例如，个人数字助理(PDA)、电话、手表…)、基于微处理器或可编程消费产品或工业电子设备等。所示各方面也可在任务由通过通信网络链接的远程处理设备中执行的分布式计算环境中实现。然而，即使不是本发明的全部方面，至少也有本发明的部分方面可以在独立计算机上实现。在分布式计算环境中，程序模块可以位于本地和远程存储器存储设备中。参考图10，描述了用于实现本发明的各方面的示例性环境1010，其包括计算机 1012。计算机1012包括处理单元1014、系统存储器1016，以及系统总线1018。系统总线 1018将系统组件，包括，但不仅限于，系统存储器1016耦合到处理单元1014。处理单元1014 可以是各种处理器中的任何一种。也可以使用双微处理器及其他多处理器体系结构作为处理单元1014。系统总线1018可以是若干类型的总线结构中的任一种，包括存储器总线或存储器控制器、外围总线或外部总线、和/或使用各种可用的总线体系结构中的任一种的局部总线，可用的总线体系结构包括，但不限于，11位总线、工业标准体系结构(ISA)、微通道体系结构(MCA)、扩展ISA(EISA)、智能驱动器电子接口(IDE)、VESA局部总线(VLB)、外围部件互连(PCI)、通用串行总线(USB)、高级图形接口(AGP)、个人计算机存储卡国际协会总线 (PCMCIA)以及小型计算机系统接口(SCSI)。系统存储器1016包括易失性存储器1020和非易失性存储器1022。基本输入/ 输出系统￠10 被存储在非易失性存储器1022中，包含例如在启动过程中帮助在计算机1012内的元件之间传输信息的基本例程。例如，非易失性存储器1022可包括只读存储器 (ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器1020包括充当外部高速缓冲存储器的随机存取存储器(RAM)。作为示例而非限制，RAM以多种形式可用，诸如同步RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双倍数据速率SDRAM (DDR SDRAM)、增强型SDRAM (ESDRAM)、同步链路DRAM (SLDRAM)以及直接存储器总线(Rambus)RAM(DRRAM)。计算机1012还包括可移动的/不可移动的，易失性/非易失性的计算机存储介质。图10示出了盘存储IOM，其中这一盘存储IOM包括但不限于诸如磁盘驱动器、软盘驱动器、磁带驱动器、Jaz驱动器、Zip驱动器、LS-60驱动器、闪存卡、或者记忆棒等设备。另外，磁盘存储器IOM可包括存储介质——分开地或与其他存储介质相结合——包括，但不限于，诸如紧致盘ROM设备之类的光盘驱动器(⑶-ROM)、⑶可记录驱动器(⑶-R驱动器)、 ⑶可重写驱动器(⑶-RW驱动器)或数字多功能盘ROM驱动器(DVD-ROM)。为便于磁盘存储设备10M连接到系统总线1018，通常使用诸如接口 10 之类的可移动或不可移动接口。应该明白，图10描述了在用户和在合适的操作环境1010中描述的基本计算机资源之间担当中介的软件。这样的软件包括操作系统1(^8。可以存储在磁盘存储器10 上的操作系统10M用于控制和分配计算机系统1012的资源。系统应用程序1030利用由操作系统10 通过存储在系统存储器1016或者存储在盘存储10 上的程序模块1032和程序数据1034对资源的管理。应该明白，在此描述的各个组件可以用各种操作系统或操作系统的组合来实施。用户通过输入设备1036向计算机1012输入命令或信息。输入设备1036包括， 但不限于，诸如鼠标、跟踪球、指示笔、触摸板之类的指示设备、键盘、麦克风、游戏杆、游戏手柄、圆盘式卫星天线、扫描仪、TV调谐器卡、数码相机、数字视频摄像机、网络摄像头等等。 这些及其他输入设备通过系统总线1018经由接口端口 1038连接到处理单元1014。接口端口 1038包括，例如，串行端口、并行端口、游戏端口，以及通用串行总线(USB)。输出设备 1040与输入设备1036使用一些相同类型的端口。如此，例如，可以使用USB端口来向计算机1012提供输入，以及从计算机1012向输出设备1040输出信息。提供输出适配器1042 是为了示出存在如监视器、扬声器、和打印机以及其他输出设备1040等需要特殊适配器的一些输出设备1040。输出适配器1042包括，作为说明而不是限制，在输出设备1040和系统总线1018之间提供连接手段的视频卡和声卡。应该注意，其他设备和/或设备的系统提供诸如远程计算机1044之类的输入和输出两种能力。计算机1012可以使用到诸如远程计算机1044之类的一个或多个远程计算机的逻辑连接来在联网环境中操作。远程计算机1044可以是个人计算机、服务器、路由器、网络 PC、工作站、基于微处理器的电器、对等设备或其他公共网络节点等等，并且通常包括就计算机1012所描述的许多或全部元件。出于简洁起见，与远程计算机1044 —起，只示出了存储器设备1046。远程计算机1044通过网络接口 1048在逻辑上连接到计算机1012，然后， 经由通信连接1050在物理上连接。网络接口 1048涵盖诸如局域网(LAN)和广域网(WAN) 这样的通信网络。LAN技术包括光纤分布式数据接口(FDDI)、铜分布式数据接口(CDDI)、以太网/IEEE 802. 3、令牌环/IEEE 802. 5等。WAN技术包括，但不限于，点对点链路、电路交换网，如综合业务数字网(ISDN)及其变体，分组交换网络，以及数字订户线(DSL)。
通信连接1050是指用来将网络接口 1048连接到总线1018的硬件/软件。尽管为清楚起见通信连接1050被示为在计算机1012内部，但是，它也可以位于计算机1012外部。连接到网络接口 1048所需的硬件/软件包括，只作示例，内部和外部技术，诸如，调制解调器，包括常规电话级调制解调器、电缆调制解调器和DSL调制解调器、ISDN适配器，以及以太网卡。图11是根据本主题发明的一个方面的可用于实现作为联盟的部分的节点的样本计算环境1100的示意性框图。系统1100包括一个或多个客户机1110。客户机1110可以是硬件和/或软件(例如，线程、进程、计算设备)。系统1100还包括一个或多个服务器1130。服务器1130也可以是硬件和/或软件 (例如，线程、进程、计算设备)。服务器1130可以容纳各线程以通过例如利用在此描述的各组件执行转换。在客户机1110和服务器1130之间的一种可能的通信能够以适合在两个或更多计算机进程之间传输的数据分组的形式进行。系统1100包括通信框架1150，该通信框架1150可以被用来促进客户机1110和服务器1130之间的通信。客户机1110可在操作上连接至一个或多个客户机数据存储1160，客户机数据存储可用来存储对客户机1110本地的信息。同样地，服务器1130可在操作上连接到可以用来存储对服务器1130本地的信息的一个或多个服务器数据存储1140。以上描述的内容包括各个示例性方面。当然，出于描绘这些方面的目的而描述每一个可以想到的组件或方法的组合是不可能的，但本领域内的普通技术人员应该认识到， 许多进一步的组合和排列都是可能的。因此，在此描述的各方面旨在包括所有这些属于所附权利要求书的精神和范围内的改变、修改和变型。此外，就在说明书或权利要求书中使用术语“包括”而言，这一术语旨在以与术语 “包含”在被用作权利要求书中的过渡词时所解释的相似的方式为包含性的。
权利要求
1.一种计算机实现的方法，包括采用处理器来执行存储在计算机可读介质上的计算机可执行指令，以执行以下动作由与联盟环相关联的种子节点的选出成员来选择超级种子节点，所述超级种子节点具有形成新环的权限；以及在种子节点的生命周期内促成引导阶段，以确保可由所述超级种子节点在任何时间形成恰好一个与一组节点相关联的环。
2.如权利要求1所述的计算机实现方法，其特征在于，还包括在所述引导阶段选择一个种子节点来作为超级种子节点。
3.如权利要求1所述的计算机实现方法，其特征在于，还包括基于在所述节点与种子节点之间建立的全局租约来定义节点的存在性。
4.如权利要求3所述的计算机实现方法，其特征在于，还包括由所述超级种子节点在所述选出成员中的所有种子节点期满之后建立所述新环。
5.如权利要求3所述的计算机实现方法，其特征在于，还包括指定种子节点的存活时间(TTL)。
6.如权利要求2所述的计算机实现方法，其特征在于，还包括基于指派给所述节点的权证的类型来指定节点的行为的类型。
7.如权利要求3所述的计算机实现方法，其特征在于，还包括一旦丢失与所述节点相关联的全局权证的选出成员，就终止所述节点。
8.如权利要求3所述的计算机实现方法，其特征在于，还包括放弃所述节点发出全局权证的权限。
9.如权利要求7所述的计算机实现方法，其特征在于，还包括在所述节点的终止之后由所述节点尝试重新加入联盟环。
10.如权利要求7所述的计算机实现方法，其特征在于，还包括选择最大全局租约超时持续期。
11.如权利要求7所述的计算机实现方法，其特征在于，还包括在确保来自所述选出成员中的所有种子节点的全局权证已期满之后形成新环。
12.如权利要求7所述的计算机实现方法，其特征在于，还包括通过向其他种子节点周期性地发送消息来维护对其他种子节点的跟踪。
13.如权利要求7所述的计算机实现方法，其特征在于，还包括由种子节点离开所述引导阶段作为超级种子节点。
14.如权利要求13所述的计算机实现方法，其特征在于，还包括将所述选出成员中的所有种子节点的期满设为相应的超级权证的期满时间。
15.如权利要求13所述的计算机实现方法，其特征在于，还包括采用蛮力来维护与种子节点的租约。
16.如权利要求13所述的计算机实现方法，其特征在于，还包括为节点续订全局租约。
17.如权利要求13所述的计算机实现方法，其特征在于，还包括用新权证替换节点的现有权证。
18.一种计算机实现的系统，包括以下计算机可执行组件联盟，表示已建立信任的节点的集合；以及环形成组件，其在节点的生命周期中促成条件作为引导阶段，以确保可由超级种子节点在任何时间形成恰好一个新环。
19.如权利要求18所述的计算机实现方法，其特征在于，还包括指定所述节点的所述生命周期的全局权证。
20.一种计算机实现的系统，包括以下计算机可执行组件 用于表示已建立信任的节点的集合的装置；以及用于在节点的生命周期中发起引导阶段，以确保可由超级种子节点在任何时间形成恰好一个新环。
全文摘要
确保在任何给定时间从种子节点形成单个环的系统和方法。“引导”阶段被包括在节点的生命周期中，以减轻网络中的脑分裂情况的影响。在此引导阶段期间，如果找到现有环，则种子节点可按与非种子节点所进行的相同的方式加入现有环。如果没有检测到环，则引导阶段尝试推选种子节点为“超级种子节点”，其中可在随后通过以此新超级种子节点作为第一节点来形成新环。
文档编号G06F15/16GK102197387SQ200980142628
公开日2011年9月21日 申请日期2009年10月16日 优先权日2008年10月24日
发明者G·K·R·卡基法亚, L·迅, R·R·辛哈 申请人:微软公司
引导会合联盟
背景技术：
计算机技术(例如，微处理器速度、存储器容量、数据传输带宽、软件功能等)的进步一般有助于各行业中的计算机应用的增长。通常提供常被配置为服务器阵列的甚至更强大的服务器系统来服务源自诸如万维网等外部源的请求。当可用电子数据的数量增长时，以便于用户友好和快速数据搜索和检索的可管理方式来储存这些数据也变得愈发重要。当今，一种常见的方法是将电子数据存储在一个或多个数据库中。典型的数据库可被称为其数据被结构化使得计算机程序可例如快速搜索和选择期望的数据的有组织的信息集合。此外，在此类环境中，联盟指的是彼此之间已建立了信任且在其间实现用户身份信息的共享的一组组织或服务提供商。例如，联合身份是识别在企业边界之间以递增的频度比率移动的个体的分布式计算构造。联合身份的实际应用由需要同时管理若干不同种类的系统的大型跨国公司来表示。一般而言，当发起联盟或环的第一节点(例如，超级种子节点)在实际上最初需要单个环之时会不经意地创建多个环时，会频繁地产生问题。此外，脑分裂(split-brain) 情形会造成进一步的复杂度，其中两个环同时存在而不知晓彼此。这会在底层通信信道不被认为可靠时进一步造成困难，且例如会促成网络中的分区。另外，常规系统采用手动过程，这通常要求管理员最初确保没有现有节点，且随后显式地指令种子节点充当超级种子节点。概述以下提出了简化概述以便提供对在此描述的某些方面的基本理解。本概述不是所要求保护的主题的详尽的概述。它既不旨在标识出所要求保护的主题的关键或重要的要素，也不描绘其范围。其唯一的目的是以简化形式呈现一些概念，作为稍后呈现的更详细描述的序言。本主题发明对分布式环境中的种子节点的选出成员(quorum)强制施行预定条件——经由环形成组件，以确保可在任何给定时间从种子节点形成恰好一个与一组节点相关联的单个环。这一环形成组件在节点的生命周期中促成条件作为“引导”阶段，以减轻脑分裂情况(例如，在两个环被同时生成却在网络中彼此不知晓时)的不利影响。例如，该组节点可与预定应用程序相关联和/或由用户定义。此外，在此引导阶段期间，如果找到现有环，则种子节点可按与非种子节点所进行的相同的方式加入现有环。然而，如果没有检测到环，则引导阶段尝试推选一种子节点作为“超级种子节点”，该超级种子节点可形成新环，其中此新的超级种子节点表示新环的第一节点。由此，超级种子节点表示具有开始新环的权限的种子节点。根据特定方面，环形成组件确保通过强制施行以下条件来确保单个环的创建和/ 或存在性即，1)在引导阶段期间，恰好一个种子节点被选择作为超级种子节点；2)由种子节点的选出成员来推选超级种子节点；以及幻超级种子节点可仅在其确保来自选出成员中的所有种子节点的全局权证已期满之后才形成新环。另外，本主题发明还在节点与一组指定种子节点之间建立全局租约——其中如果节点具有与种子节点的选出成员的活跃租约，则其可以存活。在相关方面中，诸种子节点可在它们之间通信以推选形成此环的第一节点。因此， 环的存在性可取决于与之相关联的全局租约。在一个方面，种子节点可生成两种类型的权证；即，全局权证和超级权证，它们服从以下约束1.存活时间(TTL)要求，其中相关联TTL 存在且在预定时段之后期满；幻行为要求，其中可从接收方节点和发起方种子节点保证行为(行为的类型由权证的类型来决定)；幻转移要求，其中权证可被从一个节点传递到另一个节点；4)恢复要求，其中每个权证在其被发出之前需要被保存，以使得其可幸免于节点的重新引导(例如，发出权证表示发出节点许诺负起特定责任且由此其通常必须记住其已提供了什么承诺)力)期满的次序的要求；其中权证在其于接收方节点上期满之后在发出节点上期满。根据又一方面，全局权证表示由发出种子节点对接收方节点的以下条件，即1) 种子节点不尝试形成新环，除非其确信联盟中不存在唯一性全局权证的选出成员；以及2) 一旦丢失全局权证的选出成员，则节点终止其自己并重新加入环。类似地，此类权证是当在创建新的环时，从种子节点发出到种子节点的且仅在引导阶段期间发出。在此引导阶段期间，节点通常仅被允许对该节点持有其超级权证的节点发出全局权证。由此，一旦转移了与之相关联的超级权证，节点就放弃其发出全局权证的权限。为实现上述及相关目的，在此结合以下描述和附图描述了所要求保护的主题的某些说明性方面。这些方面指示可实践本主题的各种方式，它们均落在所要求保护的主题的范围之内。当结合附图阅读以下详细描述时，本发明的其他优点和新颖特征将变得显而易见。附图简述
图1图解了根据本发明的一方面的具有联盟的多个种子/非种子节点的系统的框图。图2图解了根据本发明的一方面的结合多个节点采用权证(Ticket)的系统的框3图解了根据本发明的一方面的节点之间的权证的交换。图4图解了根据本发明的示例性方面的实现引导阶段的环形成组件。图5图解了根据本发明的一方面的示例性引导阶段。图6图解了根据又一方面的选出成员中的权证交换的方法。图7图解了根据本发明的又一方面的形成环的方法。图8图解了根据又一方面的消息交换的特定方法。图9图解了可结合本发明的一方面使用的复原组件。图10图解了用于实现本发明的各方面的示例性环境。图11是根据本发明的一方面的可用于节点形成的又一示例性计算环境的示意性框图。详细描述现在将参考附图描述本发明的各方面，全部附图中相同的标号指的是相同或相应的元素。然而应该了解，附图及其相关详细描述不旨在将所要求保护的主题限于所公开的具体形式。相反，其意图是覆盖落在所要求保护的主题的精神和范围内的所有修改、等效和替换方案。图1图解了采用环形成组件115来确保在任何时间可从与之相关联的种子节点确切地形成一单个环的系统100的框图。一般而言，这个环还表示由一组节点构成的联盟，这组节点在其间协作以形成其中可系统地且高效地散布并定位信息的动态且可伸缩的网络。例如，参与联盟的节点可包括使用自反的、反对称的、传递的、总的、以及在节点身份域上定义的二元关系的排序列表。例如，排序列表的两个端可被联结，由此自己形成环。 这规定列表中的每个节点将其自己视为处于排序列表的中间。作为另一示例，列表可被双链接，以使得节点可在任一方向上遍历列表。此外，可从节点身份的值域至节点自身定义一对一映射函数。此类映射函数解决在映射并不紧凑时值域中节点的稀疏性。在另一示例中，参与联盟的每个节点可被指派0与恰当选择的上限(含该上限) 之间的自然数，其中这个范围不必是连贯的——例如，在指派给节点的数字之间可存在间隙。指派给节点的数字进一步充当其在环中的身份。此外，映射函数通过将位于两个节点身份之间的数字映射到具有在数值上更接近该数字的身份的节点来解决数字空间中的间隙。 因此，通过向每一节点指派均勻分布的数字，可确保该环的所有段都被均勻填充。另外，指示后继者、前导者、和邻域计算的节点可使用模运算来高效地完成。系统100还允许所有节点(1到η，η是整数)与种子节点之间的租约——由全局租约101表示一的实现。由此，本主题发明要求联盟中的每个节点维护与每个种子节点的租约，其中联盟具有公知的一组种子节点(1到m，m是整数)。全局租约的最大持续期可进一步由全局租约超时时段G(例如，预定时间持续期)来指定。在相关方面，节点一剩下少于全局租约的选出成员，其通常就必须终止(例如，自杀)并尝试再次重新加入环。这通常确保一旦种子节点的选出成员终止，环就可在随后在间隔G内终止。因此，如果种子节点的选出成员决定形成新环，则这可在时段G期满之后来实现——同时确保先前环中的所有节点已离开。种子节点的这些选出成员可在随后推选一个种子节点作为超级种子并安全地形成环。图2示出根据本主题发明的又一方面的示例性系统200。如图所例示的，可由每个种子节点来发出两种类型的定时权证全局权证202和超级权证204。一般而言，每个权证遵从以下约束，即1)相关联TTL，在该TTL之后其期满；2)来自接收方节点和发起方种子节点的行为保证，其中行为的类型由权证的类型来决定；幻权证可被从一个节点传递到另一个节点；4)每个权证在其被发出之前需要被保存，以使得其可幸免于节点的重新引导 (例如，发出权证可指示发出节点许诺负起特定责任且由此其必须记住其已给出了什么承诺)；以及幻权证应当在其于接收方节点上期满之后在发出节点上期满。此外，且如图2中所例示的，种子节点可发出两种类型的权证1.全局权证每个种子节点向联盟中的所有节点发出全局权证。存在需要与全局权证相关联的两个保证。a)种子节点将不尝试形成新环，除非其确信联盟中不存在唯一性全局权证的选出成员。b)在丢失全局权证的选出成员时，节点将终止或自杀且重新加入环。2.超级权证此类权证是当在创建新环时从种子节点发出到种子节点的且仅在引导阶段期间发出(如下文中详细描述的)。在引导阶段期间，节点仅被允许对该节点持有其超级权证的节点发出全局权证。在传递其超级权证时，节点丢失其发出全局权证的权限。图3图解了根据本主题发明的一个特定方面的节点A 302与节点B 304之间的特定权证交换。为了确保发出节点上的期满在接收方节点上的期满之后的约束，可通过响应消息发送权证。例如，图3假定节点B期望从节点A获得权证。最初且在310，节点B可向节点A发送包含T·的请求消息，Tsfil表示节点B的时钟上该消息被发送的时间。节点A 在对B的响应消息中附连权证311连同T发送。当节点B接收到权证311时，其通过Tsti-T
来减去权证中的时间。由于自权证发出起的所流逝的时间被界定为Τ·-Τ·，因此，这可确保该权证在其于A上期满之前于B上期满。图4图解了根据本主题发明的特定方面的实现引导阶段412的系统400，该系统包括环形成组件402。此类引导阶段412可与种子节点的生命周期的起始相关联，以便确保在任何给定时间，仅存在一个环。此外，在此引导阶段412期间，如果找到现有环，则种子节点可如非种子节点所进行的方式那样加入现有环。否则，此阶段尝试选择种子节点来作为超级种子节点。可在随后以新的超级种子节点作为第一节点来形成新环。此外，为了确保仅一个环存在于系统中，强行以下条件la)在引导阶段期间，仅一个种子节点被选择作为超级种子节点。lb)超级种子节点可仅由种子节点的选出成员来推选。Ic)超级种子节点可仅在其确保来自选出成员中的所有种子节点的全局权证已期满之后才形成新环。类似地，在引导阶段之后，如果节点丢失全局租约的选出成员，则该节点必须终止自己并重新加入环。因此，在任何给定时间点，在系统中仅可存在一个环。例如，在第一引导阶段，不存在早前的环——因而推选仅一个超级种子节点可保证存在单个环(以上的约束la)。作为另一示例，在考虑后继引导阶段时，新环可仅在推选超级种子节点之后开始存在，因为其是加入环的第一节点。此外，超级种子节点可仅由种子节点的选出成员来推选 (约束lb)。如果种子节点中的选出成员已推选了超级种子节点，则这指示该选出成员已离开了先前的环。在超级种子节点创建新环之前，可确保自种子节点中的选出成员发出其最后的全局权证起已经过了时间G。另外，这可进一步确保环的先前实例死亡，由此指示最多存在一个环。引导阶段图5图解了助益强制施行以上详述的约束的示例性方法500。虽然该示例性方法此处被示出并描述为表示各种事件和/或动作的一系列框，但本发明并不受所示出的这些框的排序的限制。例如，根据本发明，除了在此示出的次序之外，某些动作或事件可以按不同的次序发生和/或与其他动作或事件同时发生。此外，不是所有示出的框、事件或动作都是实施根据本发明的方法所必需的。此外，将会认识到根据本发明的该示例性方法和其他方法可以与在此图示并描述的方法相关联地实现，也可与未示出或描述的其他系统和装置相关联地实现。一般而言，种子节点可总是在引导阶段中开始。在此阶段期间且在510，其通过在502向每个其他种子节点周期性地发送SEEDPING (种子查验)消息来保持对其他种子节点的状态的跟踪。每个种子节点将用SEEDPINGRESPONSE(种子查验响应)消息来作出响应，以传达其当前阶段。如果种子节点告知另一种子节点已加入联盟——如在530处确定的，则其将仅仅在540处离开引导阶段并进入加入阶段，在那里，作为加入环的消息交换的部分，其将发送JOIN(WA)消息。否则，在550，种子节点保留在引导阶段中。一般而言，每个种子节点也保持对其拥有的超级权证的跟踪。典型地，当超级节点进入引导阶段时，其将拥有其自己的超级权证——(例外的是在种子节点向其他种子节点发出超级权证并在随后在超级权证期满之前重新引导，其中在重新启动之后不再拥有任何超级权证，因为其超级权证已被授予其他种子节点。其在先前发出的权证期满之后将再次拥有超级权证。)此外，超级权证可被转移。当节点接收到SEEDPING消息时，如果其在引导阶段，且发送者的节点id小于其自己的节点id，则其将在答复发送者的SEEDPINGRESPONSE 消息中转移其拥有的所有超级权证(若有的话)。当超级权证被转移时，相应的全局权证的期满时间也被转移。类似地，当种子节点在610处确定其(例如，至少)拥有超级权证的选出成员，且在620由选出成员中的种子节点发出的每个全局权证已期满时，则在630其可离开引导阶段作为超级节点。在640，其还将代表选出成员中的每个种子节点发出全局权证，且期满时间被设置成相应的超级权证的期满时间(如图7的方法700的动作710中例示的)。在 720，其将接着形成环，并向每个其他种子节点发送通知消息，以使得它们可在在730离开引导阶段以及在740进入加入阶段。维护全局租约根据又一方面，节点无需在引导阶段和加入阶段具有全局租约。在加入阶段结束时，加入方节点将从J0INRESP0NSE(加入响应)消息接收全局租约。从此时开始，如果节点曾丢失全局租约的选出成员，则其必须终止或自杀。全局租约最初由种子节点生成且在随后被转移(直接或间接地)到其他节点。应当理解，发出活动超级权证的种子节点丢失其发出全局权证的权限。然而，这存在例外，其中如果种子节点接收到比由自己发出的最近的全局权证更新鲜的全局权证，且该全局权证也比其最后的超级权证的发出时间更新鲜(但在超级权证期满之前)，则种子节点可作出结论其超级权证必须被超级种子消费且该超级种子必须已代表该种子节点授予全局权证。在此情形中，种子节点可忽略其发出的超级权证，并授予全局权证，如同超级权证已期满那样。在没有此优化的情况下，保证存在充分小的时间窗，在该时间窗中，对于此种子节点，在整个环中不存在有效全局权证，且由此全局租约丢失是很可能的。以下讨论是关于在每个节点上如何续订全局租约。由于全局权证仅由种子节点发出，因此权证需要抵达联盟中的每个节点。在一个方面中，可强制施行蛮力选项以便使每个节点维护与每个种子节点的租约。根据进一步方面，可在现有消息上承载租约。此类消息可包括1.租约消息，在相邻节点之间交换以进行失败检测。2. UPDATE/UPDATERESPONSE (更新/更新响应)，节点必须发送该消息来更新其路由表。此外，响应消息可包含正从一个节点转移到另一个的权证。每个节点还可维护包含全局权证的表并使用消息来分送其权证。图8示出了根据本主题发明的一方面的节点之间的消息交换的特定方法800。最初且在810，每个ESTABLISH LEASE/RENEW LEASE/UPDATE (建立租约/续订租约/更新)消息可包含发送时间1^送。接着，一旦接收到ESTABLISH LEASE/RENEW LEASE/UPDATE消息并决定发送响应(LEASERESPONSE/UPDATERESPONSE (租约响应/更新响应))，节点就可在820 将其具有的权证以及Tsfil附连到响应消息。在830且一旦接收权证，节点B就通过Tsti-T 来减去权证中的时间。接着，在840，节点可针对现有种子节点检测现有权证。因此，如果新权证中的时间大于现有权证中的时间，则在860，由新权证替代现有权证。在相关方面，如果权证在其期限的内，则此节点可尝试从种子节点直接获得新权证。此外，如果在任何权证期限，节点发现其权证的选出成员期满，则其终止或死亡并尝试重新加入环。图9图解了根据本主题方面的附加方面的实现复原组件904的分布式应用程序框架的系统900。复原组件904可通过路由节点发起复原协议。探针消息可被逐跳地发送， 直至其抵达另一路由节点，后者可在随后再次逐跳地回应探针消息，直至其抵达始发者。此外，反向路径上的每个节点可增大其复原版本，以防止其自己接受在其获得回声之前转移的令牌。在此系统下，节点N声明对在其后继者S与前导者P节点之间的id范围的所有权 (其中S、N、P是整数)。可使用模运算将所有权范围确定为(N-(N-P)/2，N+(S-N)/2]。这可指示P、N和S节点必须协定保证仅一个节点接受发送到目标id的消息，其中此协定暗示环一致性。应当理解，单单环一致性不足以满足安全性特性——例如，因为经分区的环可以是各自一致的，可是违背安全性特性。本主题方面的各个方面通常阻止环分区从一开始就发展。每个节点901维护其令牌操作的序号。序号被初始化为“0”且对于每个令牌操作是递增的。令牌操作是令牌创建、令牌拆分、令牌合并、和令牌复原。所有令牌转移消息指定接收方节点可接受所转移的令牌的目标令牌序号。如果所指定的目标序号不匹配其当前令牌序号，则接收方节点不能接受所转移的令牌。例如，环中的最初种子节点对整个ID空间创建有效令牌，并自动成为路由节点。此外，任何其他加入方节点尝试从现有最靠近的路由节点获得其令牌，因为其拥有该加入方节点的ID。加入方节点通过将令牌请求消息路由到其自己的ID来定位最靠近的节点。当路由节点接收来自具有ID X(X为整数)的非路由节点的令牌请求时，其通过使用其自己的ID与χ的中点值作为分区点来将有效令牌拆分成两个，并将包含χ的令牌转移到加入方节点同时保留另一个令牌。每当路由节点找到具有ID χ的新后继者或前导者路由节点，其就可进行检查以验证其令牌是否包含更靠近该新节点的ID空间。若包含，则其通过使用其自己的ID与χ的中点值作为分区点来将其令牌拆分成两个，并将包含χ的令牌转移到新节点，同时保留另一个令牌。每个路由节点可与其直接相邻节点周期性对话，以使得其具有执行此动作的无限机会。另外，当路由节点想要离开环时，其通过使用前导者和后继者ID的中点值作为分区点来将它的令牌拆成两个部分，并将两个令牌分别转移给前导者和后继者节点。此外，如果节点不拥有令牌且传入令牌范围包含其自己的ID或其令牌与传入令牌毗邻，则节点可接受传入令牌。如果其不接受令牌，则其应当拒绝该令牌，且若有可能，则建议所知晓的与传入令牌范围相毗邻的节点。已从其后继者和前导者节点两者获得成功获得其令牌的路由节点此后被称为操作节点。应当理解，操作节点也是路由节点且其保持为操作节点直至其重新引导。如在本申请中所使用的，术语“组件”、“系统”旨在表示计算机相关的实体，其可以是硬件、硬件和软件的组合、软件、或者执行中的软件。例如，组件可以是但不限于在处理器上运行的进程、处理器、对象、可执行代码、执行的线程、程序和/或计算机。作为说明，运行在服务器上的应用程序和服务器都可以是组件。一个或多个组件可以驻留在进程和/或执行的线程内，且组件可以位于一台计算机上和/或分布在两台或更多的计算机之间。此外，本发明的全部或部分可以使用产生控制计算机以实现所公开的发明的软件、固件、硬件或其任意组合的标准编程和/或工程技术而被实现为方法、装置或制品。例如，计算机可读介质可以包括但不限于磁存储设备(例如，硬盘、软盘、磁带……)、光盘(例如，紧致盘(⑶)、数字多功能盘(DVD)……)、智能卡和闪存设备(例如，卡、棒、钥匙驱动器……)。另外，应该理解，可以使用载波携带计算机可读的电子数据，如那些在传输和接收电子邮件或在访问诸如因特网或局域网(LAN)之类的网络时所使用的。当然，本领域的技术人员将会认识到，在不背离所要求保护的主题的范围或精神的前提下可以对这一配置进行许多修改。为给所公开的主题的各方面提供上下文，图10和11以及以下讨论旨在提供可以在其中实现所公开的主题的各方面的合适的环境的简要、概括的描述。尽管以上在运行在一台和/或多台计算机上的计算机程序的计算机可执行指令的一般上下文中描述了本主题，但本领域的技术人员将认识到，本发明也可结合其他程序模块实现。一般而言，程序模块包括执行特定任务和/或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等。而且，本领域的技术人员可以理解，本发明的方法可用其他计算机系统配置实现， 包括单处理器或多处理器计算机系统、小型计算设备、大型计算机、以及个人计算机、手持式计算设备(例如，个人数字助理(PDA)、电话、手表…)、基于微处理器或可编程消费产品或工业电子设备等。所示各方面也可在任务由通过通信网络链接的远程处理设备中执行的分布式计算环境中实现。然而，即使不是本发明的全部方面，至少也有本发明的部分方面可以在独立计算机上实现。在分布式计算环境中，程序模块可以位于本地和远程存储器存储设备中。参考图10，描述了用于实现本发明的各方面的示例性环境1010，其包括计算机 1012。计算机1012包括处理单元1014、系统存储器1016，以及系统总线1018。系统总线 1018将系统组件，包括，但不仅限于，系统存储器1016耦合到处理单元1014。处理单元1014 可以是各种处理器中的任何一种。也可以使用双微处理器及其他多处理器体系结构作为处理单元1014。系统总线1018可以是若干类型的总线结构中的任一种，包括存储器总线或存储器控制器、外围总线或外部总线、和/或使用各种可用的总线体系结构中的任一种的局部总线，可用的总线体系结构包括，但不限于，11位总线、工业标准体系结构(ISA)、微通道体系结构(MCA)、扩展ISA(EISA)、智能驱动器电子接口(IDE)、VESA局部总线(VLB)、外围部件互连(PCI)、通用串行总线(USB)、高级图形接口(AGP)、个人计算机存储卡国际协会总线 (PCMCIA)以及小型计算机系统接口(SCSI)。系统存储器1016包括易失性存储器1020和非易失性存储器1022。基本输入/ 输出系统￠10 被存储在非易失性存储器1022中，包含例如在启动过程中帮助在计算机1012内的元件之间传输信息的基本例程。例如，非易失性存储器1022可包括只读存储器 (ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器1020包括充当外部高速缓冲存储器的随机存取存储器(RAM)。作为示例而非限制，RAM以多种形式可用，诸如同步RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双倍数据速率SDRAM (DDR SDRAM)、增强型SDRAM (ESDRAM)、同步链路DRAM (SLDRAM)以及直接存储器总线(Rambus)RAM(DRRAM)。计算机1012还包括可移动的/不可移动的，易失性/非易失性的计算机存储介质。图10示出了盘存储IOM，其中这一盘存储IOM包括但不限于诸如磁盘驱动器、软盘驱动器、磁带驱动器、Jaz驱动器、Zip驱动器、LS-60驱动器、闪存卡、或者记忆棒等设备。另外，磁盘存储器IOM可包括存储介质——分开地或与其他存储介质相结合——包括，但不限于，诸如紧致盘ROM设备之类的光盘驱动器(⑶-ROM)、⑶可记录驱动器(⑶-R驱动器)、 ⑶可重写驱动器(⑶-RW驱动器)或数字多功能盘ROM驱动器(DVD-ROM)。为便于磁盘存储设备10M连接到系统总线1018，通常使用诸如接口 10 之类的可移动或不可移动接口。应该明白，图10描述了在用户和在合适的操作环境1010中描述的基本计算机资源之间担当中介的软件。这样的软件包括操作系统1(^8。可以存储在磁盘存储器10 上的操作系统10M用于控制和分配计算机系统1012的资源。系统应用程序1030利用由操作系统10 通过存储在系统存储器1016或者存储在盘存储10 上的程序模块1032和程序数据1034对资源的管理。应该明白，在此描述的各个组件可以用各种操作系统或操作系统的组合来实施。用户通过输入设备1036向计算机1012输入命令或信息。输入设备1036包括， 但不限于，诸如鼠标、跟踪球、指示笔、触摸板之类的指示设备、键盘、麦克风、游戏杆、游戏手柄、圆盘式卫星天线、扫描仪、TV调谐器卡、数码相机、数字视频摄像机、网络摄像头等等。 这些及其他输入设备通过系统总线1018经由接口端口 1038连接到处理单元1014。接口端口 1038包括，例如，串行端口、并行端口、游戏端口，以及通用串行总线(USB)。输出设备 1040与输入设备1036使用一些相同类型的端口。如此，例如，可以使用USB端口来向计算机1012提供输入，以及从计算机1012向输出设备1040输出信息。提供输出适配器1042 是为了示出存在如监视器、扬声器、和打印机以及其他输出设备1040等需要特殊适配器的一些输出设备1040。输出适配器1042包括，作为说明而不是限制，在输出设备1040和系统总线1018之间提供连接手段的视频卡和声卡。应该注意，其他设备和/或设备的系统提供诸如远程计算机1044之类的输入和输出两种能力。计算机1012可以使用到诸如远程计算机1044之类的一个或多个远程计算机的逻辑连接来在联网环境中操作。远程计算机1044可以是个人计算机、服务器、路由器、网络 PC、工作站、基于微处理器的电器、对等设备或其他公共网络节点等等，并且通常包括就计算机1012所描述的许多或全部元件。出于简洁起见，与远程计算机1044 —起，只示出了存储器设备1046。远程计算机1044通过网络接口 1048在逻辑上连接到计算机1012，然后， 经由通信连接1050在物理上连接。网络接口 1048涵盖诸如局域网(LAN)和广域网(WAN) 这样的通信网络。LAN技术包括光纤分布式数据接口(FDDI)、铜分布式数据接口(CDDI)、以太网/IEEE 802. 3、令牌环/IEEE 802. 5等。WAN技术包括，但不限于，点对点链路、电路交换网，如综合业务数字网(ISDN)及其变体，分组交换网络，以及数字订户线(DSL)。
通信连接1050是指用来将网络接口 1048连接到总线1018的硬件/软件。尽管为清楚起见通信连接1050被示为在计算机1012内部，但是，它也可以位于计算机1012外部。连接到网络接口 1048所需的硬件/软件包括，只作示例，内部和外部技术，诸如，调制解调器，包括常规电话级调制解调器、电缆调制解调器和DSL调制解调器、ISDN适配器，以及以太网卡。图11是根据本主题发明的一个方面的可用于实现作为联盟的部分的节点的样本计算环境1100的示意性框图。系统1100包括一个或多个客户机1110。客户机1110可以是硬件和/或软件(例如，线程、进程、计算设备)。系统1100还包括一个或多个服务器1130。服务器1130也可以是硬件和/或软件 (例如，线程、进程、计算设备)。服务器1130可以容纳各线程以通过例如利用在此描述的各组件执行转换。在客户机1110和服务器1130之间的一种可能的通信能够以适合在两个或更多计算机进程之间传输的数据分组的形式进行。系统1100包括通信框架1150，该通信框架1150可以被用来促进客户机1110和服务器1130之间的通信。客户机1110可在操作上连接至一个或多个客户机数据存储1160，客户机数据存储可用来存储对客户机1110本地的信息。同样地，服务器1130可在操作上连接到可以用来存储对服务器1130本地的信息的一个或多个服务器数据存储1140。以上描述的内容包括各个示例性方面。当然，出于描绘这些方面的目的而描述每一个可以想到的组件或方法的组合是不可能的，但本领域内的普通技术人员应该认识到， 许多进一步的组合和排列都是可能的。因此，在此描述的各方面旨在包括所有这些属于所附权利要求书的精神和范围内的改变、修改和变型。此外，就在说明书或权利要求书中使用术语“包括”而言，这一术语旨在以与术语 “包含”在被用作权利要求书中的过渡词时所解释的相似的方式为包含性的。
权利要求
1.一种计算机实现的方法，包括采用处理器来执行存储在计算机可读介质上的计算机可执行指令，以执行以下动作由与联盟环相关联的种子节点的选出成员来选择超级种子节点，所述超级种子节点具有形成新环的权限；以及在种子节点的生命周期内促成引导阶段，以确保可由所述超级种子节点在任何时间形成恰好一个与一组节点相关联的环。
2.如权利要求1所述的计算机实现方法，其特征在于，还包括在所述引导阶段选择一个种子节点来作为超级种子节点。
3.如权利要求1所述的计算机实现方法，其特征在于，还包括基于在所述节点与种子节点之间建立的全局租约来定义节点的存在性。
4.如权利要求3所述的计算机实现方法，其特征在于，还包括由所述超级种子节点在所述选出成员中的所有种子节点期满之后建立所述新环。
5.如权利要求3所述的计算机实现方法，其特征在于，还包括指定种子节点的存活时间(TTL)。
6.如权利要求2所述的计算机实现方法，其特征在于，还包括基于指派给所述节点的权证的类型来指定节点的行为的类型。
7.如权利要求3所述的计算机实现方法，其特征在于，还包括一旦丢失与所述节点相关联的全局权证的选出成员，就终止所述节点。
8.如权利要求3所述的计算机实现方法，其特征在于，还包括放弃所述节点发出全局权证的权限。
9.如权利要求7所述的计算机实现方法，其特征在于，还包括在所述节点的终止之后由所述节点尝试重新加入联盟环。
10.如权利要求7所述的计算机实现方法，其特征在于，还包括选择最大全局租约超时持续期。
11.如权利要求7所述的计算机实现方法，其特征在于，还包括在确保来自所述选出成员中的所有种子节点的全局权证已期满之后形成新环。
12.如权利要求7所述的计算机实现方法，其特征在于，还包括通过向其他种子节点周期性地发送消息来维护对其他种子节点的跟踪。
13.如权利要求7所述的计算机实现方法，其特征在于，还包括由种子节点离开所述引导阶段作为超级种子节点。
14.如权利要求13所述的计算机实现方法，其特征在于，还包括将所述选出成员中的所有种子节点的期满设为相应的超级权证的期满时间。
15.如权利要求13所述的计算机实现方法，其特征在于，还包括采用蛮力来维护与种子节点的租约。
16.如权利要求13所述的计算机实现方法，其特征在于，还包括为节点续订全局租约。
17.如权利要求13所述的计算机实现方法，其特征在于，还包括用新权证替换节点的现有权证。
18.一种计算机实现的系统，包括以下计算机可执行组件联盟，表示已建立信任的节点的集合；以及环形成组件，其在节点的生命周期中促成条件作为引导阶段，以确保可由超级种子节点在任何时间形成恰好一个新环。
19.如权利要求18所述的计算机实现方法，其特征在于，还包括指定所述节点的所述生命周期的全局权证。
20.一种计算机实现的系统，包括以下计算机可执行组件 用于表示已建立信任的节点的集合的装置；以及用于在节点的生命周期中发起引导阶段，以确保可由超级种子节点在任何时间形成恰好一个新环。
全文摘要
确保在任何给定时间从种子节点形成单个环的系统和方法。“引导”阶段被包括在节点的生命周期中，以减轻网络中的脑分裂情况的影响。在此引导阶段期间，如果找到现有环，则种子节点可按与非种子节点所进行的相同的方式加入现有环。如果没有检测到环，则引导阶段尝试推选种子节点为“超级种子节点”，其中可在随后通过以此新超级种子节点作为第一节点来形成新环。
文档编号G06F15/16GK102197387SQ200980142628
公开日2011年9月21日 申请日期2009年10月16日 优先权日2008年10月24日
发明者G·K·R·卡基法亚, L·迅, R·R·辛哈 申请人:微软公司
最新回复(0)