제I부: 요청의 비용¶
알고리즘을 고르기 전에 그 알고리즘이 보호하려는 자원을 먼저 밝힙니다. 이 장에서는 이후의 모든 설계 결정을 재는 기준이 될 작은 모델들을 세웁니다. 원본 서버의 작업, 퍼즐 작업, 세션을 통한 비용 분할 상환, 그리고 신뢰할 수 없는 클라이언트가 서버에 붙잡아 둘 수 있는 메모리입니다.
요청 허용은 경제적 결정입니다¶
원본 서버가 허용된 요청마다 데이터베이스를 조회하고 페이지를 렌더링한다고 합시다. 그 작업을 \(c_o\), 요청당 게이트의 작업을 \(c_g\), 도착률을 \(r\)이라고 둡니다. 게이트가 없으면 원본 서버는 초당 \(r c_o\) 단위의 작업을 감당해야 합니다. 비율 \(a\)만큼 허용하는 게이트는 그 수요를 \(r a c_o\)로 바꾸고, 자신은 \(r c_g\)를 씁니다. 게이트는 절약한 원본 작업이 게이트 자신의 비용과 정상 방문자에게 지우는 비용을 넘을 때에만 쓸모가 있습니다.
이것은 용량 모델이며 측정이 아닙니다. 대역폭, 연결 상태, 저장소, 클라이언트 지연은 빠져 있습니다. 이 모델의 가치는 빠진 항이 모두 눈에 보인다는 데 있습니다. 캐시 적중은 \(c_o\)를 작게 만들 수 있고, 비싼 쿼리는 크게 만들 수 있습니다. 요청자 대 서버의 보편적인 비용 비율은 없습니다.
작업 증명이 입증하는 것¶
클라이언트 퍼즐은 누군가 공개된 검증 규칙을 만족하는 입력을 찾았다는 사실을 입증합니다. 상대가 사람이라는 사실, 신원, 선한 의도는 입증하지 않습니다. 요청자는 연산 자원을 빌리거나, 유효한 세션을 수명 안에서 재사용하거나, 작업을 여러 기계에 나눌 수 있습니다. 퍼즐은 요청 허용의 비용을 바꿉니다. 허용된 요청이 무엇을 할 수 있는지는 여전히 정책과 검사가 결정합니다.
주소 기반 제한은 이를 보완합니다. 주소 기반 제한은 주소 하나를 제약하지만, 공유 주소 하나가 많은 사람을 나타낼 수 있고 요청자 하나가 많은 주소를 쓸 수 있습니다. 퍼즐도 주소도 신원을 판정해 주지 못합니다. 그래서 Sibuna는 요청 허용, 검사, 평판을 서로 다른 결정으로 유지합니다.
확률변수로 보는 해시 탐색¶
이상적인 256비트 다이제스트에서 선행 0비트 \(b\)개를 요구하면, 독립 시행마다 성공 확률은 \(p = 2^{-b}\)입니다. 첫 성공까지의 시행 횟수를 \(K\)라고 하면 다음이 성립합니다.
기댓값은 꼬리 합에서 나옵니다.
난이도를 한 단계 올리면 기대 시행 횟수가 두 배가 됩니다. 그렇다고 모든 퍼즐이 두 배 오래 걸린다는 약속은 아닙니다. 어떤 퍼즐은 첫 시행에서 성공하고, 어떤 퍼즐은 평균보다 훨씬 오래 걸립니다. 풀이 한 번만 측정한 클라이언트는 대부분 이 무작위성을 측정한 셈입니다.
세션은 작업 비용을 분할 상환합니다¶
세션 하나가 만료 전까지 요청 \(m\)개를 허용하고, 퍼즐 비용이 \(c_p\), 검증 비용이 \(c_v\), 세션 확인 비용이 \(c_s\)라고 합시다. 실패한 시도를 무시하면 분할 상환한 요청당 게이트 비용은 \(c_v/m + c_s\)이고, 클라이언트의 퍼즐 비용은 \(c_p/m\)입니다. 세션 수명을 늘리면 사람과 자동화 클라이언트 모두에게 똑같이 도움이 됩니다. 세션 수명을 정하는 일은 정책 결정이며 암호학적 최적화가 아닙니다.
제한된 상태는 두 번째 예산입니다¶
작업을 요청 경로 밖으로 옮긴다고 작업이 사라지지는 않습니다. 인시던트가 비율 \(\lambda\)로 도착하고, 저장소 스레드가 평균 비율 \(\mu\)로 이를 영속화하며, 큐가 레코드 \(Q\)개를 담는다고 합시다. \(\lambda > \mu\)일 때 유체 근사로 다음을 얻습니다.
큐가 크면 시간을 벌 수 있지만 처리량을 늘려 주지는 않습니다. 일괄 처리는 트랜잭션 비용을 나누지만, 보관된 레코드는 여전히 메모리를 차지하고 결국 처리되어야 합니다. 과부하에서 Sibuna는 새 인시던트 레코드를 버리고 그 수를 셉니다. 요청에 대한 판단은 메모리 상태만으로 계속 내립니다. 운영자는 HTTP 성공률뿐 아니라 잃어버린 증거도 감시해야 합니다.
앞으로 지켜 갈 불변식¶
- 신뢰할 수 없는 요청은 서버 상태를 무한정 늘릴 수 없습니다.
- 유효한 요청 허용 토큰도 애플리케이션의 거부를 우회하지 못합니다.
- 버퍼는 그 버퍼에서 빌린 모든 슬라이스가 살아 있는 동안 살아 있습니다.
- 영속 재시도도 인시던트나 그 평판 효과를 여러 번 반영할 수 없습니다.
- 게시된 정책 스냅숏은 마지막으로 읽는 쪽이 놓아줄 때까지 바뀌지 않습니다.
이 책의 나머지 부분은 이 명제들을 참으로 만드는 메커니즘과, 위반을 드러낼 테스트를 이끌어 냅니다. 빠른 경로는 이 명제들이 참인 동안에만 쓸모가 있습니다.