SR-InnoDB, old 5%·ghost 승격 선별해 기본 37% 설정보다 TPC-H Q6·Q12 미스율 41.8%·40.3% 낮춰

하버드대 Yunjia Zheng과 Juncheng Yang은 반복 스캔에 따른 캐시 미스 증가를 줄이는 SR-Gadgets를 제안했습니다. 이 기법은 캐시를 채울 때 새 페이지를 보호 영역에 먼저 넣고, 퇴출 페이지를 ghost queue에 기록하거나 다시 보호 영역으로 올릴 때 최근 접근 여부를 따집니다. 연구진은 이를 MySQL InnoDB 버퍼풀에 적용해 TPC-H를 시험했습니다. 기본 설정(old sublist 37%)과 비교해 old sublist를 5%로 둔 SR-InnoDB는 Q6·Q12의 버퍼풀 미스율을 각각 41.8%, 40.3% 낮췄습니다.

기존의 스캔 저항성 논의는 대개 한 번만 순회하는 작업이 캐시를 오염시키는 문제에 초점을 뒀습니다. 같은 데이터를 반복해서 읽으면 한 차례 스캔에서 뒤에 읽힌 블록이 앞서 읽은 블록을 밀어내 다음 순회에서도 재사용할 데이터를 놓칠 수 있습니다. 캐시 용량을 조금 늘렸을 때 미스율이 급격히 떨어지는 현상은 미스율 절벽, 캐시를 키웠는데 미스율이 오르는 현상은 Belady 이상이라고 합니다. 논문은 스캔 저항성을 이런 반복 스캔 문제까지 줄이는 성질로 다룹니다.

InnoDB 버퍼풀은 페이지를 old sublist와 young sublist로 나눠 관리합니다. 새로 읽은 페이지는 old의 앞쪽에 들어가고, 다시 접근되면 young의 앞쪽으로 이동합니다. 페이지를 내보낼 때는 old의 뒤쪽부터 살핍니다. 따라서 old는 새 페이지의 재사용 여부를 가리는 구역이고 young은 재사용된 페이지를 보관하는 구역입니다.

기본 설정은 old sublist가 버퍼풀의 37%를 차지하도록 두고 크기를 조정합니다. 논문에 따르면 이 과정에서 새 접근이 없어도 old 앞쪽의 페이지가 young으로 옮겨질 수 있습니다. 캐시가 처음 채워질 때 young을 먼저 채우는 효과가 있지만, 초기 적재가 끝난 뒤에도 승격이 계속돼 최근 접근 여부를 따지지 않습니다. 재사용 가능성이 낮은 페이지가 young을 차지하면 자주 쓰는 페이지를 밀어낼 수 있습니다.

old sublist를 5%로 줄이는 것만으로는 문제가 해결되지 않았습니다. TPC-H에서 기존 InnoDB의 old 비율만 5%로 바꾼 구성은 일부 쿼리에 도움을 줬지만 Q3, Q5, Q15, Q21에서는 효율이 크게 떨어졌습니다. 작은 old 구역이 인기 페이지를 두 번째 접근까지 붙잡아 두지 못했기 때문입니다. old 5% 구성에 ghost queue만 추가하고 재승격을 제한하지 않은 경우도 충분하지 않았습니다. Q1의 버퍼풀 미스율은 기본 37% 설정에서 0.38, ghost queue만 추가한 구성에서 0.35였고 SR-InnoDB에서는 0.25였습니다.

SR-InnoDB는 초기 적재와 이후 승격을 분리합니다. 먼저 새 페이지를 young에 직접 넣어 목표 크기까지 채우고, 그다음부터는 기존 방식대로 페이지를 old의 중간 지점에 삽입합니다. 초기 적재가 끝나면 old와 young의 크기를 맞추기 위해 접근 없이 페이지를 승격하던 조정을 멈추고, 퇴출로 old의 크기를 유지합니다. 이렇게 하면 young을 먼저 채우는 동작은 초기 적재에만 적용됩니다.

RecencyGuard는 버퍼풀의 실제 LRU 목록과 같은 용량의 ghost queue를 둡니다. old tail에서 퇴출된 페이지만 기록 대상으로 삼고, young tail 페이지의 마지막 접근 시점을 최근성 기준으로 사용합니다. 퇴출 페이지의 마지막 접근이 이 기준보다 최근일 때만 ghost에 기록합니다. ghost hit이 발생하면 저장된 시점을 현재 기준과 다시 비교합니다. 충분히 최근인 페이지는 young의 앞쪽으로 올리고, 그렇지 않은 페이지는 일반 중간 지점 삽입 경로로 보냅니다.

연구진은 미스율 절벽을 C-score, Belady 이상을 P-score로 측정했습니다. 자신들이 평가한 다중 큐 알고리즘 가운데 LIRS만 두 현상이 거의 없는 엄격한 스캔 저항성에 근접했다고 보고했습니다. 연구진은 LIRS의 강점이 stack distance 자체보다 캐시 초기 적재 때 보호 큐에 페이지를 넣는 방식과 ghost 기록·승격을 선별하는 규칙에서 나온다고 분석했습니다.

Cliffhanger와 Miniature는 캐시 파티션을 적응적으로 조정합니다. Cliffhanger는 shadow queue로 미스율 곡선의 국소 기울기를 추정하고, Miniature는 표본 재생으로 미스율 곡선을 만듭니다. SR-Gadgets는 파티션을 동적으로 다시 나누는 대신 초기 삽입과 ghost 기록·승격을 제한합니다. 특정 작업 패턴을 미리 알거나 명시적으로 탐지하지 않아도 반복 스캔에 대응하도록 설계했습니다. 다만 알고리즘에 따라 연결 방식은 달랐습니다. 2Q는 보호 큐로 직접 승격하는 경로가 없어 RecencyGuard가 한 번 거부한 유용한 항목이 ghost를 거쳐야 했고, 그 결과 P-score가 커졌습니다. 연구진은 직접 승격 경로를 추가한 뒤 2Q에서도 이상이 줄었다고 보고했습니다.

연구진은 InnoDB 실험과 별도로 다섯 알고리즘을 libCacheSim으로 평가했습니다. Cloudphysics, Tencent CBS, Alibaba의 운영 블록 요청 추적 5,538개, 총 1,410억 건을 재생했습니다. 캐시 크기는 추적별 고유 객체 수의 1%와 10%로 설정했고 객체 크기는 반영하지 않았습니다. 작은 캐시인 1% 조건에서 SR-TinyLFU의 FIFO 대비 미스율 감소 지표는 추적별 분포의 90백분위에서 23.1%였습니다. TPC-H 수치는 쿼리 실행시간이 아니라 버퍼풀 미스율이며, 운영 요청 추적 실험과는 별도의 결과입니다.