들어가며
이전 포스팅에서 RESP 프로토콜을 구현해 클라이언트와 서버가 구조화된 형식으로 통신할 수 있게 되었다.
이번 포스팅에서는 Key-Value 저장소를 구현하고 SET/GET 명령어를 추가해보자. go의 map을 감싸는 단순한 구조체를 만드는 것이 전부지만, 그 뒤에 숨어있는 해시 테이블의 원리를 깊이 있게 다뤄보려 한다. 해시 함수가 갖춰야 할 조건, 충돌을 해결하는 전략, 로드 팩터와 리해싱까지 살펴보면 map[string]string 한 줄이 왜 O(1)인지 납득할 수 있을 것이다.
Key-Value 저장 모델
가장 단순한 데이터 모델
Key-Value 모델은 데이터를 저장하는 가장 단순한 방식이다. key로 값을 저장하고 같은 키로 값을 조회한다.
SET name "redis" -> 저장
GET name -> "redis" 반환
Redis, Memcached, DynamoDB 등 많은 인메모리 데이터베이스가 이 모델을 기반으로 한다. 복잡한 쿼리 대신 키만 알면 O(1)의 시간복잡도로 데이터를 조회할 수 있기에 캐시, 세션 저장소, 설정 관리 등에 널리 쓰인다.
왜 Key-Value인가
흔히아는 MySQL, Postgresql와 같은 RDBMS는 테이블, 행, 열의 구조를 가진다. 데이터를 조회하려면 SQL 쿼리를 파싱하고 실행 계획을 세우고 인덱스를 탐색해야 한다.
Key-Value는 이런 복잡한 과정이 없다. 키를 해시 함수에 넣으면 바로 저장 위치를 알 수 있다.
Key-Value 저장소의 다양한 구현
Key-Value라는 개념은 같지만 그 뒤의 저장 엔진은 목적에 따라 완전히 달라진다.
인메모리 저장소
- Go map (내장 라이브러리) - 해시 테이블 기반. 필자가 이번에 사용하는 방식이다
- Redis - 해시 테이블 기반이지만 다양한 자료구조(List, Set, Sorted Set 등)를 지원한다
- Memcached - 순수 Key-Value 캐시이다. Redis보다 단순하지만 멀티스레드로 동작한다
디스크 기반 저장소
- LevelDB / RocksDB - LSM-Tree 기반이다. 쓰기에 최적화되어 있다. 메모리에 먼저 쓰고 일정량이 쌓이면 디스크로 내려보내는 구조다.
- BoltDB - B+Tree 기반이다. 읽기에 최적화되어 있으며 정렬된 키 순회가 필요할 때 적합하다
인메모리 저장소는 빠르지만 프로세스가 종료되면 데이터가 사라진다. 디스크 기반 저장소는 느리지만 영속성을 보장한다. 레디스는 이 두 가지를 절충해서 메모리에서 동작하되 주기적으로 디스크에 스냅샷을 저장하는 방식을 사용한다.
필자가 만드는 저장소는 가장 단순한 인메모리 해시 테이블이다. 나중에 영속성이 필요해지면 디스크에 기록하는 기능을 추가하게 될 것이다.
해시 테이블
동작 원리
Go의 map은 파이썬의 딕셔너리, 자바의 HashMap과 동일하게 해시 테이블로 구현되어 있다. 해시 테이블은 키를 해시 함수에 통과시켜 저장 위치(버킷)를 결정하는 자료구조다.
data := make(map[string]string)
data["name"] = "승기" // O(1) 평균
value := data["name"] // O(1) 평균
동작 방식은 다음과 같다.
- 해시 함수 - 키
"name"을 숫자로 변환 (예: 12345) - 버킷 인덱스 - 해시값을 버킷 수로 나눈 나머지 (예: 12345 % 8 = 1)
- 저장 - 1번 버킷에 키-값 쌍 저장
조회할 때도 같은 과정을 거친다. 키만 알면 바로 버킷 위치를 계산할 수 있으니 평균 O(1) 시간에 접근 가능하다.
해시 함수의 조건
해시 테이블의 성능은 해시 함수의 품질에 달려있다. 좋은 해시 함수란 무엇일까?
결정성 (Determinism)
같은 입력에 대해 항상 같은 출력을 내야 한다. hash("name")이 12345를 반환했다면, 몇 번을 호출하든 항상 12345를 반환해야 한다. 당연한 것 같지만, 만약 호출할 때마다 결과가 달라진다면 저장한 위치를 다시 찾을 수 없다. SET에서 버킷 1에 저장했는데 GET에서 버킷 5를 찾아간다면 아무 의미가 없다.
균등 분포 (Uniform Distribution)
해시값이 버킷 전체에 고르게 퍼져야 한다. 8개의 버킷이 있는데 모든 키가 3번 버킷에 몰린다면 사실상 연결 리스트와 다를 바 없다. 좋은 해시 함수는 입력이 어떻든 출력이 버킷 공간에 균일하게 분포한다.
눈사태 효과 (Avalanche Effect)
입력이 아주 조금만 바뀌어도 출력이 크게 달라져야 한다. "name"과 "nane"은 한 글자만 다르지만, 해시값은 완전히 달라야 한다. 이 성질이 없으면 비슷한 키들이 같은 버킷으로 몰려 충돌이 집중된다.
간단한 예를 들어보자. 아래와 같이 각 문자의 아스키 값을 단순히 더하는 해시 함수가 있다.
hash("abc") = 97 + 98 + 99 = 294
hash("bac") = 98 + 97 + 99 = 294 // 같은 값
hash("cab") = 99 + 97 + 98 = 294 // 또 같은 값
문자 순서가 달라도 합이 같아서 전부 같은 버킷에 들어간다. 이런 해시 함수는 좋지 않다. 실제 해시 함수는 비트 연산, 시프트, XOR 등을 조합해 입력의 미세한 차이가 출력 전체에 퍼지도록 설계한다.
Go의 해시 함수
Go 런타임은 CPU 기능에 따라 map 해시에 AES 기반 해시를 사용하거나 폴백 해시를 사용한다(런타임에서 자동 선택)
해시 충돌
서로 다른 키가 같은 버킷에 매핑될 수 있다. 이를 해시 충돌이라 한다.
hash("name") % 8 = 1
hash("team") % 8 = 1 // 같은 버킷
아무리 좋은 해시 함수라도 충돌은 피할 수 없다. 무한한 키 공간을 유한한 버킷에 매핑하는 이상 반드시 충돌이 발생한다. 중요한 것은 충돌을 어떻게 처리하느냐이다.
해시 충돌 해결 전략
해시 충돌을 해결하는 방법은 크게 두 가지로 나뉜다.
체이닝 (Chaining)
충돌이 발생하면 같은 버킷에 연결 리스트를 만들어 여러 키-값 쌍을 이어 붙이는 방식이다. 구현이 단순하고 버킷이 꽉 차도 문제 없이 확장된다.
단점은 캐시 친화적이지 않다는 것이다. 연결 리스트의 각 노드가 메모리 곳곳에 흩어져 있으면 CPU 캐시 미스가 빈번하게 발생한다. 현대 CPU에서는 메모리를 읽어오는 시간이 연산 시간보다 훨씬 길기 때문에 이 문제가 성능에 큰 영향을 미친다.
개방 주소법 (Open Addressing)
충돌이 발생하면 별도의 공간을 만들지 않고 다른 빈 버킷을 찾아가는 방식이다. 모든 데이터가 버킷 배열 안에 저장되므로 메모리가 연속적이고 캐시 친화적이다. 빈 버킷을 찾는 방법에 따라 세 가지로 나뉜다.
- 선형 탐사 (Linear Probing) - 충돌 시 다음 칸, 그 다음 칸으로 순서대로 탐색한다. 구현이 간단하지만 데이터가 한쪽에 뭉치는 클러스터링 문제가 있다
- 이차 탐사 (Quadratic Probing) - 1칸, 4칸, 9칸… 처럼 제곱수 간격으로 탐색한다. 선형 탐사보다 클러스터링이 줄어든다
- 이중 해싱 (Double Hashing) - 두 번째 해시 함수로 탐색 간격을 결정한다. 클러스터링을 가장 효과적으로 방지하지만 해시 함수를 하나 더 계산해야 한다
개방 주소법의 단점은 삭제가 까다롭다는 것이다. 단순히 비우면 탐색 경로가 끊겨서 뒤에 있는 키를 찾을 수 없게 된다. 그래서 보통 “삭제됨” 표시를 남기는 방식을 사용한다.
Go의 선택 - 하이브리드 방식
Go의 map은 체이닝도 개방 주소법도 아닌, 둘을 절충한 독특한 구조를 사용한다. 각 버킷이 8개의 슬롯을 가지고 있고 버킷이 가득 차면 오버플로우 버킷을 연결한다.
이 설계의 핵심은 캐시 지역성이다. 하나의 버킷 안에 8개의 키-값 쌍이 연속된 메모리에 저장되므로, 버킷 내부를 탐색할 때 CPU 캐시에 한 번에 올라올 가능성이 높다. 순수 체이닝처럼 노드마다 포인터를 따라가는 것보다 훨씬 효율적이다.
버킷이 가득 차면 오버플로우 버킷을 연결하는 것은 체이닝 방식이다. 하지만 노드 하나에 값 하나가 아니라 노드 하나에 8개의 값이 들어가므로, 오버플로우 버킷까지 도달하는 경우가 드물다.
로드 팩터와 리해싱
로드 팩터 (Load Factor)
로드 팩터는 해시 테이블이 얼마나 차 있는지를 나타내는 지표다.
로드 팩터 = 저장된 엔트리 수 / 버킷 수
버킷이 8개이고 6개의 키가 저장되어 있으면 로드 팩터는 0.75다. 이 값이 높아질수록 충돌 확률이 올라가고 성능이 떨어진다.
로드 팩터가 낮으면 대부분의 버킷이 비어있어 충돌이 적고 O(1)에 가까운 성능을 보인다. 반대로 로드 팩터가 높으면 버킷마다 여러 키가 쌓여 최악의 경우 O(n)에 가까워진다.
go의 map의 경우 버킷당 평균 6.5개의 엔트리가 차면 리해싱을 시작한다. 각 버킷이 8개의 슬롯을 가지고 있으니 약 81%가 차면 확장하는 셈이다.
리해싱 (Rehashing)
로드 팩터가 임계값을 넘으면 해시 테이블은 더 큰 버킷 배열을 할당하고 모든 엔트리를 재분배한다. 이 과정을 리해싱이라 한다.
[기존] 버킷 8개, 엔트리 52개 (로드 팩터 6.5)
리해싱 -> [확장] 버킷 16개, 엔트리 52개 (로드 팩터 3.25)
버킷 수가 두 배로 늘어나면 로드 팩터가 절반으로 떨어지고 충돌이 줄어들어 성능이 회복된다. 하지만 리해싱 자체는 모든 키를 새 버킷에 다시 배치해야 하므로 O(n) 연산이다.
점진적 리해싱 (Incremental Rehashing)
엔트리가 수백만 개인 상태에서 리해싱이 발생하면 모든 키를 한 번에 옮기는 동안 서비스가 멈출 수 있다. go에서의 map은 이 문제를 점진적 리해싱으로 해결한다.
리해싱이 시작되면 기존 버킷 배열과 새 버킷 배열이 동시에 존재한다. 이후 map에 접근할 때마다(읽기든 쓰기든) 기존 버킷에서 새 버킷으로 조금씩 엔트리를 옮긴다. 한 번의 접근에 한두 개의 버킷만 처리하므로 각 연산의 비용이 크게 늘어나지 않는다.
이 방식은 최악의 경우 한 번에 O(n)이 드는 대신, n번에 걸쳐 나누어 처리하므로 분할 상환 O(1) 을 유지한다. 리얼타임 시스템에서 특히 중요한 특성이다. 갑자기 수십 밀리초의 지연이 발생하는 것보다 각 연산에 약간의 추가 비용이 고르게 분산되는 것이 훨씬 낫다.
시간 복잡도 분석
해시 테이블의 시간 복잡도를 정리하면 다음과 같다.
| 연산 | 평균 | 최악 |
|---|---|---|
| 삽입 (SET) | O(1) | O(n) |
| 조회 (GET) | O(1) | O(n) |
| 삭제 (DEL) | O(1) | O(n) |
평균 O(1)은 해시 함수가 키를 고르게 분포시키는 전제 하에 성립한다. 최악의 경우는 모든 키가 하나의 버킷에 몰릴 때 발생하지만, 좋은 해시 함수를 사용하면 현실에서는 거의 일어나지 않는다. 리해싱까지 고려하면 분할 상환 O(1)이다.
다른 자료구조와의 비교
| 자료구조 | 삽입 | 조회 | 삭제 | 순서 보장 |
|---|---|---|---|---|
| 정렬 배열 | O(n) | O(log n) | O(n) | O |
| BST / Red-Black Tree | O(log n) | O(log n) | O(log n) | O |
| 해시 테이블 | O(1) 평균 | O(1) 평균 | O(1) 평균 | X |
해시 테이블은 삽입과 조회에서 압도적이지만 순서를 보장하지 않는다. "a" 다음에 "b"를 넣어도 순회할 때 순서가 보장되지 않는다. go의 map은 의도적으로 순회 순서를 랜덤화하기까지 한다.
키를 정렬된 순서로 순회해야 하거나 범위 쿼리(e.g. 점수 100~200 사이의 유저 조회)가 필요하다면 트리 기반 자료구조가 적합할 것이다. 반면에 이 키의 값이 뭐지? 라는 단순한 질문에는 해시 테이블이 가장 빠르고 적합하다.
구현
Store 구조체
package storage
type Store struct {
data map[string]string
}
func New() *Store {
return &Store{data: make(map[string]string)}
}
func (s *Store) Set(key, value string) {
s.data[key] = value
}
func (s *Store) Get(key string) (string, bool) {
value, exist := s.data[key]
return value, exist
}
Store는 내부에 map[string]string을 가진 단순한 구조체다. Set은 키에 값을 저장하고, Get은 키로 값을 조회한다.
서버 통합
type Server struct {
listener net.Listener
addr string
store *storage.Store // 추가
}
func New(addr string) *Server {
return &Server{
addr: addr,
store: storage.New(),
}
}
Server 구조체에 Store를 추가하고 서버 생성 시 Store도 함께 초기화한다. 모든 클라이언트 연결이 하나의 Store를 공유하므로, 어떤 클라이언트가 SET한 데이터를 다른 클라이언트가 GET할 수 있다.
명령어 처리
switch command {
case "PING":
writer.WriteSimpleString("PONG")
case "ECHO":
if len(value.Array) > 1 {
writer.WriteBulkString(value.Array[1].Str)
} else {
writer.WriteError("missing argument")
}
case "SET":
key := value.Array[1].Str
val := value.Array[2].Str
s.store.Set(key, val)
writer.WriteSimpleString("OK")
case "GET":
key := value.Array[1].Str
result, exist := s.store.Get(key)
if exist {
writer.WriteBulkString(result)
} else {
writer.WriteNull()
}
default:
writer.WriteError("unknown command")
}
SET 처리
case "SET":
key := value.Array[1].Str
val := value.Array[2].Str
s.store.Set(key, val)
writer.WriteSimpleString("OK")
RESP Array에서 인덱스 0은 명령어 SET, 인덱스 1은 키, 인덱스 2는 값이다.
store에 저장 후 +OK\r\n 응답을 보낸다. 해시함수가 키를 버킷 인덱스로 변환하고 해당 버킷에 키-값 쌍의 형태로 저장하는 과정이 s.store.set(key, val) 한 줄 안에서 일어난다.
GET 처리
case "GET":
key := value.Array[1].Str
result, exist := s.store.Get(key)
if exist {
writer.WriteBulkString(result)
} else {
writer.WriteNull()
}
키가 존재하면 bulk string으로 값을 반환하고, 없으면 Null($-1\r\n)을 반환한다. Redis의 실제 동작과 동일하게 구현했다.
테스트
Store 단위 테스트
func TestSetAndGet(t *testing.T) {
// given
store := New()
// when
store.Set("name", "redis")
// then
value, exist := store.Get("name")
if !exist || value != "redis" {
t.Fatalf("기대값: redis, 실제값: %s", value)
}
}
func TestGetNonExistent(t *testing.T) {
// given
store := New()
// when
value, exist := store.Get("unknown")
// then
if exist || value != "" {
t.Fatalf("존재하지 않는 키인데 값이 반환됨: %s", value)
}
}
func TestOverWrite(t *testing.T) {
// given
store := New()
store.Set("animal", "dog")
// when
store.Set("animal", "cat")
// then
value, _ := store.Get("animal")
if value != "cat" {
t.Fatalf("덮어쓰기 실패: %s", value)
}
}
Store의 세 가지 핵심 동작을 검증한다.
- 저장 후 조회
- 존재하지 않는 키 조회
- 같은 키에 덮어쓰기
구현도 간단했던 만큼 테스트 작성도 간단했다.
통합 테스트
func TestSetCommand(t *testing.T) {
// given
input := "*3\r\n$3\r\nSET\r\n$4\r\nname\r\n$6\r\n승기\r\n"
server := New(":6379")
go server.Start()
time.Sleep(time.Second)
conn, _ := net.Dial("tcp", "localhost:6379")
defer conn.Close()
// when
conn.Write([]byte(input))
// then
reader := bufio.NewReader(conn)
response, _ := reader.ReadString('\n')
if response != "+OK\r\n" {
t.Fatalf("응답: %s", response)
}
}
func TestGetCommand(t *testing.T) {
// given
set := "*3\r\n$3\r\nSET\r\n$4\r\nname\r\n$5\r\nredis\r\n"
get := "*2\r\n$3\r\nGET\r\n$4\r\nname\r\n"
server := New(":6379")
go server.Start()
time.Sleep(time.Second)
conn, _ := net.Dial("tcp", "localhost:6379")
defer conn.Close()
// when
conn.Write([]byte(set))
conn.Write([]byte(get))
// then
reader := bufio.NewReader(conn)
reader.ReadString('\n') // SET 응답 소비
line1, _ := reader.ReadString('\n')
line2, _ := reader.ReadString('\n')
if line1+line2 != "$5\r\nredis\r\n" {
t.Fatalf("응답: %s", line1+line2)
}
}
실제 TCP 연결을 통해 RESP 형식으로 명령어를 보내고 응답을 검증한다.
마치며
이번 포스팅에서는 map[string]string을 감싸는 Store 구조체 하나로 Key-Value 저장소를 완성했다. 구현 자체는 간단했지만 그 한 줄의 map 뒤에 숨어있는 메커니즘은 생각보다 많이 깊었다. 해시 함수가 결정성, 균등 분포, 눈사태 효과를 갖춰야 하는 이유, 충돌을 해결하는 체이닝과 개방 주소법의 트레이드오프, go가 8슬롯 버킷이라는 하이브리드 방식을 선택한 배경, 로드 팩터가 올라가면 왜 점진적 리해싱이 필요한지까지 말이다.
다음 포스팅에서는 여러 클라이언트가 동시에 접속했을 때의 문제를 다룬다. 지금 구현은 go s.handleConnection(conn)으로 고루틴을 띄워 동시 접속을 처리하고 있지만 여러 고루틴이 하나의 store에 동시에 접근하면 데이터가 깨질 수 있다. 레이스 컨디션과 동시성 제어에 대해 살펴보겠다.
참고