앞 단계에서 덮어쓰지 않고 덧붙이기로 정했습니다. 그 대가가 읽기에서 나타납니다. 같은 키의 값이 여러 파일에 흩어져 있습니다.
새것부터 뒤진다
메모리 표를 먼저 보고, 없으면 정렬 파일들을 새것부터 봅니다. 찾으면 멈춥니다. 가장 새 값이 답이므로 더 볼 필요가 없습니다.
최근에 쓴 키는 앞에서 끝나므로 대개 빠릅니다. 문제는 없는 키입니다. 없다는 것을 확인하려면 파일을 전부 봐야 합니다.
| 조회 | 봐야 하는 곳 |
|---|---|
| 최근에 쓴 키 | 메모리 표나 첫 파일 |
| 오래전에 쓴 키 | 중간 파일까지 |
| 없는 키 | 전부 |
없는 키 조회는 생각보다 흔합니다. 캐시 앞단에서 처음 조회하는 키, 지워진 키, 오타가 섞인 키가 모두 여기 해당합니다.
파일마다 걸러내기를 앞에 둔다
각 파일에 "이 파일에 이 키가 있을 수 있는가" 를 아주 값싸게 답하는 장치를 붙입니다. 메모리에 작게 두고, 실제 파일을 열기 전에 먼저 묻습니다.
없다고 하면 확실히 없다. 파일을 열지 않는다
있다고 하면 아닐 수도 있다. 파일을 열어 확인한다
이 비대칭이 핵심입니다. 없다는 답이 확실하기 때문에 대부분의 파일을 건너뛸 수 있습니다. 없는 키 조회가 파일 열 번 읽기에서 한 번 이하로 줄어듭니다.
있다고 했는데 없는 경우가 조금 생깁니다. 그때는 파일을 헛읽습니다. 장치의 크기를 키우면 헛읽기가 줄어들고 메모리를 더 씁니다. 10ms 요구와 메모리 예산 사이의 균형점으로 정합니다.
파일 안에서 어떻게 찾나
정렬돼 있으므로 반씩 좁혀 찾을 수 있습니다. 다만 파일이 크면 그 탐색도 디스크 접근을 여러 번 만듭니다.
그래서 파일마다 일정 간격의 키와 그 위치를 따로 적어 둡니다. 그 목록은 메모리에 두고, 원하는 키가 어느 구간에 있는지 먼저 알아낸 뒤 그 구간만 읽습니다.
| 장치 | 무엇을 줄이나 |
|---|---|
| 걸러내기 | 열지 않아도 되는 파일 |
| 구간 목록 | 파일 안에서 읽어야 하는 양 |
파일 수가 지연을 정한다
걸러내기가 있어도 파일이 많으면 물어볼 곳이 많아지고, 있다고 잘못 답하는 경우도 함께 늘어납니다.
파일 10개: 걸러내기 10번, 헛읽기 확률도 10배
파일 3개: 걸러내기 3번
그래서 파일 수를 줄이는 일이 읽기 지연 관리의 핵심입니다. 그것이 다음 단계의 주제이고, 쓰기 구조와 읽기 성능이 여기서 맞물립니다.
사본 둘에서 읽으면 무엇을 비교하나
읽기 응답 수를 둘로 정했으므로 두 사본의 답을 받습니다. 두 값이 다르면 앞 단계의 충돌 판단을 적용합니다.
그리고 낡은 값을 준 사본에 최신 값을 알려 주는 것이 값싼 기회입니다. 읽는 김에 사본을 맞추는 셈이고, 이 방식이 뒤의 복구 단계에서 다시 나옵니다.