흐름 제한 알고리즘

영패 통:
① 네트워크 에 보 내 는 데이터 의 수 를 제어 하고 돌발 데이터 의 전송 을 허용 합 니 다.
② 원 리 는 시스템 이 일정한 속도 로 통 에 토 큰 을 넣 는 것 이 고, 요청 이 처리 되 려 면 먼저 통 에서 토 큰 을 가 져 와 야 하 며, 통 에 토 큰 이 없 을 때 서 비 스 를 거부 하 는 것 이다.
물통:
① 그 주요 목적 은 데이터 가 네트워크 에 주입 되 는 속 도 를 제어 하고 네트워크 의 돌발 트 래 픽 을 부 드 럽 게 하 는 것 이다.
② 새 는 통 (패 킷 캐 시) 이 넘 치면 패 킷 이 버 려 집 니 다.
③ 요 구 를 물 에 비유 하여 물이 오 면 통 에 먼저 넣 고 한 정 된 속도 로 물 을 내 보 냅 니 다. 물이 너무 세 게 나 와 물이 빨리 나 오지 않 으 면 물이 바로 넘 쳐 서 서 서 비 스 를 거부 합 니 다.
두 통 의 비교: 모두 데이터 성형 (Traffic Shaping) 이나 속도 제한 (Rate Limiting) 이다.

 1.     ，    
 2.        

사례: Google 의 Guava 패키지 의 Rate Limiter 클래스 가 토 큰 통 알고리즘 솔 루 션 입 니 다.
요약:
주의해 야 할 것 은 어떤 상황 에서 누 출 통 알고리즘 은 네트워크 자원 을 효과적으로 사용 할 수 없다 는 것 이다. 누 출 통 의 누 출 속 도 는 고정 적 이기 때문에 네트워크 에 정체 가 발생 하지 않 더 라 도 누 출 통 알고리즘 은 특정한 단독 데이터 흐름 을 포트 속도 에 이 르 게 할 수 없다.따라서 누 출 통 알고리즘 은 갑 작 스 러 운 특성 이 있 는 유량 에 효율 이 떨어진다.토 큰 통 알고리즘 은 갑 작 스 러 운 특성 을 가 진 트 래 픽 을 만족 시 킬 수 있다.
알고리즘 구현:
1. Leaky Bucket: 아주 작은 데이터 요청 상한 선 을 설정 하고 데이터 가 이 상한 선 에 이 르 렀 을 때 버 립 니 다. 즉, 서 비 스 를 거부 합 니 다.통 안에 새로운 공간 이 생기 면 새 요청 을 다시 받 을 수 있다.
방법: 대기 열 로 요청 한 (FIFO 선진 선 출).장점: 아주 작은 메모리 가 모든 사용자 의 흐름 을 제한 합 니 다.단점: 통 이 가득 차 면 새로운 요청 이 버 려 집 니 다.
2. Fixed Window (고정 창): 한 시간 동안 (창) 받 은 요청 수 를 설정 합 니 다. 이 요청 수 를 초과 한 요청 은 버 려 집 니 다.장점: 누 출 통 에 비해 요청 이 처 리 될 확률 이 높 아 집 니 다. 12306 의 분할 방 표 전략 처럼 '공평 해 보 입 니 다'.단점: 창 은 보통 작 지만 초기 트 래 픽 은 창 크기 보다 훨씬 크 기 때문에 창의 시작 시간 에 최 악의 경우 2 배의 트 래 픽 을 가 져 와 많은 소비자 들 이 방치 되 어 놀 라 운 효 과 를 초래 할 수 있다.
3. Sliding Log (미끄럼 로그): 미끄럼 로그 알고리즘, 단위 시간 대 에 기 록 된 모든 사용자 의 요청 시간 과 요청 수 를 이용 합 니 다.새로운 요청 이 들 어 오 면 이 요청 을 현재 요청 로그 정보 와 비교 하고 새 사용자 라면 즉시 응답 처리 하 십시오. 그렇지 않 으 면 요청 수가 창기 에 미리 설 정 된 요청 상한 선 을 초과 하 는 지 여부 에 따라 이 요청 을 처리 할 지 여 부 를 결정 합 니 다.
장점: 창 알고리즘 이 창 경계 에서 발생 할 수 있 는 두 배의 데이터 문제 (예 를 들 어 사용자 가 요청 을 중복 제출 하 는 것) 를 피 할 수 있 습 니 다. 즉, 사용자 의 놀 라 운 효 과 를 피 할 수 있 습 니 다.단점: 대량의 로 그 를 저장 하고 요청 이 완료 되 기 전에 사용자 요청 수 보다 많 기 때문에 분포 식 시스템 에서 작업 하기 어렵 습 니까?
4. Sliding Window (슬라이딩 창): 슬라이딩 창 알고리즘 은 고정 창 알고리즘 의 저비용 과 슬라이딩 로그 알고리즘 을 결합 하여 해결 할 수 있 는 경계 상황 입 니 다.구현 정책: a. "모든" 창 에 요청 수 를 설정 합 니 다.b. 이전 창의 요 구 량 과 이 창 이 지나 간 시간 을 결합 하여 상한 선 을 계산 하여 피크 값 을 부 드 럽 게 요청 합 니 다.
사례:
예 를 들 어 스 트림 제한 상한 선 은 분당 10 개의 요청 이 고 창 크기 는 1 분 이 며 이전 창 에 서 는 총 6 개의 요청 이 처리 되 었 습 니 다.현재 이 새로운 창 이 20 초 를 거 쳤 다 고 가정 하면 지금까지 허용 한 요청 상한 선 은 10 - 6 * (1 - 20 / 60) = 8
： 입 니 다.
성능 이 좋 고 누 출 통 알고리즘 이 가 져 온 배 고 픔 문제 (나중에 요청 이 거부 되 었 음) 를 피 할 수 있 으 며 고정 창 알고리즘 의 요 구 량 이 갑자기 증가 하 는 문 제 를 피 할 수 있 습 니 다.
분산 구현: 
어 려 운 점 은 흐름 제한 상한 선 이 전체 역 의 유량 에 대해 설 치 된 것 이다. 그러면 각 노드 는 어떻게 각자 처리 하 는 양 을 조율 해 야 합 니까?