从并发修改的 ConcurrentSkipListSet 创建树集的异常

collections concurrency java

2022-09-02 14:00:17

通常，并发集合可以安全地迭代;根据Javadoc的说法：“迭代器是弱一致的，返回的元素反映了迭代器创建时或自创建以来集合的状态。它们不会抛出 ConcurrentModificationException，并且可以同时进行其他操作。但是，请考虑以下情况：

import java.util.Random;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentSkipListSet;

public class ConcurrencyProblem {
    private static volatile boolean modifierIsAlive = true;

    public static void main(String[] args) {
        final ConcurrentSkipListSet<Integer> concurrentSet = new ConcurrentSkipListSet<>();
        Thread modifier = new Thread() {
            private final Random randomGenerator = new Random();

            public void run() {

                while (modifierIsAlive) {
                    concurrentSet.add(randomGenerator.nextInt(1000));
                    concurrentSet.remove(randomGenerator.nextInt(1000));
                }
            };
        };
        modifier.start();
        int sum = 0;
        while (modifierIsAlive) {
            try {
                TreeSet<Integer> sortedCopy = new TreeSet<>(concurrentSet);
                // make sure the copy operation is not eliminated by the compiler
                sum += sortedCopy.size();
            } catch (RuntimeException rte) {
                modifierIsAlive = false;
                rte.printStackTrace();
            }
        }
        System.out.println("Dummy output: " + sum);
    }
}

输出为

java.util.NoSuchElementException
at java.util.concurrent.ConcurrentSkipListMap$Iter.advance(ConcurrentSkipListMap.java:2299)
at java.util.concurrent.ConcurrentSkipListMap$KeyIterator.next(ConcurrentSkipListMap.java:2334)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2559)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2547)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2504)
at java.util.TreeMap.addAllForTreeSet(TreeMap.java:2462)
at java.util.TreeSet.addAll(TreeSet.java:308)
at java.util.TreeSet.<init>(TreeSet.java:172)
at mtbug.ConcurrencyProblem.main(ConcurrencyProblem.java:27)
Dummy output: 44910

我想知道这是一个错误还是一个功能;我们没有得到一个 ConcurrentModificationException，但是，仍然必须关心迭代（回退到同步块或其他方式）有点违背了 ConcurrentSkipListSet/Map 的目的。我已经能够用Java 7和8（目前，我的Linux盒子上的8u72）重现了这一点。

答案 1

就我从浏览源代码中可以理解的，问题在于它在迭代之前调用，然后使用它而不是调用。这可能是一个错误，但我认为这只是红黑树是复杂结构的结果，需要仔细平衡，因此需要提前知道大小才能在创建过程中在线性时间内正确平衡它。TreeSetsize()hasNext()

您可以通过手动迭代并将元素添加到中来规避这种情况，但这将导致复杂性，这可能是构造函数不这样做的原因（其 API 规范保证线性时间）。当然，它仍然可以在构建树时调用，但是在构建完成后可能需要一些额外的操作来重新平衡树，这可能导致摊销线性复杂性。但是红黑的树是一团糟，这种黑客攻击会使实现更加混乱。TreeSetn log nTreeSethasNext()

尽管如此，我认为这非常令人困惑，应该记录在API文档中的某个地方，但我不确定究竟在哪里。可能是在他们解释什么是弱一致性迭代器的部分。具体来说，应该提到的是，一些库类依赖于返回的大小，因此可能会抛出。提及特定类也会有所帮助。NoSuchElementException

答案 2

我实际上开始倾向于这是/中的一个错误（更新，它是）。正如谢尔盖所暗示的那样，问题在于在读取其元素之前缓存的结果。TreeSetTreeMapTreeMapConcurrentSkipListSet.size()

TreeSet.addAll（） 调用
TreeMap.addAllForTreeSet（） 并将集合的当前大小和可能并发传递给Iterator
TreeMap.buildFromSorted（）最终调用-times。Iterator.next()size

换句话说，它假设它通过的在构造过程中不会被修改，这是一个错误的假设。Collection

请注意，即使调用了它，它唯一的选择也是失败，因为支持数据结构在构造过程中被修改了。buildFromSorted()Iterator.hasNext()

查看其他可能在复制并发结构时可能出现问题的集合，包括 ArrayList、LinkedList 和 CopyOnWriteArrayList（我查看的大多数其他集合都只是针对每个元素），在执行任何实际工作之前，将提供的集合显式复制到数组中，以避免此确切问题。我认为并且应该做同样的事情。TreeSetTreeMap

由于这个错误，我们实际上不必接受O（n log n）性能，但这将是一个黑客攻击。我们不能简单地将值复制到数组或其他数据结构中，因为然后插入到不会是线性时间。但是，我们可以通过声称副本是.TreeSetTreeSetSortedSet

public static class IterateOnlySortedSet<E>
    extends AbstractSet<E> implements SortedSet<E> {
  private final ArrayList<E> elements;
  private final Comparator<? super E> comparator;

  public IterateOnlySortedSet(SortedSet<E> source) {
    elements = new ArrayList<>(source);
    comparator = source.comparator();
  }

  @Override
  public Iterator<E> iterator() {
    return elements.iterator();
  }

  @Override
  public int size() {
    return elements.size();
  }

  @Override
  public Comparator<? super E> comparator() {
    return comparator;
  }

  // remaining methods simply throw UnsupportedOperationException
}

将您的施工线更改为：TreeSet

TreeSet<Integer> sortedCopy = new TreeSet<>(new IterateOnlySortedSet<>(concurrentSet));

现在成功了。

不错的:)