7주차 강의록입니다!
Q. Fastpath의 전제 조건이 오른쪽 리프 노드의 첫 번째 키보다 캬야하는데, 아까 말씀하실 때 60보다 작은 값은 60의 왼쪽으로 가야한다고 하신 부분이 이해가 안됩니다
왼쪽으로 간다는 것 자체가 전제 조건에서 틀린 것 아닌가요?
오른쪽 리프 노드의 첫번째인 60보다 커야하는 게 조건인데, 60의 왼쪽으로 가는거면 fastpath 조건에 안맞지 않은지가 질문의 요지입니다
A. 먼저 복습 차 책 내용 일부를 보겠습니다.
PostgreSQL은 이 경우를 fastpath라고 부릅니다. 삽입된 키가 오른쪽 끝 페이지의 첫 번째 키보다 크고, 그 페이지가 새로운 항목을 담을 만큼 충분한 공간을 가지고 있다면, 새로운 항목은 캐시에 있는 오른쪽 리프에 적절한 위치에 삽입되며, 전체 읽기 경로(read path)는 건너뛸 수 있습니다.
결론부터 말씀드리자면 ‘fastpath’는 지름길이고, 지름길을 타기 위한 조건은 ‘오른쪽 리프의 첫 번째 키보다 크다’입니다. 지름길을 타지 못한다면 일반적인 B-Tree 탐색에 따라 삽입 위치를 식별합니다 (지난 주차 권찬님의 설명 참고 바랍니다).
이제 강의에서 언급한 예시를 보겠습니다.
[50]
/ \
[10 20] [60 70 90]
Markdown
복사
•
60보다 크다면 fastpath를 타서 지름길로 오른쪽 리프 페이지로 한 번에 접근합니다.
•
60보다 작거나 같다면 fastpath를 타지 않고 일반적인 B-Tree 탐색에 따라 여러 번에 걸쳐 접근합니다.
◦
50보다 작은 경우 애초에 왼쪽 서브트리로 가므로 질문에서 해당사항이 없겠죠?
◦
50보다 크거나 같고 60보다 작은 경우 60 왼쪽으로 삽입 위치를 결정합니다.
◦
60인 경우 중복 케이스입니다. 보통 단조 증가 키는 PK로 사용하므로, 유일성 제약조건이 걸려있습니다. 따라서 에러가 발생합니다. 이 역시 질문에서 해당사항이 없습니다.
강의에서 언급한 “60보다 작은 값은 60의 왼쪽으로 가야한다” 라는 말은 “60보다 작은 값은 fastpath를 타지 않고 60의 왼쪽으로 가야한다” 라는 뜻입니다. 삽입 위치는 60의 왼쪽이 맞습니다. 그런데 fastpath라는 지름길은 못 탄다는 뜻입니다.
오른쪽 리프 노드의 첫번째인 60보다 커야하는 게 조건인데, 60의 왼쪽으로 가는거면 fastpath 조건에 안맞지 않은지가 질문의 요지입니다
이에 대해서도 정리를 해보자면,
•
60보다 커야하는 것이 fastpath의 조건 맞습니다.
•
60의 왼쪽으로 가는 것이면, 60보다 작은 것이므로, fastpath의 조건을 충족시키지 않는 것 맞습니다.
즉 질문주신 내용은 둘 다 참입니다.
제가 질문 받았을 때 살짝 뇌정지가 왔는데요, 질문 내용이 맞는 말 + 맞는 말이어서 그러지 않았나 싶습니다. 그래서 왜 궁금해하셨을지 고민을 조금 해봤습니다. 제 생각은 이렇습니다.
55 같은 값의 경우에는, fastpath 조건에 해당되지 않지만, 삽입 위치는 오른쪽 리프 페이지이다.
65 같은 값의 경우에는, fastpath 조건에 해당되며, 삽입 위치는 오른쪽 리프 페이지이다.
따라서 ‘오른쪽 리프 페이지의 첫 번째 키보다 크다’는 조건은 55 같은 케이스가 오른쪽 리프 페이지에 삽입되는 것을 막고 있다. fastpath를 타도록 조건을 수정해도 되는데, 왜 조건을 그렇게 설정한 것일까?
먼저 ‘55 같은 케이스’는 엄밀하게 말하면 ‘50보다 크고 60보다 작은’ 경우를 말합니다. 이는 다시 부모 키보다는 크고 자식 페이지의 첫 번째 키보다 작은 경우로 표현될 수 있습니다. 이러한 케이스를 고려하기 위해서는 오른쪽 리프 페이지 캐싱만으로는 불가능합니다. 왜죠? 부모 키를 알아야 하니까요. 부모 키까지 같이 저장한다면 55 같은 경우를 핸들링할 수 있게 됩니다. 하지만…
오른쪽 리프 페이지와 부모 페이지는 라이프사이클이 다르죠. 캐시라는 것은 기본적으로 데이터 일관성 문제를 수반합니다. 오른쪽 리프 페이지에서 삽입으로 분할이 발생한다 칩시다. 그럼 오른쪽 리프 페이지도 바뀌고, 중간 키가 승격되므로 부모 키도 바뀝니다. 그런데, 여기서 부모 페이지에서도 분할이 연쇄적으로 발생한다면 다시 부모 키가 달라질 수 있겠죠.
Q) 최종적으로 모든 변경이 끝난 오른쪽 리프 페이지와 부모 키를 저장하면 되지 않나요? → 이 모든 과정은 원자적이지 않죠. 그리고 동시성도 고려를 해야 합니다. 여러 트랜잭션이 동시에 fastpath를 타는 경우를 가정한다면 상황이 아주 복잡해질 겁니다.
따라서 (제 생각은) 단순성을 위해서 55 케이스(즉 부모 키와 첫 번째 키 사이 케이스)를 희생했다고 봅니다. 오른쪽 리프 페이지만으로 판단할 수 있는 값은 당연히 60보다 큰 값밖에 없으니까요.
Q) 그렇다면 그냥 오른쪽 리프 페이지의 마지막 키와 비교하면 되지 않나요? 그러면 항상 오른쪽에서 삽입이 발생하니까요. 굳이 첫 번째 키인 이유가 있나요? → quickbalance가 그런 조건을 쓰죠. “삽입 대상이 가장 큰 값을 가진 경우”. postgresql은 ‘페이지 단위’로 캐싱을 한다고 했죠. 페이지 단위로 읽고 쓰니까 그냥 마지막 키를 캐싱하는 것보다 오른쪽 리프 페이지를 캐싱하는 게 (기왕 하는 거) 더 낫지 않을까- 해서 그렇게 한 게 아닐까 싶습니다.
그렇게 페이지 단위로 캐싱을 하다 보니 “아니 첫 번째 키로 비교하면 더 넓은 케이스가 이 fastpath를 타게 만들 수 있는데 굳이?” 싶었을 거고요. (제 생각입니다)
제가 당일 답변 드리겠다고 하고 시간이 조금 많이 지났는데요, 이후에 개인 일정이 이것저것 겹치다 보니 답변이 많이 늦어졌네요. 정말 죄송합니다…!