反向读写锁

Question

通常我们在读时使用ReadWriteLocks，在读时使用读锁，在写时使用写锁。但在一个奇特的案例中，我认为反向使用可能会有所帮助。但希望你们能告诉我一个更好的方法。

这就是我想要的。将会有大量的写入，但读取的量会很少。例如，示例是请求等待时间的平均计算器。

几乎把它当作伪代码来处理。

metric.addValue(latency); // Called a lot.

metric.getAverage(); // Called sparingly.

我们可以执行以下操作：

addValue(value) {
  atomicCount.increment();
  atomicSum.increment(value);
}

getAverage() {
  return atomicCount.get() != 0 ? atomicSum.get() / atomicCount.get() : 0.0;
}

问题出在getAverage()中，我们“可能”会计算出一些额外的计数。但大多数情况下可能是正确的值，有时还会有额外的计数。但我只想让它更精确。

诀窍是这样的：

ReadWriteLock rw = /* write preference, or a fair lock. */;
Lock read = rw.readLock();
Lock write = rw.writeLock();

addValue(value) {
  read.lock(); // Using read lock when mutating. 
  try { 
    atomicCount.increment();
    atomicSum.increment(value);
  } finally {
    read.unlock();
  }
}

getAverage() {
  write.lock(); // Using write lock when reading.
  try {
    return atomicCount.get() != 0 ? atomicSum.get() / atomicCount.get() : 0.0;
  } finally {
    write.unlock();
  }
}

我的问题是，我能做得更好吗？

Salt:我知道(强制转换)问题，可以避免多次调用count.get()等，以获得更好的性能，但又不想把代码弄得太乱。

Answer 1

并发原子增量确实没有意义；它们无论如何都不能是并发的。

最简单的解决方案-一个简单的锁，普通的count/sum变量-会执行得更好

lock
    count++;
    sum += value;
unlock

为了更并行，我们需要“分片”-每个线程维护自己的统计数据；阅读器查询所有线程以获取整个图片。(每个线程的统计信息需要是易失性的；reader使用Michael Burr的方法来检索稳定版本的每个线程的统计信息)

Answer 2

您可能想看看下面这样的技术是否执行得更好。基本上，它通过添加另一个计数器来确保count和sum是“稳定的”，该计数器跟踪第一个计数器，但只有在所有其他值完成更新后才会更新，因此不涉及锁：

addValue(value) {

  while (atomicFlag.get() != 0) {
      // spin
  }
  atomicCount.increment();
  atomicSum.increment(value);
  atomicCount2.increment();
}

getAverage() {
    int count;
    int sum;
    int count2;

    atomicFlag.increment();
    do {
        count = atomicCount.get();
        sum = atomicSum.get();
        count2 = atomicCount2.get();
    } while (count != count2);
    atomicFlag.decrement();

    return count != 0 ? (sum * 1.0) / count : 0.0;
}

Answer 3

(从G+复制讨论)。

一种优化思想是使用AtomicLong将值和计数同时存储在Long的不同位置，从而解决了在计算平均值时确保计数和值匹配的问题。

另一个(更大的)优化是使用线程特定的度量(正如前面不受欢迎的建议)。它有以下优点。

• 它避免了写入时的任何类型的争用。
• Read不需要任何锁。
• ，最重要的是，它可以更好地利用L1缓存。

最后一点的解释：

在多核处理器中，当有多个线程从单个共享内存进行大量的读写操作时，运行在不同内核中的线程会一直使其他内核的L1缓存无效。正因为如此，最新的值将不得不使用缓存一致性协议从其他内核获取。所有这些都大大放慢了速度。拥有线程特定的度量可以避免这个问题。

参考：http://www.cs.washington.edu/education/courses/cse378/07au/lectures/L25-Atomic-Operations.pdf

考虑到这一点，像这样的代码将会执行得很好。

private final AtomicLongMap<Long> metric = AtomicLongMap.create();

public void addValue(long value) {
    long threadId = Thread.currentThread().getId();
    metric.addAndGet(threadId, (value << 32) + 1);
}

public synchronized double getAverage() {
    long value = metric.sum();
    int count = (int)value;
    return (count == 0) ? 0 : ((double)(value >> 32))/count;
}

事实上，测试表明它的性能最好-比上面的无锁解决方案更好！而且也是按数量级计算的。

No thread safety: 3435ms, Average: 1.3532233016178474
(irreputable) Just synchronized {}  4665ms, Average: 4.0
(atuls) reverse read-write lock:    19703ms, Average: 4.0
(michael burr)  17150ms, Average: 4.0
(therealsachin) 1106ms, Average: 4.0