x/sync/singleflight의 주의점과 제로 시간 캐시

ISUCON7의 본전에서 갱신 처리 후에 갱신 조작을 반영한 데이터를 반드시 반환해야 하며 데이터의 계산이 매우 무거운 문제를 제기했다.
원래 아이스콘에는 "포스트가 200을 답장하면 이후 GET 요청은 결과를 반영해야 한다"는 규칙이 많았지만, 이번 질문도 그중 하나라고 할 수 있다.
그럼 올해에야 알았어singleflight.이 과제도 쓸 수 있을 것 같아.
(참조golang.org/x/sync/singleflight에서 중복 호출 제외
이 때문에 사전에 Go가 올해 문제를 조율할 때 시도해 봤지만 그냥 적용하면 일관성을 얻지 못해 실패했다.조사한singleflight의 주의점과 업무 복습을 소개한다.

singleflight 동작

Singleflight의 주요 목적은 Thundering Herd 문제를 해결하는 것이다.
예를 들어, 유효 기간의 캐시가 있으면 리소스에 대한 병렬 액세스가 만료되고 캐시를 업데이트하기 위해 소스에 병렬 요청을 제출합니다. 이것이 캐시의 Thundering Herd 문제입니다.아래 그림을 보십시오.

A와 B가 병렬로 Singleflight를 통해Calc를 호출하지만 B가 호출될 때 이미 A의 요청을 실행하고 있기 때문에 결과를 공유하기만 하면 실제 계산이 되지 않는다.
일정 시간 Expire 캐시를 업데이트하는 등 전혀 문제가 없는 행동이지만 B가 호출되기 전에 업데이트 처리를 할 때 문제가 발생할 수 있습니다.
위의 그림에서 B는 데이터를 Mod2로 업데이트했습니다.그러나 이후 Singleflight를 통해 호출된Calc는 업데이트 전 상태에 따라 계산 결과를 되돌려줍니다.만약 이것이 고객에게 일치하지 않는다면,singleflight를 직접 사용할 수 없습니다.

작업 제안

이런 용례라도singleflight를 사용하면서 통합성을 유지하는 방법으로 자물쇠도 있다.
위의 시퀀스 그림에서 'Mod1' 과 'Get' 같은 데이터 접근은 그림에 명시되지 않은sync입니다.나는 미덱스 등에서 밀려났다고 생각한다.Calc가 계산하고 결과를 기다리는 모든 고객에게 돌아갈 때까지 이 Mutex를 계속 잠그십시오.이렇게 되면 Mod2는 잠금을 기다리는 상태가 되어 실행할 수 없습니다.결과적으로 B는'Mod2'가 반영되지 않은 응답을 받을 위험을 피할 수 있었다.

0시 캐시

pixiv prive isucon 2016 공략(4/5)에서도 사용되는 개인이 0시 캐시라고 부르는 수법은 통합성에 문제가 생기지 않는다.따라서 ISUCON에 적합합니다.
이 방법은 서열도로 표시하면 다음과 같은 느낌을 받을 수 있다.

(PlantUML)
A를 계산하기 시작하면 B와 C가 요구하지만 B와 C는 A의 요구를 공유하지 않는다.A에 대한 계산이 끝나면 B와 C에 대한 계산이 시작됩니다.B와 C가 받아들인 반응은 B가 한'Mod2'와 C가 한'Mod3'을 반영했다.
지금까지 아이디움으로 반복해서 썼지만,singleflight를 모방해 프로그램 라이브러리를 만들어 봤다.

창고.

샘플 코드

샘플 코드는 100goroutine에서 각각 10번씩 호출하는 방법이다.실행 후 출력은 다음과 같습니다.

direct: called 1000 times, 0 errors
singleflight: called 145 times, 140 errors
ZeroTimeCache: called 151 times, 0 errors
ZeroTimeCacheDelay: called 19 times, 0 errors

direct를 직접 호출할 때 실제 호출은 1000회입니다.

singleflight는singleflight를 통해 호출되었을 때 대상 방법의 호출은 145회로 통제되었지만 140차례의 업데이트가 반영되지 않은 결과가 관측되었다.

Zero Time Cache가 이 프로그램 라이브러리를 통해 호출할 때 대상 방법의 호출을 151회로 제어하고 일치성을 유지했다.

Zero Time Cache Delay는 고속 캐시에서 대상 방법을 호출하기 전에sleep을 끼워 넣었다.이렇게 하면 높은 병행도와 높은 주파수의 제로 시간 캐시 호출이 바쁜 회로가 되지 않기 때문에 CPU의 여가 시간을 확보할 수 있다.대상 방법의 호출 횟수를 19회로 줄이다.

문서와 README는 아직 준비되지 않았지만 코드는 매우 간단하니 반드시 코드를 직접 읽어 주십시오.

불순한 작업 보상: 2회 Do()라고 합니다

singleflight와 0 시간 캐시 시퀀스를 봤는데 B는singleflight입니다.Do()를 두 번 부르면 "지금 처리 중"이 아니라 "다음"의 결과로 제로 타임 캐시처럼 보입니다.
그런데 이게 잘 안 돼요.singleflight의 마지막 응답을 처리하는 부분은 공유 잠금을 가져와야 하기 때문에 때때로 대기 시간이 커질 수 있습니다.그리고 그 록의 취득 순서가 FIFO가 없기 때문에 B의 두 번째 도(都)가 먼저 록을 취득할 가능성이 있다.

(PlantUML)