@kyanny's blog

My thoughts, my life. Views/opinions are my own.

■

https://github.com/throttled/throttled と同じ GCRA アルゴリズムを実装（移植）した https://github.com/viafintech/gcra-ruby/tree/master には正式な mem_store 実装はないけどテストコードの中に実質 mem_store な実装がある。しかしそれを使ってレートリミットを実装してみると、時間が経過しても回復しない。

class TestStore
  attr_accessor :now
  attr_accessor :fail_sets

  def initialize
    @now = 0
    @data = {}
    @fail_sets = false
  end

  def get_with_time(key)
    return @data[key], @now
  end

  def set_if_not_exists_with_ttl(key, value, ttl)
    return false if fail_sets

    if @data.has_key?(key)
      return false
    end

    @data[key] = value
    return true
  end

  def compare_and_set_with_ttl(key, old_value, new_value, ttl)
    return false if fail_sets

    if @data[key] != old_value
      return false
    end

    @data[key] = new_value
    return true
  end
end
#!/usr/bin/env ruby

require 'gcra/rate_limiter'
require_relative 'test_store'

store = TestStore.new

rate_period = 0.5  # Two requests per second
max_burst = 10     # Allow 10 additional requests as a burst
limiter = GCRA::RateLimiter.new(store, rate_period, max_burst)

p limiter

x = 0
loop do
  exceeded, info = limiter.limit('foo', 1)
  pp [exceeded, info]
  if exceeded
    x += 1
  end
  if x > 50
    break
  end
  sleep(rand(0.01..0.02))
end
❯ ruby mem.rb
#<GCRA::RateLimiter:0x000000010a8091d8 @store=#<TestStore:0x000000010a8092a0 @now=0, @data={}, @fail_sets=false>, @emission_interval=500000000, @delay_variation_tolerance=5500000000, @limit=11>
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=10, reset_after=0.5, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=9, reset_after=1.0, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=8, reset_after=1.5, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=7, reset_after=2.0, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=6, reset_after=2.5, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=5, reset_after=3.0, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=4, reset_after=3.5, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=3, reset_after=4.0, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=2, reset_after=4.5, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=1, reset_after=5.0, retry_after=nil>]
[false, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=nil>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]
[true, #<struct GCRA::RateLimitInfo limit=11, remaining=0, reset_after=5.5, retry_after=0.5>]

TestStore のなかで ttl を無視してるからだと思うが、不思議なのは Go 実装の方の mem_store も ttl は無視しているのに、それを使ったレートリミットの実装ではちゃんと回復するところ。

https://github.com/throttled/throttled/blob/master/store/memstore/memstore.go

↓このコードは GOでGCRAレートリミット - aptpod Tech Blog から拝借したものを改変した。

package main

import (
    "flag"
    "fmt"
    "log"
    "time"

    "github.com/throttled/throttled/v2"
    "github.com/throttled/throttled/v2/store/memstore"
)

func main() {
    var (
        maxRate  int
        burst    int
        interval time.Duration
    )

    flag.IntVar(&maxRate, "r", 100, "")
    flag.IntVar(&burst, "b", 2, "")
    flag.DurationVar(&interval, "i", time.Second, "")

    flag.Parse()

    store, err := memstore.New(65536)
    if err != nil {
        log.Fatal(err)
    }

    quota := throttled.RateQuota{
        MaxRate:  throttled.PerSec(maxRate),
        MaxBurst: burst,
    }
    rateLimiter, err := throttled.NewGCRARateLimiter(store, quota)
    if err != nil {
        log.Fatal(err)
    }

    ticker := time.NewTicker(interval / 100)
    defer ticker.Stop()

    for i := 0; i < 100; i++ {
        ng, res, err := rateLimiter.RateLimit("sample", 1)
        if err != nil {
            log.Fatal(err)
        }
        if ng {
            fmt.Printf("NG res = %+v\n", res)
            continue
        }
        fmt.Printf("OK res = %+v\n", res)
    }
}
go mod init
go mod tidy
go run main.go
❯ go run main.go | head
OK res = {Limit:3 Remaining:2 ResetAfter:10ms RetryAfter:-1ns}
OK res = {Limit:3 Remaining:1 ResetAfter:19.95ms RetryAfter:-1ns}
OK res = {Limit:3 Remaining:0 ResetAfter:29.947ms RetryAfter:-1ns}
NG res = {Limit:3 Remaining:0 ResetAfter:29.942ms RetryAfter:9.942ms}
NG res = {Limit:3 Remaining:0 ResetAfter:29.94ms RetryAfter:9.94ms}
NG res = {Limit:3 Remaining:0 ResetAfter:29.938ms RetryAfter:9.938ms}
NG res = {Limit:3 Remaining:0 ResetAfter:29.936ms RetryAfter:9.936ms}
NG res = {Limit:3 Remaining:0 ResetAfter:29.934ms RetryAfter:9.934ms}
NG res = {Limit:3 Remaining:0 ResetAfter:29.932ms RetryAfter:9.932ms}
NG res = {Limit:3 Remaining:0 ResetAfter:29.931ms RetryAfter:9.931ms}

こちらは一応ちゃんと ResetAfter と RetryAfter の値が変化しているのでちゃんと動いているように見える。

どこに違いがあるのか、Go の mem_store のどこが Ruby の TestStore と意味的に違うのかがわからない。