들어가며

이번 포스팅에서는 이중 연결 리스트를 직접 구현하고, 저장소를 다중 타입으로 확장하여 LPUSH, RPUSH, LPOP, RPOP, LRANGE 명령어를 추가한다. 배열과 연결 리스트의 근본적인 차이부터 시작해서 왜 이중 연결 리스트가 이 상황에 적합한지, 그리고 포인터로 노드 간 연결을 어떻게 구현하는지를 다룬다.



배열과 연결 리스트

데이터를 순차적으로 저장하는 가장 기본적인 두 자료구조가 배열과 연결 리스트이다. 이 둘의 핵심 차이는 메모리 배치에 있다.

배열은 연속된 메모리 공간에 요소를 나란히 저장한다. 컴파일러가 시작 주소 + (인덱스 × 요소 크기)로 바로 계산할 수 있기 때문에 인덱스 접근이 O(1)이다. 하지만 앞쪽에 요소를 삽입하거나 삭제하면 나머지 요소를 전부 한 칸씩 밀거나 당겨야 하므로 O(n)이 된다. go의 슬라이스([]string)가 내부적으로 배열 기반이다.

연결 리스트는 각 요소가 데이터와 함께 다음 노드를 가리키는 참조(포인터)를 가진다. 노드들이 메모리 여기저기에 흩어져 있어도 포인터로 연결되어 있으므로 연속된 공간이 필요 없다. 삽입이나 삭제 시 포인터만 변경하면 되므로 양 끝에서 O(1)이다. 대신 특정 인덱스에 접근하려면 Head부터 하나씩 따라가야 하므로 O(n)이다.

연산배열 (슬라이스)Doubly Linked List
앞쪽 삽입/삭제O(n)O(1)
뒤쪽 삽입/삭제O(1)*O(1)
인덱스 접근O(1)O(n)
범위 조회O(k)O(n+k)

*슬라이스의 append는 용량 초과 시 O(n) 재할당 발생

레디스의 LPUSH/RPUSH/LPOP/RPOP은 모두 양쪽 끝에서의 삽입/삭제다. 이 4가지의 연산이 모두 O(1)이어야 하므로 연결 리스트가 적합하다. 슬라이스로 구현하면 앞쪽 삽입/삭제(LPUSH, LPOP)에서 O(n)이 되어 데이터가 많아질수록 성능이 저하된다.



단일 연결 리스트와 이중 연결 리스트

연결 리스트에도 종류가 있다. 노드가 가진 포인터의 수에 따라 단일 연결 리스트와 이중 연결 리스트로 나뉜다.


단일 연결 리스트

Singly Linked List

각 노드가 Next 포인터 하나만 가진다. 앞쪽(Head) 삽입/삭제는 O(1)이지만 뒤쪽(Tail) 삭제가 O(n) 이다. 마지막 노드를 제거하려면 그 직전 노드의 Next를 nil로 바꿔야 하는데, 직전 노드를 찾으려면 Head부터 끝까지 순회해야 한다. Prev 포인터가 없기 때문이다.


이중 연결 리스트

Doubly Linked List

각 노드가 Prev와 Next 포인터를 모두 가진다. 꼬리 노드에서 Prev를 따라가면 직전 노드를 바로 찾을 수 있으므로 양쪽 끝의 삽입/삭제가 모두 O(1) 이다. 포인터 하나를 추가하는 대가로 노드당 메모리가 조금 더 필요하지만, 모든 방향의 접근이 상수 시간이 된다.



다중 타입 Store

이전의 Store는 map[string]string으로 모든 값이 문자열이었다. List를 지원하려면 하나의 키에 문자열 또는 리스트가 들어갈 수 있어야 한다.

이를 위해 값의 타입을 나타내는 태그와 실제 데이터를 함께 묶는 Entry 구조체를 도입한다.

type EntryType int

const (
    TypeString EntryType = iota
    TypeList
)

type Entry struct {
    Type EntryType
    Str  string
    List *List
}

iota는 go의 상수 자동 증가 키워드다. TypeString은 0, TypeList는 1이 된다. Entry는 Type 필드로 현재 어떤 타입인지를 나타내고, 타입에 따라 Str 또는 List 필드를 사용한다.

store의 내부 맵도 map[string]*Entry로 변경된다. 이제 각 키가 문자열 값, 리스트 두 개를 가질 수 있게 되었다.


WRONGTYPE 에러

레디스는 SET으로 만든 문자열 키에 LPUSH를 시도하면 다음과 같은 에러를 반환한다.

-ERR WRONGTYPE Operation against a key holding the wrong kind of value

반대로 LPUSH로 만든 리스트 키에 GET을 시도해도 마찬가지다. 타입이 맞지 않는 연산은 기존 데이터를 보호하기 위해 거부된다. 다만 SET은 예외적으로 키의 기존 타입에 관계없이 덮어쓴다.

타입 검사 규칙을 정리하면 다음과 같다.

  • 키가 존재하지 않으면 해당 타입으로 새로 생성 (에러 아님)
  • 키가 존재하고 타입이 일치하면 정상 처리
  • 키가 존재하지만 타입이 다르면 WRONGTYPE 에러 반환


코드 구현

list.go

이중 연결 리스트를 직접 구현한다. go 표준 라이브러리의 container/list를 사용하지 않고 포인터로 노드 간 연결을 직접 관리하도록 해준다.

package storage

type Node struct {
	Value string
	Prev  *Node
	Next  *Node
}

type List struct {
	Head   *Node
	Tail   *Node
	Length int
}

func NewList() *List {
	return &List{}
}

// 앞쪽 삽입 - O(1)
func (l *List) LPush(value string) {
	newNode := &Node{Value: value}

	if l.Head != nil {
		newNode.Next = l.Head
		l.Head.Prev = newNode
	} else {
		l.Tail = newNode
	}

	l.Head = newNode
	l.Length++
}

// 뒤쪽 삽입 — O(1)
func (l *List) RPush(value string) {
	newNode := &Node{Value: value}

	if l.Tail != nil {
		newNode.Prev = l.Tail
		l.Tail.Next = newNode
	} else {
		l.Head = newNode
	}

	l.Tail = newNode
	l.Length++
}

// 앞쪽 삭제 — O(1). 빈 리스트면 ("", false) 반환
func (l *List) LPop() (string, bool) {
	if l.Head == nil {
		return "", false
	}

	value := l.Head.Value
	l.Head = l.Head.Next

	if l.Head != nil {
		l.Head.Prev = nil
	} else {
		l.Tail = nil
	}

	l.Length--
	return value, true
}

// 뒤쪽 삭제 — O(1). 빈 리스트면 ("", false) 반환
func (l *List) RPop() (string, bool) {
	if l.Tail == nil {
		return "", false
	}

	value := l.Tail.Value
	l.Tail = l.Tail.Prev

	if l.Tail != nil {
		l.Tail.Next = nil
	} else {
		l.Head = nil
	}

	l.Length--
	return value, true
}

// 범위 조회. 음수 인덱스 지원 (-1 = 마지막, -2 = 마지막에서 두 번째)
func (l *List) Range(start, stop int) []string {
	if start < 0 {
		start = l.Length + start
	}
	if stop < 0 {
		stop = l.Length + stop
	}

	if start < 0 {
		start = 0
	}
	if stop > l.Length-1 {
		stop = l.Length - 1
	}

	if start > stop {
		return make([]string, 0)
	}

	current := l.Head
	for i := 0; i < start; i++ {
		current = current.Next
	}

	result := make([]string, 0, stop-start+1)
	for i := start; i <= stop; i++ {
		result = append(result, current.Value)
		current = current.Next
	}

	return result
}

store.go

store의 내부 맵을 map[string]*Entry로 변경하고 List 연산 메서드를 추가한다. 이전 챕터에서 적용한 RWMutex도 새 메서드에도 동일하게 적용한다. 쓰기 연산(LPush, RPush, LPop, RPop)에는 Lock(), 읽기 연산(LRange)에는 RLock()을 사용한다.

package storage

import (
	"errors"
	"sync"
)

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
}
type Store struct {
	data map[string]*Entry
	mu   sync.RWMutex
}

func New() *Store {
	return &Store{data: make(map[string]*Entry)}
}

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.RLock()
	defer s.mu.RUnlock()

	entry, exist := s.data[key]

	if !exist {
		return "", false
	} else {
		if entry.Type != TypeString {
			return "", false
		}
	}

	return entry.Str, exist
}

// 키가 존재하지 않으면 새 리스트를 생성한다
// 키가 존재하지만 TypeList가 아니면 ErrWrongType을 반환한다
func (s *Store) LPush(key string, values ...string) (int, error) {
	s.mu.Lock()
	defer s.mu.Unlock()

	entry, exist := s.data[key]

	if !exist {
		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 {
		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
}

// 빈 리스트가 되면 키를 삭제한다 (Redis 동작)
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
	}

	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
	}

	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.RLock()
	defer s.mu.RUnlock()

	entry, exist := s.data[key]

	if !exist {
		return []string{}, nil
	}

	if entry.Type != TypeList {
		return nil, ErrWrongType
	}

	result := entry.List.Range(start, stop)

	return result, nil
}

writer.go (추가 메서드)

LPUSH/RPUSH는 리스트의 길이를 정수로, LRANGE는 값들을 배열로 응답해야 한다. RESP 프로토콜의 Integer와 Array 타입에 해당하는 Writer 메서드를 추가한다.

func (w *Writer) WriteInteger(n int) error {
	w.writer.Write([]byte(":" + strconv.Itoa(n) + "\r\n"))
	return nil
}

// 빈 배열이면 "*0\r\n"
func (w *Writer) WriteArray(values []string) error {
	length := len(values)
	strLen := strconv.Itoa(length)

	w.writer.Write([]byte("*" + strLen + "\r\n"))

	for _, v := range values {
		w.WriteBulkString(v)
	}
	return nil
}

server.go

handleConnection의 switch문에 기존 PING, ECHO, SET, GET은 그대로 유지하면서 5개의 새 명령어 핸들러를 추가한다.

func (s *Server) handleConnection(conn net.Conn) {
	defer conn.Close()

	bufReader := bufio.NewReader(conn)
	reader := protocol.NewReader(bufReader)
	writer := protocol.NewWriter(conn)

	for {
		value, err := reader.Read()
		if err != nil {
			return
		}

		command := strings.ToUpper(value.Array[0].Str)

		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
			value := value.Array[2].Str
			s.store.Set(key, value)
			writer.WriteSimpleString("OK")

		case "GET":
			key := value.Array[1].Str
			result, exist := s.store.Get(key)
			if exist {
				writer.WriteBulkString(result)
			} else {
				writer.WriteNull()
			}

		case "LPUSH":
			if len(value.Array) < 3 {
				writer.WriteError("missing argument")
			} else {
				values := make([]string, 0, len(value.Array)-2)
				for _, v := range value.Array[2:] {
					values = append(values, v.Str)
				}
				length, err := s.store.LPush(value.Array[1].Str, values...)
				if err != nil {
					writer.WriteError(err.Error())
				} else {
					writer.WriteInteger(length)
				}
			}

		case "RPUSH":
			if len(value.Array) < 3 {
				writer.WriteError("missing argument")
			} else {
				values := make([]string, 0, len(value.Array)-2)
				for _, v := range value.Array[2:] {
					values = append(values, v.Str)
				}
				length, err := s.store.RPush(value.Array[1].Str, values...)
				if err != nil {
					writer.WriteError(err.Error())
				} else {
					writer.WriteInteger(length)
				}
			}

		case "LPOP":
			value, result, err := s.store.LPop(value.Array[1].Str)
			if err != nil {
				writer.WriteError(err.Error())
			} else {
				if !result {
					writer.WriteNull()
				} else {
					writer.WriteBulkString(value)
				}
			}

		case "RPOP":
			value, result, err := s.store.RPop(value.Array[1].Str)
			if err != nil {
				writer.WriteError(err.Error())
			} else {
				if !result {
					writer.WriteNull()
				} else {
					writer.WriteBulkString(value)
				}
			}

		case "LRANGE":
			if len(value.Array) < 4 {
				writer.WriteError("missing argument")
			} else {
				start, _ := strconv.Atoi(value.Array[2].Str)
				stop, _ := strconv.Atoi(value.Array[3].Str)
				result, err := s.store.LRange(value.Array[1].Str, start, stop)
				if err != nil {
					writer.WriteError(err.Error())
				} else {
					writer.WriteArray(result)
				}
			}

		default:
			writer.WriteError("unknown command")
		}
	}
}

테스트

이번 챕터에서 작성한 테스트코드가 너무 많은 관계로 핵심 케이스만 살펴보도록 하겠다.


포인터 연결 검증 (list_test.go)

func TestLPush_MultipleElements(t *testing.T) {
	// given
	list := NewList()

	// when: a, b, c 순서로 LPush -> [c, b, a]
	list.LPush("a")
	list.LPush("b")
	list.LPush("c")

	// then
	if list.Length != 3 {
		t.Fatalf("길이가 다릅니다. actual: %d, expected: 3", list.Length)
	}
	if list.Head.Value != "c" {
		t.Fatalf("Head 값이 다릅니다. actual: %s, expected: c", list.Head.Value)
	}
	if list.Tail.Value != "a" {
		t.Fatalf("Tail 값이 다릅니다. actual: %s, expected: a", list.Tail.Value)
	}
	// 포인터 연결 검증: c -> b -> a
	if list.Head.Next.Value != "b" {
		t.Fatalf("Head.Next 값이 다릅니다. actual: %s, expected: b", list.Head.Next.Value)
	}
	if list.Tail.Prev.Value != "b" {
		t.Fatalf("Tail.Prev 값이 다릅니다. actual: %s, expected: b", list.Tail.Prev.Value)
	}
}

단순히 값이 들어갔는지만 확인하는 것이 아니라 Head.Next와 Tail.Prev로 노드 간에 포인터 연결이 올바른지까지 검증한다. 이중 연결 리스트의 핵심은 양방향 연결이므로 이 검증이 빠지면 단일 연결 리스트와 다를 바가 없다.


WRONGTYPE 에러 검증 (store_test.go)

func TestLPush_WrongType(t *testing.T) {
	// given: String 타입으로 키 설정
	store := New()
	store.Set("key", "value")

	// when: 같은 키에 LPush 시도
	_, err := store.LPush("key", "a")

	// then: WRONGTYPE 에러
	if err != ErrWrongType {
		t.Fatalf("에러가 다릅니다. actual: %v, expected: %v", err, ErrWrongType)
	}
}

다중 타입 Store에서 설명한 타입 안전성을 검증한다. SET으로 만든 문자열 키에 LPUSH를 시도하면 ErrWrongType이 반환되어야 한다.


빈 리스트 자동 삭제 검증 (store_test.go)

func TestLPop_DeletesEmptyList(t *testing.T) {
	// given: 1개짜리 리스트
	store := New()
	store.LPush("mylist", "a")

	// when: Pop으로 비우기
	store.LPop("mylist")

	// then: 키 자체가 삭제됨 (다시 Pop하면 값 없음)
	_, ok, _ := store.LPop("mylist")
	if ok {
		t.Fatal("빈 리스트의 키가 삭제되지 않았습니다")
	}
}

LPop으로 리스트의 마지막 요소를 제거하면 빈 리스트가 되는데 레디스는 빈 리스트를 존재하지 않는 것과 동일하게 취급한다. 키 자체가 맵에서 삭제되어야 하고 다시 Pop하면 “키가 없다"는 결과(ok == false)가 나와야 한다.


LRANGE 서버 통합 테스트 (server_test.go)

func TestLRangeCommand(t *testing.T) {
	// given: RPUSH range-list a b c → [a, b, c]
	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("*5\r\n$5\r\nRPUSH\r\n$10\r\nrange-list\r\n$1\r\na\r\n$1\r\nb\r\n$1\r\nc\r\n"))
	reader.ReadString('\n') // :3 소비

	// when: LRANGE range-list 0 -1
	conn.Write([]byte("*4\r\n$6\r\nLRANGE\r\n$10\r\nrange-list\r\n$1\r\n0\r\n$2\r\n-1\r\n"))

	// then: *3\r\n$1\r\na\r\n$1\r\nb\r\n$1\r\nc\r\n
	// 1줄(배열 헤더) + 2줄*3(bulk string) = 7줄
	var response string
	for i := 0; i < 7; i++ {
		line, _ := reader.ReadString('\n')
		response += line
	}

	expected := "*3\r\n$1\r\na\r\n$1\r\nb\r\n$1\r\nc\r\n"
	if response != expected {
		t.Fatalf("응답: %q, expected: %q", response, expected)
	}
}

RESP Array 응답은 이전까지 없던 새로운 패턴이다. 배열 헤더(*3\r\n)에 이어 3개의 Bulk String이 연속으로 오므로, 총 7줄(1 + 2×3)을 읽어서 조합해야 한다.



라인별 Deep Dive


LPush - Head에 노드 삽입

func (l *List) LPush(value string) {
	newNode := &Node{Value: value}

	if l.Head != nil {
		newNode.Next = l.Head
		l.Head.Prev = newNode
	} else {
		l.Tail = newNode
	}

	l.Head = newNode
	l.Length++
}

새 노드를 만들고 리스트의 Head 앞에 연결하는 과정이다.

l.Head != nil은 리스트에 기존 노드가 있는지를 확인한다. 기존 노드가 있으면 새 노드의 Next를 현재 head로, 현재 head의 Prev를 새 노드로 연결한다.

리스트가 비어있으면 새 노드가 유일한 노드이므로 Tail도 새 노드를 가리키도록 해준다.

마지막에 l.Head = newNode는 조건과 무관하게 항상 실행된다. 빈 리스트든 아니든 새 노드는 항상 Head가 되기 때문이다.


LPop - Head에서 노드 제거

func (l *List) LPop() (string, bool) {
	if l.Head == nil {
		return "", false
	}

	value := l.Head.Value
	l.Head = l.Head.Next

	if l.Head != nil {
		l.Head.Prev = nil
	} else {
		l.Tail = nil
	}

	l.Length--
	return value, true
}

l.Head == nil이면 빈 리스트이므로 ("", false)를 반환한다.

핵심은 l.Head = l.Head.Next 한 줄이다. head를 다음 노드로 이동시키면 기존 head 노드는 어디서도 참조하지 않게 되어 go의 가비지 컬렉터가 자동으로 회수한다.

그 다음에는 새 head가 nil이 아니면 이전 노드와의 연결을 끊기 위해 Prev를 nil로 설정한다. 새 head가 nil이면 리스트가 비었다는 뜻이므로 tail도 nil로 설정한다.


Range - 음수 인덱스 변환

if start < 0 {
    start = l.Length + start
}
if stop < 0 {
    stop = l.Length + stop
}

LRANGE는 음수 인덱스를 지원한다. Length + 음수값연산을 통해 인덱스를 찾는다.

if start < 0 {
    start = 0
}
if stop > l.Length-1 {
    stop = l.Length - 1
}

음수 변환 후에도 범위를 벗어날 수 있는 상황을 고려하여 start가 여전히 음수면 0으로, stop이 리스트 범위를 초과하면 마지막 인덱스로 맞춰준다.

if start > stop {
    return make([]string, 0)
}

보정 후에도 start가 stop보다 크면 유효한 범위가 없으므로 빈 배열을 반환한다.


Store.LPush - 키 생성과 타입 검사

entry, exist := s.data[key]

if !exist {
    newEntry := Entry{Type: TypeList, List: NewList()}
    entry = &newEntry
    s.data[key] = entry
}

if entry.Type != TypeList {
    return 0, ErrWrongType
}

이 두가지의 분기 패턴은 store의 모든 List 연산에서 반복된다. 먼저 키의 존재 여부를 확인하고 없으면 새로운 Entry를 생성한다. 그 다음은 타입을 검사한다.



마치며

지금까지 만든 데이터베이스는 모든 데이터가 메모리에만 존재하기 때문에 서버가 종료되면 모두 사라진다. 다음 포스팅에서는 데이터에 TTL을 설정하고, 만료된 데이터를 자동으로 정리하는 메커니즘을 구현해보겠다.



참고