내가 INSERT한 레코드는 어떤 구조로 파일에 저장될까?
운전을 하다 보면 가끔 엔진이나 미션 등이 어떻게 동작하는지 궁금할 때가 있다. 연료가 어떻게 엔진에 전달되는지, 엔진은 어떻게 연료를 연소하여 동력을 얻는지, 또 이를 미션에 전달하여 어떻게 차를 움직이게 하는지 등에 대해 말이다. CUBRID를 사용하는 사용자들도 가끔 이런 호기심이 생기지 않을까? 이런 호기심 많은 사용자를 위한 첫번째로 "사용자가 INSERT한 레코드는 어떤 구조로 파일에 저장될까?"란 주제로 이야기 해보려고 한다. 티타임을 이용해 가벼운 마음으로 읽을 수 있도록 작성하였으니 여유 시간에 재미로 읽을 수 있길 바래본다.
슬랏 페이지(slotted page) 구조
CUBRID도 OS나 다른 DBMS와 같이 성능상의 이유로 페이지(page) 단위 디스크 I/O를 수행한다. CUBRID 페이지 크기는 최소 4KB ~ 최대 16KB 이며, 디폴트로 16KB 디스크 페이지 크기를 사용한다. 슬랏 페이지 구조란 이런 페이지에 데이터 저장을 구조화하는 하나의 방식을 말한다. CUBRID 사용자가 INSERT 구문을 사용하여 데이터(레코드)를 입력하게 되면, 여러 처리를 거친 후 결국 디스크 페이지에 입력된 데이터가 쓰여지게 된다. 그럼 다음 4개의 INSERT를 수행해 보자.
- INSERT INTO t1(c1) VALUES ('aaa');
- INSERT INTO t1(c1) VALUES ('bbbbb');
- INSERT INTO t1(c1) VALUES ('cc');
- INSERT INTO t1(c1) VALUES ('dddddd');
위 4개의 INSERT 구문을 수행하게 되면 < 그림 1 >과 같이 쓰여지게 될까?
< 그림 1 >
데이터를 추가하였으니, SELECT 문을 이용해 데이터를 조회해 보도록 하자.
- SELECT * FROM t1 WHERE c1 = 'bbbbb';
< 그림 1 >의 페이지에서 어떻게 'bbbbb'를 찾을 수 있을까? 즉, 페이지 내 어느 위치에서 얼마나 읽어야 'bbbbb'를 찾아낼 수 있을까? 정답은 '알 수 없다' 이다. 페이지 내에서 원하는 데이터를 찾기 위해서는 추가적인 정보를 필요로 하며, 이런 정보를 저장하고 있는 것이 데이터 헤더(data header) 이다. < 그림 2 >를 보면 각 데이터의 앞에 데이터 길이 정보를 가지는 데이터 헤더를 포함시켰다. 이제 우리는 'bbbbb'의 위치를 찾을 수 있게 되었다. 페이지의 시작에서 '데이터 헤더 크기' + 'aaa 길이(3)' = 'bbbbb 데이터 시작 위치' 이다. 같은 방식으로 'cc', 'dddddd' 역시 쉽게 찾을 수 있음을 알 수 있다.
< 그림 2 >
이번에는 데이터 'cc'를 삭제해 보자.
- DELETE FROM t1 WHERE c1 = 'cc';
우선 'cc'를 삭제하기 위해서는 'cc'의 위치를 찾아야 한다. 'cc'의 위치는 데이터 헤더에 기록된 데이터 길이 정보를 이용하여 쉽게 찾을 수 있다. 이제 어떻게 지울까? 'cc'를 '\0'로 덮어쓰면 될까? 데이터 길이 정보를 0으로 바꾸면 될까? < 그림 3 >은 데이터 삭제 시 'cc'를 '\0'로 덮어 쓴 후 데이터 길이 정보를 0으로 바꾼 경우를 나타낸다.
< 그림 3 >
여기서 문제. 'dddddd'는 어떻게 찾을까? 'cc'의 길이 정보 2를 이용해야 'dddddd'의 위치를 찾을 수 있었다. 그럼 데이터 길이 정보는 기존 2로 나두면 해결될까? SELECT * FROM t1 WHERE c1 != 'cc' 수행 시 우선 데이터 길이가 2이기 때문에 삭제 여부를 알 수 없다. 그럼 데이터 삭제 여부 확인을 위해 데이터를 읽을 때마다 첫 바이트가 '\0' 인지 확인해야 한다. 데이터가 천만건이라면? '\0' 자체가 데이터라면? 따라서, 데이터 헤더에 삭제 여부를 나타내는 필드를 추가해서 데이터가 삭제되었다는 표시를 한다. < 그림 4 >를 보면 삭제 플래그를 두어 'cc'가 삭제되었음을 나타내고 있다. 그럼 데이터 헤더 확인을 통해 데이터가 삭제되었는지 여부를 알 수 있다.
< 그림 4 >
여기서 우리는 한가지 문제를 더 생각해 보아야 한다. 바로 페이지 내 데이터 찾기 '효율성' 이다. 첫번째 데이터 'aaa'는 한번에 찾을 수 있다. 두번째 데이터인 'bbbbb'의 경우 반드시 'aaa' 헤더의 데이터 길이 정보를 이용해야 찾을 수 있다. 그럼 'cc' 는? 앞 2개 데이터 헤더 정보를 이용해야 한다. 그럼 마지막에 추가된 데이터의 경우 거의 모든 헤더 정보를 다 읽어야만 데이터를 찾을 수 있게 된다. 매우 비효율적이다. 그럼 데이터 헤더에 데이터 위치 정보를 나타내는 오프셋을 추가한 후 데이터 헤더를 별도로 분리해보면 어떨까? 보통 쉽게 생각할 수 있는 방법은 페이지 헤더를 만들고 여기에 데이터 헤더를 기록하는 것이다. < 그림 5 >를 보면 페이지 헤더에 데이터 헤더 6개를 담을 수 있는 배열이 있고, 각 데이터 헤더에는 오프셋 정보가 추가되었다. 찾을 데이터에 매핑되는 데이터 헤더 배열의 인덱스만 있으면, 오프셋을 이용하여 같은 시간 안에 페이지 내 모든 데이터를 찾을 수 있다. 이를 통해 페이지 내 데이터 찾기 문제를 해결할 수 있다.
< 그림 5 >
그럼 2개의 데이터를 더 입력해 보자.
- INSERT INTO t1(c1) VALUES ('e');
- INSERT INTO t1(c1) VALUES ('ff');
< 그림 6 >을 보면, 데이터 헤더 배열 크기가 6이기 때문에 페이지에 충분한 여유 공간이 남아 있음에도 불구하고 더이상의 데이터를 추가할 수 없음을 알 수 있다. 그럼 데이터 헤더 배열 크기를 늘이면 해결될까? 정답은 '아니다' 이다. 페이지에 버려진 여유 공간의 크기는 쓰여지는 데이터의 크기에 따라 달라질 것이다. 따라서, 모든 데이터 헤더를 사용한 후에도 페이지 내 공간이 남는다거나 반대로, 데이터 헤더 배열을 100% 사용하지 못하는 경우가 발생할 수 있다. 이는 곧 페이지 공간 낭비에 해당한다. 우리는 디스크 I/O 효율성을 위해 페이지 단위로 I/O를 수행하지만, 페이지 공간을 효율적으로 사용하지 못할 경우 이는 곧 불필요한 I/O를 발생시키는 원인이 될 것이다.
< 그림 6 >
이런 문제를 해결할 수 있는 방법 중 하나가 슬랏 페이지 구조이다. 여기서 슬랏(slot) 이란 곧 데이터 헤더이다. < 그림 7 >은 슬랏 페이지 구조를 나타낸다. 페이지 헤더에 위치하던 데이터 헤더가 페이지 끝으로 이동했다. 페이지 헤더에는 현재 페이지에 몇 개의 데이터 헤더가 있는지를 나타내는 정보 등이 기록된다. 이 페이지 구조에서 데이터는 기존처럼 페이지 시작에서 끝 방향으로 추가된다. 반면 데이터 헤더는 페이지 끝에서 페이지 시작 방향으로 추가된다. 새로운 데이터 추가 시 데이터 길이에 따라 발생하던 페이지 공간 사용 효율성 문제는 더이상 발생하지 않는다.
< 그림 7 >
지금까지 "사용자가 INSERT한 레코드는 어떤 구조로 파일에 저장될까?"란 주제로 이야기 했으며, 결론은 '슬랏 페이지 구조로 저장된다' 이다. CUBRID 뿐 아니라 많은 DBMS들이 슬랏 페이지 구조를 사용하고 있으며, 이에 대한 이해를 위해 개념적인 관점에서 이야기 하였다. 실제로, 얼라인먼트(alignment), 단편화(fragmentation) 처리, 인/아웃-플레이스 갱신 등 다양한 이야기 거리가 있지만 이는 다음 기회를 기약하며, 이만 마치도록 한다.