Parquet 해부

열 기반 데이터 구조

행 4개짜리 작은 표가 있다.

이 표를 파일로 저장한다고 하자. 파일은 결국 바이트가 한 줄로 늘어선 것이라, 2차원 표를 집어넣으려면 눕히는 순서부터 정해야 한다.

CSV는 행부터 눕힌다. 1, 김, OK 다음에 2, 이, OK가 온다. 유저 한 명의 정보가 한 자리에 모여 있으니, 한 건을 통째로 읽고 쓰는 서비스 DB에는 이 배치가 맞다. Parquet은 열부터 눕힌다. user_id 넷이 먼저 오고 이름 넷, status 넷이 뒤따른다.

같은 표가 두 순서로 파일에 늘어서는 모습은 이렇다.

왜 이렇게 하는 걸까. status별 실패율을 집계한다고 하자. 행 지향 파일에서 status는 세 칸에 한 번씩 나와서 필요한 건 status뿐인데 user_id와 name까지 같이 끌려온다. 열 지향이라면 status 블록 하나만 읽으면 된다. 분석 쿼리는 대개 행은 많이 건드리고 열은 몇 개만 건드린다. 분석 쪽 포맷이 열 지향으로 수렴한 이유다.

압축에서도 차이가 난다. 같은 열에는 같은 타입의 비슷한 값이 모인다. OK가 세 번 연달아 나오면 셋을 묶어 적을 수 있고, 값의 종류가 적으면 사전을 만들어 번호로 대신 적을 수 있다. 숫자와 이름과 상태가 번갈아 나오는 행 지향에서는 이런 기회가 잘 없다.

파일 구조

Parquet은 열끼리 모으되, 표 전체를 한 번에 모으지는 않는다. 먼저 행을 덩어리(row group)로 자르고 덩어리 안에서만 열끼리 모은다. 행이 수백만 개면 덩어리도 여러 개가 된다.

파일의 물리적인 순서는 쓰는 순서 그대로다. 매직넘버 PAR1 네 바이트로 시작해 덩어리들이 차례로 쌓인다. 덩어리 안에는 열마다 청크(column chunk)가 하나씩 있고 청크는 다시 페이지(page)로 잘린다. 페이지 앞에는 이 페이지가 몇 바이트인지, 값이 몇 개인지 적은 머리말(page header)이 붙는다.

쓰는 순서를 따라가면 파일이 이렇게 조립된다.

단위가 셋이라 헷갈리는데, 자르는 기준이 다 다르다. 덩어리는 행 방향으로 자른다. 청크는 자르는 것이 아니라 덩어리와 열이 교차하는 자리마다 저절로 생긴다. 페이지는 크기로 자른다. 값을 쌓다가 인코딩된 크기가 임계값에 차면 페이지를 닫고 다음 페이지를 여는 식이라, 논리적인 경계가 아니라 양의 경계다. 쓰임도 다르다. 건너뛰기는 덩어리 단위로, I/O는 청크 단위로, 압축과 인코딩은 페이지 단위로 움직인다.

세 단위를 한 장에 겹쳐 보면 이렇다.

본문을 다 쓰고 나면 꼬리를 붙인다. 페이지 색인과 블룸 필터 같은 부가 색인이 먼저 오고 마지막이 목차(footer)다. 목차에는 스키마와 함께 덩어리마다 각 컬럼 청크가 몇 바이트부터 몇 바이트까지인지, 그 안에 어떤 범위의 값이 들었는지(min/max)가 적힌다. 목차 길이 4바이트와 PAR1로 파일이 끝난다.

색인이 덩어리 사이에 끼어 있지 않은 것은 쓰는 방식 때문이다. 덩어리의 위치와 통계는 그 덩어리를 다 쓰고 나서야 알 수 있다. 그래서 쓰는 쪽은 앞으로 돌아가지 않고 한 번에 흘려 쓰고, 전부 알게 된 맨 끝에 목차를 붙인다. 읽는 쪽도 색인이 한 곳에 모여 있어야 꼬리 한 번 읽고 파일 전체의 지도를 얻는다.

덩어리 건너뛰기

목차를 읽고 나면 엔진은 어떤 덩어리를 읽을지부터 고른다. user_id = 42인 행을 찾는다고 하자. 목차에는 덩어리별 user_id의 min/max가 적혀 있다. 데이터가 user_id로 정렬돼 쌓였다면 덩어리 1은 1~25, 덩어리 2는 26~50, 덩어리 3은 51~99처럼 범위가 갈리고, 42가 있을 수 있는 곳은 덩어리 2뿐이다. 나머지는 열어보지도 않는다. 여기까지 본문은 한 바이트도 읽지 않았다. 목차만 읽고 내린 결정이다.

목차를 펼쳐 42를 고르기까지의 과정이다.

이 건너뛰기의 전제는 덩어리끼리 min/max가 갈린다는 것이다. 갈리려면 그 열로 정렬돼 있어야 한다. 시간순으로 쌓인 파일에서 user_id를 찾으면 덩어리마다 min 1, max 99로 거의 같은 범위가 나온다. 42는 어느 덩어리에나 있을 수 있고 하나도 거를 수 없다.

정렬로 해결하려 해도 축은 하나뿐이다. user_id로 정렬하면 user_id의 min/max는 갈리지만 message_id 같은 다른 열은 다시 겹친다. min/max로 못 거르는 열이 반드시 남는다. Parquet이 덩어리마다 블룸 필터를 준비해 둔 이유가 이것인데, 블룸 필터가 무엇인지부터 보자.

블룸 필터

블룸 필터는 집합이다. 값을 넣어 두고 나중에 “이 값 있어?”라고 묻는 용도인데, 답이 특이하다. 확실히 없다와 있을 수도 있다 둘 중 하나로만 답한다. “확실히 있다”는 못 한다.

생김새는 단순하다. 0으로 초기화된 비트 배열 하나와 해시 함수 몇 개가 전부다. 배열이 12칸이고 해시가 3개라고 하자.

삽입은 이렇다. “alice”를 넣으면 해시 3개가 각자 자리 하나씩을 내놓는다. 2, 5, 9가 나왔다면 그 세 칸을 1로 켠다. “bob”을 넣어 4, 5, 11이 나오면 마찬가지로 켠다. 5는 이미 켜져 있는데 그대로 둔다. 누가 켰는지는 기록하지 않는다.

조회는 같은 해시를 다시 돌린다. “carol”을 물었더니 4, 7, 9가 나왔다. 7번 칸이 0이다. carol을 넣은 적이 있다면 7번은 반드시 켜져 있어야 하므로, 이 순간 답은 확실히 없다로 끝난다. 나머지 칸은 볼 필요도 없다.

문제는 반대 경우다. “dave”를 물었더니 2, 4, 11이 나왔다. 셋 다 1이다. 그런데 이 세 칸은 alice와 bob이 켜 놓은 자리다. dave는 넣은 적이 없는데 답은 “있을 수도 있다”가 나온다. 이것이 거짓 양성(false positive)이다. 다른 값들이 켜 놓은 자리를 우연히 전부 밟으면 생긴다. 반대 방향의 오답은 없다. 넣은 값이라면 그 자리들이 전부 켜져 있을 수밖에 없어서, 없다는 답은 언제나 맞다.

삽입 둘과 조회 둘을 그대로 재생하면 이렇다.

이상한 자료구조처럼 보이지만 대가로 얻는 것이 크기다. 블룸 필터는 값 자체를 저장하지 않는다. 어느 칸이 켜졌는지만 남는다. 값이 수백만 개라도 비트 배열은 미리 정한 크기 그대로이고, 배열을 키우고 해시를 늘릴수록 거짓 양성 확률이 내려간다. 오답률 1%짜리 필터는 값 하나당 10비트 정도면 된다. 값을 전부 담는 인덱스와는 자릿수가 다르다.

배열이 차오르면 무슨 일이 생기는지 보자.

지우기가 안 된다는 성질도 있다. 어떤 칸을 0으로 되돌리면 그 칸을 같이 쓰던 다른 값까지 망가진다. 그래서 블룸 필터는 한 번 만들고 다시 안 고치는 곳에 어울린다. 한 번 쓰면 바뀌지 않는 Parquet 파일에는 정확히 맞는 조건이다.

Parquet과 블룸 필터

Parquet은 덩어리마다 블룸 필터를 하나씩 만들 수 있다. 그 덩어리에 든 열의 값을 전부 넣은 필터다. 만들어진 필터는 부가 색인으로 파일 꼬리 쪽에 저장되고 위치는 목차가 가리킨다.

message_id = 'M-42'를 찾는다고 하자. message_id는 정렬 축이 아니라서 덩어리마다 min/max가 겹치고 목차만으로는 하나도 거를 수 없다. 대신 엔진은 M-42를 해시해서 덩어리 네 개의 블룸 필터에 같은 질문을 던진다. 셋에서 “확실히 없음”이 나오면 그 셋은 본문을 열지 않고 건너뛴다. “있을 수 있음”이 나온 하나만 읽는다.

네 덩어리에 같은 질문을 던지는 장면이다.

거짓 양성이 나면 어떻게 될까. 없는데 “있을 수 있음”이 나온 덩어리를 하나 더 읽게 될 뿐이다. 읽어 보고 없으면 그만이라 결과는 틀리지 않고 낭비도 오답률만큼만 생긴다. 중요한 것은 반대 방향이 보장된다는 점이다. 건너뛴 덩어리에 값이 있었다면 결과가 틀리는데, 블룸 필터의 “없다”는 언제나 맞으니 건너뛰기는 안전하다. 확실히 있다는 못 해도 확실히 없다는 하는 자료구조가 건너뛰기라는 용도에 정확히 맞는다.

꼬리부터 읽기

어느 덩어리의 어느 청크를 읽을지는 정해졌다. 남은 문제는 가져오기다. 파일이 로컬 디스크에 있다면 원하는 위치로 이동해 읽으면 되지만 S3는 파일 시스템이 아니라 HTTP로 객체를 주고받는 저장소다. 기본 동작에서는 GET 한 번에 객체 전체가 넘어온다.

조각만 받는 방법이 HTTP에 이미 있다. 요청에 Range: bytes=1000-1199처럼 바이트 구간을 적으면 서버는 206 Partial Content로 딱 그 구간만 잘라 보낸다. S3도 이 헤더를 그대로 지원한다.

주소를 적어 조각만 받는 과정은 이렇다.

엔진이 S3의 Parquet 파일 하나를 조회하는 과정을 처음부터 이어 보면 이렇다. 파일 끝 쪽을 Range로 받아 목차를 읽는다. min/max와 블룸 필터로 읽을 덩어리를 고른다. 목차에 적힌 바이트 위치로 필요한 청크만 다시 Range로 받는다. 100MB짜리 파일이라도 실제로 넘어오는 것은 목차와 청크 몇 개, 몇 MB다. 파일을 통째로 내려받는 일은 처음부터 끝까지 한 번도 없다.

정리

Parquet의 설계는 전부 덜 읽기 위한 것이다. 열끼리 모아서 필요한 열만 읽고, 덩어리로 잘라서 필요한 덩어리만 읽고, 페이지로 잘라서 필요한 페이지만 푼다. 어디를 읽을지는 꼬리의 목차가 알려주고, min/max가 못 거르는 열은 블룸 필터가 거른다. 파일이 S3에 있어도 Range가 그 조각만 집어온다. JSONL과의 비교는 다음 글에서 한다.