用多领导者选举和领导委托进行负载平衡

摘要

一种用于与分布式计算系统所提供的应用程序或服务结合使用的负载平衡方法可通过从一组参与者中为与所述应用程序或所述服务相关联的多个任务中的每一者选举领导者来开始。响应于检测到运行特定任务的信号或某一其他指示，所述特定任务的所选举领导者可将运行所述特定任务的责任委托给特定参与者。所述特定参与者在随后发现所述特定任务的责任已经被委托给它时通过运行所述任务来作出响应。在一些实施方案中，任务的所选举领导者可将运行所述任务的责任委托给最小负载参与者。

说明书

技术领域

本公开涉及信息处置系统，并且更具体地涉及分布式信息处置系统中的负载平衡。

背景技术

随着信息的价值和使用不断增加，个体和企业寻求另外的方式来处理和存储信息。用户可用的一个选项是信息处置系统。信息处置系统通常处理、编译、存储和/或传达用于商业、个人或其他目的的信息或数据，从而允许用户利用这些信息的价值。由于技术和信息处置需要和要求在不同的用户或应用之间有所不同，因此信息处置系统也可能在以下方面有所不同：处置什么信息，如何处置信息，处理、存储或传达多少信息，以及可多快速且多高效地处理、存储或传达信息。信息处置系统的变化允许信息处置系统是通用的或者针对特定用户或特定用途(诸如财务事务处理、航班预定、企业数据存储或全球通信)进行配置。另外，信息处置系统可包括可被配置为处理、存储和传达信息的多种硬件和软件部件，并且可包括一个或多个计算机系统、数据存储系统和联网系统。

信息处置系统可被实现为分布式计算系统或更简单地说实现为集群，其中一组节点(在本文中有时称为集群节点以将它们与本文也描述的树形数据结构的节点区分开)被配置为运行与由集群提供的应用程序或服务相关联的任务。集群可实现分布式配置服务(诸如Apache ZooKeeper服务器)以提供或支持集群的配置管理、数据同步和命名服务功能性。每个节点可构成不同的信息处置系统，其中的一些或全部可具有类似或等效的计算和存储资源和能力。分布式配置服务可支持各种领导者选举算法中的任一种以标识有资格监督分布式任务的执行的可能大量集群节点中的一者。尽管常规的领导者选举算法可适合于其预期目的，即，为任务选举领导者，但是它们可能无法考虑或在集群内实现期望的工作负载分布。

发明内容

根据在以下描述中公开的主题，一种用于与分布式计算系统所提供的应用程序或服务结合使用的负载平衡方法可通过从一组参与者中为与所述应用程序或服务相关联的多个任务中的每一者选举领导者来开始。在一些实施方案中，选举步骤可包括多领导者选举过程，所述多领导者选举过程为多个任务中的每一者选举领导者，其中每个参与者是N或N+1个任务的领导者，其中N是由任务数量T和参与者数量P决定的非负整数。在至少一个实施方案中，如果P＝T，则每个参与者是1个任务的领导者。如果P>T，即，参与者多于任务，则每个参与者是0或1个任务的领导者。如果T>P，则每个参与者是int[T/P]个或int[T/P]+1个任务的领导者。示例性多领导者选举资源在2021年12月27日提交的共同待决的美国申请第17/562094号中描述，该申请以引用的方式全文并入本文。

每个参与者可以是不同的信息处置系统，诸如机架安装式服务器。所述一组参与者可对应于集群的节点。在一些实施方案中，集群节点可用一个或多个超融合基础架构(HCI)设备来实现。

响应于检测到运行特定任务的信号或某一其他指示，所述特定任务的所选举领导者可将运行所述特定任务的责任委托给特定参与者。所述特定参与者在随后发现所述特定任务的责任已经被委托给它时通过运行所述任务来作出响应。在一些实施方案中，任务的所选举领导者可将运行所述任务的责任委托给最小负载参与者，即，负载量不大于所述集群中的任何其他参与者的负载量的参与者。

在采用ZooKeeper或另一种分布式配置服务的实施方案中，每个参与者可在两个树形数据结构(在本文中称为负载树和委托树)中创建对应节点。每个负载树节点的值可周期性地更新，使得每个负载树节点具有指示对应参与者的当前或最近负载量的值。每个节点的负载量值可四舍五入或以其他方式估计，以防止因负载量的相对较小改变而引起的过度委托改变。为了说明，从0至99的负载量值可除以10并截断以产生从0至9的负载量指示符。负载树节点可被创建有临时属性，其中当对应的参与者崩溃或退出时，临时节点自动地从负载数据结构移除。

任务的所选举领导者可将指示委托的任务的值存储到负责的参与者(即，被委托负责任务的参与者)的委托树节点中。委托树节点可被配置有观察特征，所述观察特征在节点的值改变时用信号通知对应的参与者。因此，当任务的所选举领导者将标识任务的值存储在负责的参与者的委托树中时，负责的参与者将检测到值的改变并且可以开始运行适用任务。

从本文所包括的附图、描述和权利要求中，本公开的技术优点对本领域技术人员来说可显而易见。实施方案的目的和优点将至少通过权利要求中特别地指出的要素、特征和组合来达成和实现。

将理解，以上大体描述和以下详细描述都是示例并且是解释性的，而不是对本公开中阐述的权利要求的限制。

附图说明

通过参考结合附图进行的以下描述，可获得对本发明实施方案及其优点的更全面理解，在附图中，相同的附图标记指示相同的特征，并且其中：

图1示出了高度可靠的分布式计算系统；

图2示出了由分布式配置管理器维护的树形数据结构；

图3示出了负载树形数据结构；

图4示出了委托树形数据结构；

图5示出了多领导者选举和委托方法的流程图；以及

图6示出了示例性信息处置系统。

具体实施方式

通过参考图1至图6最佳地理解示例性实施方案及其优点，其中除非另外明确地指示，否则相似的附图标记用于指示相似且对应的部分。

出于本公开的目的，信息处置系统可包括可操作来计算、分类、处理、传输、接收、检索、产生、切换、存储、显示、表明、检测、记录、再现、处置或利用任何形式的信息、情报或数据以用于商业、科学、控制、娱乐或其他目的的任何工具或工具集合。例如，信息处置系统可以是个人计算机、个人数字助理(PDA)、消费型电子装置、网络存储装置或任何其他合适的装置，并且可在大小、形状、性能、功能性和价格方面有所不同。信息处置系统可包括存储器、一个或多个处理资源，诸如中央处理单元(“CPU”)、微控制器，或者硬件或软件控制逻辑。信息处置系统的附加部件可包括一个或多个存储装置、用于与外部装置进行通信的一个或多个通信端口以及各种输入/输出(“I/O”)装置(诸如键盘、鼠标和视频显示器)。信息处置系统还可包括可操作来在各种硬件部件之间传输通信的一条或多条总线。

另外地，信息处置系统可包括用于控制例如硬盘驱动器、网络电路、存储器装置、I/O装置和其他外围装置和/或与它们通信的固件。例如，管理程序和/或其他部件可包括固件。如在本公开中使用，固件包括嵌入在用于执行预定义任务的信息处置系统部件中的软件。固件通常存储在非易失性存储器或在断电时不会丢失存储的数据的存储器中。在某些实施方案中，与信息处置统部件相关联的固件存储在一个或多个信息处置系统部件可访问的非易失性存储器中。在相同或可选的实施方案中，与信息处置系统部件相关联的固件存储在专用于该部件且构成该部件的一部分的非易失性存储器中。

出于本公开的目的，计算机可读介质可包括可在一段时间内保留数据和/或指令的任何工具或工具集合。计算机可读介质可包括但不限于：存储介质，诸如直接存取存储装置(例如，硬盘驱动器或软盘)、顺序存取存储装置(例如，磁带磁盘驱动器)、光盘、CD-ROM、DVD、随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)和/或快闪存储器；以及通信介质，诸如电线、光纤、微波、无线电波和其他电磁和/或光学载波；和/或前述项的任何组合。

出于本公开的目的，信息处置资源可广义地指代信息处置系统的任何部件系统、装置或设备，包括但不限于：处理器、服务处理器、基本输入/输出系统(BIOS)、总线、存储器、I/O装置和/或接口、存储资源、网络接口、主板和/或信息处置系统的任何其他部件和/或元件。

在以下描述中，通过示例阐述了细节以便于讨论所公开的主题。然而，本领域普通技术人员将明白，所公开的实施方案是示例性的，而不是所有可能实施方案的详述。

贯穿本公开，带连字符形式的附图标记是指元件的特定实例，并且不带连字符形式的附图标记泛指该元件。因此，例如，“装置12-1”是指一个装置类别的实例，所述装置类别可统称为“装置12”，并且其中任一者可泛称为“装置12”。

如本文所使用，当两个或更多个元件被称为彼此“耦合”时，此类术语指示此类两个或更多个元件在适用的情况下处于电子通信、机械连通(包括热和流体连通、热连通或机械连通)，无论是间接还是直接连接、是具有还是不具有中间元件都是如此。

现在参考附图，图1示出了被实现为高度可靠的分布式计算系统的信息处置系统100，所述分布式计算系统包括由三个不同的节点111-0至111-2组成的集群110，所述节点被配置为提供应用程序或服务。

每个节点111可对应于在硬件、软件或两者的组合中实现的不同的信息处置资源。在至少一个实施方案中，每个节点111包括服务器类计算系统，诸如机架安装式服务器。在一些实施方案中，每个节点111包括相同或基本上类似的硬件和操作系统配置。

每个节点111可包括融合基础架构(CI)或超融合基础架构(HCI)资源(未明确地描绘)，所述资源利于每个节点111的单独计算、存储和联网资源的集成和集中式管理。在至少一个实施方案中，节点111可用来自Dell Technologies的VxRail设备实现。尽管图1示出了具有三个节点111的集群110，但是本领域普通技术人员将了解，集群110可包括更多或更少的节点111。

顾名思义，分布式配置管理器102为集群110提供集中式配置管理。分布式配置管理器102可用Apache zookeeper服务器实现，或者可包括Apache zookeeper服务器的特征。在此类实施方案中，分布式配置管理器102支持并管理一个或多个数据结构，包括但不必限于一个或多个树形数据结构，所述数据结构实现类似于文件系统的分层名称空间以利于集群110的部署和管理。在此类实施方案中，每个节点111可包括用于与那些数据结构交互的客户端资源。与Apache ZooKeeper术语一致，集群节点(诸如图1所示的节点111)在本文中可简称为节点，而与分布式配置管理器102所维护的树形数据结构(在下文讨论)相关联的树形结构节点在本文中可称为znode。另外，由于每个节点111可有助于或参与应用程序或服务的部署，因此节点111在本文中可称为参与者。

与集群(诸如集群111)相关联的应用程序或服务可包含多个不同的任务。如先前所提出，在此类部署中可能期望提供一个或多个资源来标识和指定，即，选举特定节点作为每个任务的领导者。当有必要或期望执行任务时，该任务的所选举领导者进行执行该任务所必要的操作。

所示的分布式配置管理器102包括以高效且可靠的方式选举任务领导者的多领导者选举资源104。在至少一个实施方案中，多领导者选举资源104确保在集群节点之间的领导者的最佳均匀分布。出于本公开的目的，领导者的最佳均匀分布可指代其中每个参与者都被指定为N个或N+1个任务的所选举领导者的分布，其中N是由参与者数量(P)和任务数量(T)决定的非负整数。例如，如果T＝P，则每个参与者是一个任务的所选举领导者。如果参与者多于任务，即，P>T，则每个参与者是0或1个任务的所选举领导者。如果任务多于参与者，即，T>P，那么每个参与者是K个或K+1个任务的所选举领导者，其中K＝int[T/P]，并且int[x]是返回小于或等于x的最大整数的floor函数。

如先前所提出，高效且可靠的多领导者选举过程的实现可能无法确保集群111内的高效工作负载分布。图1所示的分布式配置管理器102包括用于解决这个问题的委托资源。更具体地，图1所示的分布式配置管理器102包括为分布式任务提供可靠且轻型的负载管理工具的最小负载委托资源106。

现在转到图2、图3和图4，示出了用于实现多领导者选举资源104(图2)和最小负载委托资源106(图3和图4)的示例性树形数据结构。

图2示出了由分布式配置管理器102维护的树形数据结构200。在下面的描述中，与本领域普通技术人员将熟悉的Apache ZooKeeper术语一致，树形数据结构200的节点被称为znode。然而，Apache ZooKeeper术语在以下描述中的使用是说明性的而不是限制性的，并且不将所公开的主题限于采用Apache ZooKeeper的实现方式。

图2的树形数据结构200包括根节点201和根节点201的两个子树。图2中描绘的两个子树包括第一子树(在本文中称为参与者树210)和第二子树(在本文中称为领导者树220)。图2所示的参与者树210包括对应于图1中的每个节点111的参与者znode 211。每个参与者znode211具有唯一标识符212，所述唯一标识符可由分布式配置管理器102确定。作为示例，在分布式配置管理器102(图1)内包括Apache ZooKeeper的实施方案中，可通过序列特征来促进唯一标识符212的生成，所述序列特征利于通过将整数附加到唯一标识符的基本部分并且随后使整数递增来创建每个节点的唯一标识符。

图2所示的领导者树220包括对应于与由集群110(图1)提供的应用程序或服务相关联的多个任务中的每一者的znode 221。每个领导者树节点221包括适用任务的唯一标识符222和指示已经被选举为适用任务的领导者的参与者节点的值223。因此，例如，znode221-1的值(223-1)P_1指示节点111-1(图1)是与znode的唯一标识符222-1相关联的任务A的所选举领导者。

图2示出了其中三个参与者(P_0、P_1和P_2)的集群负责执行与应用程序或服务相关联的5个任务(A、B、C、D和E)的示例。图2描绘了在已经执行并完成多领导者选举过程之后参与者树210和领导者树220的状态。作为领导者选举过程的结果，任务A和B的所选举领导者是P-1，如由领导者节点222-1和222-2的值223-1和223-2所指示，任务C的所选举领导者是P-2，以此类推。与多领导者选举资源104的至少一些实施方案一致，每个参与者是1个或2个任务的所选举领导者。

图3和图4示出了用于实现用于运行适用任务的基于实时负载的委托的附加树形数据结构。图3示出了包括znode 301的负载树300，其中每个znode与唯一标识符302和负载值303相关联。每个负载树znode 301中的值303是对应的节点111(图1)的负载量的定量指示符。在所示的示例中，有效负载量值可以是在0至9的范围内，其中值9指示比值8更多的负载量，值8指示比值7更多的负载量，以此类推。每个节点111可周期性地运行后台进程来更新znode 301中的每一者中的负载量值303。负载量值可用于将任务的运行委托给特定参与者。在采用最小负载委托的实施方案中，例如，要委托的下一任务将被委托给作为最小负载参与者的参与者P_2。在至少一些实施方案中，负载量树znode 301被配置有临时设置，如果对应的参与者崩溃或退出，则所述临时设置致使znode被移除。

图4示出了包括对应于每个参与者的znode 401的示例性委托树400。当任务的所选举领导者使用最小负载标准或某一其他标准将对应的任务委托给特定参与者时，设定委托znode 401的值。如在图4中所描绘，例如，作为任务A的所选举领导者的参与者P_1响应于确定应执行任务A而基于图3中的负载量值303来确定参与者中的哪个是最小负载的。参与者P_1然后通过将委托znode 401-2的值设定为A来将任务A的实际执行委托给参与者P_2。在至少一些实施方案中，委托znode 401被配置有观察设置，每当对应的委托znode 401的值改变时，所述观察设置便向适用参与者传递消息。因此，当参与者P_1将委托znode 401-2的值设定为“A”时，参与者P_2检测到值的改变并且通过运行在其委托znode 401-2的值中指示的任务来作出响应。

下面列出了特定任务的所选举领导者在领导者检测到应执行对应任务时可执行的示例性代码。该示例性代码调用delegateTask函数或子例程，所述函数或子例程调用idelNode函数来确定哪个参与者是当前最小负载的并且然后通过设定对应于最小负载参与者的委托znode的值以指示要运行的任务来将适用任务的运行委托给最小负载参与者。

while(True):

{

idleNode＝findMostIdleNode()

delegateTask(idleNode,taskName)

sleep(n_sec)

}

已经被委托任务的参与者检测其委托znode 401中的值的改变并且通过运行任务来作出响应。用于该过程的示例性代码在下面阐述。

callBackFun():

{

taskName＝getTaskName()

runTask(taskName)

return

}

现在参考图5，以流程图格式示出了多领导者选举和委托方法500。所示的方法500包括从一组集群节点或参与者中为多个任务中的每一者选举领导者(框502)。集群可被配置为支持分布式应用程序或服务，并且集群节点可用来运行与应用程序或服务相关联的任务。当特定任务的所选举领导者检测到(框504)有必要或期望执行任务时，领导者可执行委托过程，诸如本文所述的基于负载的委托，并且将任务委托(框506)给最适合的参与者，诸如最小负载参与者。在一些实施方案中，可通过负载树数据结构来促进委托确定，所述负载树数据结构包括用于每个参与者的节点，其中每个节点具有指示节点的当前或最近负载量的值。在至少一些实施方案中，可通过采用委托树来将委托传达(框510)给负责的参与者，所述委托树具有用于每个参与者的节点，其中委托树节点被配置有观察属性，所述观察属性在节点的值改变时致使每个节点通知其对应的参与者。因此，当任务的所选举领导者将任务委托给参与者时，领导者将标识委托的任务的值存储在负责的参与者的委托树节点中。负责的参与者将检测到其委托树节点的值已经改变并且然后可基于存储在委托树节点中的值确定并执行适用任务。通过这种方式，多领导者选举过程可用基于负载的委托过程进行加强以同时地平衡领导角色在参与者之间的分布并且平衡每个参与者的负载量。

现在参考图6，图1至图4所示的元件中的任一者或多者可被实现为由图6所示的信息处置系统600例示的信息处置系统或在所述信息处置系统内实现。所示的信息处置系统包括通信地耦合到存储器资源610和输入/输出集线器620的一个或多个通用处理器或中央处理单元(CPU)601，各种I/O资源和/或部件通信地耦合到所述输入/输出集线器。在图6中明确地描绘的I/O资源包括网络接口640(通常被称为NIC(网络接口卡))、存储资源630以及附加的I/O装置、部件或资源650，作为非限制性示例，所述附加的I/O装置、部件或资源包括键盘、鼠标、显示器、打印机、扬声器、传声器等。所示的信息处置系统600包括基板管理控制器(BMC)660，所述基板管理控制器除了其他特征和服务之外还提供可耦合到管理服务器(未描绘)的带外管理资源。在至少一些实施方案中，BMC 660可管理信息处置系统600，甚至在信息处置系统600断电或通电至待机状态时也是如此。BMC660可包括处理器、存储器、与信息处置系统600的带内网络接口分开且物理地隔离的带外网络接口，和/或其他嵌入式信息处置资源。在某些实施方案中，BMC 660可包括或可以是远程访问控制器(例如，戴尔远程访问控制器或集成式戴尔远程访问控制器)或者机箱管理控制器的组成部分。

本公开涵盖本领域普通技术人员将设想的对本文的示例实施方案的所有改变、替换、变化、变更和修改。类似地，在适当时，所附权利要求涵盖本领域普通技术人员将设想的对本文的示例实施方案的所有改变、替换、变化、变更和修改。此外，在所附权利要求中对被适配成、被布置成、能够、被配置为、被启用以、可操作以或操作以执行特定功能的设备或系统或者设备或系统的部件的引用涵盖所述设备、系统或部件，无论是否激活、开启或解锁所述设备、系统或部件或者所述特定功能，只要所述设备、系统或部件被适配成、被布置成、能够、被配置为、被启用以、可操作以或操作以执行特定功能即可。

本文中叙述的所有示例和条件语言都意图用于教学目的，以帮助读者理解发明人为了推进本技术而促成的本公开和构思，并且被解释为不限于此类具体地叙述的示例和条件。尽管已经详细地描述了本公开的实施方案，但是应理解，在不脱离本公开的精神和范围的情况下，可对本公开进行各种变化、替换和变更。