多线程共享二进制数组

Question

我有一个多线程应用程序，运行良好。但是它正在遇到锁竞争问题（通过快照Java堆栈并查看等待的对象来检查）。

每个线程从列表中消耗对象，然后拒绝每个对象或将其放入Bin中。

由于每个Bin可能很昂贵（而且可能会有很多），因此最初它们为空。

导致争用的代码大致如下：

public void addToBin(Bin[] bins, Item item) {
   Bin bin;
   int bin_index = item.bin_index
   synchronized(bins) {
      bin = bins[bin_index];
      if(bin==null) {
        bin = new Bin();
        bins[bin_index] = bin;
      }
   }
   synchronized(bin) {
     bin.add(item);
   }
}

瓶颈在于对bins数组的同步。

我的同事建议我使用双重检查锁定来解决这个问题，但我们不确定需要哪些步骤才能确保安全。建议的解决方案如下：

public void addToBin(Bin[] bins, Item item) {
   int bin_index = item.bin_index
   Bin bin = bins[bin_index];

   if(bin==null) {
     synchronized(bins) {
        bin = bins[bin_index];
        if(bin==null) {
          bin = new Bin();
          bins[bin_index] = bin;
        }
     }
   }

   synchronized(bin) {
     bin.add(item);
   }
}

这样做安全吗？是否有更好/更安全/更符合惯用法的方法？

- Michael Anderson

---

为什么不使用一个队列来提供给一个处理垃圾箱的收集器线程呢？ - chrylis -cautiouslyoptimistic-

此外，请更具体地说明“昂贵”和“很多”。除非我们谈论本地数据结构或反射和数十万个对象，否则这种惰性初始化看起来像是过早优化。（鉴于您的分箱值得多线程的开销，我假设您的输入数据集很大。） - chrylis -cautiouslyoptimistic-

数百万个存储单元并不罕见。数据集可以达到10个或更多的TB。内存使用量在10至100 GB之间。 - Michael Anderson

为什么所有这些都被保存在RAM中呢？这听起来像是一种每个bin追加到文件的工作方式更有效的情况。 - chrylis -cautiouslyoptimistic-

这些数据都被保存在内存中，因为访问磁盘的速度很慢。已经尽可能少地从磁盘中读取对象，将中间结果写回磁盘会降低性能（比现有的锁争用问题更严重）。一旦数据被分组和处理，最终的缩减结果将被写入磁盘。 - Michael Anderson

Answer 1

正如Malt的回答中已经说明的那样，Java已经提供了许多无锁数据结构和概念，可以用来解决这个问题。我想使用AtomicReferenceArray来添加一个更详细的示例：

假设bins是一个AtomicReferenceArray，以下代码在null条目的情况下执行无锁更新：

Bin bin = bins.get(index);
while (bin == null) {
    bin = new Bin();
    if (!bins.compareAndSet(index, null, bin)) {
        // some other thread already set the bin in the meantime
        bin = bins.get(index);
    }
}
// use bin as usual

自Java 8以来，有一种更加优雅的解决方案：

Bin bin = bins.updateAndGet(index, oldBin -> oldBin == null ? new Bin() : oldBin);
// use bin as usual

Node：尽管仍然是非阻塞的，但Java 8版本明显比上面的Java 7版本慢，这是因为updateAndGet将始终更新数组，即使值没有改变。这可能是可以忽略不计的，也可能取决于整个bin-update操作的总成本。

---

另一个非常优雅的策略可能是在将整个bins数组交给工作线程之前，仅使用新创建的Bin实例填充整个数组。由于线程不必修改数组，因此这将减少对Bin对象本身进行同步的需求。可以使用Arrays.parallelSetAll（自Java 8以来）轻松地进行多线程数组填充：

Arrays.parallelSetAll(bins, i -> new Bin());

更新2： 如果这是一个选项，取决于算法的预期输出：最终 bins 数组会完全填充、密集填充还是稀疏填充？（在第一种情况下，建议预先填充。在第二种情况下，情况各不相同。在后一种情况下，这可能是个坏主意）。

---

更新1： 不要使用双重检查锁定！它不安全！问题在于可见性，而不是原子性。在您的情况下，读取线程可能会获取一个部分构造（因此损坏的）Bin实例。有关详细信息，请参见http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html。

- isnot2bad

---

从OP的问题中可以看出：“每个箱子最初都是空的，因为每个箱子可能都很昂贵（而且可能会有很多箱子）。”因此提前设置它们似乎不可行。 - Matthieu M.

@MatthieuM。你说得对。令人尴尬的是，我错过了那一部分。问题是最终bins数组是否完全、密集或只是稀疏填充。在前两种情况下，使用parallelSetAll仍然可能是一个选项。 - isnot2bad

即使值没有改变，“updateAndGet”也会像更新一样行为（即执行易失性写入）。因此，这不是一个“非常优雅”的解决方案。一个优雅的解决方案将是一个像“compareAndSet”这样的函数，它需要一个“供应商”，但这样的函数不存在... 顺便说一句，如果您知道引用值永远不会从非“null”更改为“null”，则不需要“while”循环。一个简单的“if”就可以了。 - Holger

不要感到难过，这很容易被忽略，而预填充则可以消除很多问题。我实际上希望你能建议在这里添加一层间接性：如果我们有一个Lazy<Bin>和一个get()方法，该方法在第一次调用时惰性地实例化Bin(安全地)，那么您可以预先填充Lazy<Bin>数组，然后避免锁定数组本身。 - Matthieu M.

@Holger，它之所以优雅是因为它是一条非阻塞的单行代码。事实上，它比我发布的Java 7版本要慢得多。但是，由于根据问题描述构建Bin很耗费时间，因此这种额外的成本很可能会远远超过它的速度。关于while你是正确的。我一开始用的是if，但将其改为while后，如果有人重用这个模式而没有考虑到微妙的细节，代码将更加健壮。 - isnot2bad

Answer 2

Java有许多出色的无锁并发数据结构，因此在这种情况下没有必要使用带同步的数组。 ConcurrentSkipListMap是一个并发的、有序的键值映射。 ConcurrentHashMap是一个并发的、无序的键值对。

您可以简单地使用其中之一来替换数组。只需将映射键设置为您已经使用的整数索引即可。

还有谷歌的ConcurrentLinkedHashMap和谷歌的Guava Cache，它们非常适合保持有序数据，并删除旧条目。

- Malt

---

不要忘记AtomicReferenceArray。 - isnot2bad

@isnot2bad 我在发布原始问题之前查看了AtomicReferenceArray。我无法找到一种将上面的代码转换为其可用功能的方法。但很可能我错过了什么。如果它可以用来解决 - 我很想看到一个回答，演示如何解决。 - Michael Anderson

@Malt 你说得对，这并不像我想象的那么简单。代码太多了，无法在评论中贴出。我已经为此添加了一个新的答案。 - isnot2bad

Answer 3

我建议不要使用第二种解决方案，因为它在同步块之外访问了bins数组，因此不能保证另一个线程所做的更改对于未同步读取元素的代码是可见的。

不能保证同时添加的新Bin将被看到，因此可能会为相同的索引创建一个新的Bin并且丢弃一个同时创建和存储的-还忘记了物品可能放置在被丢弃的物品中。

- icza

---

我不这么认为。在第二个解决方案中，在同步区域内再次检查了bin是否仍为空。因此，可以保证只添加了一个bin。 - EarlGrey

至少有一条执行路径在数组上没有正确同步，因此可能存在微妙但被忽视的可见性问题导致它失败。因此，建议不要使用双重检查锁定，特别是当有其他更优雅的解决方法时。 - isnot2bad

@isnot2bad 是什么执行路径？我愿意学习，没有看到任何问题出现的路径。 - EarlGrey

如果从数组中检索到的bin不为null，则代码路径不会进入在数组上同步的块，因此读取线程可能无法看到完全构造的Bin实例。有关详细信息，请参见http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html。这是一个可见性问题，而不是原子性问题。 - isnot2bad

Answer 4

如果没有内置的Java类能够帮助您，您可以创建8个bin锁，例如binsALock到binsFLock。

然后将bin_index除以8，使用余数选择要使用的锁。

---

如果你选择一个比你拥有的线程数更多的大数，并使用在竞争时非常快速的锁，那么你可能会比选择8更好。

此外，通过减少使用的线程数，您也可以获得更好的结果。

- Ian Ringrose