들어가며
지금까지 구현한 데이터베이스에서 저장된 모든 데이터는 명시적으로 삭제하지 않는 한 영구적으로 존재한다. 하지만 세션 토큰, 캐시 데이터, 인증 코드 같은 것들은 일정 시간이 지나면 자동으로 사라져야 한다. 이번 포스팅에서는 키에 만료 시간(TTL)을 설정하고 만료된 키를 자동으로 삭제하는 두 가지 전략을 구현한다. 그 과정에서 최소 힙 자료구조를 직접 구현하고 백그라운드 고루틴의 라이프사이클도 관리해보는 과정을 다뤄보겠다.
TTL
TTL(Time To Live)은 데이터가 유효한 시간을 의미한다. 네트워크 패킷에서는 홉 수를 제한하고 DNS 캐시에서는 레코드의 유효 기간을 정하고, CDN에서는 캐시 갱신 주기를 결정한다. 컴퓨터 시스템 전반에서 “이 데이터가 얼마나 오래 살아야 하는가"를 제어하는 수단으로 널리 쓰인다.
인메모리 데이터베이스에서 TTL은 메모리 관리의 핵심 도구다. 모든 키를 영구 보관하면 메모리가 계속 증가한다. 세션 데이터나 임시 캐시처럼 일정 시간이 지나면 가치가 없어지는 데이터에 TTL을 설정하면 데이터가 스스로 만료되어 메모리가 자동으로 회수된다.
레디스에서 TTL 관련 명령어는 다음과 같다.
EXPIRE key seconds- 키에 만료 시간을 설정한다. 키가 존재하면 1, 존재하지 않으면 0을 반환한다TTL key- 키의 남은 수명을 초 단위로 반환한다. TTL이 설정되지 않았으면 -1, 키가 존재하지 않으면 -2를 반환한다DEL key- 키를 즉시 삭제한다. 삭제된 키의 개수를 반환한다PERSIST key- 키에서 만료 시간을 제거하여 영구 키로 전환한다. TTL이 존재하고 제거했으면 1, 아니면 0을 반환한다
만료 전략 - Lazy Deletion vs Active Deletion
키에 TTL을 설정했다고 해서 정확히 그 시각에 키가 사라지는 것은 아니다. “만료된 키를 언제 실제로 삭제할 것인가"가 핵심 설계 결정이며, 두 가지 접근 방식이 있다.
Lazy Deletion (게으른 삭제)
클라이언트가 키에 접근하는 시점에 만료 여부를 확인하고, 만료되었으면 그때 삭제한다. 접근하지 않는 키는 만료되어도 메모리에 남아있다.
- 장점: 구현이 단순하다. 접근 시점에만 검사하므로 별도의 백그라운드 작업 없이 동작한다
- 단점: 아무도 접근하지 않는 키는 만료되어도 영원히 메모리를 차지한다. 수백만 개의 만료된 키가 메모리에 쌓일 수 있다
Active Deletion (적극적 삭제)
백그라운드에서 주기적으로 만료된 키를 찾아 삭제한다. 접근하지 않는 키도 삭제 대상이 된다.
- 장점 - 접근하지 않는 키도 정리되어 메모리가 확실히 회수된다
- 단점 - 백그라운드 작업이 CPU를 사용한다. 만료된 키를 효율적으로 찾는 자료구조가 필요하다
레디스에서는 두 전략을 동시에 사용한다. 모든 키 접근 시 Lazy Deletion을 수행하면서, 백그라운드에서도 주기적으로 만료된 키를 정리한다. 어느 한쪽만으로는 부족하기 때문이다. Lazy Deletion만 사용하면 접근하지 않는 키가 메모리를 낭비하고, Active Deletion만 사용하면 tick 간격 사이에 만료된 키를 클라이언트가 읽을 수 있다. 그렇기에 이 두 가지 전략을 모두 활용하여 구현을 했다.
Lazy Deletion의 트레이드오프 - RLock에서 Lock으로
Lazy Deletion을 적용하면 한 가지 대가를 치르게 된다. 이전 챕터에서 Get이나 LRange 같은 읽기 함수에는 RWMutex의 RLock을 사용했다. 여러 고루틴이 동시에 읽기를 수행할 수 있어 동시성이 좋았다.
근데 위에서 설명했듯 Lazy Deletion은 클라이언트가 키에 접근하는 시점에 만료 여부를 체크하기 때문에 기존의 읽기작업만 이루어지는 Get, LRange 함수 내부에서 특정 키의 만료기한을 확인하는 isExpired 를 호출하는 동시에 읽기잠금(RLock)을 쓰기잠금(Lock) 으로 변경해야 한다. isExpired 함수에서 만료된 키를 delete로 맵에서 제거하는 쓰기 동작을 포함하기 때문이다. RLock은 읽기 전용 잠금이므로 쓰기 동작을 보호할 수 없다.
// 이전: RLock - 동시 읽기 가능
s.mu.RLock()
defer s.mu.RUnlock()
// 변경 후: Lock — 동시 읽기 불가
s.mu.Lock()
defer s.mu.Unlock()
Lock으로 바뀌면 읽기 요청끼리도 서로 블로킹된다. 10개의 고루틴이 동시에 Get을 호출해도 한 번에 하나씩만 실행된다. Lazy Deletion이라는 편리함을 얻는 대신 읽기 동시성을 잃은 것이다.
먼저 RLock으로 만료 여부만 확인하고, 만료되었으면 RLock을 해제한 뒤 Lock을 잡아서 삭제하는 최적화 패턴이 있지만, 코드 복잡도가 크게 올라갈 것으로 예상되기에 지금은 Lock을 사용하여 해결하고 추후에 리팩토링 할때 한 번 들여다 볼 생각이다.
힙 자료구조
Active Deletion에서 핵심 문제는 가장 먼저 만료될 키가 무엇인가를 효율적으로 찾는 것이다. 매번 모든 키를 순회하면 O(n)이고 키가 수십만 개일 때 1초마다 O(n) 순회를 하면 성능에 치명적이다.
힙(Heap) 은 최솟값(또는 최댓값)을 O(1)로 조회하고, 삽입과 삭제를 O(log n)으로 수행하는 트리 기반 자료구조이다. 이전에 알고리즘 문제를 풀 때 우선순위 큐를 사용해서 풀었던 몇몇의 문제가 있었는데 우선순위 큐가 일반적으로 heap 자료구조 기반으로 구현 된다. (heap뿐만 아니라 다른 방법으로도 구현이 가능하다) 그럼 이제 힙에 대해 더 자세히 알아보자.
완전 이진 트리와 힙 속성
힙은 완전 이진 트리 형태를 가진다. 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진다.
Min-Heap(최소 힙) 에서는 부모 노드가 항상 자식보다 작거나 같다. 이 규칙이 루트부터 리프까지 재귀적으로 적용되기 때문에 루트에 항상 전체 최솟값이 위치한다.
만료 시간을 기준으로 최소힙을 구성하면, Peek으로 가장 먼저 만료될 키를 O(1)에 확인할 수 있다.
배열 기반 구현
완전 이진 트리는 배열로 효율적으로 표현할 수 있다. 트리의 레벨 순서대로 배열에 넣으면 부모-자식 관계가 인덱스 계산으로 바로 나온다.
- 부모 인덱스 -
(i - 1) / 2 - 왼쪽 자식 인덱스 -
2 * i + 1 - 오른쪽 자식 인덱스 -
2 * i + 2
위의 트리 자료구조 이미지에서 보면, 인덱스 1의 노드(값 2)의 부모는 (1 - 1) / 2 = 0(값 1), 왼쪽 자식은 2 * 1 + 1 = 3(값 17), 오른쪽 자식은 2 * 1 + 2 = 4(값 19)다. 포인터 없이 인덱스 연산만으로 트리를 탐색할 수 있어서 메모리 효율이 좋다.
Bubble Up과 Bubble Down
힙에 요소를 삽입하거나 제거할 때 힙 속성이 깨질 수 있다. 이를 복원하는 두 가지 연산이 Bubble Up과 Bubble Down이다.
Bubble Up - 새 요소를 배열 끝에 추가한 뒤, 부모와 비교하며 위로 올라간다. 부모보다 작으면 교환하고, 루트에 도달하거나 부모보다 크면 멈춘다. Push에 사용된다.
Bubble Down - 루트를 제거한 뒤 배열의 마지막 요소를 루트에 놓고, 자식과 비교하며 아래로 내려간다. 더 작은 자식과 교환하고, 리프에 도달하거나 자식보다 작으면 멈춘다. Pop에 사용된다.
두 연산 모두 트리의 높이만큼만 이동하므로 O(log n)이다.
백그라운드 고루틴의 라이프사이클
Active Deletion을 위해 주기적으로 실행되는 백그라운드 고루틴이 필요하다. go의 time.Ticker는 일정 간격으로 이벤트를 발생시키고, select문은 여러 채널 중 준비된 하나를 선택한다.
go func() {
ticker := time.NewTicker(1 * time.Second)
defer ticker.Stop()
for {
select {
case <-done:
return
case <-ticker.C:
// 만료 처리
}
}
}()
ticker.C는 설정한 간격마다 현재 시간을 보내주는 채널이다. for-select 루프에서 매 tick마다 만료 처리를 수행한다. done 채널이 닫히면 <-done이 즉시 반환되어 고루틴이 종료된다. 서버가 꺼질 때 close(done)을 호출하면 백그라운드 고루틴도 함께 정리된다.
코드 구현
heap.go
만료 시간 기준으로 정렬되는 최소 힙을 직접 구현한다.
package storage
import "time"
type HeapItem struct {
Key string
ExpireAt time.Time
}
type MinHeap struct {
items []*HeapItem
}
func NewMinHeap() *MinHeap {
return &MinHeap{}
}
// 새 항목을 추가하고 Bubble Up으로 힙 속성을 복원한다. O(log n)
func (h *MinHeap) Push(item *HeapItem) {
h.items = append(h.items, item)
curIdx := len(h.items) - 1
parentIdx := (curIdx - 1) / 2
for curIdx != 0 && h.items[curIdx].ExpireAt.Before(h.items[parentIdx].ExpireAt) {
h.items[parentIdx], h.items[curIdx] = h.items[curIdx], h.items[parentIdx]
curIdx = parentIdx
parentIdx = (curIdx - 1) / 2
}
}
// 최솟값(가장 먼저 만료되는 항목)을 제거하고 반환한다. O(log n)
func (h *MinHeap) Pop() *HeapItem {
if len(h.items) == 0 {
return nil
}
min := h.items[0]
last := len(h.items) - 1
h.items[0] = h.items[last]
h.items = h.items[:last]
curIdx := 0
for {
left := 2*curIdx + 1
right := 2*curIdx + 2
smallest := curIdx
if left < len(h.items) && h.items[left].ExpireAt.Before(h.items[smallest].ExpireAt) {
smallest = left
}
if right < len(h.items) && h.items[right].ExpireAt.Before(h.items[smallest].ExpireAt) {
smallest = right
}
if smallest == curIdx {
break
}
h.items[curIdx], h.items[smallest] = h.items[smallest], h.items[curIdx]
curIdx = smallest
}
return min
}
// 최솟값을 제거하지 않고 조회한다. O(1)
func (h *MinHeap) Peek() *HeapItem {
if len(h.items) == 0 {
return nil
}
return h.items[0]
}
// 힙의 크기를 반환한다.
func (h *MinHeap) Len() int {
return len(h.items)
}
store.go
Entry 구조체에 만료 시각 필드를 추가하고 Store에 최소 힙과 종료 신호 채널을 추가한다. TTL 관련 메서드(Expire, TTL, Del, Persist)를 구현하고, 기존 읽기/쓰기 메서드에 Lazy Deletion을 적용한다.
package storage
import (
"errors"
"sync"
"time"
)
type EntryType int
var ErrWrongType = errors.New("WRONGTYPE Operation against a key holding the wrong kind of value")
const (
TypeString EntryType = iota
TypeList
)
type Entry struct {
Type EntryType
Str string
List *List
ExpireAt *time.Time
}
type Store struct {
data map[string]*Entry
mu sync.RWMutex
heap *MinHeap
done chan struct{}
}
func New() *Store {
return &Store{
data: make(map[string]*Entry),
heap: NewMinHeap(),
done: make(chan struct{}),
}
}
func (s *Store) Set(key, value string) {
s.mu.Lock()
defer s.mu.Unlock()
s.data[key] = &Entry{Type: TypeString, Str: value}
}
func (s *Store) Get(key string) (string, bool) {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if !exist {
return "", false
} else {
if entry.Type != TypeString || s.isExpired(key) {
return "", false
}
}
return entry.Str, exist
}
func (s *Store) LPush(key string, values ...string) (int, error) {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if !exist || s.isExpired(key) {
newEntry := Entry{Type: TypeList, List: NewList()}
entry = &newEntry
s.data[key] = entry
}
if entry.Type != TypeList {
return 0, ErrWrongType
}
for _, v := range values {
entry.List.LPush(v)
}
return entry.List.Length, nil
}
func (s *Store) RPush(key string, values ...string) (int, error) {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if !exist || s.isExpired(key) {
newEntry := Entry{Type: TypeList, List: NewList()}
entry = &newEntry
s.data[key] = entry
}
if entry.Type != TypeList {
return 0, ErrWrongType
}
for _, v := range values {
entry.List.RPush(v)
}
return entry.List.Length, nil
}
func (s *Store) LPop(key string) (string, bool, error) {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if !exist {
return "", exist, nil
}
if entry.Type != TypeList {
return "", false, ErrWrongType
}
if s.isExpired(key) {
return "", false, nil
}
value, result := entry.List.LPop()
if entry.List.Length == 0 {
delete(s.data, key)
}
return value, result, nil
}
func (s *Store) RPop(key string) (string, bool, error) {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if !exist {
return "", exist, nil
}
if entry.Type != TypeList {
return "", false, ErrWrongType
}
if s.isExpired(key) {
return "", false, nil
}
value, result := entry.List.RPop()
if entry.List.Length == 0 {
delete(s.data, key)
}
return value, result, nil
}
func (s *Store) LRange(key string, start, stop int) ([]string, error) {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if !exist {
return []string{}, nil
}
if entry.Type != TypeList {
return nil, ErrWrongType
}
if s.isExpired(key) {
return []string{}, nil
}
result := entry.List.Range(start, stop)
return result, nil
}
func (s *Store) Expire(key string, seconds int) int {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if exist {
expire := time.Now().Add(time.Duration(seconds) * time.Second)
entry.ExpireAt = &expire
s.heap.Push(&HeapItem{Key: key, ExpireAt: expire})
return 1
} else {
return 0
}
}
func (s *Store) TTL(key string) int {
s.mu.RLock()
defer s.mu.RUnlock()
entry, exist := s.data[key]
if exist {
if entry.ExpireAt == nil {
return -1
}
return int(time.Until(*entry.ExpireAt).Seconds())
} else {
return -2
}
}
func (s *Store) Del(key string) int {
s.mu.Lock()
defer s.mu.Unlock()
_, exist := s.data[key]
if !exist {
return 0
} else {
delete(s.data, key)
return 1
}
}
func (s *Store) Persist(key string) int {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if !exist || entry.ExpireAt == nil {
return 0
} else {
entry.ExpireAt = nil
return 1
}
}
func (s *Store) isExpired(key string) bool {
expire := s.data[key].ExpireAt
if expire == nil {
return false
}
if expire.Before(time.Now()) {
delete(s.data, key)
return true
} else {
return false
}
}
func (s *Store) StartExpiry() {
go func() {
ticker := time.NewTicker(1 * time.Second)
defer ticker.Stop()
for {
select {
case <-s.done:
return
case <-ticker.C:
s.mu.Lock()
for {
item := s.heap.Peek()
if item == nil || !item.ExpireAt.Before(time.Now()) {
break
}
s.heap.Pop()
entry, exist := s.data[item.Key]
if exist && entry.ExpireAt != nil && entry.ExpireAt.Equal(item.ExpireAt) {
delete(s.data, item.Key)
}
}
s.mu.Unlock()
}
}
}()
}
func (s *Store) StopExpiry() {
close(s.done)
}
server.go (변경 부분)
서버 시작 시 백그라운드 만료 처리를 시작하고, switch문에 EXPIRE, TTL, DEL, PERSIST 핸들러를 추가한다. 모든 응답은 RESP Integer(WriteInteger)로 처리하며, 추가 Writer 메서드는 필요 없다.
func (s *Server) Start() error {
listener, err := net.Listen("tcp", s.addr)
if err != nil {
return err
}
s.listener = listener
defer s.listener.Close()
log.Printf("현재 서버가 [%s] 에서 리스닝중입니다.", s.addr)
s.store.StartExpiry()
defer s.store.StopExpiry()
for {
conn, err := s.listener.Accept()
if err != nil {
log.Print("연결 중 오류: ", err)
continue
} else {
go s.handleConnection(conn)
}
}
}
case "EXPIRE":
if len(value.Array) < 3 {
writer.WriteError("missing argument")
} else {
seconds, _ := strconv.Atoi(value.Array[2].Str)
result := s.store.Expire(value.Array[1].Str, seconds)
writer.WriteInteger(result)
}
case "TTL":
if len(value.Array) < 2 {
writer.WriteError("missing argument")
} else {
result := s.store.TTL(value.Array[1].Str)
writer.WriteInteger(result)
}
case "DEL":
if len(value.Array) < 2 {
writer.WriteError("missing argument")
} else {
result := s.store.Del(value.Array[1].Str)
writer.WriteInteger(result)
}
case "PERSIST":
if len(value.Array) < 2 {
writer.WriteError("missing argument")
} else {
result := s.store.Persist(value.Array[1].Str)
writer.WriteInteger(result)
}
테스트
이번 챕터에서도 테스트코드가 많은 관계로 핵심 케이스만 살펴보겠다.
Heap Pop 순서 검증
func TestHeapPopOrder(t *testing.T) {
// given: 5개 항목을 무작위 순서로 Push
heap := NewMinHeap()
now := time.Now()
heap.Push(&HeapItem{Key: "d", ExpireAt: now.Add(40 * time.Second)})
heap.Push(&HeapItem{Key: "a", ExpireAt: now.Add(10 * time.Second)})
heap.Push(&HeapItem{Key: "e", ExpireAt: now.Add(50 * time.Second)})
heap.Push(&HeapItem{Key: "b", ExpireAt: now.Add(20 * time.Second)})
heap.Push(&HeapItem{Key: "c", ExpireAt: now.Add(30 * time.Second)})
// when & then: Pop 순서가 만료 시간 순이어야 한다
expected := []string{"a", "b", "c", "d", "e"}
for i, key := range expected {
item := heap.Pop()
if item.Key != key {
t.Fatalf("Pop 순서 오류 [%d]: actual: %s, expected: %s", i, item.Key, key)
}
}
}
어떤 순서로 Push하든 pop은 항상 만료 시간이 빠른 순서대로 나와야 한다. 이 테스트가 통과하면 Bubble Up과 Bubble Down이 모두 정상 동작하는 것이다.
Lazy Deletion 검증
func TestLazyDeletion(t *testing.T) {
// given: TTL 1초 설정
store := New()
store.Set("session", "abc")
store.Expire("session", 1)
// when: 2초 대기 후 Get
time.Sleep(2 * time.Second)
value, exist := store.Get("session")
// then: 만료되어 존재하지 않음
if exist {
t.Fatalf("만료된 키가 존재합니다: %s", value)
}
}
TTL 1초를 설정하고 2초 후에 Get을 하면 isExpired가 만료를 감지하여 키를 삭제하고 exist = false를 반환한다. Active Deletion 없이도 접근 시점에 만료가 처리되는 것을 확인할 수 있다.
Active Deletion 검증
func TestActiveDeletion(t *testing.T) {
// given: 백그라운드 만료 시작, TTL 1초 설정
store := New()
store.StartExpiry()
defer store.StopExpiry()
store.Set("session", "abc")
store.Expire("session", 1)
// when: 3초 대기 (1초 TTL + 1초 ticker 간격 + 여유)
time.Sleep(3 * time.Second)
// then: Active Deletion으로 키가 삭제됨
ttl := store.TTL("session")
if ttl != -2 {
t.Fatalf("Active Deletion 실패. TTL: %d, expected: -2", ttl)
}
}
TTL은 Lazy Deletion을 적용하지 않은 읽기 전용 함수(RLock)다. 3초 대기 후 TTL이 -2(키 없음)를 반환한다는 것은 백그라운드 고루틴이 키를 삭제했다는 의미다. Get이 아닌 TTL로 확인하는 것이 Active Deletion만의 동작을 검증하는 핵심이다.
서버 통합 테스트
func TestPersistCommand(t *testing.T) {
// given: SET + EXPIRE
server := New(":6379")
go server.Start()
time.Sleep(time.Second)
conn, _ := net.Dial("tcp", "localhost:6379")
defer conn.Close()
reader := bufio.NewReader(conn)
conn.Write([]byte("*3\r\n$3\r\nSET\r\n$11\r\npersist-key\r\n$5\r\nvalue\r\n"))
reader.ReadString('\n') // +OK 소비
conn.Write([]byte("*3\r\n$6\r\nEXPIRE\r\n$11\r\npersist-key\r\n$2\r\n60\r\n"))
reader.ReadString('\n') // :1 소비
// when: PERSIST persist-key
conn.Write([]byte("*2\r\n$7\r\nPERSIST\r\n$11\r\npersist-key\r\n"))
// then: 1 반환
response, _ := reader.ReadString('\n')
if response != ":1\r\n" {
t.Fatalf("응답: %s", response)
}
// TTL 확인: -1 (만료 없음)
conn.Write([]byte("*2\r\n$3\r\nTTL\r\n$11\r\npersist-key\r\n"))
ttlResponse, _ := reader.ReadString('\n')
if ttlResponse != ":-1\r\n" {
t.Fatalf("PERSIST 후 TTL: %s", ttlResponse)
}
}
SET → EXPIRE → PERSIST → TTL 순서로 명령어를 보내 전체 파이프라인을 검증한다. PERSIST 후 TTL이 -1(만료 없음)을 반환하면 만료 시간이 정상적으로 제거된 것이다.
라인별 Deep Dive
Expire - 시간 계산과 힙 등록
func (s *Store) Expire(key string, seconds int) int {
s.mu.Lock()
defer s.mu.Unlock()
entry, exist := s.data[key]
if exist {
expire := time.Now().Add(time.Duration(seconds) * time.Second)
entry.ExpireAt = &expire
s.heap.Push(&HeapItem{Key: key, ExpireAt: expire})
return 1
} else {
return 0
}
}
time.Duration(seconds)는 seconds를 나노초로 해석한다. time.Duration(5)는 5나노초다. time.Second를 곱해야 5초가 된다. time.Now().Add()는 현재 시각에 duration을 더한 새로운 time.Time을 반환한다. 원본을 수정하는 것이 아니라 새 값을 반환하는 점이 중요하다.
만료 시각을 Entry에 기록하는 것과 동시에 힙에도 등록한다. 이 두 곳에 동일한 정보가 존재하는 것이 Lazy Heap Cleanup의 전제가 된다.
isExpired - Lazy Deletion의 핵심
func (s *Store) isExpired(key string) bool {
expire := s.data[key].ExpireAt
if expire == nil {
return false
}
if expire.Before(time.Now()) {
delete(s.data, key)
return true
} else {
return false
}
}
이 함수는 mu.Lock()이 잡힌 상태에서 호출되는 내부용 함수다. 자체적으로 뮤텍스를 잡지 않는다. go의 뮤텍스는 재진입을 지원하지 않기 때문에 이미 Lock이 걸린 상태에서 다시 Lock을 잡으면 데드락이 발생한다.
ExpireAt이 nil이면 만료 시간이 설정되지 않은 것이므로 바로 false를 반환한다. 만료 시각이 현재 시각보다 이전이면(Before) 맵에서 키를 삭제하고 true를 반환한다. 이 delete 호출이 있기 때문에 호출하는 쪽에서 RLock이 아닌 Lock을 사용해야 한다.
Active Deletion - Lazy Heap Cleanup
case <-ticker.C:
s.mu.Lock()
for {
item := s.heap.Peek()
if item == nil || !item.ExpireAt.Before(time.Now()) {
break
}
s.heap.Pop()
entry, exist := s.data[item.Key]
if exist && entry.ExpireAt != nil && entry.ExpireAt.Equal(item.ExpireAt) {
delete(s.data, item.Key)
}
}
s.mu.Unlock()
힙에서 pop한 항목을 바로 삭제하지 않고 세 가지를 확인한다.
exist— 키가 이미 DEL이나 Lazy Deletion으로 삭제되었을 수 있다entry.ExpireAt != nil- PERSIST로 만료가 제거되었을 수 있다entry.ExpireAt.Equal(item.ExpireAt)- EXPIRE가 재설정되어 힙의 만료 시각과 Entry의 만료 시각이 달라졌을 수 있다
이 패턴을 Lazy Heap Cleanup이라 한다. 힙에서 항목을 직접 제거하는 대신 pop 시점에 유효성을 확인하는 방식이다. 힙에서 임의의 요소를 제거하려면 O(n) 탐색이 필요하지만, pop은 O(log n)이므로 훨씬 효율적이다. 대신 힙에 이미 무효화된 항목이 남아있을 수 있어 약간의 메모리를 사용하지만, pop 시점에 걸러지므로 동작에는 영향이 없다.
마치며
Lazy Deletion만으로는 접근하지 않는 키가 메모리에 계속 남고, Active Deletion만으로는 체크 주기 사이에 만료된 키가 조회될 수 있다. 결국 두 전략을 조합해야 하고, 그 과정에서 읽기 함수의 RLock이 Lock으로 바뀌면서 동시 읽기 성능을 포기하는 트레이드오프도 있었다. 만료된 키를 즉시 삭제하려면 모든 읽기 경로에 쓰기 동작이 끼어들 수밖에 없고, 이건 Lazy Deletion이라는 전략이 가진 본질적인 비용인 것 같다.
그리고 DEL이나 PERSIST로 키가 먼저 제거되는 상황까지 고려하면 Lazy Heap Cleanup 같은 보완 전략이 추가로 필요해지는 것을 보면 자료구조 하나를 선택하는 것만으로 끝나지 않고 그 자료구조가 실제 시스템에서 어떻게 동작하는지까지 고민해야 한다는 걸 체감했다.
다음 포스팅에서는 메모리에만 존재하는 데이터를 파일에 저장하여 서버가 재시작되어도 데이터가 유지되는 영속성을 구현해보겠다.
참고