com.google.common.cache.AbstractCache.SimpleStatsCounter is NOT thread-safe

[mkramanathan]

While using the SimpleStatsCounter class in the com.google.common.cache package, we found that it is not thread-safe as documented. As a simple example, we can have one thread invoking recordLoadSuccess with a non-zero value. It executes loadSuccessCount.increment() and before it can execute totalLoadTime.add(loadTime), if another threads calls a snapshot on the cache, it will return an inconsistent state (where the successCount and loadtime are inconsistent).

Should the methods be synchronized in this class? If not, may be the documentation can be fixed to remove claims on thread-safety?

[lowasser]

Thread safety is a tricky subject, and I believe this logic is working as intended: the intention is to take a snapshot of cache activity, which may be racy. See e.g. the Javadoc for AbstractCache.cacheStats():

Returns a snapshot of this counter's values. Note that this may be an inconsistent view, as it may be interleaved with update operations.

Synchronizing would defeat the purpose of CacheStats and, frankly, the purpose of Cache itself: the whole idea is for many threads to be able to operate on the cache without contending for a common lock, but if the SimpleStatsCounter were globally synchronized, every thread accessing the cache would content for that lock.

Additionally, SimpleStatsCounter itself depends on a thread-safe but not atomic abstraction, LongAdder, whose sum() method carries the Javadoc

/**
 * Returns the current sum.  The returned value is <em>NOT</em> an
 * atomic snapshot; invocation in the absence of concurrent
 * updates returns an accurate result, but concurrent updates that
 * occur while the sum is being calculated might not be
 * incorporated.
 *
 * @return the sum
 */

From what I can tell, SimpleStatsCounter is essentially in the same position as LongAdder, though it does have the added issue that it has multiple fields which may be updated inconsistently.

I think the conclusion here has to be that a) SimpleStatsCounter is intended to be used from multiple threads, b) it implements its intended semantics correctly, though those intended semantics only make weak guarantees, c) "threadsafe" is a very vague word and we should possibly document the intended semantics more clearly.

[ben-manes]

The challenge is that multiple fields have to be updated together, which cannot be done efficiently. The locking approach won't scale. Creating a new struct (composite update) for a CAS update won't scale due to GC pressure and CAS storms.

Perhaps the only way to implement it efficiently would be thread-local StatsCounters (mimic memcached's approach). The thread would synchronize and update, and the aggregator would synchronize to read. This would allow consistent read/writes with low overhead as the locks are not contended on. However, Java's ThreadLocal is not very efficient so a variant of Striped64 would be required (e.g. see Caffeine's StripedBuffer).

Given that the stats are often consumed by a reporter which itself doesn't guarantee atomic updates of composite metrics, this is a moot point. If the stats are being captured as monotonically increasing over the lifetime of the cache, then an inconsistent view has marginal impact.

The current implementation is thread safe, but not atomic. I think that's a reasonable trade-off.

[mkramanathan]

I agree that it is probably an overkill to synchronise to ensure thread-safe behaviour.

But the class is still not thread-safe as Ben suggests above. It is neither atomic nor thread-safe according to the definition of thread-safety by Brian Goetz ("Java Concurrency in Practice"),

Furthermore, for a class to be thread-safe, it must continue to behave correctly, in the sense described above, when accessed from multiple threads, regardless of the scheduling or interleaving of the execution of those threads by the runtime environment, without any additional synchronization on the part of the calling code. The effect is that operations on a thread-safe object will appear to all threads to occur in a fixed, globally consistent order.

We all seem to agree that there won't be a globally consistent order here. Therefore, the documentation probably can be updated to remove the thread-safe guarantee and clarify the intended semantics of the SimpleStatsCounter (similar to AbstractCache.cacheStats()).

[ben-manes]

A slightly looser definition is what is used in practice. The term is typically meant as whether the class functions correctly when operated on by multiple threads. What "correctly" means is defined by the API contract. This more liberal definition is used by Wikipedia,

A piece of code is thread-safe if it only manipulates shared data structures in a manner that guarantees safe execution by multiple threads at the same time.

SimpleStatsCounter is thread-safe in terms of the contract's requirements, which includes the necessary caveats. If those were missing or not honored, then the races would break the thread safety requirements. The requirements is monotonically increasing counts over the lifetime of the cache, with an inconsistent snapshot view of those counts. If counters were lossy (e.g. non-volatile updates) then it couldn't honor its contract when operated on by multiple threads.

It does not perform each method operation atomically, which would be a stronger requirement. Of the options, only the approach I'd favor is experimenting with a Striped64 version. The impact might even be less costly than the current approach by reducing the number of CAS operations (simply spin wait locking of the struct). If there is interest then I can benchmark that approach.

Adding more documentation can't hurt, though.

[lowasser]

@ben-manes, SimpleStatsCounter is already using a Striped64-based implementation for each of its individual counters.

[ben-manes]

@lowasser
Yes, but instead of one per counter there could be one per composite. Then the composite is synchonized on to read or write to it. The aggregation would be like sum. Each composite would be updated as a single step so the inconsistency wouldn't be visible. Due to the low collision rate, synchronized would not be contended and use spin locking instead of a full lock.

StripedBuffer already adapts Striped64 to custom objects. In that case a lock-free ring buffer. A variant could be used to operate on composite counters.

[ben-manes]

A quick hack showing what this would look like. The only missing portion is to have custom bi-functions to avoid creating a new capturing function on every call (avoid GC). Other than that making it pretty and benchmarking would be necessary.

[ben-manes]

An updated example that is cleaned up a bit. Using a simple JMH benchmark of 8 threads incrementing the counts and 1 thread reading we get the following on a 4-core / 8HT laptop.

StatsBenchmark.stats:record        atomic  thrpt   10  171937150.141 ops/s
StatsBenchmark.stats:snapshot      atomic  thrpt   10     109742.654 ops/s
StatsBenchmark.stats:record    concurrent  thrpt   10  152614121.235 ops/s
StatsBenchmark.stats:snapshot  concurrent  thrpt   10    3928269.479 ops/s

Not surprisingly the writes are a little faster by combining the operations but the read performance is reduced. That's because writers now contend with reads, so the impact is observable. Of course in practice counters won't be heavily contended on and the difference won't matter.

So that's how this could be done. Its a fun exercise, but probably not worth the effort.

[ben-manes]

Oh, I forgot to add padding to avoid false sharing. A big improvement, but reads are still pretty poor. Updated commit.

StatsBenchmark.stats:record        atomic  thrpt   10  215337580.177 ops/s
StatsBenchmark.stats:snapshot      atomic  thrpt   10     182681.894 ops/s
StatsBenchmark.stats:record    concurrent  thrpt   10  156842262.685 ops/s
StatsBenchmark.stats:snapshot  concurrent  thrpt   10    4037267.672 ops/s

[kevinb9n]

I would support adding some text to CacheStats explaining the non-atomic
updates. It may be worth a special warning on
hitRate/missRate/exceptionRate as well, and a tweak to guarantee that the
returned value is always <= 1.0?

On Thu, Nov 19, 2015 at 10:26 AM, Ben Manes notifications@github.com
wrote:

Oh, I forgot to add padding to avoid false sharing. A big improvement, but
reads are still pretty poor. Updated commit
ben-manes/caffeine@ab0da7e
.

StatsBenchmark.stats:record atomic thrpt 10 215337580.177 ops/s
StatsBenchmark.stats:snapshot atomic thrpt 10 182681.894 ops/s
StatsBenchmark.stats:record concurrent thrpt 10 156842262.685 ops/s
StatsBenchmark.stats:snapshot concurrent thrpt 10 4037267.672 ops/s

—
Reply to this email directly or view it on GitHub
#2230 (comment).

Kevin Bourrillion | Java Librarian | Google, Inc. | kevinb@google.com

[lowasser]

If we always increment the denominators before the numerators we shouldn't
have that problem? I'm not certain which order we increment things now.

On Thu, Nov 19, 2015, 10:35 AM kevinb9n notifications@github.com wrote:

I would support adding some text to CacheStats explaining the non-atomic
updates. It may be worth a special warning on
hitRate/missRate/exceptionRate as well, and a tweak to guarantee that the
returned value is always <= 1.0?

On Thu, Nov 19, 2015 at 10:26 AM, Ben Manes notifications@github.com
wrote:

Oh, I forgot to add padding to avoid false sharing. A big improvement,
but
reads are still pretty poor. Updated commit
<
ben-manes/caffeine@ab0da7e

.

StatsBenchmark.stats:record atomic thrpt 10 215337580.177 ops/s
StatsBenchmark.stats:snapshot atomic thrpt 10 182681.894 ops/s
StatsBenchmark.stats:record concurrent thrpt 10 156842262.685 ops/s
StatsBenchmark.stats:snapshot concurrent thrpt 10 4037267.672 ops/s

—
Reply to this email directly or view it on GitHub
#2230 (comment).

Kevin Bourrillion | Java Librarian | Google, Inc. | kevinb@google.com

—
Reply to this email directly or view it on GitHub
#2230 (comment).

[kluever]

Louis said: "Racyness is probably OK here, and done so for performance reasons. We should beef up the documentation though."