RCFile의 과거, 현재, 그리고 미래

RCFile은 하둡 데이터 처리 환경에서 널리 사용되는 파일 포맷입니다. RCFile은 2011년 ICDE 컨퍼런스 (IEEE International Conference on Data Engineering) 에서 “RCFile: A Fast and Space-efficient Data Placement Structure in MapReduce-based Warehouse Systems” 논문으로 처음 공개되었습니다. 당시 페이스북에서는 매일 20TB의 데이터가 발생하고 있었는데, 이 데이터를 고속으로 HDFS에 저장하고 임의의 쿼리를 효율적으로 실행하도록 설계하는 것이 중요한 문제였습니다.

하둡 생태계의 다양한 오픈소스 프로젝트들을 살펴보면, 이미 데이터베이스 분야에서 해결된 문제들을 분산시스템 기반으로 다시 구현하는 사례들을 많이 볼 수 있는데, 이 RCFile도 마찬가지로 과거 데이터베이스 연구의 역사를 좀 알아볼 필요가 있습니다.

컬럼지향 DBMS의 등장

오라클을 비롯하여 잘 알려진 대다수의 데이터베이스 관리 시스템들은 디스크 영역을 페이지 단위로 나누어 레코드를 저장하고 슬롯으로 구분된 페이지 구조 (Slotted Page)를 사용합니다. 하나의 레코드는 다수의 필드로 구성되는데, 조금이라도 빠른 데이터 액세스를 위해서 고정 길이 필드는 앞쪽으로, 가변길이 필드는 뒤쪽으로 배열하고, 가변길이 필드의 오프셋은 페이지 끝부분에 거꾸로 기록합니다. 이런 페이지 레이아웃을 N개의 인자를 가진 페이지라 해서 N-ary Storage Model, NSM이라 부르기도 합니다.

PAX 논문의 NSM 예시

문제는 이러한 레이아웃이 대용량 데이터 분석 쿼리에 적합한 형태가 아니라는 것입니다. 페이지 단위의 디스크 접근 및 캐시 관리 체계에서는 분석 쿼리가 일부 컬럼만 요구하는 경우에도 불필요하게 레코드 전체 데이터를 메모리에 올려야 했으며, 메모리 내에서도 오프셋을 참조하여 데이터 영역에 접근하느라 많은 CPU 사이클을 소모하고 캐시 미스가 발생합니다. 이 때문에 아예 릴레이션을 속성(Attribute) 단위로 쪼개서 데이터를 저장하는 모델이 제안됩니다.

이 모델은 앞에서 제시한 NSM과 달리 속성 단위로 물리적 배치를 수행하기 때문에 Decomposition Storage Model, DSM이라 불리게 됩니다. DSM 모델은 동일한 속성을 물리적으로 인접하게 배치하므로 디스크 I/O, 캐시 측면에서 NSM 모델에 비해 우월한 모습을 보입니다. 뿐만 아니라 같은 타입과 길이를 가진 데이터가 공간적으로 밀집되기 때문에, 압축 효율도 증가합니다.

하지만 모든 속성을 물리적으로 분리하면서 튜플 식별자를 속성 개수만큼 중복해서 저장해야 하는 오버헤드가 발생하고, 속성을 여러 개 조회하는 쿼리에 대해서는 조인을 수행해야 하기 때문에 더 느려지게 됩니다. 이를 극복하기 위해 물리적 설계 단계에서 쿼리 패턴을 고려한 컬럼 그룹 (혹은 컬럼 패밀리) 단위의 파티셔닝을 수행하는 방식이 제안되기도 합니다.

상업적으로는 1995년 Sybase IQ가 컬럼지향 DBMS를 출시하였고, 지금도 잘 알려진 버티카(Vertica), 벡터와이즈 (VectorWise) 데이터베이스가 이런 흐름 속에서 개발되었습니다.

NSM과 DSM의 조합, PAX의 등장

이 상황에서 만약 양쪽의 장점만 뽑아낼 수 있다면, 기존의 어떤 시스템보다 전반적으로 나은 성능 특징을 가진 모델이 만들어 질 수 있습니다. DSM 모델은 물리적으로 페이지를 속성 단위로 쪼개서 성능을 극대화하지만, 사실 페이지 내부의 데이터 배열만 컬럼 단위로 바꿔도 그에 가까운 성능 향상 효과를 얻을 수 있습니다. 그렇게 제안된 것이 바로 Partition Attributes Across, PAX 모델입니다.

위의 그림처럼 같은 속성끼리 모아서 페이지 안에 미니 페이지를 구성하면, 튜플 전체를 조회해야 하는 경우에도 별도의 조인 비용 없이 간단히 조립할 수 있습니다. 속성 단위로 값이 연속되어 있기 때문에, 캐시 역시 효율적으로 활용할 수 있게 됩니다.

RCFile의 등장

하둡 분산파일시스템과 맵리듀스 프레임워크에 기반한 HIVE를 개발하고 운영하면서, 많은 사람들이 어떻게 하면 HIVE에 데이터를 더 빠르게 적재하고 쿼리를 고속으로 실행할 수 있을지 고민하기 시작합니다. RCFile의 설계 목표는 아래와 같았습니다:

  1. 빠른 데이터 적재
  2. 빠른 쿼리 수행
  3. 효율적인 디스크 활용
  4. 동적인 부하 시나리오에 대응

RCFile 개발자들은 기존의 NSM, DSM, PAX 모델을 검토하였고, PAX를 개선한 데이터 레이아웃을 만들기로 결심합니다. 그들이 생각한 NSM, DSM, PAX의 단점은 아래와 같이 요약됩니다:

  1. NSM: 데이터 적재는 빠르게 할 수 있으나, 쿼리가 느리고 압축에 불리함.
  2. DSM: HDFS 환경에서는 물리적으로 같은 데이터 노드에 서브-릴레이션이 저장되리란 보장이 없기 때문에, DSM 모델은 쿼리에 따라 심각한 성능 저하를 유발할 수 있음.
  3. PAX: 고정 길이 페이지로 설계되어 불필요하게 공간을 낭비함. 하지만 데이터 적재도 빠르고, 쿼리도 고속으로 수행할 수 있으므로, 가변 레이아웃으로 바꾸고 압축을 추가하면 되겠음.

RCFile의 구조

RCFile은 크게 파일 헤더와 데이터 블록으로 구분할 수 있습니다. 논문에서는 각 데이터 블록을 Row Group 으로 지칭합니다.

파일 헤더의 구조

이 그림에서 점선으로 표시된 항목은 선행 조건에 따라 선택적으로 삽입되는 부분입니다.

파일 헤더는 아래와 같이 구성됩니다:

  • 매직 스트링 (3바이트): 파일 타입을 구분하도록 “RCF”가 아스키 문자열로 입력됩니다. 초기 파일 포맷에서 “SEQ”가 사용된 적이 있습니다.
  • 버전 (1바이트): 향후 파일 구조가 변경될 경우를 대비하여 버전을 표시합니다. 0x1을 사용합니다.
  • 압축 여부 (1바이트): 바이트가 0x1인 경우, 코덱 클래스 이름 문자열이 이어집니다.
  • 압축 코덱 (가변 길이): 가변 정수 인코딩으로 된 문자열 길이에 이어 UTF-8로 인코딩된 클래스 이름이 배치됩니다.
  • 메타데이터 (가변 길이): 최초 4바이트는 메타데이터 키/값 쌍의 개수를 의미합니다. 이후 해당 개수만큼 키 문자열과 값 문자열이 반복됩니다. 각 문자열은 압축 코덱과 마찬가지로 가변 정수 인코딩으로 된 문자열 길이에 이어 문자열 값이 배치됩니다. HIVE에서 저장한 경우 hive.io.rcfile.column.number 키로 컬럼 개수가 저장됩니다.
  • 싱크 마커 (16바이트): 난수 값으로 데이터 블록 간 경계를 구분하는 역할을 합니다. 데이터 블록은 길이 4바이트로 시작하는데, 만약 싱크 마커가 삽입된다면 길이를 0xFFFFFFFF로 써서 구분합니다.

아래는 실제 RCFile의 파일 헤더를 덤프한 것입니다. 매직 스트링 (빨강), 버전 (노랑), 압축 여부 (연두색), 메타데이터 (하늘색), 싱크 마커 (보라색) 각 영역의 값을 확인할 수 있습니다.

데이터 블록의 구조

데이터 블록의 배치는 다음과 같습니다:

  • 데이터 블록 길이 (4바이트): 초기 12바이트 헤더를 제외한 블록 길이를 저장합니다.
  • 원본 헤더 블록 길이 (4바이트): 헤더 블록 압축을 풀었을 때의 바이트 길이입니다.
  • 압축 헤더 블록 길이 (4바이트): 헤더 블록이 압축된 상태의 바이트 길이입니다.
  • 헤더 블록 — 튜플 개수 (가변 정수): 튜플 개수는 컬럼 값 배열의 길이이기도 합니다.
  • 헤더 블록 — 값 블록 헤더: 값 블록에 대한 메타 정보를 저장합니다.
    * 압축된 값 블록 길이
    * 원본 값 블록 길이: 압축을 풀었을 때 값 블록의 길이를 저장합니다.
    * 값 길이 블록의 크기: 뒤에 이어지는 값 길이 배열의 바이트 크기를 저장합니다.
    * 값 길이 배열: 값 블록 영역에서 값을 하나씩 읽어들일 때 필요한 개별 값의 바이트 길이를 저장합니다.
  • 값 블록: 각 컬럼의 타입에 맞춰 인코딩된 값 배열을 저장합니다. 파일 헤더에 압축이 지정되었다면, 값 배열을 압축하여 저장합니다.

아래는 실제 RCFile의 데이터 블록을 덤프한 것입니다. 데이터 블록 길이 (빨강), 원본 헤더 블록 길이 (노랑), 압축된 헤더 블록 길이 (연두색), 튜플 개수 (하늘색), 값 헤더 (보라색) 영역을 확인할 수 있습니다. 이 파일은 비압축 모드였기 때문에 원본 헤더 블록 길이와 압축된 헤더 블록 길이가 동일하고, 비압축 상태이므로 쉽게 원본 데이터를 눈으로 확인할 수 있습니다.

컬럼 단위로 데이터를 저장하면, 길이가 유사할 가능성이 높기 때문에, RCFile은 길이 배열을 인코딩할 때 RLE (Run-Length Encoding) 압축을 시도합니다. 길이는 음수 값이 없으므로 값이 음수이면 반복 횟수로 취급합니다. 예를 들어, 길이 배열 값이 3, -4 이면 3, 3, 3, 3으로 해석됩니다.

RCFile의 가변 정수 인코딩은 일반적으로 알려진 VByte 인코딩 방식과 약간 다릅니다. VByte 인코딩이 MSB 1비트를 시그널 비트로 사용하는 반면, RCFile의 VInt 인코딩은 MSB 4비트가 1000으로 시작하는 경우 LSB 3비트를 추가로 읽어야 할 길이로 인식합니다. 즉, -128 (1000 0000) 부터 -113 (1000 1111) 범위에서 하위 비트를 길이로 인식하는 것입니다. 이는 가장 흔한 길이 값에 대해 인코딩/디코딩을 빠르게 하는 효과가 있습니다.

RCFile은 각 컬럼 값 블록을 압축하고, 최대한 게으르게 압축을 해제하여 불필요한 압축 해제에 CPU 사이클을 낭비하지 않으려고 노력합니다. 예를 들어, HIVE에서 쿼리 시 WHERE 구문으로 필터링 조건이 스토리지 엔진으로 푸시 다운되는 경우, 조건식에 있는 컬럼 값을 먼저 풀어서 평가하고, 값이 조건에 불일치한다면 SELECT 할 컬럼들의 압축을 해제하지 않습니다.

RCFile의 미래

RCFile은 PAX 모델을 개선하여 앞에 언급했던 4개의 목표를 달성했으나, 이후 아파치 커뮤니티에서는 HIVE 쿼리를 더 가속하기 위해 데이터 블록별 인라인 인덱스와 기본 통계, 타입별로 최적화된 데이터 직렬화, 딕셔너리를 통한 문자열 압축 향상 등을 추가한 ORCFile (Optimized Row Columnar)을 개발하게 됩니다. 이는 이 글의 범위를 벗어나므로 다음을 기약하겠습니다.

레퍼런스

  • Stonebraker; et al. (2005). “C-Store: A column-oriented DBMS” (PDF). Proceedings of the 31st VLDB Conference. Trondheim, Norway.
  • A. Ailamaki, D. J. DeWitt, M. D. Hill, and M. Skounakis, “Weaving relations for cache performance,” in VLDB, 2001, pp. 169–180.
  • Yongqiang He, Rubao Lee, Yin Huai, Zheng Shao, Namit Jain, Xiaodong Zhang, Zhiwei Xu, “RCFile: A Fast and Space-efficient Data Placement Structure in MapReduce-based Warehouse Systems”, Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2011
Like what you read? Give Logpresso a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.