Rate Limiting system design | TOKEN BUCKET, Leaky Bucket, Sliding Logs

แชร์
ฝัง
  • เผยแพร่เมื่อ 14 ธ.ค. 2024

ความคิดเห็น • 272

  • @khalidelgazzar
    @khalidelgazzar ปีที่แล้ว +11

    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)

  • @vcfirefox
    @vcfirefox 2 ปีที่แล้ว +5

    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!!

  • @praveenakarapu
    @praveenakarapu 6 ปีที่แล้ว +17

    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.

  • @logeshkumar8333
    @logeshkumar8333 5 ปีที่แล้ว +11

    This channel is just hidden Gem!

  • @RandomShowerThoughts
    @RandomShowerThoughts ปีที่แล้ว

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

  • @princenarayana
    @princenarayana 3 ปีที่แล้ว +10

    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

  • @ambujbaranwal9351
    @ambujbaranwal9351 3 หลายเดือนก่อน

    00:04 Rate limiting is essential for managing API usage and protecting against misuse and attacks.
    04:46 Rate-limiting algorithm for token management
    09:30 The algorithm for managing tokens and requests can be memory efficient but may cause race conditions in a distributed environment.
    13:57 Using sliding locks algorithm to calculate the rate in real time
    18:28 Implement sliding-window counter for efficient memory usage
    22:47 The solution optimizes memory usage by using counters instead of storing every request entry
    27:11 Inconsistency in rate limiting leads to exceeding request limits
    31:28 Syncing data between distributed systems can result in latency and race conditions.

  • @ShivamSingh-jw8ey
    @ShivamSingh-jw8ey 4 ปีที่แล้ว +2

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

  • @sbylk99
    @sbylk99 5 ปีที่แล้ว +6

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

  • @lolnikal6851
    @lolnikal6851 10 หลายเดือนก่อน

    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

  • @mohammadfarseenmanekhan4820
    @mohammadfarseenmanekhan4820 3 ปีที่แล้ว

    very underrated youtube channel for system design

  • @valeriiryzhuk4126
    @valeriiryzhuk4126 5 ปีที่แล้ว +5

    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

  • @nikhilchopra9247
    @nikhilchopra9247 6 ปีที่แล้ว +3

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

  • @prabudasv
    @prabudasv 4 ปีที่แล้ว +3

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

  • @rabbanishahid
    @rabbanishahid 3 ปีที่แล้ว +2

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

  • @terigopula
    @terigopula 5 ปีที่แล้ว +24

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

  • @abasikhan100
    @abasikhan100 2 ปีที่แล้ว +2

    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.

  • @1qwertyuiop1000
    @1qwertyuiop1000 3 ปีที่แล้ว

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

  • @SanjayKumar-di5db
    @SanjayKumar-di5db 3 ปีที่แล้ว +10

    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
      @himanshu111284 3 ปีที่แล้ว +2

      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
      @SanjayKumar-di5db 3 ปีที่แล้ว +5

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

    • @rajsekharmahapatro
      @rajsekharmahapatro 2 ปีที่แล้ว

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

    • @xuanwang7400
      @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.

  • @Awaarige
    @Awaarige 4 ปีที่แล้ว +3

    Bro, You saved my months. Love from Pakistan

  • @JoshKemmerer
    @JoshKemmerer 3 ปีที่แล้ว +1

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

  • @VirgiliuIonescu
    @VirgiliuIonescu 4 ปีที่แล้ว +3

    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

  • @vinodcs80
    @vinodcs80 2 ปีที่แล้ว

    very comprehensive video. Great work. subscribed

  • @rajeshd7389
    @rajeshd7389 4 ปีที่แล้ว

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

  • @dragonmohammad
    @dragonmohammad 4 ปีที่แล้ว

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

  • @screen189
    @screen189 6 ปีที่แล้ว +6

    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
      @TechDummiesNarendraL  6 ปีที่แล้ว +6

      Added to TODO, Thanks

    • @screen189
      @screen189 6 ปีที่แล้ว +1

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

  • @molugueshwar1
    @molugueshwar1 5 ปีที่แล้ว

    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
      @nikhilneela 5 ปีที่แล้ว

      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
      @molugueshwar1 5 ปีที่แล้ว

      @@nikhilneela yes Nikhil. That's right

  • @amitchaudhary6199
    @amitchaudhary6199 4 ปีที่แล้ว

    Great work Narendra👍👍

  • @ishansoni8494
    @ishansoni8494 4 ปีที่แล้ว

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

  • @karthikrangaraju9421
    @karthikrangaraju9421 4 ปีที่แล้ว +4

    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

  • @PankajKumar-mv8pd
    @PankajKumar-mv8pd 4 ปีที่แล้ว +2

    One of best explanation, thanks man :)

  • @gulati9
    @gulati9 5 ปีที่แล้ว +6

    At 19:18 How can we serve 11 requests , when the limit is set to 10?

  • @akhashramamurthy8774
    @akhashramamurthy8774 4 ปีที่แล้ว

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

  • @rationalthinker3223
    @rationalthinker3223 ปีที่แล้ว

    Outstanding Explanation

  • @keatmin
    @keatmin 3 ปีที่แล้ว +4

    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?

  • @adityagoel123able
    @adityagoel123able 3 ปีที่แล้ว

    Awesome Narendra..

  • @saurabhchako89
    @saurabhchako89 ปีที่แล้ว

    Great video. Well explained.

  • @r3jk8
    @r3jk8 5 ปีที่แล้ว +1

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

  • @dev-skills
    @dev-skills 5 ปีที่แล้ว +6

    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
      @victoryang7734 4 ปีที่แล้ว

      I think his assumption is redis is seperate

    • @Priyam_Gupta
      @Priyam_Gupta 3 ปีที่แล้ว

      Yes this will be taking care as they are atomic.

    • @abcdef-fo1tf
      @abcdef-fo1tf ปีที่แล้ว

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

  • @153deep
    @153deep 5 ปีที่แล้ว

    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
      @vaidyanathanpk9221 5 ปีที่แล้ว

      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.

  • @thejaswiniuttarkar620
    @thejaswiniuttarkar620 4 ปีที่แล้ว

    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 !!

  • @mszjuliak
    @mszjuliak 5 ปีที่แล้ว +17

    What's the difference between token bucket and fixed window? they seem so similar

    • @mumbaibusa
      @mumbaibusa 4 ปีที่แล้ว +5

      The key and value stores are different for the two. In the case of the fixed counter, the key is defined by the Userid+minute whereas for token bucket the key is userid. For value the FC is just number of reqs, for token you track the time and the number of requests so the checking algorithm has more to do.

    • @preety202
      @preety202 4 ปีที่แล้ว +2

      Burst problem at boundary seem to exist in token bucket as well right?

    • @romangavrilovich8453
      @romangavrilovich8453 4 ปีที่แล้ว

      @@preety202 yes

    • @grantl3032
      @grantl3032 4 ปีที่แล้ว

      seems they are about the same to be functionally, maybe a bit diff implement wise?

    • @paraschawla3757
      @paraschawla3757 4 ปีที่แล้ว

      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.

  • @dbenbasa
    @dbenbasa 4 ปีที่แล้ว +8

    For token bucket - why do we need to update the timestamp (and not only the counter) when we are within the same minute, e.g. from 11:01:10 to 11:01:15?
    Why not just upata the timestamp when refilling the bucket, i.e. when we switched to a different minute, e.g.: from 11:01:10 to 11:02:07?

    • @alivesurvive471
      @alivesurvive471 3 ปีที่แล้ว

      You only set the timestamp on the first connection within the period or if you using something like memcached you can set the instance with a ttl value.

  • @shrimpo6416
    @shrimpo6416 2 ปีที่แล้ว

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

  • @081sidd
    @081sidd 5 ปีที่แล้ว +11

    at 10:37 video time, you mentioned that race condition may occur because of multiple requests coming from the different or same server.
    As you said, we are using Redis for this solution. Redis commands are atomic in itself and while executing atomic commands there is no scope of any data races. Did I get something wrong here?

    • @gxbambu
      @gxbambu 5 ปีที่แล้ว

      same question here!

    • @musheerahmed5815
      @musheerahmed5815 5 ปีที่แล้ว +1

      Two request from the same user coming at the same time. Both get the same data one after the other. Both increment the count one after the other. The count ends up incremented only once.

    • @mukeshbansiwal
      @mukeshbansiwal 5 ปีที่แล้ว +4

      @@musheerahmed5815 Use optimistic locking by adding version column to avoid lost update

    • @vivek9876
      @vivek9876 5 ปีที่แล้ว +4

      Because here two operation are required. 1) Get the current counter value 2) And If its less than threshold then increment the counter. For example current counter value is 9 and threshold is 10 and if two request comes at the same time and both request see current value as 9 and so both request allowed but in real case one of the request must fail. You either has to take Lock implementation on Redis or have to write atomic operation using WATCH/MULTI or write LUA script for your usecase.

    • @faizanfareed9076
      @faizanfareed9076 4 ปีที่แล้ว

      Using redis lock or lua scripts increases latency to user request.

  • @aeb242
    @aeb242 ปีที่แล้ว

    Great lesson! Thank you!

  • @IC-kf4mz
    @IC-kf4mz 4 ปีที่แล้ว +9

    Token Bucket and Fixed Window counter, what's the difference?

    • @uditagrawal6603
      @uditagrawal6603 3 ปีที่แล้ว +1

      Yes this explanation for token bucket doesn't seem correct as in token bucket tokens are added at a particular rate in a particular window time , also there might be chances of going over rate limit in certain scenarios.

    • @PABJEEGamer
      @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

    • @abcdef-fo1tf
      @abcdef-fo1tf ปีที่แล้ว

      @@uditagrawal6603 why can't we have a set and compare operation on the counter, or just a restriction that it can't go over a certain amount, and have requests try to increment number by 1 and reject them if it can't?

  • @cantwaittowatch
    @cantwaittowatch 5 ปีที่แล้ว

    Well explained Narendra

  • @RandomShowerThoughts
    @RandomShowerThoughts ปีที่แล้ว

    31:00 and you can't even lock across the nodes. If you are sharding then maybe, but as soon as you introduce replication, I don't think it'll just work like that

  • @resetengineering
    @resetengineering 2 ปีที่แล้ว

    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

  • @bhaskargurram94
    @bhaskargurram94 4 ปีที่แล้ว +4

    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
      @paraschawla3757 4 ปีที่แล้ว

      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
      @curiousbhartiya8410 4 ปีที่แล้ว

      @@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
      @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

  • @michael4799
    @michael4799 3 ปีที่แล้ว

    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
      @prajwal9610 3 ปีที่แล้ว

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

    • @rekhakalasare4910
      @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

  • @sumonmal009
    @sumonmal009 3 ปีที่แล้ว

    THIS COMMENT IS FOR MY PERSONAL REFERENCE. TO UNDERSTAND PROPERLY WATCH THE FULL VIDEO
    --------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    algorithms of rate-limiting 4:19
    token bucket 6:01
    problem 10:35
    leaky bucket 10:42
    fixed window counter 12:56
    sliding logs 16:31
    problem 20:01
    solution 24:35
    Global rate-limiting in distributed system 25:35 26:50
    solution for inconsistency 28:01
    solution for race condition 29:59
    relaxing rate limit 32:30

  • @poojachauhan1509
    @poojachauhan1509 3 ปีที่แล้ว

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

  • @ajaypuri1837
    @ajaypuri1837 5 ปีที่แล้ว +3

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

  • @rangak7502
    @rangak7502 6 ปีที่แล้ว +1

    Awesome work sir.. 👍🏼

  • @saip7137
    @saip7137 4 ปีที่แล้ว

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

  • @krishankantsharma3655
    @krishankantsharma3655 4 ปีที่แล้ว +3

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

  • @rbsrafa
    @rbsrafa 2 ปีที่แล้ว

    Great video, congrats!!

  • @itsNaveen9
    @itsNaveen9 5 ปีที่แล้ว

    You have already served 8 instead of 5 at 28:34 , your intention is right, but Cache 1 = U1:3 and Cache 2 = U1:2, should be the case, instead of u1:4 in both.

  • @themynamesb
    @themynamesb 4 ปีที่แล้ว

    Great video.. Thanks for the knowledge.

  • @JitendraSarswat
    @JitendraSarswat 4 ปีที่แล้ว

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

  • @ashutoshbang5836
    @ashutoshbang5836 3 ปีที่แล้ว

    Great video, keep up the good work :)

  • @helishah6719
    @helishah6719 3 ปีที่แล้ว +1

    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)?

  • @rahulsharma5030
    @rahulsharma5030 3 ปีที่แล้ว

    @31:00 you have confused me here, if we use locks, region 1 will have lock in region 1 redis only. Still regions 2 call can read old data from region 2 redis and allow more requests. R1 should take lock of all regions DB theoretically if u say locking is one way to solve consistency?

  • @Ghost_1823
    @Ghost_1823 2 ปีที่แล้ว

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

  • @anonym705
    @anonym705 2 ปีที่แล้ว

    Excellent videos, just lacking good sound system.

  • @vishalkohli3953
    @vishalkohli3953 3 ปีที่แล้ว

    What a guy!! bless you bro

  • @DeepakMishra117
    @DeepakMishra117 5 ปีที่แล้ว +1

    At 17:50 and 22:56 do we need to sort the array? Won't the array be already sorted, as the requests are only appending the time at the end of the list?

    • @mmshaban2002
      @mmshaban2002 5 ปีที่แล้ว

      Same question I had in mind

  • @anuraggupta6890
    @anuraggupta6890 5 ปีที่แล้ว +4

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

  • @mostaza1464
    @mostaza1464 5 ปีที่แล้ว +1

    Great video! Thank you!

  • @anand2009ish
    @anand2009ish 3 ปีที่แล้ว

    Excellent..hats off

  • @divyeshgaur
    @divyeshgaur 5 ปีที่แล้ว

    thank you for sharing the video. neatly explained.

  • @dataguy7013
    @dataguy7013 4 ปีที่แล้ว +2

    @Naren, even with local memory, you can have inconsistency. It just is a bit faster. Do I have that right?

    • @Priyam_Gupta
      @Priyam_Gupta 3 ปีที่แล้ว

      yes it won't work. if we are even talking about updating it all the time its better to rely on redis cluster to do the copy then our application server.

  • @springtest540
    @springtest540 6 ปีที่แล้ว +3

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

  • @hemangakrishnaborah4987
    @hemangakrishnaborah4987 4 ปีที่แล้ว +1

    I found this video very useful. One thing that can be improved is the way it is presented. At times the material seems unorganized. For example, there are flashes on the screen because the speaker forgot to mention it verbally. Adding a few notes before making the video may help the presenter have a good flow.

  • @DharaVisual
    @DharaVisual 3 ปีที่แล้ว

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

  • @amanshivhare5592
    @amanshivhare5592 4 ปีที่แล้ว

    So Ideally, Token Bucket can have more request in particular time. Like if 5 request were made on 11:55:00 and the very next minute 11:56:00 5 more request are made, so total 10 request can be made in a minute. (or size of a bucket)? Right?

    • @IC-kf4mz
      @IC-kf4mz 4 ปีที่แล้ว

      Yes. If it's implemented as explained you are right.

  • @madhusogam5823
    @madhusogam5823 4 ปีที่แล้ว

    very nice tutorial .. great work :)

  • @singhalvikash
    @singhalvikash 3 ปีที่แล้ว

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

  • @prasukjain8488
    @prasukjain8488 ปีที่แล้ว

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

  • @prakashkaruppusamy3817
    @prakashkaruppusamy3817 4 หลายเดือนก่อน

    Good one bro !

  • @harinale4483
    @harinale4483 3 หลายเดือนก่อน

    Hi Narendra,
    Relaxing Rate Limit and Local Memory + sync service is almost similar because in both the solution we might serve couple of extra request. what is your thought on my understanding?

  • @imranhussain8700
    @imranhussain8700 3 ปีที่แล้ว

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

  • @akshaytelang4532
    @akshaytelang4532 4 ปีที่แล้ว +1

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

  • @raghugrinus4779
    @raghugrinus4779 3 ปีที่แล้ว

    Can you please let us know the books which you have read to prepare for the video?

  • @mritunjayyadav3788
    @mritunjayyadav3788 4 ปีที่แล้ว +2

    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
      @anirbanghosh1176 2 ปีที่แล้ว +2

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

    • @namanmishra08
      @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.

  • @aeshwer
    @aeshwer 3 หลายเดือนก่อน

    excellent video

  • @nishathussain3672
    @nishathussain3672 4 ปีที่แล้ว

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

  • @sethuramanramaiah1132
    @sethuramanramaiah1132 2 ปีที่แล้ว

    Don't the fixed window counter also run into concurrency issue like the first scenario ?

  • @indrajitbanerjee5131
    @indrajitbanerjee5131 2 ปีที่แล้ว

    This is not efficient and optimized, cause it has to do linear O(N) time processing for each requests. The way it actually solves rate limiting is:
    1. Create a container/ list of max N size, when you have to serve N requests/ min let say.
    2. When a request comes:
    2.1. If the container size is lesser than N, then add the timestamp.
    2.2. If no, then do a binary search on the list with (TS - 1 min), this will return the index of the timestamp which got served at the beginning of the last minute. Get the index diff from that position and that is the number of requests you already served.
    2.2.1. If that is more than or equal to N -> wait in the message queue with a signal or wait time.
    2.2.2. If no, then add the TS entry at the list.
    3. Keep a sanity check on each list size, that it should always contain the timestamps of last N requests. Keep on deleting the old requests.
    This way the response time reduces to O(logN) and also the latency is resolved.

  • @vigneshbaskaran631
    @vigneshbaskaran631 3 ปีที่แล้ว

    Imo, redis key value pair is the only viable solution(first one). Others are examples for over engineering if we implement.

  • @manasranjan4
    @manasranjan4 2 ปีที่แล้ว

    Good bro. Awesome

  • @rushio8673
    @rushio8673 หลายเดือนก่อน

    the video was good, but i think token bucket wasn't explained clearly, we took example of 5 tokens per minute, but do we update the last request time everytime after receiving the request ? or we just keep the first request time so that we know whether 1 minute is elapsed after the first request, or since which second we started making a request that started getting deducted from the max limit ? for example what if 4 requests were made in the later half of the minute and 4 more requests were made in the first half of the next minute ? in that case we made 8 requests exceeding the threshold limit of 5, no clear explanation threre

  • @pratyushprateek2503
    @pratyushprateek2503 2 ปีที่แล้ว

    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?

  • @abcd12272
    @abcd12272 4 ปีที่แล้ว

    Could there be race conditions for the window method too?

  • @javacoder1986
    @javacoder1986 5 ปีที่แล้ว

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

  • @shrikantkhadilkar4019
    @shrikantkhadilkar4019 2 ปีที่แล้ว

    Hello Narendra, Fixed window counter looks the same as token bucket for me - only the concept is different but the effect will be the same, right?

  • @santoshdl
    @santoshdl 5 ปีที่แล้ว

    thanks Narendra

  • @cbest3678
    @cbest3678 3 ปีที่แล้ว

    isnt the token bucket and fixed window has the same problem of boundary request problem... ? since even in token bucket you can request more token in end of the first request window and request more token to the second of the window.?