我正在尝试实现分布式 Multimap。该映射使用状态机，只要将提交写入底层集群的日志（如果重要，则为 raft 集群），就会触发该状态机。我遇到的问题是在传统的分布式映射中，一旦删除命令已提交到集群中所有机器的日志或更新提交已放置在大多数节点上，您就可以将提交标记为压缩。在这种情况下，日志中的多个提交可能会影响与单个键关联的一组值。我想合理有效地压缩日志条目，这在我的解释中意味着选择会导致 Multimap 当前状态的最小条目集是系统崩溃并且重播日志中的非压缩提交。
我目前最好的解决方案是一个贪心算法，它选择对当前状态贡献最多值的提交，然后在第一次提交存在的情况下选择对状态贡献最大的提交，依此类推，直到提交的子集代表整个当前状态被选中。然后将未选择的提交标记为压缩。
我希望有人可以提出更有效的解决方案，因为贪心算法肯定不是最理想的，应该注意算法性能很重要，并且此处理是在单个线程上执行的。
谢谢！