![\"Netflix](\"https:\/\/miro.medium.com\/v2\/resize:fill:88:88\/1*BJWRqfSMf9Da9vsXG9EBRQ.jpeg\")
<\/div>\n<\/div>\n<\/a><\/div>\n<\/div>\n
![\"Netflix](\"https:\/\/miro.medium.com\/v2\/resize:fill:48:48\/1*ty4NvNrGg4ReETxqU2N3Og.png\")
<\/div>\n<\/div>\n<\/a><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\u00b7<\/span><\/span><\/p>\n 18 hours in the past<\/p><\/div>\n <\/span><\/div>\n <\/span><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n By: Rajiv Shringi<\/a>, Oleksii Tkachuk<\/a>, Kartik Sathyanarayanan<\/a><\/p>\n In our earlier weblog publish, we launched Netflix\u2019s TimeSequence Abstraction<\/a>, a distributed service designed to retailer and question giant volumes of temporal occasion knowledge with low millisecond latencies. Today, we\u2019re excited to current the Distributed Counter Abstraction<\/strong>. This counting service, constructed on prime of the TimeSequence Abstraction, permits distributed counting at scale whereas sustaining related low latency efficiency. As with all our abstractions, we use our Data Gateway Control Plane<\/a> to shard, configure, and deploy this service globally.<\/p>\n Distributed counting is a difficult downside in pc science. In this weblog publish, we\u2019ll discover the various counting necessities at Netflix, the challenges of reaching correct counts in close to real-time, and the rationale behind our chosen strategy, together with the required trade-offs.<\/p>\n Note<\/strong>: When it involves distributed counters, phrases similar to \u2018accurate\u2019 or \u2018precise\u2019 ought to be taken with a grain of salt. In this context, they seek advice from a depend very near correct, offered with minimal delays.<\/em><\/p>\n At Netflix, our counting use circumstances embrace monitoring thousands and thousands of person interactions, monitoring how usually particular options or experiences are proven to customers, and counting a number of sides of information throughout A\/B take a look at experiments<\/a>, amongst others.<\/p>\n At Netflix, these use circumstances could be categorised into two broad classes:<\/p>\n Both classes share widespread necessities, similar to excessive throughput and excessive availability. The desk beneath gives an in depth overview of the various necessities throughout these two classes.<\/p>\n To meet the outlined necessities, the Counter Abstraction was designed to be extremely configurable. It permits customers to decide on between completely different counting modes, similar to Best-Effort<\/strong> or Eventually Consistent<\/strong>, whereas contemplating the documented trade-offs of every possibility. After deciding on a mode, customers can work together with APIs while not having to fret concerning the underlying storage mechanisms and counting strategies.<\/p>\n Let\u2019s take a better take a look at the construction and performance of the API.<\/p>\n Counters are organized into separate namespaces that customers arrange for every of their particular use circumstances. Each namespace could be configured with completely different parameters, similar to Type of Counter, Time-To-Live (TTL), and Counter Cardinality, utilizing the service\u2019s Control Plane.<\/p>\n The Counter Abstraction API resembles Java\u2019s AtomicInteger<\/a> interface:<\/p>\n AddCount\/AddAndGetCount<\/strong>: Adjusts the depend for the required counter by the given delta worth inside a dataset. The delta worth could be constructive or damaging. The AddAndGetCount<\/em> counterpart additionally returns the depend after performing the add operation.<\/p>\n The idempotency token can be utilized for counter varieties that assist them. Clients can use this token to securely retry or hedge<\/a> their requests. Failures in a distributed system are a given, and being able to securely retry requests enhances the reliability of the service.<\/p>\n GetCount<\/strong>: Retrieves the depend worth of the required counter inside a dataset.<\/p>\n ClearCount<\/strong>: Effectively resets the depend to 0 for the required counter inside a dataset.<\/p>\n Now, let\u2019s take a look at the various kinds of counters supported throughout the Abstraction.<\/p>\n The service primarily helps two varieties of counters: Best-Effort<\/strong> and Eventually Consistent<\/strong>, together with a 3rd experimental sort: Accurate<\/strong>. In the next sections, we\u2019ll describe the completely different approaches for these kinds of counters and the trade-offs related to every.<\/p>\n This sort of counter is powered by EVCache<\/a>, Netflix\u2019s distributed caching answer constructed on the broadly fashionable Memcached<\/a>. It is appropriate to be used circumstances like A\/B experiments, the place many concurrent experiments are run for comparatively brief durations and an approximate depend is ample. Setting apart the complexities of provisioning, useful resource allocation, and management airplane administration, the core of this answer is remarkably simple:<\/p>\n \/\/ add operation \/\/ get operation \/\/ clear counts from all replicas EVCache delivers extraordinarily excessive throughput at low millisecond latency or higher inside a single area, enabling a multi-tenant setup inside a shared cluster, saving infrastructure prices. However, there are some trade-offs: it lacks cross-region replication for the increment<\/em> operation and doesn’t present consistency ensures<\/a>, which can be vital for an correct depend. Additionally, idempotency will not be natively supported, making it unsafe to retry or hedge requests.<\/p>\n While some customers could settle for the restrictions of a Best-Effort counter, others go for exact counts, sturdiness and world availability. In the next sections, we\u2019ll discover numerous methods for reaching sturdy and correct counts. Our goal is to focus on the challenges inherent in world distributed counting and clarify the reasoning behind our chosen strategy.<\/p>\n Approach 1: Storing a Single Row per Counter<\/strong><\/p>\n Let\u2019s begin easy by utilizing a single row per counter key inside a desk in a globally replicated datastore.<\/p>\n Let\u2019s study a number of the drawbacks of this strategy:<\/p>\n Secondary Keys<\/strong>: One technique to scale back rivalry on this strategy can be to make use of a secondary key, similar to a bucket_id<\/em>, which permits for distributing writes by splitting a given counter into buckets<\/em>, whereas enabling reads to mixture throughout buckets. The problem lies in figuring out the suitable variety of buckets. A static quantity should still result in rivalry with sizzling keys<\/em>, whereas dynamically assigning the variety of buckets per counter throughout thousands and thousands of counters presents a extra advanced downside.<\/p>\n Let\u2019s see if we will iterate on our answer to beat these drawbacks.<\/p>\n Approach 2: Per Instance Aggregation<\/strong><\/p>\n To handle problems with sizzling keys and rivalry from writing to the identical row in real-time, we might implement a method the place every occasion aggregates the counts in reminiscence after which flushes them to disk at common intervals. Introducing ample jitter to the flush course of can additional scale back rivalry.<\/p>\n However, this answer presents a brand new set of points:<\/p>\n That stated, this strategy should still be appropriate in situations the place these trade-offs are acceptable. However, let\u2019s see if we will handle a few of these points with a distinct event-based strategy.<\/p>\n Approach 3: Using Durable Queues<\/strong><\/p>\n In this strategy, we log counter occasions right into a sturdy queuing system like Apache Kafka<\/a> to stop any potential knowledge loss. By creating a number of subject partitions and hashing the counter key to a selected partition, we make sure that the identical set of counters are processed by the identical set of shoppers. This setup simplifies facilitating idempotency checks and resetting counts. Furthermore, by leveraging further stream processing frameworks similar to Kafka Streams<\/a> or Apache Flink<\/a>, we will implement windowed aggregations.<\/p>\n However, this strategy comes with some challenges:<\/p>\n Furthermore, all approaches that pre-aggregate counts make it difficult to assist two of our necessities for correct counters:<\/p>\n Barring these few necessities, this strategy can nonetheless be efficient if we decide the correct technique to scale our queue partitions and shoppers whereas sustaining idempotency. However, let\u2019s discover how we will alter this strategy to satisfy the auditing and recounting necessities.<\/p>\n Approach 4: Event Log of Individual Increments<\/strong><\/p>\n In this strategy, we log every particular person counter increment together with its event_time<\/strong> and event_id<\/strong>. The event_id can embrace the supply info of the place the increment originated. The mixture of event_time and event_id may function the idempotency key for the write.<\/p>\n However, in its easiest kind<\/em>, this strategy has a number of drawbacks:<\/p>\n The mixed influence of those points can result in elevated infrastructure prices that could be troublesome to justify. However, adopting an event-driven strategy appears to be a big step ahead in addressing a number of the challenges we\u2019ve encountered and assembly our necessities.<\/p>\n How can we enhance this answer additional?<\/p>\n We use a mixture of the earlier approaches, the place we log every counting exercise as an occasion, and repeatedly mixture these occasions within the background utilizing queues and a sliding time window. Additionally, we make use of a bucketing technique to stop broad partitions. In the next sections, we\u2019ll discover how this strategy addresses the beforehand talked about drawbacks and meets all our necessities.<\/p>\n Note<\/strong>: From right here on, we’ll use the phrases \u201c<\/em>rollup<\/em><\/strong>\u201d and \u201c<\/em>aggregate<\/em><\/strong>\u201d interchangeably. They primarily imply the identical factor, i.e., amassing particular person counter increments\/decrements and arriving on the last worth.<\/em><\/p>\n TimeSequence Event Store:<\/strong><\/p>\n We selected the TimeSequence Data Abstraction<\/a> as our occasion retailer, the place counter mutations are ingested as occasion data. Some of the advantages of storing occasions in TimeSequence embrace:<\/p>\n High-Performance<\/strong>: The TimeSequence abstraction already addresses lots of our necessities, together with excessive availability and throughput, dependable and quick efficiency, and extra.<\/p>\n Reducing Code Complexity<\/strong>: We scale back a number of code complexity in Counter Abstraction by delegating a significant portion of the performance to an present service.<\/p>\n TimeSequence Abstraction makes use of Cassandra because the underlying occasion retailer, however it may be configured to work with any persistent retailer. Here is what it appears like:<\/p>\n Handling Wide Partitions<\/strong>: The time_bucket<\/em> and event_bucket<\/em> columns play a vital position in breaking apart a large partition, stopping high-throughput counter occasions from overwhelming a given partition. For extra info concerning this, seek advice from our earlier <\/em>weblog<\/em><\/a>.<\/p>\n No Over-Counting<\/strong>: The event_time<\/em>, event_id<\/em> and event_item_key<\/em> columns kind the idempotency key for the occasions for a given counter, enabling purchasers to retry safely with out the chance of over-counting.<\/p>\n Event Ordering<\/strong>: TimeSequence orders all occasions in descending order of time permitting us to leverage this property for occasions like depend resets.<\/p>\n Event Retention<\/strong>: The TimeSequence Abstraction contains retention insurance policies to make sure that occasions usually are not saved indefinitely, saving disk area and lowering infrastructure prices. Once occasions have been aggregated and moved to a cheaper retailer for audits, there\u2019s no have to retain them within the major storage.<\/p>\n Now, let\u2019s see how these occasions are aggregated for a given counter.<\/p>\n Aggregating Count Events:<\/strong><\/p>\n As talked about earlier, amassing all particular person increments for each learn request can be cost-prohibitive by way of learn efficiency. Therefore, a background aggregation course of is critical to repeatedly converge counts and guarantee optimum learn efficiency.<\/p>\n But how can we safely mixture depend occasions amidst ongoing write operations?<\/em><\/p>\n This is the place the idea of Eventually Consistent <\/em>counts turns into essential. By deliberately lagging behind the present time by a secure margin<\/em>, we make sure that aggregation all the time happens inside an immutable window.<\/p>\n Lets see what that appears like:<\/p>\n Let\u2019s break this down:<\/p>\n This does imply that the counter worth will lag behind its most up-to-date replace by some margin (usually within the order of seconds). This strategy does go away the door open for missed occasions because of cross-region replication points. See \u201cFuture Work\u201d part on the finish.<\/em><\/p>\n Rollup Store:<\/strong><\/p>\n We save the outcomes of this aggregation in a persistent retailer. The subsequent aggregation will merely proceed from this checkpoint.<\/p>\n We create one such Rollup desk per dataset<\/em> and use Cassandra as our persistent retailer. However, as you’ll quickly see within the Control Plane part, the Counter service could be configured to work with any persistent retailer.<\/p>\n LastWriteTs<\/strong>: Every time a given counter receives a write, we additionally log a last-write-timestamp<\/strong> as a columnar replace on this desk. This is finished utilizing Cassandra\u2019s USING TIMESTAMP<\/a> characteristic to predictably apply the Last-Write-Win (LWW) semantics. This timestamp is identical because the event_time<\/em> for the occasion. In the following sections, we\u2019ll see how this timestamp is used to maintain some counters in lively rollup circulation till they’ve caught as much as their newest worth.<\/p>\n Rollup Cache<\/strong><\/p>\n To optimize learn efficiency, these values are cached in EVCache for every counter. We mix the finalRollupCount<\/strong> and finalRollupTs<\/strong> right into a single cached worth per counter<\/em> to stop potential mismatches between the depend and its corresponding checkpoint timestamp.<\/p>\n\n
![\"\"](\"https:\/\/miro.medium.com\/v2\/resize:fit:640\/format:webp\/1*_Mx2WRBWOfASpK_e2xgoVw.png)
{{{\/\/ counter cache key<\/picture><\/div>\n<\/div>\n<\/figure>\n
\n
<\/picture><\/div>\n<\/div>\n<\/figure>\n
\n
<\/picture><\/div>\n<\/div>\n<\/figure>\n
\n
\n
<\/picture><\/div>\n<\/div>\n<\/figure>\n
\n
<\/picture><\/div>\n<\/div>\n<\/figure>\n
<\/picture><\/div>\n<\/div>\n<\/figure>\n
\n
<\/picture><\/div>\n<\/div>\n<\/figure>\n
\n
<\/picture><\/div>\n<\/div>\n<\/figure>\n
<\/picture><\/div>\n<\/div>\n<\/figure>\n