可靠快速的数据广播方法及系统

摘要

本发明公开了一种可靠可扩展的且时间步为0(2)的广播信息到通信网络中的其他计算机节点的系统和方法。根据一个方面，通过0(1)步广播数据到网络的所有节点后，所述系统和方法提供一个分布式可靠性协议以保证其传送，且只需要额外的0(1)步。因此，不同于负责数据传送的根或合作根的现有方法，网络中的每一个节点负责传送消息到一个伙伴/近邻节点。该广播系统和方法能够作为大多数的集/散操作的标准部件（building block），以及给所有已知的包括硬件支持组播/广播功能的并行计算机系统提供明显的性能优势。

权利要求

1.一种在复数个节点之间共享数据的方法，其特征在于，包括步骤：向复数个节点中的每个节点提供一个接收伙伴ID和一个发送伙伴ID，所述接收伙伴ID从所述复数个节点中的其他节点中指定发射机节点以从所述发射机节点接收共享数据的接收确认，所述发送伙伴ID从所述复数个节点中的其他节点中指定接收机节点以将共享数据的接收确认发送到所述接收机节点；

从所述复数个节点中的一个源节点发送所述共享数据到所述复数个节点中的其它节点；以及在每一所述节点接收到所述共享数据时，

使用所述接收伙伴ID发送共享数据的接收确认到其各自指定的发射机节点，以及使用所述发送伙伴ID等待来自其各自指定的接收机节点的共享数据的接收确认，而没有考虑所述复数个节点中的哪个是源节点，直至具有指定接收机节点ID的第二个确认被接收共享数据的节点所接收，所述共享数据才会被认为已经被接收所述共享数据的节点所接收，每个发送所述共享数据或发送所述确认的步骤在一个时间步内完成。

2.如权利要求1所述的方法，其特征在于，所述共享数据在2个时间步内完成。

3.如权利要求2所述的方法，其特征在于，还包括步骤，在每一所述节点接收到所述共享数据时：当在预设的时间间隔内没有接收到所述共享数据的接收确认时，发送所述共享数据到具有所述发送伙伴ID的所述指定的接收机节点。

4.如权利要求3所述的方法，其特征在于，所述预设的时间间隔大于两个时间步。

5.如权利要求3所述的方法，其特征在于，一个时间步为在其它节点传送所述共享数据以及接收所述共享数据的时间间隔。

6.如权利要求1所述的方法，其特征在于，所述数据发送步骤通过使用广播消息而被执行。

7.如权利要求1所述的方法，其特征在于，所述数据发送步骤通过使用组播消息而被执行。

8.如权利要求1所述的方法，其特征在于，所述节点包含一个并行计算系统。

9.如权利要求1所述的方法，其特征在于，所述节点包含一个网络连接存储高速缓存。

10.如权利要求1所述的方法，其特征在于，所述节点包含一个虚拟内存磁盘。

11.如权利要求1所述的方法，其特征在于，所述节点包含一个存储区域网。

12.如权利要求1所述的方法，其特征在于，所述节点包含一个计算机集群。

13.如权利要求1所述的方法，其特征在于，所述提供步骤被执行使得：所述复数个节点中的每个所述节点与唯一指定的发送机节点和唯一指定的接收机节点相关联，所述唯一指定的发送机节点具有用于向所述节点发送确认的接收伙伴ID，所述唯一指定的接收机节点具有用于等待确认的发送伙伴ID，所述确认用以发送以响应接收发送的共享数据。

14.如权利要求1所述的方法，其特征在于，所述源节点是所述复数个节点中的任意一个。

15.一种用于在复数个节点之间共享数据的系统，其特征在于，复数个节点中每一个节点具有节点ID，所述系统包括：所述复数个节点中的源节点，配置成传送共享数据到至少一个第一节点、第二节点以及第三节点，每个所述第一节点、所述第二节点以及所述第三节点配置成每个节点包括：所述第一节点、所述第二节点或所述第三节点中一个节点的指定发送节点ID；

所述第一节点、所述第二节点或所述第三节点中一个节点的指定接收节点ID，所述发送节点ID及所述接收节点ID识别所述第一节点、所述第二节点或所述第三节点中的不同节点；

设置在每个节点的网络接口，用于接收包含所述共享数据的消息；并且，直至具有指定接收机节点ID的第二个确认被接收共享数据的节点所接收，所述共享数据才会被认为已经被接收所述共享数据的节点所接收，即使所述接收所述共享数据的节点没有发送所述共享数据到具有指定的接收节点ID的节点。

16.如权利要求15所述的系统，其特征在于，所述消息通过使用广播消息而被发送。

17.如权利要求15所述的系统，其特征在于，所述消息通过使用组播消息而被发送。

18.如权利要求15所述的系统，其特征在于，所述源节点为所述第一节点、所述第二节点或所述第三节点中的一个。

说明书

可靠快速的数据广播方法及系统

技术领域

[0001] 本发明涉及数据广播，更具体地涉及一种包括复数个节点的系统内的可靠快速的信息广播。

背景技术

[0002] 并行计算系统，例如计算机集群、对称多处理（SMP）计算机及其他架构正变得越来越买得起和物有所值，从而广泛应用。许多这样的系统通过产品和相对廉价的计算机部件连接高速网络（例如LAN，专有互连等）或系统区域网络（SANs）而构建。这些类型的计算系统比得上历史性的昂贵的定制的超级计算机。

[0003] 大部分规划模型提供写并行应用，以及多数并行应用使用集/散通信操作。此外，多数科学的应用唯一依靠集/散操作来实现它们的通信。因此，提供一种高性能的且可扩展的集/散通信方法以广播信息，对基于并行技术系统的产品的操作和成功来说是至关重要的。

[0004] 提供一种高性能的且可扩展的集/散通信方法的一个关键问题是可靠地且快速地广播一条消息。现有的方法需要至少O(log n)步以可靠地传送一条消息到n个节点。这意味着对于可靠数据广播的努力和时间，增加以对数方式的节点数量。

[0005] 图1A～1C为详细显示了现有技术中通过并行计算体制以广播数据的方框图。如图1A所示，广播数据的最简单的方法是将数据一个接一个的发送到群里的每个接收机。当节点的总数为n时，这个方法需要n次发送和n次接收。因此需要0(2n)步。

[0006] 图1所示的方法的直接改进是使用特定的互联连接（例如，以太网，无限带宽Infiniband等）的广播/组播功能。然而，这种广播和组播的协议支持仅仅是不可靠的数据报网络服务，其不能保证可靠的数据传送。

[0007] 因此需要使用硬件支持广播/组播功能，以及额外的可靠协议来代替。所有已知的和现有技术中实施这种可靠协议的方法为（1）一种简单的方法，其中每个接收机发送一个确认直接回到根处（root）；或（2）一种可逆的基于树的确认方法，其中树叶（leaves）开始发送确定到合作根（co-roots）和最后通知主根（main root）所传送的消息。

[0008] 例如，结合如图1B所示的第一种改进，根节点使用组播，同时其他节点等待它。当接收到消息时，发送一个确定（ACK）返回到该根节点。该根阻滞（blocks）和等待所有将被接收的ACK。如果不是所有的ACK在特定的时间内到达，则超时以及再传送消息。这种方式为0(n+l)，其中发送为0(1)以及返回确定为O(n)。

[0009] 第二种改进是使用基于树型结构的算法，其基于点到点的通信操作。与滚雪球原理相似，根发送（消息）到多个节点，反过来，每个节点发送每个（消息）给多个节点，直至到达树叶。在基于树型结构的方法中，到达树叶节点的步骤数随着典型地使用对数方式0(log n)的节点的总数n而增加。

[0010] 更特别地，如图1C所示，与图1B的方案相反，通过根发送机的广播后，避免一连串的ACK全部在相同时间到达（hitting）发送机（如我们所知的“ACK内爆（ACK implosion）情况），使用一种分级结构实现ACK收集，从而分散负担到多个节点上。用于收集ACK的基于树的结构中，所有节点形成带根的树结构，且作为树的根。中间节点负责为它们的孩子收集ACK。一种称为合作根（co-root）的方案，其中除了根节点以外，还选择其他节点的子集作为合作根以通过可靠方式接收数据。剩下的节点被称为树叶节点。每一个根以及合作根负责一组树叶节点并实施上述操作。这种类型的方法使用0(log n)步给n个节点。

[0011] 虽然基于树型结构的方案提高了吞吐量（throughput），随着节点数量的增加仍然会增加延迟（尽管通过log n的减慢对数因子）。

[0012] 以及存在即使在基于树的实施的额外延迟的原因。例如，广播通常作为一种阻滞操作被实施，以保证该操作在通信缓冲器能够被重新使用前不会返回到根节点。相应地，可靠协议将重发消息以及通信缓冲器只好保持最初的消息直到最后一个节点已经确定接收。对于接收节点来说，该操作仅仅在广播数据已经传送到各自的接收缓冲器以后才返回。这个阻滞要求因此能够产生明显的延迟，尤其当节点的数量增加以及通信中断发生的可能性相应的增加。

[0013] 基于树型结构的方法的另一个缺点是，如果期望发送广播数据的中间节点为忙时，它们延迟发送，从而给应用的执行时间带来不利的影响。

[0014] 相应地，渴望获得一种可靠的方法，其仅仅需要固定数量的步骤以实现并行计算系统中的散/集通信功能，以及允许使用基于集群计算机的简单产品以实现和定制的超级计算机相比的相似的性能。

发明内容

[0015] 公开了一种可靠可扩展的且时间步为0(2)的广播信息到通信网络中的其他计算机节点的系统和方法。根据一个方面，通过0(1)步广播数据到网络的所有节点后，所述系统和方法提供一个分布式可靠性协议以保证其传送，且只需要额外的0(1)步。因此，不同于负责数据传送的根或合作根的方法，网络中的每一个节点负责传送消息到一个伙伴/近邻节点。该广播系统和方法能够作为大多数的集/散操作的标准部件（building block），以及给所有已知的包括硬件支持组播/广播功能的并行计算机系统提供明显的性能优势。

[0016] 根据一个实施例，一种在复数个节点之间共享数据的方法，包括发送数据到所有节点；以及在每一所述节点接收到所述数据时，发送响应于所述发送数据的一个确认到其各自指定的发射机节点，所述指定的发射机节点为其他节点中的一个。

[0017] 根据另一个实施例，一种用于在复数个节点之间共享数据的装置，包括用于发送数据到所有节点的装置；以及在每一所述节点接收到所述数据时，用于发送响应于所述发送数据的一个确认到其各自指定的发射机节点的装置，所述指定的发射机节点为其他节点中的一个。

[0018] 根据另一个实施例，一种用于在复数个节点之间共享数据的系统，在每一个节点中，包括指定的发送节点ID、指定的接收节点ID、用于接收包含共享数据的消息的网络接口，以及用于使用指定的发送节点ID以促使发送响应于被接收的消息的第一个确认的可靠性协议。

附图说明

[0019] 图1A～1C为显示了现有技术中实现可靠数据广播的方法的方框图；

[0020] 图2为显示了本发明的实施广播方法和系统的一个实例系统的方框图；

[0021] 图3为详细显示了本发明的广播方法的一个实例的流程图；以及

[0022] 图4A～4E为进一步说明了本发明的广播方法和系统的一个实例应用的示意图。

具体实施方式

[0023] 下面将结合附图详细描述本发明的系统和方法，其中结合实施例说明以使得本技术领域的人员能够实践该系统和方法。显然，以下的附图和实施例并非限制本发明的保护范围为特定的实施例，其他的实施例可以通过交换部分或全部描述的或显示的要素。另外，系统和方法中的一些元素可以部分地或完全地使用已知的部件来实施，仅仅描述这些已知的部件中的必须部分以理解本发明的保护范围，而已知的部件中的其他部分不再详述。

[0024] 在本说明书中，显示一个单一的部件的实施例不一定理解为限制的；相反，包括多个相同的部件的其他实施例也是可能的，反之亦然，除非另外明确指出。另外，申请人并不希望说明书以及权利要求书中的任何术语被认为是属于不寻常的或特别的含义，除非本身有明确地说明。进一步的，本发明还包括在这里通过显示方式引用的已知部件的现在以及将来所知的等效物。

[0025] 一般的，公开的系统和方法提供了一种从根本上不同的方法以广播数据到并行计算系统的所有过程。而现有的系统和方法需要根发送过程以等待来自所有过程的ACK被收集（或直接地或通过分级结构），本发明公开的系统和方法将ACK的收集功能分散到系统中的所有节点。

[0026] 根据第一个实施例，系统中的每一个节点包括一个指定的发送伙伴/近邻（partner/neighbor）节点以及一个指定的接收伙伴/近邻节点。一旦一个节点从它的指定的接收伙伴/近邻节点中接收到一个消息时，它表现为好像它本身就是最初的组播发送机。它等待来自它的指定的发送伙伴/近邻的ACK，并且如果发生超时情况下再次发送该消息。

[0027] 虽然这里公开的数据广播技术可能发现尤其适合应用到并行计算系统中，但是本发明主张的原理并不局限于这个应用，本领域的技术人员通过本发明的公开信息的教导后显然可运用到其他应用中。

[0028] 图2为显示了一个包括数据广播功能的系统的方框图。如图2所示，系统200包括复数个节点或者处理器202-1～202-n，彼此通过网路204相互连接。

[0029] 数据广播功能能够具有多种应用，而图2中的简图只用于说明而非限制作用。该系统200能够实施并行计算系统，例如计算机集群、对称多处理(SMP)系统或者其他体系结构，而且还能够实施共享的以及分布式的存储系统，例如网络存储（network attached storage，NAS）缓存（caches）、虚拟存储磁盘和连续的存储器组，进一步的还能够实施如SAN同步和文件锁定以及软件集群的方案。处理器202可以为任何类型的计算机或者处理器，其使用任何类型的操作系统，例如Windows,Linux,Solaris或Unix etc。网路204可以为任何类型的高速（high speed）或其他网路，例如以太网、无线宽带、专用连接（proprietary interconnects）、交换结构（switch fabrics）、总线（buses）或者系统区域网路(SANs)。

[0030] 图2更详细地显示了处理器202的实施例。如图2所示，处理器202包括一个可靠性协议功能220和一个网络接口222，该网路接口222包括发送缓冲器和接收缓冲器。该处理器202还包括局部存储器或其他存储器224，其被所述可靠性协议功能220使用，其包括发送搭档ID、接收搭档ID以及组播ID。应该注意的是，该处理器202可以包括其他硬件和软件部件，其类型并非必然理解为这里所公开的概念，因此为了清楚这里省略对其说明。

[0031] 可靠性协议功能220优选作为软件被实施，该软件与特定的操作系统处理器202的计算环境一致，且可靠性协议功能220提供分布式的信息广播确认收集方法，这些在下面会结合存储器224中的ID进行详细描述。该协议功能进一步优选为结合使用例如IP、UDP或者无限宽带的网路协议类型而实施，而该系统和方法是可以服从具有任何基于包（packet-based）的协议的应用，且该应用优选具有广播或组播功能，以及可能被设计为，例如，在OSI堆的第5级操作。

[0032] 网络接口222结合系统运行的特定网络204以及处理器202的操作系统和CPU功能的要求来实施。例如，如果网络为以太网局域网（Ethernet LAN），网络接口222则为一个以太网兼容的接口。本领域技术人员可以理解和实施特定的网络接口以适合给出的实施例。保存在存储器224内的ID也结合系统运行的特定网络224实施。例如，在一些实施例中，所述ID可以是IP地址，而所述组播ID可以是子网。在其他实施例中，所述ID能够作为专用表、机器级或其他类型地址而被保存。

[0033] 应注意系统200内的所有的处理器202并非必须设置一样。然而，系统内的每一节点含有的可靠性协议功能220优选为与其计算功能一致。

[0034] 图3为显示了并行计算系统中的广播数据方法的一个实例的流程图。本领域的技术人员通过这个实例的教导后，将明白如何实施这个方法到不同的处理器系统和软件环境中。

[0035] 如图3所示，处理开始于步骤S302，通过识别系统内的所有节点以及通知每一节点它们的指定的发送伙伴/近邻节点和指定的接收伙伴/近邻节点。这可以通过多种途径完成并且依赖于网络的类型以及所使用的协议。但是，优选地，该识别步骤确保系统内的所有节点被识别为另一个节点的指定接收机以及另外一个（不同的）节点的指定发送机。例如，系统内的每一个节点给定一个具有节点总数的一个模数（modulus）的识别序列号，而它的接收伙伴/近邻节点可以为下一个更高数字节点，而它的发送伙伴/近邻节点可以为下一个更低数字节点。可选的，每个节点之间的距离（或时延）是可测的，并且基于节点间的最小距离（或时延）来决定分配伙伴/近邻节点。在其他实施例中，每一个节点还可以获得系统内的所有其他节点的ID，无论是否为一组标识符的详细列表，例如IP组播组、子网掩码、广播列表等。在获悉所述这些ID后，他们将被存储在每个对应的节点的存储器224内。

[0036] 在步骤S304，在处理过程中，系统允许任何节点在任何时刻广播数据。当一个节点准备发送数据时，执行步骤S306，其中该数据组播到系统内的所有节点，优选使用特定网络的广播或组播技术。

[0037] 当没有发送消息时则执行步骤S308，在该步骤中，确定是否接收到与系统相关的新的广播消息。如果节点没有发送或接收消息，则转至步骤S304。

[0038] 当接收到系统的一个新的广播消息时，除非节点它本身发送步骤S306中的消息，否则该节点发送一个确认（ACK）到其指定的接收伙伴/近邻节点（步骤S310）。进一步的，在步骤S312中，发送消息的节点以及接收消息的每一个节点，均存储该消息到本地的且与其指定的发送伙伴/近邻节点相关的发送缓冲器内。

[0039] 在步骤S314中，在缓冲消息后，该节点等待来自其指定的发送伙伴/近邻节点的确认（ACK）（不管其是否实际发送其发送缓冲器内的消息）。如果该节点接收到来自发送伙伴/近邻节点的一个ACK，其删除发送缓冲器内的消息，因为该ACK提供了该消息已被传送的确认。

[0040] 如果在超时时间（在步骤S314中确定的）内没有接收到指定的发送伙伴/近邻节点的确认（ACK），该节点重发消息到其指定的发送伙伴/近邻节点（步骤S316），并再次等待ACK(步骤S314)。这个行为能够保证消息传送到伙伴/近邻节点，该伙伴/近邻节点通过第一次组播没有接收到该消息。

[0041] 图4A～4E进一步显示了该广播方法的实施例。

[0042] 如图4A所示，与现有技术的方法相似，发送机节点s使用网络硬件提供的广播/组播功能而在网络上发送数据。当消息传送后，每一个节点r将消息本地存储到发送缓冲器内。但是，与现有技术的方法不同的是，接收消息的每一个节点还假装（pretends）其发送消息到指定的发送伙伴/近邻节点，以及从指定的接收伙伴/近邻节点中接收消息。

[0043] 如图4B所示，在假装发送机的情况下，每一个节点等待来自其指定的发送伙伴/近邻节点的确认（ACK）。如果一个节点接收到来自其伙伴/近邻节点的确认，则删除发送缓冲器内的消息，因为其接收到消息已经被传送的确认。在作为接收机的情况下，每一个节点发送一个确认(ACK)返回到其指定的接收伙伴/近邻节点。

[0044] 如果没有丢失消息，所有节点大约同时发送确认(ACK)，这样需要单个时间步骤O(l)。在这种情况下，所有节点接收一个ACK,删除发送缓冲器内的消息以及继续该程序。

[0045] 该系统和方法的一个重要方面是其在数据丢失或者丢落且一个或多个节点没有接收到组播数据的情况下，提供自动恢复能力。在这个情况下，假装发送机的节点将撞上超时，因为其没有接收一个ACK。

[0046] 更特别地，如图4C所示，节点402和404没有接收到来自它们对应的指定的发送伙伴/近邻节点406和408的ACK。这样，该假装发送机的节点402和404将重发（re-send）该消息到发送伙伴/近邻节点406和408以及再次等待ACK。这个行为能够保证消息传送到伙伴/近邻节点，该伙伴/近邻节点通过第一次组播没有接收到该消息。

[0047] 公开的系统和方法能够克服极端的情况，即在连续的伙伴/近邻节点中多于一个节点没有接收到最初的组播消息。在这种情况下，该可靠性方法将继续工作并弥补差距。

[0048] 更特别地，返回参考图4C，节点410从不接收到最初的消息，以及其指定的发送伙伴/近邻节点408也没有接收到最初的消息。但是，如上所述，以及如图4D所示，节点408最终接收以及确认来自节点404的重发消息。当接收到来自节点404的消息时，节点408启动其计时器以接收它自己的确认，当时间到达还没有接收到来自它自己的发送伙伴/近邻节点410的确认。那么，它“重发”该消息（即使最初它从没发送过一个）到节点410。相应的，如图4E所示，节点410最终确认接收到最后的消息时，那么将连同它自己的指定的发送伙伴/近邻节点412并通过执行如上所述的同一过程以完成整个循环。

[0049] 以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也视为本发明的保护范围。