링 큐 와 토 큰 통 을 기반 으로 한 스 트림 제한 모듈

개술
분포 식 서비스 구조 에서 예 를 들 어 마이크로 서비스 구 조 는 일반적으로 독립 된 gateway 모듈 을 구축 해 야 한다.gateway 모듈 의 주요 역할 은 유량 제어, 규칙 경로, 부하 균형, 감 권, 퓨즈 등 을 포함한다.한편, gateway 는 일반적으로 stateless 이기 때문에 자 유 롭 고 탄력 적 으로 클 러 스 터 규 모 를 신축 하여 실제 방문 장면 에 대응 할 수 있다.본 고 는 주로 golang 을 통 해 흐름 제한 모듈 을 실현 하 는 방안 을 소개 하 는데 그 관건 은 주로 두 가지 가 있다.

링 큐 (ring queue)

토 큰 통 알고리즘 (token bucket)

링 기반 대기 열 (ring queue)

type Queue struct {
    mtx      sync.RWMutex
    head     int64
    tail     int64
    capacity int64
    elemcnt  int64
    data     []interface{}
}

//          n 
func func (q *Queue) AtomEnqueue(d interface{}, n int64) bool {
}

//             ，            
func (q *Queue) DequeueBy(fc func(interface{}) bool) []interface{
}

링 대기 열 은 현재 접근 빈도 가 제한 값 에 도 달 했 는 지 여 부 를 판단 하기 위해 상태 저장 공간 을 제공 하 는 역할 을 합 니 다.
이 대기 열 을 사용 하기 전에 time. Tick () 시계 방법 으로 토 큰 을 정기 적 으로 발급 하 는 것 을 시도 해 보 았 으 나 성능 은 높 지 않 습 니 다.주파수 가 1000 rps 를 초과 할 때 time. Tick 을 사용 하 는 것 을 권장 하지 않 는 다 고 하 므 로 구체 적 으로 는 여기 controlling throughput with rate. limiter 를 참고 할 수 있 습 니 다.
또한 time. Tick () 을 사용 하면 정기 적 으로 goroutine 을 새로 열 어야 합 니 다.비록 많은 성능 을 소모 하 지 는 않 았 지만 피 할 수 있 는 것 은 항상 좋다.그리고 흐름 제한 이 ip 이나 user 등급 의 입도 까지 이 루어 지 려 면 비용 을 무시 하기 어렵다.
그리고 링 대기 열의 장점 중 하 나 는 메모리 가 초기 화 된 후에 기본적으로 고정 되 어 있다 는 것 입 니 다. 대기 열 에 있 는 모든 요 소 는 모든 요청 상태 (현재 예제 에 저 장 된 것 은 방문 시간 스탬프) 입 니 다. 요청 이 도 착 했 을 때 데이터 상 태 를 조회 하 는 동시에 대기 열 요소 의 업 데 이 트 를 진행 합 니 다.(time. Tick 과 는 다른 정기 성 이 있 습 니 다. 이것 은 요청 에 의 해 작 동 되 며, 다른 시스템 자원 에 의존 할 필요 가 없습니다.) 또 다른 장점 은 접근 속도 가 빠 르 고 메모리 복사 도 많 지 않 습 니 다. 그 중에서 주의해 야 할 것 은 경쟁 문 제 를 해결 하 는 것 입 니 다. 읽 기와 쓰기 자 물 쇠 를 사용 하 는 것 이 해결 방법 입 니 다.
토 큰 통 기반 (token bucket) 알고리즘

type TokenBucket struct {
    mutex    sync.Mutex
    capacity int64
    interval time.Duration
    tsQ      *Queue
}

//   token，     true，     false        
func (tb *TokenBucket) Take(n int64) (bool, time.Duration) {
}

//   token，     true，         
func (tb *TokenBucket) Wait(n int64, t time.Duration) bool {
}

자주 사용 하 는 흐름 제한 알고리즘 은 두 가지 가 있 습 니 다. 누 출 통 알고리즘, 토 큰 통 알고리즘 입 니 다. 인터넷 에 더 자세 한 알고리즘 설명 이 있 습 니 다. 여 기 는 설명 하지 않 습 니 다.
제 가 여기 서 사용 하 는 것 은 토 큰 통 과 유사 한 알고리즘 입 니 다. 원래 알고리즘 은 일정 시간 마다 통 에 token 을 넣 고 요청 이 있 을 때 token 을 가 져 갑 니 다. token 이 없 을 때 요청 을 기다 리 거나 실패 (Take) 로 돌아 갑 니 다. 여기 서 의 실현 은 차이 가 있 습 니 다.

우선 실현 중 token 을 넣 는 것 이 아니 라 요청 한 시간 스탬프 를 기록 하 는 것 입 니 다. 링 대기 열 에 남 은 요소 가 있어 야 성공 을 기록 할 수 있 습 니 다. 그렇지 않 으 면 기다 리 거나 되 돌아 오 는 데 실 패 했 습 니 다.

또한 촉발 시기 도 다르다. 시계의 주기 적 촉발 이 아니 라 요청 에 의 해 촉발 된다

원본 주소 및 테스트 사례
github 프로젝트 주소
엄격 한 검증 이 되 지 않 았 습 니 다. 여러분 이 bug 를 떨 어 뜨리 는 것 을 환영 합 니 다. 그 중에서 테스트 사례 는 다음 과 같 습 니 다.

$ go test
[1 2 3 4 5 6]
[1 2 3 4 5 6 7 8]
[3 4 5 6 7 8 9 10]
[9 10 3 4 5 6 7 8]
[10 11 12 13 14 15 16 17]
[10 11 12 13 14]
[15 16 17]
[]
[9 10 haha 15 3 6]
[9 10]
take-n:1 time-used:3.327341023s suc-cnt:4000 fail-cnt:9996000
take-n:2 time-used:3.334162956s suc-cnt:2000 fail-cnt:9998000
take-n:1 time-used:1.257582083s suc-cnt:1499 fail-cnt:1001
take-n:1 time-used:2.250956732s suc-cnt:2500 fail-cnt:0
take-n:2 time-used:1.254886958s suc-cnt:999 fail-cnt:1501
take-n:2 time-used:4.251330391s suc-cnt:2499 fail-cnt:1
take-n:2 time-used:2.251117604s suc-cnt:2500 fail-cnt:0
PASS
ok      github.com/moxiaomomo/token-bucket23.931s

모 과 망 동기 화 링크:https://www.imooc.com/article/31788