B-tree와 LSM-tree - 읽기와 쓰기 중 무엇을 팔 것인가

센서 데이터를 초당 5만 건 넣는다. 디스크 사용률이 100%인데 처리량은 안 오른다. 서버를 키워도 그대로다.

이유는 간단하다. 8바이트를 넣으려고 디스크에는 8KB를 쓰고 있다.

인덱스도, 조인도, 실행 계획도 전부 B-tree를 깔고 한 이야기였다. 이번엔 그 바닥을 뒤집는다.

B-tree는 제자리에 쓴다

인덱스 글에서 본 그 구조다. 값이 정렬된 채로 블록에 담겨 있고, 위에서부터 몇 번 내려가면 원하는 블록에 닿는다.

핵심은 제자리 갱신이다. 값을 바꾸려면 그 값이 있는 블록을 찾아가서 덮어쓴다. 값 하나는 늘 한 군데에만 있다.

그래서 읽기가 빠르다. 한 군데만 보면 끝이다. 인덱스도, 조인도, 실행 계획도 전부 이걸 깔고 한 얘기였다.

그런데 디스크는 8바이트를 못 쓴다

여기가 문제의 뿌리다. 그리고 블록 글에서 이미 예고한 그것이다. 디스크는 블록 단위로만 읽고 쓴다. 8KB짜리 블록 안의 8바이트를 바꾸려면 8KB를 통째로 다시 써야 한다.

조회에서는 이게 이득이었다. 어차피 통째로 읽을 거면 블록을 값으로 꽉 채우면 됐으니까. 쓰기에서는 그냥 손해다. 같은 성질이 방향을 바꾸면 반대로 작동한다.

그리고 한 번이 아니다.

• 블록에 자리가 없으면 쪼갠다. 한 번의 삽입이 여러 블록을 건드린다.
• 쪼개다 죽으면 인덱스가 깨지니, 그걸 막으려고 로그(WAL)에도 먼저 쓴다. 지속성이 공짜가 아닌 이유다.
• 블록들은 디스크 여기저기에 흩어져 있다. 무작위 위치에 쓴다.

무작위 위치라는 말이 낯익다면 맞다. 키 설계에서 무작위 UUID가 인덱스를 망가뜨린 이유가 이것이었다. 다만 거기서는 키를 바꿔서 피했다. 여기서는 그럴 수가 없다. 애초에 쓰기가 너무 많다.

뒤집는다

LSM-tree의 발상은 하나다. 제자리에 안 쓴다. 그냥 끝에 덧붙인다.

새 값이 들어오면 일단 메모리에 모은다. 디스크는 안 건드린다. 메모리가 어느 정도 차면 정렬해서 파일 하나로 통째로 떨군다. 그 파일은 그 뒤로 절대 안 고친다.

값을 바꾸면? 새 값을 또 덧붙인다. 옛 값은 옛 파일에 그대로 남는다. 지우면? “지웠음”이라고 덧붙인다. 실제로 지우지 않는다.

그래서 디스크에는 순차 쓰기만 나간다. 헤드가 왔다 갔다 할 일이 없고, 블록을 찾아가 덮어쓸 일도 없다. 디스크가 가장 좋아하는 패턴이다.

공짜일 리가 없다

읽기가 낸다.

값 하나를 찾으려면 메모리를 보고, 없으면 최신 파일을 보고, 없으면 그다음 파일을 본다. 파일이 쌓일수록 뒤질 곳이 늘어난다. B-tree는 한 군데였는데 여기는 여러 군데다.

없는 키를 찾을 때가 최악이다. 전부 뒤진 뒤에야 없다고 답할 수 있다.

그래서 두 가지를 붙인다.

블룸 필터. 파일마다 “이 파일에 이 키가 있을 수도 있다 / 확실히 없다”를 아주 싸게 답하는 요약본을 둔다. “확실히 없다”가 나오면 그 파일은 안 연다. 없는 키를 찾는 게 싸진다.

컴팩션. 파일들을 백그라운드에서 병합해서 개수를 줄인다. 이때 낡은 값과 “지웠음” 표시도 같이 정리된다. 뒤질 곳이 줄어든다.

컴팩션이 진짜 대가다

여기가 LSM을 쓸 때 실제로 아픈 지점이다.

컴팩션은 계속 돈다. 그리고 같은 데이터를 몇 번이고 다시 쓴다.

그리고 컴팩션은 쓰기와 같은 디스크를 쓴다. 쓰기가 몰리면 컴팩션이 못 따라오고, 파일이 쌓이고, 읽기가 느려지고, 결국 DB가 쓰기를 막아버린다.

그래서 성질이 다르다. B-tree는 느려도 일정하다. LSM은 대체로 빠르다가 가끔 확 튄다. 평균만 보면 LSM이 이기는데 p99를 보면 뒤집히는 일이 흔하다. 응답 시간이 일정해야 하는 곳에서는 이게 결정적이다.

세 가지 증폭

둘의 차이는 결국 무엇을 증폭시키느냐로 정리된다.

셋을 동시에 좋게 할 수 없다. 하나를 누르면 다른 게 부푼다. 이건 튜닝을 못 해서가 아니라 구조가 그렇다.

• B-tree는 읽기를 잡는다. 한 군데만 보면 되니까. 대신 쓰기 증폭이 크다.
• LSM은 쓰기를 잡는다. 순차로 덧붙이니까. 대신 여러 군데를 봐야 한다.

LSM 안에서도 같은 저울이 또 있다. 컴팩션을 얼마나 부지런히 하느냐다. 부지런히 하면 파일이 적어져 읽기가 좋아지고 낡은 값도 빨리 사라지지만 쓰기 증폭이 커진다. 게으르게 하면 반대로 쓰기는 싸지지만 낡은 값이 오래 남아 공간을 먹는다. 앞쪽을 레벨드(leveled), 뒤쪽을 티어드(tiered) 컴팩션이라고 부른다. 어느 쪽으로도 공짜는 없다.

트랜잭션은 어떻게 되나

샤딩에서는 ACID를 잃었다. 여기서는 안 잃는다.

자료구조와 트랜잭션은 다른 층이다. LSM 위에도 트랜잭션을 올릴 수 있고 실제로 그렇게 쓴다.

오히려 궁합이 좋은 데가 있다. MVCC는 덮어쓰지 않고 버전을 쌓는 방식이었다. LSM도 덮어쓰지 않는다. 애초에 하는 일이 같다.

MVCC의 대가가 “쌓인 옛 버전을 누군가 치워야 한다”였던 것도 기억할 만하다. LSM에서는 컴팩션이 그 일을 겸한다. 파일을 병합하면서 아무도 안 보는 옛 버전을 같이 버린다. 이름은 다르지만 같은 청소다.

무엇이 무엇을 쓰나

대부분의 RDBMS가 B-tree인 건 우연이 아니다. 업무 시스템은 읽기가 많고, 응답 시간이 일정해야 하고, 데이터가 SSD 하나에 들어간다. 그 조건에서는 B-tree가 맞다.

LSM은 쓰기가 압도적으로 많고, 가끔 튀어도 되고, 데이터가 아주 큰 쪽에서 쓴다. 로그, 시계열, 이벤트 같은 것들이다. 맨 앞의 센서 데이터가 정확히 이 자리다.

시리즈를 관통한 것

시리즈를 마치며 하나만 남긴다면 이것이다. DB에는 공짜가 없다. 빨라졌다면 무언가를 판 것이고, 판 게 뭔지 모르면 그게 나중에 청구된다.

패턴이 보인다. DB가 해주던 걸 포기할수록 규모를 얻고, 그 대신 사람이 지켜야 할 규칙이 늘어난다. 정규화를 풀면 코드가 일관성을 지켜야 하고, 샤딩하면 코드가 트랜잭션 경계를 지켜야 하고, 복제하면 코드가 어디로 읽을지 정해야 한다.

그래서 DB를 안다는 건 문법을 아는 게 아니라 이 거래표를 아는 것이다. 무엇을 팔고 있는지 알면서 파는 것과, 모르고 파는 것은 다르다.