Aleksey Yeschenko

<h2>TL;DR</h2>

<p>Apache Cassandra 2.1 will have a safer, simpler, and often faster distributed counters implementation. The crucial difference is that rather than logging counter deltas (increments) directly to the commit log – making replay non-idempotent and potentially unsafe – Cassandra will now read the current value for every counter update and apply the delta. The final result is then added to the memtables. You should expect more accurate values and more consistent performance from the new implementation. The price for all the improvements is increased latency for RF=1/CL.ONE/replicate_on_write=false counter tables (the latter being an anti-pattern and heavily recommended against even in pre–2.1 era). In fact, the replicate_on_write option is entirely gone.</p>

<p>This also lays the foundation for Cassandra 3.0 to bring even&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-6506">better performance</a>&nbsp;for counters users.</p>

<h2>Intro</h2>

<p>Apache Cassandra introduced fast, distributed counters back in version 0.8.0 – almost 3 years ago. Cassandra is still one of the only databases that allows race-free increments with local latency across multiple datacenters simultaneously, but through Cassandra 2.0 some limitations in the original counters’ design continued to cause headaches, notably&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-4071">topology changes potentially leading to bad counters</a>&nbsp;and the infamous&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-4417">invalid counter shard detected</a>&nbsp;problem.</p>

<p>These problems and the extra complexity caused by the counters-related special cases in the code base have been fixed in the upcoming Cassandra 2.1 release. The new implementation also creates many fewer objects for the JVM to garbage-collect, so use of counters will not cause&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-6405">pathological behaviour</a>&nbsp;under heavy load anymore.</p>

<h2>How Counters Used to Work</h2>

<p>Internally, counters are split into fragments that we call ‘shards’. A shard is basically a 3-tuple of {node’s counter id, shard’s logical clock, shard’s value}.</p>

<p>Counter id is a unique value (a timeuuid) uniquely identifying the node that created the shard. Logical clock is the monotonically increasing version of the shard, and value is the size of the increment or the total value, depending on the shard type.</p>

<p>A counter’s value is calculated as the sum of all the shards’ values of the counter in its replica set.</p>

<p>Finally, a counter cell can (and will) contain multiple shards, packed into a binary blob as a&nbsp;<em>counter context</em>.</p>

<p>To illustrate how counters used to work before 2.1, let’s start with a simple 1-node (A) clean-state cluster as an example, with initial counter id of A0, and assume that there is only one counter foo. Shards are grouped into counter contexts, outlined in dotted lines, below.</p>
<img alt="initial counter id of A0" data-align="center" data-entity-type="file" data-entity-uuid="9adc0737-8821-4953-b0b7-802253eecada" src="https://www.datastax.com/sites/default/files/inline-images/pre-2.1-counters.png" />
<p>As you can see, to get the counter value you need to merge all the contexts from all the sstables and the memtable, and sum up the shards’ values. Simple as that.</p>

<p>Things get complicated, however, once we introduce another node and replication.</p>

<p>Let’s add node B with an initial counter id of B0, increase the RF (replication factor) to 2, and run repair. Now, when a write requests hits node A, we have to replicate the update to node B (and vice versa). This is where the pain begins, because we can’t simply replicate the delta itself, for several reasons. Instead, after writing the delta to the local memtable and commitlog, the coordinator sums up its local shard values, and sends the&nbsp;<em>total</em>, not the delta, to its neighbours. From now on, the deltas will be called ‘local shards’ and the totals - ‘remote shards’.</p>
<img alt="legend" data-align="center" data-entity-type="file" data-entity-uuid="3b8beb38-5329-473d-8861-f39e6684a318" src="https://www.datastax.com/sites/default/files/inline-images/legend.png" />
<p>Let’s see at the result of some writes to the counter executed at node B:</p>
<img alt="node B" data-align="center" data-entity-type="file" data-entity-uuid="39b33a6b-fadd-465e-8b9f-c8ba107e7654" src="https://www.datastax.com/sites/default/files/inline-images/pre-2.1-counters-Bnode.png" />
<p>Looks complicated? It should, because it is. One node’s local shard is another node’s remote shard, and the&nbsp;<a href="https://github.com/apache/cassandra/blob/cassandra-1.2/src/java/org/apache/cassandra/db/context/CounterContext.java#L299-L428">merge rules</a>&nbsp;are different for local and remote shards. Every time a local shard is sent to another node, it must be converted into a remote one - this includes any streaming, not just regular writes.</p>

<p>This local/remote distinction doesn’t just create a lot of edge case complexity in the codebase - it also leads to several practical issues for Cassandra users.</p>

<h2>Pre–2.1 Issues</h2>

<p>Topology changes at RF=1 will lead to bad incorrect results. The problem is described in details in&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-4071">this JIRA issue</a>.</p>

<p>Losing some data because of a corrupt sstable&nbsp;<em>or</em>&nbsp;replaying the commit log can lead to&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-4417">invalid counter shards</a>.</p>

<p>To properly repair a counter column family, or even to run scrub, you need to renew the node’s counter id, which leads to growth of counter contexts and means that you need more space, and to send more data over the network with time if you repair or cleanup.</p>

<p>Reconciling two counter cells (two counter contexts) requires allocating a third counter cell, large enough for the combined counter shards of the two cells being reconciled. This means N extra cells allocated for a counter read from N sstables and one memtable, for example. This is also true for the write process when racing to the memtable update. Concurrent updates to a small group of partitions can lead to&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-6405">pathological GC behaviour</a>&nbsp;under heavy load.</p>

<h2>The 2.1 Solution</h2>

<p>To deal with the listed issues, Cassandra 2.1 gets rid of the local shards entirely. Instead, we grab a (local) lock for each counter being updated, read the current value, then write the incremented value (not the increment itself as in C* 2.0) to the commitlog and to the memtable.</p>

<p>We no longer have to convert between local and remote shards when sending data between the nodes.</p>

<p>We don’t have to renew nodes’ counter ids, ever, ensuring that the counters’ size doesn’t grow unbounded.</p>

<p>For an illustration, let’s see the result of the same write sequence in 2.1:</p>
<img alt="sequence in 2.1" data-align="center" data-entity-type="file" data-entity-uuid="b1e055cf-8287-40cf-af3f-a14d9c3a7bf7" src="https://www.datastax.com/sites/default/files/inline-images/2.1-counters.png" />
<p>We no longer need to sum the sub-counts of the node’s shards - we can just pick the shard with the largest logical clock and stop there. Without the local/remote distinction, the distributed case is also a lot simpler:</p>
<img alt="2.1 counters B node" data-align="center" data-entity-type="file" data-entity-uuid="b122f7ee-85b0-4c77-9150-dd230b9a2f96" src="https://www.datastax.com/sites/default/files/inline-images/2.1-counters-Bnode.png" />
<p>Eliminating local shards simplifies almost every counters aspect - from writes and reads to streaming and cleanup.</p>

<p>As a bonus, we have to allocate a lot fewer objects on reads and writes, since often we are just able to pick the context with shards with larger timestamps instead of having to sum them up, making bursts of garbage collection activity a thing of the past.</p>

<h2>Performance Implications</h2>

<p>The new implementation does come with a price. Because we perform a mutexed read-before-write now, latency for CL.ONE (or RF=1) to would suffer with a naive implementation, particularly for many updates contenting for few counter objects. To mitigate this, Cassandra 2.1 introduces a new form of cache,&nbsp;<em>counter cache</em>, to keep hot counter values performant. Counter cache size and save period can be configured in cassandra.yaml.</p>

<p>Removing legacy local/remote shards entirely in Cassandra 3.0 and implement&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-6506">CASSANDRA–6506</a>&nbsp;will eliminate the need for the counter cache.</p>

<p>Other use cases should see uniformly better and more predictable performance, both with and without counter cache enabled (orange&nbsp;for Cassandra 2.1,&nbsp;blue&nbsp;for Cassandra 2.0):</p>
<img alt="low contention" data-align="center" data-entity-type="file" data-entity-uuid="4251eac6-8bba-459d-8382-fa9acc8c9885" src="https://www.datastax.com/sites/default/files/inline-images/low-contention.png" /><img alt="high contention" data-align="center" data-entity-type="file" data-entity-uuid="d1e08995-3605-4c83-a02e-5c65044b36f7" src="https://www.datastax.com/sites/default/files/inline-images/high-contention.png" />
<h2>Future work</h2>

<p>Cassandra 3.0 will finalise what was started in Cassandra 2.1. The primary task left is CASSANDRA–6506 -&nbsp;<a href="https://issues.apache.org/jira/browse/CASSANDRA-6506">split counter context shards into separate cells</a>, that will simplify counters implementation even further, and bring even more performance improvements for counters.</p>


Build and scale cloud native apps

Discover the benefits of DBaaS and why your apps deserve an upgrade.

Learn about NoSQL Databases

Learn about NoSQL databases with Apache Cassandra and Astra DB.

2022 Recap: A Year for Customers, Community, and Real-Time Data

Highlights from 2022 and a glimpse into the year ahead.

ViewingTechnical How To’s

What’s New in Cassandra 2.1: Better Implementation of Counters

Sign up for our Developer Newsletter