Imran Chaudhry

<p>DSE Advanced Replication feature in&nbsp;<a href="https://www.datastax.com/products/datastax-enterprise">DataStax Enterprise</a>&nbsp;underwent a major refactoring between DSE 5.0 (“V1”) and DSE 5.1 (“V2”), radically overhauling its design and performance characteristics.</p>

<p>DSE Advanced Replication builds on the multi-datacenter support in Apache Cassandra® to facilitate scenarios where selective or "hub and spoke" replication is required. DSE Advanced Replication is specifically designed to tolerate sporadic connectivity that can occur in constrained environments, such as retail, oil-and-gas remote sites and cruise ships.</p>

<p>This blog post provides a broad overview of the main performance improvements and &nbsp;drills down into how we support CDC ingestion and deduplication to ensure efficient transmission of mutations.</p>

<p><strong>Note:</strong>&nbsp;This blog post was written targeting DSE 5.1. Please refer to the&nbsp;<a href="http://docs.datastax.com/en/" title="DataStax Documentation">DataStax documentation</a>&nbsp;for your specific version of DSE if different.</p>

<h1>Overview</h1>

<p>Discussion of performance enhancements is split into three broad stages:</p>

<ol>
	<li><b>Ingestion</b>: Capturing the Cassandra mutations for an Advance Replication enabled table</li>
	<li><b>Queueing</b>: Sorting and storing the ingested mutations in an appropriate message queue</li>
	<li><b>Replication</b>: Replicating the ingested mutation to the desired destination(s).</li>
</ol>

<h2>Ingestion</h2>

<p>In Advanced Replication v1 (included in DSE 5.0); capturing mutations for an Advanced Replication enabled table used Cassandra triggers. Inside the trigger we unbundled the mutation and extract the various partition updates and key fields for the mutation. By using the trigger in the ingestion transaction, we provided backpressure to ingestion and reduced throughput latency, as the mutations were processed in the ingestion cycle.</p>

<p>In Advanced Replication v2 (included in DSE 5.1), we replaced triggers with the Cassandra Change Data Capture (CDC) feature added in Cassandra version 3.8. CDC is an optional mechanism for extracting mutations from specific tables from the commitlog. This mutation extraction occurs outside the Ingestion transaction, so it adds negligible direct overhead to the ingestion cycle latency.</p>

<p>Post-processing the CDC logs requires CPU and memory. This process competes with DSE for resources,&nbsp;so decoupling of ingestion into DSE and ingestion into Advanced Replication allows us to support bursting for mutation ingestion.</p>

<p>The trigger in v1 was previously&nbsp;run on a single node in the source cluster. CDC is run on every node in the source cluster, which means that there are replication factor (RF) number of copies of each mutation. This change creates the need for deduplication which we’ll explain later on.</p>

<h2>Queuing</h2>

<p>In Advanced Replication&nbsp;v1, we stored the mutations in a blob of data within a vanilla DSE table, relying on DSE to manage the replication of the queue and maintain the data integrity. The issue was that this insertion was done within the ingestion cycle with a negative impact on ingestion latency, at a minimum doubling the ingestion time. This could increase the latency enough to create a query timeout, causing an exception for the whole Cassandra query.</p>

<p>In Advanced Replication&nbsp;v2 we offloaded the queue outside of DSE and used local files. So for each mutation, we have RF copies of it that mutation - due to capturing the mutations at the replica level via CDC versus at the coordinator level via triggers in v1 – on the same nodes as the mutation is stored for Cassandra. This change ensures&nbsp;data integrity and redundancy and provides&nbsp;RF copies of the mutation.</p>

<p>We have solved this CDC deduplication problem based on an intimate understanding of token ranges, gossip, and mutation structures to ensure that, on average, each mutation is only replicated once.The goal is to replicate all mutations at least once, and to try to minimize replicating a given mutation multiple times. This solution will be described later.</p>

<h2>Replication</h2>

<p>Previously in Advanced Replication&nbsp;v1, replication could be configured only to a single destination. This replication stream was fine for a use case which was a net of source clusters storing data and forwarding to a central hub destination, essentially 'edge-to-hub.'</p>

<p>In Advanced Replication&nbsp;v2 we added support for multiple destinations, where data could be replicated to multiple destinations for distribution or redundancy purposes. As part of this we added the ability to prioritize&nbsp;which destinations and channels (pairs of source table to destination table) are replicated first, and &nbsp;configure whether channel replication is LIFO or FIFO to ensure newest or oldest data is replicated first.</p>

<h1>CDC Deduplication and its integration into the Message Queue to support replication</h1>

<p>With the new implementation of the v2 mutation Queue, we have the situation where we have each mutation stored in Replication Factor number of queues, and the mutations on each Node are interleaved depending on which subset of token ranges are stored on that node.</p>

<p>There is no guarantee that the mutations are&nbsp;received on each node in the same order.</p>

<p>With the Advanced Replication&nbsp;v1 trigger implementation there was a single consolidated queue which made it significantly easier to replicate each mutation only once.</p>

<h2>Deduplication</h2>

<p>In order to minimize the number of times we process each mutation, we triage the mutations that extract from the CDC log in the following way:</p>

<ol>
	<li>Separate the mutations into their distinct tables.</li>
	<li>Separate them into their distinct token ranges.</li>
	<li>Collect the mutations in time sliced buckets according to their mutation timestamp (which is the same for&nbsp;<b>that</b>&nbsp;mutation across all the replica nodes.)</li>
</ol>

<h2>Distinct Tables</h2>

<p>Separating them into their distinct table represents the directory structure:</p>
<img alt="distinct tables" data-align="center" data-entity-type="file" data-entity-uuid="8c42bb39-ac05-4811-831d-ceb48afa710d" src="https://www.datastax.com/sites/default/files/inline-images/Figure1.png" />
<h2>token Range configuration</h2>

<p>Assume a three node cluster with a replication factor of 3.</p>

<p>For the sake of simplicity, this is the token-range structure on the nodes:</p>
<img alt="three node cluster" data-align="center" data-entity-type="file" data-entity-uuid="4575a7b1-aa5a-4394-a1cd-b1789b36d95e" src="https://www.datastax.com/sites/default/files/inline-images/Figure2.png" />
<p>Primary, Secondary and Tertiary are an arbitrary but consistent way to prioritize the token Ranges on the node – and are based on the token Configuration of the keyspace – as we know that Cassandra has no concept of a primary, secondary or tertiary node.</p>

<p>However, it allows us to illustrate that we have three token ranges that we are dealing with in this example. If we have Virtual-Nodes, then naturally there will be more token-ranges, and a node can be ‘primary’ for multiple ranges.</p>

<h2>Time slice separation</h2>

<p>Assume the following example CDC files for a given table:</p>
<img alt="cdc files" data-align="center" data-entity-type="file" data-entity-uuid="62cbdb1d-fb9e-49c2-bfc1-5c808aa939c2" src="https://www.datastax.com/sites/default/files/inline-images/Figure4.png" />
<p>As we can see the mutation timestamps are NOT always received in order (look at the id numbers), but in this example we contain the same set of mutations.</p>

<p>In this case, all three nodes share the same token ranges, but if we had a 5 node cluster with a replication factor of 3, then the token range configuration would look like this, and the mutations on each node would differ:</p>
<img alt="token range cluster" data-align="center" data-entity-type="file" data-entity-uuid="16b92845-c497-4f63-b079-1356af400c18" src="https://www.datastax.com/sites/default/files/inline-images/Figure6.png" />
<h2>Time slice buckets</h2>

<p>As we process the mutations from the CDC file, we store them in time slice buckets of one minute’s worth of data. We also keep a stack of 5 time slices in memory at a time, which means that we can handle data up to 5 minutes out of order. Any data which is processed more than 5 minutes out of order would be put into the out of sequence file and treated as exceptional data which will be need to be replicated from all replica nodes.</p>

<h3>Example CDC Time Window Ingestion</h3>
<img alt="cdc time window ingestion" data-align="center" data-entity-type="file" data-entity-uuid="5efe37da-eea8-4f1d-bef3-9222afec02c1" src="https://www.datastax.com/sites/default/files/inline-images/Figure7.png" />
<ul>
	<li>In this example, assume that there are 2 time slices of 30 seconds</li>
	<li>Deltas which are positive are ascending in time so are acceptable.</li>
	<li>Id’s 5, 11 and 19 jump backwards in time.</li>
	<li>As the sliding time window is 30 seconds, Id’s 5, 12 &amp; 19 would be processed, whilst ID 11 is a jump back of 45 seconds so would not be processed into the correct Time Slice but placed in the Out Of Sequence files.</li>
</ul>

<h2>Comparing Time slices</h2>

<p>So we have a time slice of mutations on different replica nodes, they&nbsp;<b>should</b>&nbsp;be identical, but there is no guarantee that they are in the same order. But we need to be able to compare the time slices and treat them as identical regardless of order. So we take the CRC of each mutation, and when we have sealed (rotated it out of memory because the current mutation that we are ingesting is 5 minutes later than this time slice)&nbsp;the time slice , we sort the CRCs and take a CRC of all of the mutation CRCs.<br />
That [TimeSlice] CRC is comparable between time slices to ensure they are identical.</p>

<p>The CRCs for each time slice are communicated between nodes in the cluster via the Cassandra table.</p>

<h2>Transmission of mutations</h2>

<p>In the ideal situation, identical time slices and all three nodes are active – so each node is happily ticking away only transmitting its primary token range segment files.</p>

<p>However, we need to deal with robustness and assume that nodes fail, time slices do not match and we still have the requirement that ALL data is replicated.</p>

<p>We use gossip to monitor which nodes are active and not, and then if a node fails – the ‘secondary’ become active for that nodes ‘primary’ token range.</p>

<h3>Time slice CRC processing</h3>

<p>If a CRC matches for a time slice between 2 node – then when that time slice is fully transmitted (for a given destination), then the corresponding time slice (with the matching crc) can be marked as sent (synchdeleted.)</p>

<p>If the CRC mismatches, and there is no higher priority active node with a matching CRC, then that time slice is to be transmitted – this is to ensure that no data is missed and everything is fully transmitted.</p>

<h3>Active Node Monitoring Algorithm</h3>

<p>Assume that the token ranges are (a,b], (b,c], (c,a], and the entire range of tokens is [a,c], we have three nodes (n1, n2 and n3) and replication factor 3.</p>

<ul>
	<li>
	<ul>
		<li>On startup the token ranges for the keyspace are determined - we actively listen for token range changes and adjust the schema appropriately.</li>
		<li>These are remapped so we have the following informations:
		<ul>
			<li>node =&gt; [{primary ranges}, {secondary ranges}, {tertiary ranges}]</li>
			<li><b>Note</b>: We support vnodes where there may be multiple primary ranges for a node.</li>
		</ul>
		</li>
		<li>In our example we have:
		<ul>
			<li>n1 =&gt; [{(a,b]}, {(b,c]}, {c,a]}]</li>
			<li>n2 =&gt; [{(b,c]}, {c,a]}, {(a,b]}]</li>
			<li>n3 =&gt; [{c,a]}, {(a,b]}, {(b,c]}]</li>
		</ul>
		</li>
		<li>When all&nbsp;<b>three nodes are live</b>, the active token ranges for the node are as follows:
		<ul>
			<li>n1 =&gt; [{(a,b]},&nbsp;<del>{(b,c]}</del>,&nbsp;<del>{c,a]}</del>] =&gt; {(a,b]}</li>
			<li>n2 =&gt; [{(b,c]},&nbsp;<del>{c,a]}, {(a,b]}</del>] =&gt; {(b,c]}</li>
			<li>n3 =&gt; [{c,a]},&nbsp;<del>{(a,b]}, {(b,c]}</del>] =&gt; {(c,a]}</li>
		</ul>
		</li>
		<li>Assume that&nbsp;<b>n3 has died</b>, its primary range is then searched for in the secondary replicas of live nodes:
		<ul>
			<li>n1 =&gt; [{(a,b]},&nbsp;<del>{(b,c]}</del>,&nbsp;<del>{c,a]}</del>] =&gt; {(a,b], }</li>
			<li>n2 =&gt; [{(b,c]}, {c,a]},&nbsp;<del>{(a,b]}</del>] =&gt; {(b,c], (c,a]}</li>
			<li><del><b>n3</b></del><b>&nbsp;=&gt;</b>&nbsp;<b><del>[{c,a]}</del>,&nbsp;</b><b><del>{(a,b]}</del>,&nbsp;</b><b><del>{(b,c]}</del>]</b>&nbsp;=&gt; {}</li>
		</ul>
		</li>
		<li>Assume that&nbsp;<b>n2 and n3 have died</b>, their primary range is then searched for in the secondary replicas of live nodes, and if not found the tertiary replicas (assuming replication factor 3) :
		<ul>
			<li>n1 =&gt; [{(a,b]}, {(b,c]}, {c,a]}] =&gt; {(a,b], (b,c], (c,a]}</li>
			<li><b><del>n2</del>&nbsp;=&gt;&nbsp;<del>[{(b,c]}</del>,&nbsp;<del>{c,a]}</del>,&nbsp;<del>{(a,b]}]</del>&nbsp;=&gt; {}</b></li>
			<li><del><b>n3</b></del><b>&nbsp;=&gt;</b>&nbsp;<b><del>[{c,a]}</del>,&nbsp;</b><b><del>{(a,b]}</del>,&nbsp;</b><del><b>{(b,c]}]</b></del>&nbsp;=&gt;&nbsp;<b>{}</b></li>
		</ul>
		</li>
	</ul>
	</li>
</ul>

<ul>
	<li>This ensures that data is only sent once from each edge node, and that dead nodes do not result in orphaned data which is not sent.</li>
</ul>

<h4>Handling the Node Failure Case</h4>

<p>Below illustrates the three stages of a failure case.</p>

<ol>
	<li>Before - where everything is working as expected.</li>
	<li>Node 2 Fails - so Node 1 becomes Active for its token Slices and ignores what it has already been partially sent for 120-180, and resends from its secondary directory.</li>
	<li>Node 2 restarts - this is after Node 1 has sent 3 Slices for which Node 2&nbsp;<em>was</em>&nbsp;primary (but Node 1 was Active because it was Node 2’s secondary), it synchronously Deletes those because the CRCs match. It ignores what has already been partially sent for 300-360 and resends those from its primary directory and carries on.</li>
</ol>
<img alt="3 stages of failure case" data-align="center" data-entity-type="file" data-entity-uuid="82918673-c7a7-4954-9404-79800649cc75" src="https://www.datastax.com/sites/default/files/inline-images/Figure8.png" />
<p>Before</p>
<img alt="before" data-align="center" data-entity-type="file" data-entity-uuid="f5847eb5-764f-4893-bdf3-2a8167a633db" src="https://www.datastax.com/sites/default/files/inline-images/Figure9.png" />
<p>Node 2 Dies</p>
<img alt="node 2 dies" data-align="center" data-entity-type="file" data-entity-uuid="4c586620-f416-47fd-89de-b350f6891e5c" src="https://www.datastax.com/sites/default/files/inline-images/Figure10.png" />
<p>Node 2 Restarts</p>

<p>&nbsp;</p>
<img alt="node 2 restarts" data-align="center" data-entity-type="file" data-entity-uuid="4399608a-f1c0-4b9f-a6f5-6dbf20cdea9a" src="https://www.datastax.com/sites/default/files/inline-images/Figure11.png" />
<h1>Conclusion</h1>

<p>The vastly improved and revamped DSE Advanced Replication v2 in DSE 5.1 is more resilient and performant with support for multi-hubs and multi-clusters.</p>

<p>For more information see our documentation&nbsp;<a href="https://docs.datastax.com/en/dse/5.1/dse-admin/datastax_enterprise/advReplication/advRepTOC.html">here</a>.</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

DSE Advanced Replication in DSE 5.1

Sign up for our Developer Newsletter