페이지 유지보수 중 안정적인 행 식별자 유지

Source: Dev.to

번역할 텍스트가 제공되지 않았습니다. 번역이 필요한 본문을 알려주시면 한국어로 번역해 드리겠습니다.

Source: …

소개

크리스마스, 새해, 1주일간의 스키 여행, 가족과의 시간, How to Take Smart Notes를 읽은 뒤 내 Obsidian 보관함을 Zettelkasten 슬립 박스로 완전 재구성하는 일에 빠진 것 등—이 모든 일들 때문에 예상보다 프로젝트 진행이 크게 뒤처졌습니다. 특히 3주간의 겨울 방학 동안은 더욱 그랬습니다. 그럼에도 불구하고 약간의 진전은 있었습니다.

저는 아직도 저장 시스템 안에서 힙을 위한 슬롯 페이지 작업을 진행 중이며, 데이터베이스 엔진이 특정 페이지 유지 관리 작업을 처리하는 방식에서 몇 가지 흥미로운 점을 발견했습니다.

Row IDs

대부분의 시스템(여기서는 주로 SQL Server가 처리하는 방식에 대해 알고 있음)은 내부적으로 행을 식별하기 위해 row ID를 사용합니다.

row ID는 시스템이 단일 행을 고유하게 식별할 수 있게 해주는 식별자라 볼 수 있습니다. 엔진이 이 식별자를 저장해야 하는 위치가 여러 곳 있을 수 있지만, 가장 좋은 예는 비클러스터드(또는 보조) 인덱스입니다. 비클러스터드 인덱스에서는 각 엔트리가 해당 행 전체에 대한 포인터를 포함합니다. 해당 인덱스를 기반으로 행을 검색할 때, 필요에 따라 전체 행을 얻기 위해 행 식별자를 사용합니다.

SQL Server가 이를 수행하는 방법

SQL Server에서 비클러스터형 인덱스에 사용되는 행 ID는 원본 테이블에 따라 달라지며 일반적으로 행 북마크 값이라고 합니다 (Delaney et al., 2013, p. 308):

• 클러스터형 테이블 – 비클러스터형 인덱스는 클러스터링 키를 행 식별자로 사용합니다.
• 힙 – 비클러스터형 인덱스는 물리적 행 로케이터를 사용하여 행을 식별합니다.

오늘은 클러스터형 테이블이 완전히 다른 개념이므로 힙에만 집중합니다. 그 물리적 행 로케이터(마이크로소프트에서는 RID라고 부름)는 FileID:PageID:SlotID 형태의 8바이트 값으로, 다음과 같이 세 구간으로 나뉩니다:

핵심 포인트: 행 ID에는 행의 슬롯 번호가 포함되어 있으며, 이 행 ID는 모든 비클러스터형 인덱스에 나타납니다. 이것이 이 글의 개념을 이끌어냅니다.

안정적인 슬롯 번호

인덱스는 슬롯 ID를 행 식별자의 일부로 사용하기 때문에, 시스템은 내부 페이지 유지 관리 작업 중에 행이 슬롯 번호를 유지하도록 보장해야 합니다. 행이 다른 슬롯으로 재배정된다면, 모든 비클러스터드 인덱스도 업데이트해야 하므로 비용이 많이 드는 작업이 됩니다.

이 규칙의 가장 직접적인 함의는 페이지 압축에 해당하지만, 이를 보장하기 위한 과정은 삭제 작업에서 시작됩니다.

행 삭제

슬롯 배열을 통해 행에 대한 접근을 추상화하면 삭제와 같은 특정 작업이 매우 간단해진다는 장점이 있습니다. 파일 시스템과 유사하게, 슬롯 페이지에서의 삭제는 실제 행 데이터를 건드릴 필요가 없습니다; 해당 행을 가리키는 슬롯을 무효화하면 그 행에 속한 바이트에 접근할 수 없게 되면 충분합니다.

내 구현에서는 슬롯을 무효화한다는 것은 offset과 length 필드를 모두 0으로 설정하고, 헤더에 있는 슬롯 개수는 그대로 두는 것을 의미합니다:

initial: [(96, 100), (196, 50), (246, 50)]
slot_count = 3

// delete slot index 1 (196, 50)
after:   [(96, 100), (0, 0), (246, 50)]
slot_count = 3

왜 이것이 안정적인 슬롯 번호 규칙을 만족하는가

• 슬롯을 배열에서 완전히 제거하고 slot_count를 감소시키면, 뒤에 있는 슬롯들을 모두 앞으로 이동시켜야 하므로 규칙이 깨집니다.
• 슬롯을 (0,0) 으로 설정하고 하지만 slot_count를 감소시키면, 마지막 유효 슬롯에 접근할 수 없게 됩니다.

따라서 이 규칙은 구현을 크게 단순화합니다. 삭제와 관련된 유일한 복잡한 부분은 내가 추가한 작은 최적화입니다: 삭제되는 행이 페이지의 물리적으로 마지막 행(즉, 데이터 섹션의 끝에 위치한 경우)이라면, free_start 포인터를 이전 행의 끝으로 이동시켜 페이지가 단편화되는 것을 방지할 수 있습니다. 이 “행복한 경우”에는 헤더의 can_compact 플래그가 설정되지 않으며, 이는 단편화가 시작되지 않았음을 나타냅니다.

Rust 구현에서는 이 최적화를 처음에 놓쳤습니다(다른 화면에 열려 있던 Java 버전에는 존재했습니다). 삽입 테스트를 설정하면서 누락을 깨달았습니다. 처음에는 이러한 시나리오를 “기술적으로는 가능하지만 유효하지 않다”고 표시했지만, 더 생각해 본 결과 이 최적화를 구현하면 실제로는 불가능함을 알게 되었습니다. 여기에서 내가 이를 불가능하다고 표시한 주석을 확인할 수 있습니다:
GitHub commit comment.

페이지 압축

페이지 압축은 페이지 내부의 레코드를 재배열하여 단편화를 제거하는 과정입니다. 모든 페이지는 행이 연속적인 바이트 청크를 차지하는 빽빽한 배열로 시작하지만, 삭제와 업데이트가 발생하면 행 사이에 작은 틈이 생길 수 있습니다. 그 결과 페이지의 자유 공간 카운터는 높게 표시될 수 있지만, 새 행을 넣을 만큼 충분히 연속된 공간이 없을 수도 있습니다.

압축은 기존 행들을 서로 옆에 붙여 이동시켜 모든 틈을 없애는 방식으로 작동합니다. 이는 일반적으로 지연(lazy) 방식으로 수행되며, 삽입 시 충분히 큰 조각을 찾지 못했을 때만 실행됩니다.

내 구현이 가장 최적이라고는 할 수 없지만 동작합니다. 새 바이트 배열을 할당하고, 행을 순서대로 복사한 뒤 슬롯 오프셋을 적절히 업데이트합니다. (나머지 구현은 위에서 설명한 안정적인 슬롯 번호 원칙을 그대로 따릅니다.)

데이터 압축 개요

데이터 세그먼트의 크기는 free_start - header_size 로 계산됩니다.
페이지를 압축하려면 다음을 수행합니다:

1. 슬롯 배열을 순회합니다.
2. 유효한 슬롯마다 해당 행을 새 바이트 배열에 복사하여 행을 연속적으로 배치합니다.
3. 슬롯의 오프셋 값을 행의 새로운 위치를 가리키도록 업데이트합니다.

모든 슬롯을 처리한 뒤 원본 데이터 세그먼트를 새 바이트 배열로 덮어씁니다. 남은 바이트(단편이 차지했던 만큼)는 0 으로 채워집니다.

참고: 더 정교한 제자리(in‑place) 알고리즘을 사용하면 최대 4 KB 크기의 임시 배열 할당을 피할 수 있지만, 해당 최적화는 나중에 “있으면 좋은” 수준에 해당합니다. 현재 구현은 가장 중요한 요구 사항을 만족합니다: 안정적인 슬롯 번호가 유지됩니다.

원래 Java 버전은 완전히 새로운 페이지를 할당하고, 유효한 슬롯만 복사한 뒤 페이지의 바이트 배열을 교체했습니다. 편리했지만 이 접근 방식은 안정적인 슬롯 규칙을 깨뜨렸으며, 이는 동료와 프로세스를 논의한 후 1년 뒤에야 발견한 실수였습니다. 따라서 위에서 설명한 대로 코드를 다시 작성했습니다.

마무리

이 글은 예상보다 길어졌지만, 기본적으로 여기까지가 전부입니다. 시작할 때 언급했듯이, 지난 몇 주 동안 진행이 더뎠지만, 이제 휴일이 끝났으니 상황이 나아질 것입니다.

또한 더 나은 테스트 인프라를 구축하고 있습니다. 제 목표는 코드를 작성하면서 바로 테스트를 추가하여 나중에 시나리오가 대량으로 쌓이는 것을 방지하는 것입니다. Rust의 기능을 활용해 어떤 테스트 시나리오든 손쉽게 설정할 수 있는 헬퍼를 만드는 방법을 탐구하고 있으며, 이는 추후 글에서 다룰 예정입니다.

제가 바쁘게 작업하고 있는 또 다른 영역은 삽입 알고리즘입니다. Java 구현이 꽤 무거웠기 때문에 이를 더 작은 단위로 나누고, 정리하며, 가능한 한 철저히 테스트를 입히고 있습니다.

다음 단계

• 힙 페이지와 관련된 작업 마무리
• 스토리지 엔진에 머물지(예: 인덱스 페이지와 B+‑트리) 다른 모듈로 옮길지 결정

저는 후자를 선호합니다. 이 과정은 언어 차이 때문이 아니라, Java DB 구현 세부 사항을 지속적으로 재검토하며 개선점과 부족한 부분을 찾아 고치고 있기 때문에 의도적으로 천천히 진행되고 있습니다. 모든 계층을 아우르는 작은 작동 프로토타입을 구축하면 향후 결정이 쉬워지고 MVP를 더 빨리 달성할 수 있습니다. 개인적인 목표로는 가능한 한 빨리 기능적인 프로토타입을 갖는 것이 좋겠습니다.

참고 문헌

• Delaney, K., Beauchemin, B., Cunningham, C., Kehayias, J., Freeman, C., Nevarez, B., & Randal, P. S. (2013). Microsoft SQL Server 2012 Internals. https://www.microsoftpressstore.com/store/microsoft-sql-server-2012-internals-9780735658561