代码之家 › 专栏 › 技术社区 › John

并行无锁递增id生成

lock-free parallel-processing concurrency java

2

John · 技术社区 · 6 年前

我有一个映射,它应该将字符串与id相关联。必须不

请求总是带有两个字符串,其中一个、两个或没有可能已经被索引。

AtomicInteger 不为地图中已经存在的关键点按顺序创建间隙。

public class Foo {
    private final Map<String, Integer> idGenerator = new ConcurrentHashMap<>();

    // invoked from multiple threads
    public void update(String key1, String key2) {
      idGenerator.dosomething(key, ?) // should save the key and unique id
      idGenerator.dosomething(key2, ?) // should save the key2 and its unique id
      Bar bar = new Bar(idGenerator.get(key), idGenerator.get(key2));
      // ... do something with bar
   }
}

我认为 size() 方法结合 merge() 也许能解决问题,但我不能完全说服自己。有人能提出解决这个问题的方法吗?

编辑

关于复制标志,这不能用 AtomicInteger.incrementAndGet() 如链接的答案所示。如果我对每根弦都这么做的话差距按顺序。有必要复合检查密钥是否存在并只生成id的操作。 Map 应用程序编程接口。

第二个答案与我在问题中明确提出的要求背道而驰。

2 回复 | 直到 6 年前

1

4

lscoughlin 6 年前

没有一种方法可以完全按照你想要的方式去做-- ConcurrentHashMap java.util.Map.computeIfAbsent 功能。

下面是一个代码示例,它与您提供的样式相同,应该可以帮助您继续。

ConcurrentHashMap<String, Integer> keyMap = new ConcurrentHashMap<>();
AtomicInteger sequence = new AtomicInteger();

public void update(String key1, String key2) {
    Integer id1 = keyMap.computeIfAbsent(key1, s -> sequence.getAndIncrement());
    Integer id2 = keyMap.computeIfAbsent(key2, s -> sequence.getAndIncrement());

    Bar bar = new Bar(id1, id2);
    // ... do something with bar
}

2

3

Peter Cordes 6 年前

我不确定你能做你想做的事。但是,您可以批处理一些更新,或者将检查与枚举/添加分开进行。

延迟不是那么重要。这个应用程序应该处理大量数据并最终产生输出。大多数情况下,地图上应该有搜索结果

如果大多数搜索命中,那么我们主要需要地图上的读取吞吐量。

一个writer线程就足够了。

因此,与直接添加到主映射不同,并发读卡器可以检查它们的输入,如果不存在,则将它们添加到要枚举并添加到主ConcurrentHashMap的队列中。

那么您就不需要原子计数器,或者当两个线程看到相同的字符串时,在将其添加到映射之前将计数器递增两次也没有任何问题(否则这是个大问题。)

如果一个作家有办法锁定 ConcurrentHashMap

为了减少主前端线程之间的争用,可以有多个队列,比如每个线程可能有一个生产者/消费者队列,或者一对物理内核上运行的一组4个线程共享一个队列。

在读写器不争用的队列中,枚举线程没有争用。但是多个队列减少了写入程序之间的争用(写入这些队列的线程是以只读方式访问主ConcurrentHashMap的线程,如果命中率很高,则大部分CPU时间将花在这里。)

某种程度上 read-copy-update (RCU) 数据结构可能是好的,如果Java有这个功能的话

在90%的命中率下,一个writer线程可能可以跟上10个左右的reader线程,这些线程根据主表过滤新的键。

您可能需要设置一些队列大小限制,以允许来自单个writer线程的背压。或者,如果您拥有的内核/线程比单个编写器所能跟上的还要多,那么某种并发设置可能会有帮助,让多个线程在编号之前消除重复。

我想也许试着在比赛条件下找出错误的地方,然后再回去解决问题,但这可能不是更好的办法。