Categories
Uncategorized

Take you to understand what is limiting

Foreword

Only the head can become strong.

Text has been included to my GitHub repository, welcome Star: https: //github.com/ZhongFuCheng3y/3y

Before learning when this kind of thing can not be in contact with high concurrency / high flow, of course, is not so limiting contact of the. When looking at the project company, I found to be useful to limit the flow (RateLimiter), incidentally understand wave.

First, limiting the basics of presentation

Why would limit, I believe I do not have much to say.

    For example, I went to a restaurant for dinner on weekends, but too many people, I can only go to the front desk to get a number, and other number to me when to get into a restaurant for dinner. If the hotel is not limiting how to do? A meal to the point, people rushed inside, and they can not deal with so many restaurants crowd, it is easy to have an accident (hotel filled with people, no way. The hotel staff broke down, handle, however)

    Back to the code in the world is the same, the server can handle a limited number of requests, particularly if a large volume of requests, we do need to limit the flow (either let the request to wait, or put the request to throw)

In the code of the world, there are two common limiting algorithm:

    Token bucket algorithm

    Leaky Bucket Algorithm

1.1 What is a leaky bucket

For example, now I have a bucket, I can hold a piece of green water capacity, if I can hold over capacity in, go down to pour buckets inside, it will overflow (limiting):

We currently know is:

    Bucket capacity is fixed (FIG green piece is)

    It exceeds the capacity of the bucket will overflow (or wait, either directly discarded)

OK, now we have to dig a hole in a bucket, so that water can flow out from inside the cave:

Bucket size of the hole is fixed, the rate of water flow out from the hole is fixed.

So conclude two parameters required for the algorithm:

    Bucket capacity

    Leakage rate

Leaky Bucket algorithm implemented in two:

    Bursty traffic is not allowed: if the water rate greater than the rate of water directly discard excess water. For example, I can hold the bucket capacity of 100L, but my water bucket rate is 10L / s. At this point, if there are 100L / s of water came in, I just let 10L of water into the bucket, and the rest are limiting. (Defining a requested speed)

    Allow some unexpected flow situation: my bucket can hold 100L, if now my bucket is empty, then this could 100L of water into my bucket. I’m at a rate of 10L / s flow out of these, if there 100L of water came in, only the current limit.

After the above analysis we know:

Leaky bucket algorithm may burst traffic on the network a smooth (because leakage rate is fixed)

1.2 What is a token bucket algorithm

Now I have another bucket, the bucket is not used to hold water, used to hold the token:

Token will be thrown into the bucket inside a certain rate, for example, one second I threw 10 tokens into the bucket:

Token bucket can hold the number of capped, such as my bucket can only hold up to 1000 tokens.

For each request, it will take a token bucket to

  • 比如这秒我有1001个请求,我就去桶子里边拿1001个令牌,此时可能会出现两种情况:

      No bucket inside 1001 tokens, only 1000, it did not get the token request can only be blocked (wait)

      1,001 tokens inside the bucket, all the requests can be executed.

Bursty traffic on the network token bucket algorithm support

The difference between the drain and the tub token buckets: we estimated from the above examples can be seen, only the leaky bucket at a fixed rate to process the request, the token bucket may be the maximum number of tokens the bucket to process the request

Two, RateLimiter use

RateLimiter is a limiting component of Guava, my side of this system will have to use current limiting components, very convenient to use.

The introduction of pom-dependent:


    com.google.guava
    guava
    20.0

RateLimiter It is based on the token bucket algorithm, API is very simple, look at the following Demo:

public static void main(String[] args) {
        //线程池
        ExecutorService exec = Executors.newCachedThreadPool();
        //速率是每秒只有3个许可
        final RateLimiter rateLimiter = RateLimiter.create(3.0);

        for (int i = 0; i < 100; i++) {
            final int no = i;
            Runnable runnable = new Runnable() {
                @Override
                public void run() {
                    try {
                        //获取许可
                        rateLimiter.acquire();
                        System.out.println("Accessing: " + no + ",time:"
                                + new SimpleDateFormat("yy-MM-dd HH:mm:ss").format(new Date()));

                    } catch (Exception e) {
                        e.printStackTrace();
                    }

                }
            };
            //执行线程
            exec.execute(runnable);
        }
        //退出线程池
        exec.shutdown();
    }

We can see from the results, can be performed only three per second:

Third, limiting distributed

RateLimiter is limiting a stand-alone component, if the application is distributed, then how to do?

May be used Redis + Lua way to achieve substantially the lua script code is as follows:

local key = "rate.limit:" .. KEYS[1] --限流KEY
local limit = tonumber(ARGV[1])        --限流大小
local current = tonumber(redis.call('get', key) or "0")
if current + 1 > limit then --如果超出限流大小
  return 0
else  --请求数+1,并设置1秒过期
  redis.call("INCRBY", key,"1")
   redis.call("expire", key,"1")
   return current + 1
end

Java code is as follows:

public static boolean accquire() throws IOException, URISyntaxException {
    Jedis jedis = new Jedis("127.0.0.1");
    File luaFile = new File(RedisLimitRateWithLUA.class.getResource("/").toURI().getPath() + "limit.lua");
    String luaScript = FileUtils.readFileToString(luaFile);

    String key = "ip:" + System.currentTimeMillis()/1000; // 当前秒
    String limit = "5"; // 最大限制
    List keys = new ArrayList();
    keys.add(key);
    List args = new ArrayList();
    args.add(limit);
    Long result = (Long)(jedis.eval(luaScript, keys, args)); // 执行lua脚本,传入参数
    return result == 1;
}

Explanation:

    Java code passed in key parameters and maximum limit limit into the lua script

  • 执行lua脚本(lua脚本判断当前key是否超过了最大限制limit)

      If so, it returns 0 (limiting)

      If not, the returns 1 (the program continues)

Reference Source:

  • https://segmentfault.com/a/1190000016552464

More information Reference:

  • https://segmentfault.com/a/1190000016042927
  • [Http://wuwenliang.net/2018/10/27/%E8%87%AA%E5%B7%B1%E5%86%99%E5%88%86%E5%B8%83%E5%BC% 8F% E9% 99% 90% E6% B5% 81% E7% BB% 84% E4% BB% B6-% E5% 9F% BA% E4% BA% 8ERedis% E7% 9A% 84RateLimter /] (http: / /wuwenliang.net/2018/10/27/ write their own distributed limiting component - based Redis of RateLimter /)

At last

Dry willing output of Java technology public number: Java3y. There are more than 200 original articles technical articles, massive video resources within the public number, exquisite mind map, you can get attention!

I think the article is well written, thumbs up!

Leave a Reply