Best explanation, almost searched everywhere for my scenario, but found this tutorial very very helpful, once again thanks man.

04:16 Token bucket 10:40 Leaky bucket 12:50 Fixed window counter 16:15 Sliding logs 20:36 Sliding Window counter 25:21 Distributed system setup (Sticky sessions | locks)

This channel is just hidden Gem!

i was reading alex xu, i did not get good idea about sliding window and sliding window counter. now after i watched your explanation it is crystal clear and with pros and cons. thank you for doing this!!

This video was a clear and concise explanation of these topics! Great job! You have a new subscriber.

Narendra L! You doing good job! I watched your couple of videos. Keep it up!

you have my respect Narendra.. great work! :)

Good Stuff Naren! Even famous profs are not able to explain this kind of stuff so clearly.

@TechDummiesNarendraL

5 жыл бұрын

Thanks

My implementation takes advantage of Redis expiration.. When a call comes in, I create a record and the increment the value. Consequent calls will increment the value until the quota is reached. If the quota is not reached by the time the record expires, consequential request will cause a creation of new record and restart the counter.. This way I dont need to check and compare dates at any point. Code is very simple. Albeit, I am not maintaining a perpetual quota, I am only preventing abuse, which is really the main gist of request throttling

@varshard0

2 жыл бұрын

This is the way I implemented for my org also. Simple and served its purpose well.

@shelendrasharma9680

2 жыл бұрын

how would you manage the concurrancy here in redis.

@bazzalseed

2 жыл бұрын

@@shelendrasharma9680 redis is single thread.

@dhruveshkhandelwal8104

2 жыл бұрын

this is indirectly fixed window counter

@sid007ashish

2 ай бұрын

This is fixed window counter only.

Narendra, your video are great resources for learning system design. Your explanation of concepts is crystal clear. Big thumbs up for you

I love your voice brother. It makes it exciting to listen to what you have to say about this very interesting design topic.

Great explanation. The pattern you followed is very good i.e. when you mention a problem with some approach, you also provide the solution for that instead of just identifying problems.

I love your cap.. Looks like a trademark for you.. Thanks for all your videos..

Narendra, very informative video, keep it up. About locking in case of distributed token bucket you can use following technique Optimistic locking or conditional put - many no sql databases support conditional put. This is how it works * Read current value, say 9 * You do a conditional put with value 10 only if current value is 9. * When 2 concurrent requests try to update the value to 10, only one of them will succeed and other will fail as current value for that request will be 10.

I think you're easily the best youtuber for system design content

One of best explanation, thanks man :)

Bro, You saved my months. Love from Pakistan

Narendra L !! This is just superb ... keep going.

One additional case, were sliding logs should be used: limit a bitrate of video/audio/internet signal. In such case you need to store a packet size with a timestamp

You have a new subscriber. Thanks for making this video.

I love your videos. Thank you for making such detailed videos which explain the concepts so clearly. :)

Awesome work sir.. 👍🏼

thank you for sharing the video. neatly explained.

very comprehensive video. Great work. subscribed

Great work Narendra..! I am currently planning to switch jobs and your videos on system design are amazing...!!

Great video! Thank you!

very underrated youtube channel for system design

Great tutorial. Tricky part comes at 25:12:)

Great work Narendra👍👍

Great lesson! Thank you!

Great tutorial :)

Great video. Well explained.

Awesome Narendra..

Outstanding Explanation

very nice tutorial .. great work :)

Great video, congrats!!

Great video.. Thanks for the knowledge.

Sliding window can be optimized by setting the size of the queue to Max Requests allowed and try to remove the old entries only if max size is reached by comparing timestamp

Well explained Narendra

As usual naren rocks !!!

What a guy!! bless you bro

For the last example with concurrency. How about optimistic locking on the counter. Number of req has a version. If you try to update from 2 different RL, one of them will have the NoReq version smaller than the current one and will fail. The RL can retry or drop

Great video, keep up the good work :)

Informative !!

Distributed Systems, a necessary evil.. very nicely explained Narendra !!

A good one. Thanks

Thanks for the great tutorial, but I have a question as how would a rate limit service obtain lock of a record in separate db affect another rate limiter service obtain the count from different db within a node？

Hi Narendra - You are doing a good job in your knowledge transfer. I suggest you cover these topics as well - a) Job Scheduler b) Internals of Zoo Keeper c) Dist.Sys concepts like 2PC, 3PC, Paxos d) DB Internals.

@TechDummiesNarendraL

5 жыл бұрын

Added to TODO, Thanks

@screen189

5 жыл бұрын

Thanks for your response. Looking forward for her videos!!@@TechDummiesNarendraL

Excellent..hats off

Perfect! I wish I can give you 1,000,000 likes!

Thank you Narendra. The incredible content archive that you are building is invaluable. Thank you.

You can solve this with the help of increment or decrement method on redis which works atomically on any key so there is no chance for data inconsistencies and no need to put any lock 😊

@himanshu111284

3 жыл бұрын

2 services firing increment concurrently will still face the same problem, so i think it will not work without locking. Read + Write has to be an atomic transaction.

@SanjayKumar-di5db

3 жыл бұрын

@@himanshu111284 in redis increment and decrement methods on id are atomic so no need for lock

@rajsekharmahapatro

2 жыл бұрын

@@SanjayKumar-di5db First time i am learning something new by going through KZread comments bro. Thanks for it man.

@xuanwang7400

2 жыл бұрын

"compare and set" kind of logic works perfectly without explicit locking in simple operation case. But in complex situation, the app server may need a few requests. e.g. read the data first, the do some processing, then write back. and then two servers can do the same thing with same data at same time, thus race condition.

Great content. Thanks for sharing. Just one question, there should be only 1 LB which will send the request to either A1 or A2?

Awesome!

Great work! Would you be able to system design Elevators? Parking Lot?

Good bro. Awesome

thanks for this video

Amazing content

Great work, Searching for System design like leetcode or Hackerank...

For the Local Memory solution that you provided, how is it different from the solution that you explained just before (where the rate limiter is connected directly to the Redis)?

Thanks Man

Thanks for great video, very informative, however last several minutes of video is not very clear and crisp like other part of the video.

thanks Narendra

great explanation (y)

Sir, for amazon any particular series of questions you want to suggest.

This is really nice.. Do you have anything on how a coupon system works, for example : Doordash, Ubereats or rideshare coupons

20:36 Sliding Window counter The rate limit is 10R/M While in explanation , he considered 10R/S so please don't get confuse and think he is wrong

amazing video

Your content is good. But please try to change your voice modulation. It really helps for long videos.

Thank You

Why are you using two caches? Your sync issues are solved by keeping one single cache. Then, coming to race conditions, redis automatically acquires a lock on the transaction since it is atomic and therefore, the other request(second) should get an updated value. For SPOF on one cache, we can keep a master slave nodes for redis

Narendra from where do you get such a great understanding of system

Sir thank you what is internal implementation of token bucket from data structure side

Redis provides INCR and DECR commands which are atomic operations for increment and decrement of its Integer Data Type. Will this not take care of distributed access without any lock ?

@victoryang7734

4 жыл бұрын

I think his assumption is redis is seperate

@Priyam_Gupta

3 жыл бұрын

Yes this will be taking care as they are atomic.

@abcdef-fo1tf

Жыл бұрын

@@victoryang7734 what does separate redis mean. Is distributed redis not a shared cache?

Why he is looking like varun singla sir from Gate smashers , btw nice lecture

Hi Narendra, In token bucket scenario above, I would like to add one point that in order to reset the requests count after one minute to 5 again, we have to store the time(start time) of the first request so that we can check the difference of one minute to reset the count

@nikhilneela

4 жыл бұрын

Yes, I agree. If you simply reset the tokens to 5 when the minute changes, it would allow more than 5 requests/minute. Storing the start time and always comparing it with the current request time and if the delta is equal to or more than a minute, only then we can reset the tokens. @Eshwar, is this what you meant ?

@molugueshwar1

4 жыл бұрын

@@nikhilneela yes Nikhil. That's right

For the situation of distributed race limit, even though one user send two requests at the same time in one server, it dosen't mean that the actual two processing threads will deal them serially, so the inconsistency problem seems still exist. I think to address this problem we can make the read and update operation as atomic with redis+Lua.

@prajwal9610

2 жыл бұрын

Redis does this by having a lock which is already suggested in the video

@rekhakalasare4910

Жыл бұрын

​@@prajwal9610 yea but in case of local memory suppose single user two request going to 2 regions and regions local cache first read from db and then update in cache and db. Then also there is inconsistency as both req operating parellely

Nice explanation. Could you please make a video for Google ad sense analytics collection system ?

The inconsistency problem is basically a common DB problem called "lost update" due to two threads reading committed data concurrently and performing writes without any locks. Solution is to introduce locking to enforce ordering. Or enforce ordering by sticky session at a much higher level

you are the best

Hi Naren, what's the essential differences between sliding window log and leaky bucket. They look like pretty much the same in functionality.

can't we use Zookeeper for synchronization to manage requests along multiple regions

Excellent videos, just lacking good sound system.

Question about using locks. In example where two requests come in, RL1 gets the lock first, and then "locks" the key. How does it lock the key though such that it somehow impacts RL2? I'd imagine it only has access to the db in its own region (the one on the right on your drawing), so how does it lock the key such that when RL2 access the db in its own region (the one on left), that it knows to wait for the lock to be released? Thanks for the video as always.

04:15 Rate Limting Algorithms 25:11 Race Conditions in distributed systems

Is there any way to use sticky session for a user on the seconds level, so that we can use sliding window counter and the nodes can sync themselves over a minute?

Sir please make video on elevator design and google doc design as well.

@sanjanind

5 жыл бұрын

I also want for these two.

@TechDummiesNarendraL

5 жыл бұрын

Sure I will work on it.

Why cant we use the distributed counter method that you had explained in some other video? Like having zookeeper manager the counters?

Also on Movies Reviews Aggregator System

Hi Narendra great work I loved your content but i have one question . why not keep only one Redis DB instance instead of two in that case we dont have to sync them ? or is there any significance of having diff instances of Redis (per LB , RL , App instances) .

@anirbanghosh1176

2 жыл бұрын

@mritunjay yadav - in ditributed system you cannot have single point of failure

@namanmishra08

Жыл бұрын

That's because the entire point of having multiple regions is to have fault tolerance. For a single region, we can have a primary-secondary model with asynchronous replication between them but for a multi-region setup, each component should have a replica. One approach to solve this is to use distributed locks that Redis provides.

Thanks for the nice explanation. One question - What is the difference between fixed window counter and token bucket? Are they not doing the same?

@paraschawla3757

3 жыл бұрын

token bucket is the number of tokens in a bucket, there is refill() happening in bucket after nth min/sec. Number of tokens represent number of request that can be served. with every new request, it keeps going down...but tokens keep increasing based on ratelimit as well. Fixed window counter is having User+TimeStamp as key and count as value for particular window and then start again. Essence of both alogos are very different.

@curiousbhartiya8410

3 жыл бұрын

@@paraschawla3757 But the underlying problem of both algorithms is the same is what the original comment meant. That they both might end up serving twice the amount of the desired RPM.

@PABJEEGamer

3 жыл бұрын

With token bucket algorithm we have control over cost of each operation(we can associate how many tokens an operation costs), where as in fixed window we dont, since we increase the counter by 1 each time

Can you do system design for Groupon?

There is one con to all your videos. If you skip 10 sec of this video, you are doomed :-P Exceptional work, Narendra.

the threshold is calculated per second, for example AWS API gateway 5000 req/sec .. we can just declare an Array Queue or Array stack and start pushing elements in to it and keep flushing it every second ... + or - 10/20 request would not matter .. if the stack/Queue fills up it would throw an error and that error could be propagated to the user !!

Consider this scenario for token bucket: We can only serve 5 request/5 min. One request (10.05), Two request(10.06), Two request(10.07) we have served all the 5 requests so at 10.07 we will have 0. Now when we get new request at 10.11 it should be the valid request because request at 10.05 & 10.06 should be removed but as per token bucket it won't be served because 10.07 is set to 0 & will be reset at 10.12

@vaidyanathanpk9221

4 жыл бұрын

Not really. Read about the token bucket algorithm. Before serving the operation at 10.12, it'll try to figure out the time elapsed so far ( 10.12 - 10:07 ) Then it'll figure out the number of tokens to add for this time elapsed ( For 5 minutes, we need to add 5 tokens ) So before doing the serving calculation, these addition of tokens will be done and then when you do the calculation, you should be able to serve these requests. The key point is maintaining something called as lastUpdateTime in the bucket.

can we have sync service + memory between RL and Redis/Casandra ? So all RLs will go via sync service to get quick response. Sync service is responsible to write to Redis/Casandra. If sync service is not available, RL will make direct call to Redis/Casandra. Not sure how optimal this change is .

Is it ok that the LB is before the RL? Shouldn't be the other way around?

In case of token bucket algorithm, isn't Redis thread safe or can't we enforce synchronization using locks if requests from multiple application servers are meant to be served concurrently?

Hi is it possible to lock a key across replicas ? They are essentially copies of each other right ?

can you make a video for 'system design of live video broadcasting software'