多线程与共享内存

Question

我有一个问题，本质上是在一个巨大但在内存中的数据库(10GB)中对多个项目(针)副本进行一系列搜索 - 干草堆。

这分为多个任务，每个任务都是在大海捞针中找到一系列针中的每一个每个任务在逻辑上都独立于其他任务。

(这已经分布在多台机器上，每台机器有自己的干草堆副本。)

有很多方法可以在单独的机器上并行化。

我们可以让每个 CPU 核心共享内存一个搜索进程。或者我们可以有一个具有多个线程的搜索进程(每个核心一个)。甚至多个多线程进程。

3种可能的架构:

1. 进程将干草堆加载到 Posix 共享内存中。

   后续进程使用共享内存段(如缓存)

2. 进程将干草堆加载到内存中，然后进行 fork 。

   由于写时复制语义，每个进程都使用相同的内存。

3. 进程将干草堆加载到内存中并生成多个搜索线程

问题是一种方法可能更好，为什么？或者更确切地说，权衡是什么。

(为了论证，假设性能胜过实现复杂性)。

实现两个或三个并进行测量当然是可能的，但需要艰苦的工作。有什么理由可以证明一个人可能会变得更好吗？

• 大海捞针中的数据是不可变的。
• 进程正在 Linux 上运行。因此进程并不比线程昂贵得多。
• 大海捞针跨越了许多 GB，因此 CPU 缓存不太可能有帮助。
• 搜索过程本质上是二分搜索(实际上是 equal_range 加上一点插值)。
• 由于任务在逻辑上是独立的，因此线程间通信没有任何好处比进程间通信便宜(例如 https://stackoverflow.com/a/18114475/1569204 )。

我想不出线程和共享内存之间有任何明显的性能权衡。有吗？也许代码维护权衡更相关？

---

背景研究

我能找到的唯一相关的答案是指同步线程的开销 - Linux: Processes and Threads in a Multi-core CPU - 这是事实，但在这里不太适用。

相关且有趣但不同的问题是:

• Multithreading: What is the point of more threads than cores?
• Performance difference between IPC shared memory and threads memory
• performance - multithreaded or multiprocess applications

一个有趣的演示是 https://elinux.org/images/1/1c/Ben-Yossef-GoodBadUgly.pdf

这表明线程与进程上下文切换的速度可能存在微小差异。我假设除了监视线程/进程之外，其他线程/进程永远不会被关闭。

Answer 1

一般建议:能够衡量改进!如果没有这个，您可以根据互联网上的建议进行所有您喜欢的调整，但仍然无法获得最佳性能。实际上，我告诉你不要相信我或其他任何人(包括你自己)，而是要进行衡量。还要准备好在生产系统上实时测量这一点。基准测试可能会在一定程度上帮助您，但实际负载模式仍然是另一回事。

然后，你说操作纯粹在内存中，因此速度不依赖于(网络或存储)IO 性能。您面临的两个瓶颈是 CPU 和 RAM 带宽。因此，为了在正确的部分上工作，找出限制因素。确保相应部分高效可确保您的搜索获得最佳性能。

此外，您还说您进行二分搜索。这基本上意味着您需要进行 log(n) 比较，其中每次比较都需要从干草堆中加载某个元素。此负载可能会遍历所有缓存，因为数据的大小使得缓存命中的可能性很小。但是，您可以同时持有多个针在缓存中搜索。如果您随后设法首先触发针的缓存加载，然后执行比较，则可以减少 CPU 或 RAM 空闲的时间，因为它们等待新操作执行。这显然(与其他参数一样)是您需要针对其运行的系统进行调整的参数。

更进一步，重新考虑二分搜索。二分搜索执行可靠，对随机数据具有良好的上限。如果您的数据中有任何模式(即任何非随机的)，请尝试利用这些知识。如果您可以粗略地估计您正在搜索的针的位置，则可以减少查找次数。这基本上是将工作从 RAM 总线转移到 CPU，因此这又取决于哪个是实际瓶颈。请注意，您还可以切换算法，例如当您需要考虑的元素少于一定数量时，从有根据的猜测转向二分搜索。

最后，您说每个节​​点都有数据库的完整副本。如果为 N 个节点中的每个节点分配数据库的 N 分之一，则可以改进缓存。然后，您将第一步定位元素以确定节点，然后将搜索分派(dispatch)到负责的节点。如果有疑问，每个节点仍然可以将搜索作为后备处理。