ConcurrentSkipListSet如何拥有弱一致性的迭代器?理解“弱一致性”的含义。

huangapple go评论72阅读模式
英文:

How does ConcurrentSkipListSet has Iterators that are weakly consistent? Understanding meaning of 'weakly consistent'

问题

Fail-fast迭代器对集合进行迭代。如果在迭代时修改了集合,就会抛出异常。而fail-safe迭代则相反,迭代在一个集合上进行,而写操作在其副本上进行,这就是fail-safe的工作原理(例如CopyOnWriteArrayList)。

有人可以解释一下ConcurrentSkipListSet是如何具有fail-safe性质的吗?在修改集合时没有创建副本(就像CopyOnWrite类所做的那样),所以是如何实现的呢?我阅读过文档,但仍然不太理解(尽管我了解并发中的代码可见性或happens-before关系)。

有没有什么逻辑简单且易于记忆的解释呢?因为我是初学者。

//示例代码:

ConcurrentSkipListSet<Integer> set = new ConcurrentSkipListSet<>();
set.add(1);
set.add(2);
set.add(3);
set.add(4);

Iterator<Integer> iterator = set.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
    set.remove(4);
}

输出结果:
1
2
3
我原以为会在这里抛出ConcurrentException.. 请帮帮我 ConcurrentSkipListSet如何拥有弱一致性的迭代器?理解“弱一致性”的含义。

英文:

Fail-fast iterator iterates over collection. If collection gets modified while iterating, we get exception. Opposite applies for fail-safe, where iteration is happening on one collection, while write operation happen on copy of it, thus it is how fail-safe works (f.e. CopyOnWriteArrayList).

Can someone explain me how does ConcurrentSkipListSet has fail-safe? There are no copies when modifying collection (like CopyOnWrite classes do), so how does it happen? I read because its Iterator is weakly consistent. I read docs, I still don't understand. (but I do know what code visibility or happens-before relation in concurrency is).

Does anyone have logic and easy to remember explanation, as I am a beginner?

//Example:

 ConcurrentSkipListSet&lt;Integer&gt; set = new ConcurrentSkipListSet&lt;&gt;();
      set.add(1);
      set.add(2);
      set.add(3);
      set.add(4);

      Iterator&lt;Integer&gt; iterator = set.iterator();
      while (iterator.hasNext()){
          System.out.println(iterator.next());
          set.remove(4);
      }

OUTPUT:
1
2
3

I was expecting ConcurrentException to be thrown here.. Please help ConcurrentSkipListSet如何拥有弱一致性的迭代器?理解“弱一致性”的含义。

答案1

得分: 2

"弱一致性"这个术语在java.util.concurrent包描述中有定义:

> 大多数并发集合实现(包括大多数队列)的行为也与通常的java.util惯例不同,它们的迭代器和Spliterators提供的是弱一致性而不是快速失败的遍历:
>
> - 它们可以与其他操作并发进行
> - 它们永远不会抛出ConcurrentModificationException
> - 它们保证遍历元素时会精确地遍历一次,就像它们在构造时存在的那样,并且可能会(但不保证会)反映构造后的任何修改。

在使用ConcurrentSkipListSet的情况下,迭代器没有"快速失败"的特性,而是会反映已从集合中移除的4的修改。

在内部,ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的,其迭代器通过跟踪应该遍历哪个跳表节点来实现。这自然地赋予了你"弱一致性"的特性:如果下一个项被删除,迭代器仍然会返回它。如果在下一个项之后的项被删除,迭代器将会反映这些更改。

英文:

The "weakly consistent" term is defined in the java.util.concurrent package description:

> Most concurrent Collection implementations (including most Queues)
> also differ from the usual java.util conventions in that their
> Iterators and Spliterators provide weakly consistent rather than
> fast-fail traversal:
>
> - they may proceed concurrently with other operations
> - they will never throw ConcurrentModificationException
> - they are guaranteed to traverse elements as they existed upon construction exactly once, and may (but are not guaranteed to) reflect
> any modifications subsequent to construction.

In this case with ConcurrentSkipListSet, the iterator does not have a "fast-fail" property, instead it reflects the modification of 4 having been removed from the set.

Internally, ConcurrentSkipListSet is implemented with ConcurrentSkipListMap, and its iterators are implemented by keeping track of which skip list node should be traversed next. This naturally gives you the "weakly consistent" property: If the next item is deleted, the iterator will still return it. If items beyond the next are deleted, the iterator will reflect those changes.

huangapple
  • 本文由 发表于 2020年8月22日 19:05:01
  • 转载请务必保留本文链接:https://go.coder-hub.com/63535420.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定