1

I am working on problem where a call to reduce a counter will come to a service and if counter is greater zero then call should be able to reduce it else fail.

Pretty straightforward? huh!

For a request get the counter value, reduce and put it back

Well it becomes interesting with below Constraints:

  1. Request is sandboxed: So request can come to any host, each request creates a new thread and dies after returning the response. (So no batch update possible out of the box, in other words can't update counter with -10 on behalf of 10 requests if each request wanted to do -1)
  2. Maximize success rate of parallel requests for same counter update
  3. Minimize latency impact due to your solution (<700ms)
  4. Counter is stored in some data store (lets say DynamoDB, may not be the right data store for accessing same key with high rate as it causes hot partition and increasing the throughput just to support this weird call pattern is not acceptable)

Whats the problem exactly, you ask?

  1. Accessing same record many times tend to create hot partition scenario where most of underneath data store starts throttling you as your requests/access pattern seems sort of attack. (don't suggest keeping high throughput to support the pattern, not acceptable!)

  2. Directly processing a request used to work when there is no contention or say not many parallel request updating the same counter. Now most of the requests (99%) will fail due to lock/conditional fail cases and retries will take hell lot of time for all of them to succeed. (I am ok few requests fail ~10%)

About failures: "failure due to counter reaching 0" is not retryable while "failure due to lock/conditional fail cases" is retryable.

Aim is to maximize the success rate of parallel request as much as possible.

Side Note:

I am not limited or restricted with particular data model or store. That means you can come up with any data model which help you crack the problem is efficient way and choose any data store you believe is right for such use-case.

I have a fairly good solution(using randomness) which I can talk about later. (Not putting it upfront in order to keep problem open and interesting to be solved rather than discussing a single solution)

Wanted to collect thoughts here, how you will approach it!

  • Is this some single counter that will go for hours/days before it reaches zero, or will the counter exist for small moment before being reset? is this just single counter or are there many parallel counters? Is there some leeway on accuracy of request fail? Eg. what is accepted percent of requests that would cause counter to reach 0 (and thus), but succeed? I think you should describe in bigger detail on what those requests are meant to be used for. – Euphoric Jan 18 '17 at 13:17
  • 1
    Also, is "failure due to counter reaching 0" and "failure due to lock/conditional fail cases" same failure? If not, then update your question to clearly differentiate the two. – Euphoric Jan 18 '17 at 13:19
  • added clarification on failure cases. counter existence is not time bound, it can exist as long as it can be reduced to 0. There are more such counters. All requests are accepted if it was successful in reducing the counter it will return success else it will fail. – gitesh.tyagi Jan 18 '17 at 15:28
3

An easy solution would be to split the counter in N different "buckets", each containing a number X/N (rounding apart) where X is the initial value of the counter.

Each thread would then pick a random bucket and decrease its value. If the value of the bucket is already 0, the thread can try to access the next bucket and repeat. You are not writing anything in this case, so it only costs you a new read operations until you find a viable bucket.

This would cut the rate of collision down to 1/N of the original situation. The actual overhead would depend on the number of buckets and access times, so it's impossible to judge against a specific time limit such as 700ms. If that becomes a real problem (which I strongly doubt), you can extend the solution by adding a scheduled job to redistribute the values in the buckets (sum all the buckets and spread the result again, so to reduce the chance of having a bucket contain the value 0, which would result in the necessity of a new read).

The best part of course is you don't have to set up new architectural elements (e.g. queue processor) apart from a more complex logic in the counter and a few records instead of just one.

  • 1
    Thats more or less is what I have planned when I mentioned I have a solution using randomness. Improving a bit we can pick two buckets randomly and choose the best of two (defining best can be as simple as going for greater available value bucket) – gitesh.tyagi Jan 18 '17 at 15:15
  • 1
    Interesting. The only problem with using Max as the selection criteria is that you are introducing a bias and rising the probability of collisions. However, with only 2 buckets selected over N the rise in probability should be marginal and probably the benefit of having a more "flat" distribution is worth the cost. – lud1977 Jan 18 '17 at 16:11
1

Where there exists a source of truth record on a data value like a counter, and this value is universal to all running processes and volatile as many processes may be performing operations that change the value of said value, then you will require some kind of record or transaction lock on the field. Only one process can change the counter value at one time. That much is certain.

I won't go into the details of how to lock a table record. The challenge then becomes the matter of how we best manage the fair and equitable access to the decrement counter by all competing processes, and how can we do this in a well performing way that minimizes call failures. After all, we would not want 10 concurrent processes consistently receiving a value while 20 other more latent processes receive mostly failures.

The very first thing I would do would be to ensure that getting the counter value and decrement of the value exist as a single complete transaction. If they are two separate calls then the value received may be out of date by the time the decrement operation is invoked.

Secondly, the most fair and equitable way to distribute access IMO is through an asynchronous Message Queue interface. Requests for decrement and value retrieval of the counter will queue up and can be processed one at a time retaining the order in which requests were sent. MQ clients sending the messages will receive the appropriate response asynchronously on a Reply queue via corellation id. Clients to the interface can wait for a designated timeout period before deciding to fail out.

The problems with the above approach is that your ability to process messages must be on average faster than your average request peak time to prevent timeouts. If not then you may experience large volumes of requests on the end of the queue timing out and failing before they have a chance to be processed.

  • What we are essentially doing is trying to sequentialize our parallel calls... Achievable using transactional/realTime bus(say AWS Kinesis) or Message Queues and since you have already mentioned the downside of the solution so not repeating, One addition though its not scalable in sense more the number of parallel requests more timeouts you'll see. – gitesh.tyagi Jan 18 '17 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.