有分布式计算节点，数据库表中有一组由行表示的计算任务(每个任务一行)：
- 一个节点没有其他节点的信息：无法与其他节点对话，甚至不知道还有多少其他节点
- 可以添加和删除节点，节点可能会死亡并重新启动
- 仅连接到数据库的节点
- 每个节点的任务没有限制
- 任务池不是有限的，新任务总是到达
- 一个节点通过用一些时间戳标记该行来接受任务，这样其他节点就不会考虑它，直到该时间戳之后经过一些超时(以防节点死亡和任务未完成)
目标是在节点之间均匀分配任务。为了实现这一点，我需要定义一些常见的任务获取算法：当一个节点启动时，需要执行多少任务？
如果一个节点承担所有可用任务，则其中一个节点总是繁忙，而其他节点则空闲。所以这不是一个选择。
一个好的方法是每个节点以一定的延迟执行任务1乘1。所以每个节点周期性地(一段时间内一次)检查是否有空闲任务，并且只执行一个任务。这样，在启动后不久，所有节点都会获取或多或少均匀分布的所有任务。然而，缺点是，由于延迟，处理最后一个任务需要一些时间(假设有10000个任务，10个节点，延迟为1秒：从开始到完成所有任务需要10000个任务*1秒/10个节点=1000秒)。此外，分布是不确定的，并且偏斜是可能的。
问题：什么类型/类别的算法可以解决这样的问题，允许使用某些同步点(本例中为数据库)快速、均匀地分配任务，而无需选举领导者？
例如：节点使用一些表格来宣布他们想要执行的任务，然后在一些协调步骤后，他们达成共识并开始处理，等等。
所以这归结为几个需要考虑的因素。
- 当前总共有多少任务可用
- 目前总共接受了多少任务
- 节点在过去X分钟内接受了多少任务
- 节点在过去X分钟内完成了多少任务
- 行字段可以修改吗？(添加了一个字段)
- 节点在完成当前任务后是否可以请求更多任务，或者必须立即分发所有任务
我倾向于做以下事情：
- 如果可行，添加一个"；节点标识符"；字段(UUID)添加到具有行的表中。节点在运行时会生成UUID节点标识符。当它接受一个任务时，它会添加一个时间戳和UUID。这很容易让其他节点能够确定有多少"；活动的"；有节点
- 为了确定分配，节点确定有多少任务可用/可接受。然后，它注意到有多少唯一的节点标识符(包括它自己)已经接受了任务。然后，它使用这个公式来接受更多的任务(理想情况下是随机的，以最大限度地减少与其他节点竞争的机会)。CCD_ 1。因此，如果有100个可用任务，10个活动节点，并且该节点已经接受了5个任务。然后它将接受：
100 / 10 - 5 = 5任务。如果节点在不再有任何任务时只查找更多任务，则可以只使用available_tasks / active_nodes - 为了避免问题，一个节点一次接受的任务数量应该是最大的
如果节点标识符不切实际。我只想说，每个节点都应该以ceil(sqrt(N))随机任务为目标，其中N是可用任务的数量。如果有100个任务。第一个节点需要10个，第二个需要10个、第三个需要9个、第四个需要9、第五个需要8个，依此类推。这不会同时均匀分配所有任务，但会确保节点获得大致偶数的任务。任务数量的轻微交错意味着节点不会同时完成所有任务(诚然，这可能是可取的，也可能不是可取的)。通过不完全分布它们(除非有sqrt(N)个节点)，它还降低了冲突(特别是如果任务是随机选择的)的可能性。它还减少了"；失败"；如果节点出现故障，则执行任务。
当然，这是假设一个节点在启动后可以请求更多的任务，如果不这样做，就会变得更加棘手。
至于另一个表，您实际上可以使用它来跟踪节点的当前状态。每个节点记录它有多少任务，它的唯一UUID，以及它上次完成任务的时间。尽管这可能会带来数据库流失的潜在问题。我认为只记录哪个节点接受了任务以及何时接受任务可能就足够了。如果节点将来可以请求任务，这也会更有用。