共享内存与消息传递如何处理大型数据结构?

在看Go和Erlang的并发方法时,我注意到它们都依赖于消息传递。

这种方法显然减轻了对复杂锁的需求,因为没有共享状态。

但是,考虑许多客户机需要对内存中的单个大型数据结构进行并行只读访问的情况 – 如后缀数组。

我的问题:

  • 将使用共享状态更快,并使用更less的内存比消息传递,因为数据是只读的,只需要在一个单一的位置存在锁通常是不必要的?

  • 在消息传递上下文中如何处理这个问题? 会不会有一个访问数据结构的进程,客户端只需要按顺序请求数据呢? 或者,如果可能的话,数据是否会被分块来创build多个处理大块的进程?

  • 鉴于现代CPU和内存的架构,这两种解决scheme之间是否有很大的区别?即,多核可以共享内存是否可以被并行读取?这意味着没有任何硬件瓶颈,否则这两个解决scheme会大致执行相同的操作?

10 Solutions collect form web for “共享内存与消息传递如何处理大型数据结构?”

  • 是的,在这种情况下共享状态可能会更快。 但是,只有当你可以放弃这些锁,而且只有在绝对只读的情况下才可行。 如果它“大部分是只读的”,那么你需要一个锁(除非你设法写无锁结构,被警告它们甚至比锁更复杂),然后你很难做到作为一个很好的消息传递体系结构是快

  • 是的,你可以写一个“服务器进程”来分享它。 通过真正轻量级的stream程,与编写一个小型API来访问数据相比,这并不复杂。 想象一个“拥有”数据的对象(在OOP意义上)。 以块为单位分割数据以提高并行性(在数据库中称为“分片”)有助于在大的情况下(或者数据caching)。

  • 即使NUMA正在成为主stream,每个NUMA单元仍然拥有越来越多的核心。 最大的区别是消息只能在两个内核之间传递,而锁必须从所有内核的caching中清除,限制为单元间总线延迟(甚至比RAM访问慢)。 如果有的话,共享状态/锁越来越不可行。

总之……习惯于消息传递和服务器进程,这是一帆风顺的。

编辑 :重新审视这个答案,我想添加关于在Go的文档中find的短语:

通过通信共享内存,不要通过共享内存进行通信。

这个想法是:当线程之间共享一块内存时,避免并发访问的典型方法是使用一个锁进行仲裁。 Go的风格是传递一个带有引用的消息,一个线程在接收消息时只访问内存。 它依赖于一些程序员的纪律措施; 但结果是非常干净的代码,可以很容易校对,所以debugging相对容易。

好处是您不必在每条消息上复制大块数据,也不必像在某些locking实现上那样有效地刷新caching。 如果风格导致更高性能的devise,还是有点早。 (特别是因为当前的Go运行时对于线程调度来说有些天真)

有一件事要认识到,Erlang并发模型并没有真正地指定消息中的数据必须在进程之间被复制,它表明发送消息是唯一的通信方式,并且没有共享状态。 由于所有的数据都是不可变的,这基本的,所以一个实现可能不会复制数据,只是发送一个引用。 或者可以使用两种方法的组合。 与往常一样,没有最好的解决scheme,在select如何做的时候有一些权衡。

BEAM使用复制,除了发送引用的大型二进制文件。

在Erlang中,所有的值都是不可变的 – 所以在进程之间发送消息时不需要复制消息,因为无论如何都不能修改消息。

在Go中,消息传递是按照惯例 – 没有任何东西可以阻止你向某个通道发送指针,然后修改指向的数据,只有约定,所以再次不需要复制消息。

大多数现代处理器使用MESI协议的变体。 由于共享状态,在不同线程之间传递只读数据非常便宜。 修改后的共享数据是非常昂贵的,因为存储这个caching行的所有其他caching都必须使其无效。

所以,如果你有只读数据,在线程之间共享是非常便宜的,而不是用消息复制。 如果读取数据主要是数据,则在线程之间共享代价可能非常昂贵,部分原因是需要同步访问,部分原因是写入会破坏共享数据的caching友好行为。

不变的数据结构在这里可能是有益的。 不用改变实际的数据结构,只需要创build一个共享大部分旧数据的新数据结构,但是需要改变的东西发生了变化。 共享一个版本是很便宜的,因为所有的数据都是不可变的,但是你仍然可以有效地更新到一个新版本。

这里没有提供的一个解决scheme是主从复制。 如果您拥有较大的数据结构,则可以将更改复制到在其副本上执行更新的所有从服务器。

如果想要扩展到几台甚至没有可能共享内存的机器,这个特别有趣,而不需要非常人为的设置(从远程计算机内存读取/写入的块设备的mmap)?

它的一个变体是有一个事务pipe理器,可以很好地更新复制的数据结构,并确保它同时处理一个且唯一的更新请求。 这是mnesia表格数据主 – 主复制的mnesia模型,它被认为是“大数据结构”。

请注意,您的问题在技术上是不合理的,因为消息传递可以使用共享状态,所以我将假定您的意思是通过深度复制来传递消息以避免共享状态(就像Erlang当前所做的那样)。

将使用共享状态更快,并使用更less的内存比消息传递,因为数据是只读的,只需要在一个单一的位置存在锁通常是不必要的?

使用共享状态将会快很多

在消息传递上下文中如何处理这个问题? 会不会有一个访问数据结构的进程,客户端只需要按顺序请求数据呢? 或者,如果可能的话,数据是否会被分块来创build多个处理大块的进程?

任何一种方法都可以使用。

鉴于现代CPU和内存的架构,这两种解决scheme之间是否有很大的区别?即,多核可以共享内存是否可以被并行读取 – 这意味着没有任何硬件瓶颈,否则这两个解决scheme会大致执行相同的操作?

复制是caching不友好的,因此,破坏多核的可扩展性,因为它加剧了争夺主存的共享资源。

最终,Erlang风格的消息传递是为并发编程devise的,而关于吞吐量性能的问题实际上是针对并行编程的。 这是两个完全不同的主题,在实践中它们之间的重叠很小。 具体来说,延迟通常与并发编程环境中的吞吐量一样重要,而且,Erlang式消息传递是实现所需延迟概要(即始终如一的低延迟)的好方法。 共享内存的问题并不是读者和写者之间的同步,而是低延迟的内存pipe理。

目前的问题确实是locking和caching行一致性可能与复制一个更简单的数据结构(比如几个hundert字节)一样昂贵。

但是大多数情况下,一个聪明的新的multithreadingalgorithm试图消除大部分的locking总是会更快 – 而现代的无锁数据结构要快得多。 特别是当你有像Sun的Niagara芯片级multithreading那样devise良好的caching系统时。

如果你的系统/问题不容易分解成几个简单的数据访问,那么你有一个问题。 并不是所有的问题都可以通过消息传递来解决。 这就是为什么仍然有一些基于Itanium的超级计算机被出售,因为它们具有千兆字节的共享内存和多达128个CPU在相同的共享内存上工作。 与具有相同CPUfunction的主streamx86群集相比,它们的价格要高得多,但不需要分解数据。

但是到目前为止还没有提到的另一个原因是,当你使用multithreading的方式时,程序可以变得更容易编写和维护。 消息passign和共享没有使得它更容易维护。

例如,Erlang从来没有devise过让事情更快,而是使用大量的线程来构造复杂的数据和事件stream。

我想这是devise中的一个重点。 在谷歌的networking世界中,你通常不关心性能 – 只要它可以在云中并行运行。 通过消息传递,您可以在不更改源代码的情况下添加更多计算机。

什么是数据结构?

一个人大,另一个人小。

上个星期我跟两个人谈过 – 一个人用embedded式设备做“大”这个词 – 我问他这是什么意思 – 他说超过256千字节 – 稍后一个人在谈论媒体发布的那个星期 – 他用“大”这个词我问他是什么意思 – 他想了一下,说“不适合一台机器”说20-100 TB

在Erlang中,“大”可能意味着“不适合RAM” – 所以4GB的RAM数据结构> 100 MBytes可能被认为是大的 – 复制500 MB的数据结构可能是一个问题。 复制小型数据结构(比如<10 MB)在Erlang中永远不会有问题。

真正的大数据结构(即不适合在一台机器上的数据结构)必须被复制和“分条”到几台机器上。

所以我想你有以下几点:

小数据结构是没有问题的 – 因为它们的数据处理时间很短,复制速度很快等等(仅仅因为它们很小)

大数据结构是一个问题 – 因为它们不适合在一台机器上 – 所以复制是必不可less的。

通常情况下,消息传递语言(这在erlang中是非常简单的,因为它具有不可变的variables)优化了进程之间的实际数据复制(当然,本地进程只是想明智地考虑你的networking分布模式),所以这不是这不是一个问题。

另一个并发范例是STM,软件事务内存。 Clojure的裁判正在引起很多关注。 蒂姆·布雷有一个很好的系列探索erlang和clojure的并发机制

http://www.tbray.org/ongoing/When/200x/2009/09/27/Concur-dot-next

http://www.tbray.org/ongoing/When/200x/2009/12/01/Clojure-Theses

  • 函数式编程:什么是“不正确的列表”?
  • 函数式语言(特别是Erlang)如何/为什么能很好地扩展?
  • 进程和线程有什么区别?
  • 我可以使用哪些库来与Erlang构buildGUI?
  • 如何在Erlang中连接两个二进制文件?
  • 在Erlang,我什么时候使用; 或者,或者?
  • 当前的function反应式编程实现的状态是什么?
  • 在游戏开发中使用函数式编程的好资源?