목차
Under the hood, BigQuery employs a vast set of multi-tenant services driven by low-level Google infrastructure technologies like Dremel, Colossus, Jupiter and Borg.
- Google Cloud Blog 발췌
여러분들은 빅쿼리가 여러 첨단(?) 기술들로 이루어진 구글 기술의 총집합체라는 사실을 알고 계셨나요?
저는 꽤나 오랫동안 Bigquery를 애용하고 있는데요. 문득 자칭 Bigquery 매니아라면서 작동 원리도 모르고 쓰는 것이 굉장히 무례하다는 생각이 들었습니다.
그렇게 개인적인 호기심+리스펙으로 빅쿼리의 내부 아키텍처를 리서치해보았습니다.
Dremel: 논문으로 알아보는 Bigquery 컴퓨팅 핵심
위에서 언급했지만 빅쿼리는 여러 기술들이 사용되었습니다. 그 중 빅쿼리 서버리스 아키텍처의 핵심 포인트는 스토리지와 컴퓨팅이라고 볼 수 있는데요. 빅쿼리는 이 둘을 디커플링하여 독립적으로 유연하게 관리할 수 있다는 장점이 있습니다.
이번 포스팅에서 알아볼 부분은 빅쿼리의 컴퓨팅 아키텍처입니다. 이를 위해서는 Dremel(드레멜)이라고 하는 기술에 대해서 알아야 합니다. 드레멜 아키텍처에 대해서는 오늘 살펴볼 드레멜 논문인 Dremel: Interactive Analysis of Web-Scale Datasets에 아주 자세하게 나와있었습니다. 그래서 이 글에서도 해당 논문의 중요 내용들을 따라가며 천천히 아키텍처를 뜯어보려고 합니다.
물론 저의 첫 논문 리뷰(?)인지라 많은 부분에서 해석을 실수할 수 있어 이 부분은 혹시 틀렸다 싶으시면 댓글로 피드백 주시면 감사드리겠습니다
본격적으로 글을 시작하기에 앞서 글의 전개방식에 대해 알려드리려고 합니다. 앞서 언급한 것처럼 이 글은 드레멜 논문을 기반으로 전개될 예정입니다. 따라서 구성 또한 논문 목차를 따라갈 예정입니다. 하지만 논문의 전체 내용을 모두 다루지는 않고 중요한 부분만 발췌하였고, 이해가 어렵다고 생각되는 부분은 저의 개인적인 설명을 곁들었습니다.
ABSTRACT
드레멜은 read-only nested 데이터 분석을 위한 scalable하면서 interactive한 애드혹 쿼리 시스템입니다. 드레멜은 멀티 레벨의 실행 트리와 컬럼형 데이터 레이아웃의 조합을 통해 수조개 이상의 데이터를 단 몇초 안에 처리할 수 있습니다.
밑에서 자세하게 알아보겠지만 드레멜은 쿼리를 실행 트리로 만들어 병렬로 분산처리할 수 있도록 쿼리를 쪼개어 이를 트리의 리프 노드로 전달합니다.
참고로 빅쿼리를 사용하면 한 번쯤은 들어본 슬롯이라는 개념이 바로 실행 트리의 리프들을 의미합니다. 드레멜은 필요에 따라 쿼리를 동적으로 슬롯에 배정하여 효율적으로 처리할 수 있는 구조를 가지고 있습니다.
이 논문에서는 드레멜의 아키텍처와 구현, 그리고 어떻게 이것이 MapReduce(MR) 기반의 컴퓨팅을 보완하는지 설명합니다. 또한 nested 레코드와 열기반 스토리지의 표상을 제시하고, 수천 개의 노드 실험에 대해서도 다룹니다.
1. INTRODUCTION
드레멜은 기본적으로 실행할 때 MR 작동방식을 사용하고 있습니다. 하지만 그렇다고 드레멜이 MR의 대체제는 아닌데요. 드레멜은 구글에서 2006년부터 사용했고, 굉장히 다양한 영역에서 활용되어 왔습니다.
•
크롤링된 웹 문서 분석
•
안드로이드 앱 설치 데이터 트래킹
•
스팸 분석
•
구글 분산 빌드 시스템에서 실행된 테스트에 대한 결과
•
…
드레멜의 아이디어는 웹 검색과 병렬 DBMS로부터 왔습니다.
1.
트리 컨셉의 아키텍처를 가지고 있음. 트리의 가장 아래에서부터 실행되어 합쳐지는 방식.
2.
고수준 언어를 제공함. Pig, Hive와 다르게 MR Job으로 번역될 필요없이 SQL로 처리.
3.
열 기반 스토리지를 사용하여 보조기억장치로부터 데이터를 효율적으로 읽을 수 있고, 압축되어 있어 CPU 비용도 적게 듦.
2. BACKGROUND
앨리스라는 구글의 엔지니어가 있다고 가정해보겠습니다. 그녀는 어떤 데이터를 알고 싶어서 쿼리를 만들어서 드레멜을 통해 실행을 합니다. 이 후 결과를 공유하기 위해 파이프라인을 만들어 이 쿼리가 지속적으로 실행될 수 있게끔하고, 대시보드까지 만들었습니다. 또 다른 엔지니어들이 빠르게 쿼리를 활용할 수 있도록 카탈로그에도 등록을 합니다.
이 모든 과정에는 쿼리 프로세서와 데이터 매니지먼트 도구가 있어야 합니다.
1.
common storage layer(GFS): 데이터를 안전하게 저장하고, 빠르게 쿼리할 수 있음. DBMS에서는 하나의 쿼리를 수행할 시간에 수십 개의 쿼리를 실행할 수 있음. 그 밖에도 데이터를 다른 클러스터로 옮기거나 엑세스 권한을 설정하는 등의 추가적인 장점도 있음.
2.
shared storage format: nested된 데이터 모델에도 동작해야 했고, 열 기반 스토리지에서 nested 필드의 모든 값들은 연속적으로 저장되기 때문에 다른 필드랑 상관없이 읽어올 수가 있음.
아래 그림을 통해 쉽게 살펴볼 수 있는데, 행 기반 스토리지에서는 A.B.C라는 nested된 데이터를 가져오려면 다른 관계없는 데이터인 A.E와 A.B.E 또한 읽어와야 하는데 열 기반 스토리지에서는 원하는 필드만 읽어올 수가 있습니다.
3. DATA MODEL
논문에서 다룰 데이터 모델을 소개하겠습니다. 구조가 크게 어렵지는 않기 때문에 구조에 대해서 자세하게 설명하지는 않도록 하겠습니다.
4. NESTED COLUMNAR STORAGE
4.1 Repetition and Definition Levels
값 하나만으로는 레코드 형태의 데이터를 전달할 수가 없습니다. 반복되는 두 개의 값이 있을 때 우리는 이 두개의 값이 같은 레코드에 속해있는지 아닌지와 같은 “레벨”을 파악할 수가 없고, 마찬가지로 만약 optional한 필드라면 값이 비어있는지 알 수도 없습니다.
그래서 드레멜에서는 repetition level과 definition level라는 개념을 만들어 이를 설명할 수 있도록 하였습니다.
이 부분부터 드레멜의 nested 데이터 저장방식의 핵심 컨셉인 repetition level과 definition level에 대해서 설명하고 있습니다. 논문의 설명이 이해하기 꽤나 까다로워서 이 부분은 제 설명으로 대체하고자 합니다. 가독성을 위해 같은 이미지이지만 필요할 때마다 계속 첨부를 하였습니다.
먼저 repetition level(r)입니다. r은 반복되는 값을 어떻게 정의하는가에 대한 내용입니다. 다시 예시 데이터 모델을 가져와보겠습니다.
위의 모델에서 repeated으로 저장되는 필드를 정리해보죠.
•
Links.Backward
•
Links.Forward
•
Name.Language.Code
•
Name.Language.Country
•
Name.Url
만약 이런 반복되는 값을 아무런 규칙없이 저장해보겠습니다. Name.Language.Code 필드 값을 저장해보도록 하죠. 그러면 아래와 같이 value만 저장을 하게 됩니다.
value |
en-us |
en |
en-gb |
이렇게 저장했을 때의 가장 큰 문제는 “en-us”가 어떤 레코드에 속해있는지 알 수 있는 방법이 없다는 것입니다. “en-us”이 1번에 속해있는지 2번에 속해있는지 알 수가 없죠. 그렇다고 어떤 레코드에 속해있는지 일일이 명시적으로 기록하기에는 저장에 있어서 굉장히 비효율적입니다.
이를 위해 repetition level이라는 개념을 통해 이런 반복되는 구조를 쉽게 정의할 수 있도록 하였는데요. Name.Language.Code의 r을 어떤 식으로 정의하는지 살펴보도록 하겠습니다.
가장 첫번째 나타난 필드의 r은 무조건 0입니다. 그래서 "en-us"의 r은 0으로 시작합니다. 그리고 동일 문서의 동일 필드에는 0이 두번 이상 나올 수 없어 필드가 식별 가능하도록 합니다.
다음은 "en"인데 두번째 나타났으니 1이라고 생각할 수 있지만 2라고 되어있습니다. 이 부분이 repetition level을 이해하기 어려운 부분인데요. 가장 쉽게 정의하는 방법은 이전에 등장한 같은 path의 value와 비교했을때 어느 depth부터 반복이 됐는지로 이해하면 되는데요. 가장 첫번째 depth를 1로 정의하면 "en"은 "en-us"과 비교했을 때 Name.Language depth가 반복된거라 r은 2입니다. "en-gb"은 Name부터 반복되었으니 r은 1입니다.
그리고 중요한 것은 repetition level은 첫번째 레코드에서 "en-gb"가 마지막 필드라는 순서를 보장하기 위해 두번째 나온 Name 안에는 Language.Code가 없지만 NULL로 저장을 해야합니다. NULL도 마찬가지로 Name부터 반복되었으니 1로 저장됩니다.
definition level(d)은 얼마나 많은 필드가 정의되지 않을 수 있는지를 의미하는데 이를 풀어서 설명하면 optional한 부모 필드가 몇 개나 있는지 판단할 때 사용하는 값입니다. 똑같이 Name.Language.Code로 살펴보면 "en-us"는 Name, Language 필드는 optional이지만 Code는 required이기 때문에 d는 2입니다.
Name.Language.Country를 살펴보죠. “us”은 동일하게 Name, Language와 함께 이번에는 Country까지 optional이기 때문에 d는 3입니다.
또한 definition level도 repetition level과 동일하게 NULL을 저장하고 로직은 위와 동일합니다.
정리해보자면 아래와 같습니다.
•
repetition level: 어느 depth부터 반복이 됐는지
•
definition level: optional한 부모 필드가 몇 개나 있는지
이제 이렇게 정의된 r, d와 함께 각 컬럼은 압축된 필드의 블록 형태로 저장이 됩니다. 참고로 이 과정에서 NULL은 명시적으로 저장되지는 않는데 d<r이면 무조건 그 값은 NULL이라 d로도 충분히 NULL 판별이 가능하기 때문입니다. 또 만약 d가 무조건 저장되는 값이라면 따로 d가 저장되지 않습니다. r도 마찬가지로 저장이 안될 때가 있는데 예를 들어 d가 0이면 자동으로 r도 0이 되기 때문에 생략이 됩니다.
4.2 Splitting Records into Columns
이 부분부터는 드레멜이 어떻게 레코드를 컬럼단위로 저장하고 이를 다시 레코드로 구성하는지에 대한 내용입니다. 구글에서 사용하는 대부분의 데이터셋은 sparse 했기 때문에 빠진 데이터들을 최대한 효율적으로 저장하고, 처리해야 했습니다.
이를 위해 field writer라고 하는 트리 기법을 활용했는데요. 간단하게 설명하면 필드가 데이터를 가지고 있어야지만 업데이트하고 그렇지 않다면 꼭 필요하지 않은 이상 부모 노드 아래로 컴퓨팅을 전개하지 않는다는 아이디어를 가지고 있습니다.
이에 대한 pseudo code는 아래와 같습니다.
핵심적인 부분은 5번째와 14번째 줄인데요. 이 둘을 살펴보면 field writer가 더 이상 데이터를 가지고 있지 않을 때까지 계속해서 재귀하는 것을 볼 수 있습니다. 이런 식으로 레코드를 컬럼 단위로 효율적으로 저장할 수 있도록 합니다.
4.3 Record Assembly
이제 컬럼화한 데이터를 다시 레코드로 재구성하는 방법에 대해 알아보겠습니다. 드레멜에서는 FSM(Finite State Machine)를 통해 필드를 재구성하는데, FSM는 필드의 값과 레벨을 읽어 레코드에 순차적으로 값을 추가합니다.
아래 그림을 통해 작동 방식을 어느정도 시각화해볼 수 있는데요.
field reader는 결과로 필요한 필드를 읽고, State transition은 repetition level을 라벨링하여 FSM가 다음에 읽을 repetition level을 확인하여 사용할 다음 reader를 결정합니다.
5. QUERY LANGUAGE
드레멜은 SQL을 기본으로 하고, 열 기반의 nested 스토리지에서 효율적으로 동작하도록 설계되어 있습니다.
위의 그림은 r1, r2 레코드로 이루어진 테이블에서 샘플 쿼리가 어떤 식으로 동작하는지 보여주는데요. select 오퍼레이터는 특정한 조건을 만족시키지 않는 데이터는 가지치기하여 오직 http로 시작하는 Name.Url nested된 레코드만 골라냅니다.
쿼리 자체는 어렵지는 않기 때문에 자세한 쿼리 분석은 생략하도록 하겠습니다.
그 밖에도 nested 서브쿼리, 레코드 간, 레코드 내 집계, top-k, joins, udf 등 다양한 연산을 지원합니다.
6. QUERY EXECUTION
Tree architecture
루트 서버는 테이블로부터 메타데이터를 읽고, 쿼리를 다음 단계의 서빙 트리로 넘겨줍니다. 리프 서버에서는 스토리지 레이어와 상호작용을 통해 로컬 디스크로부터 데이터를 가져옵니다.
루트 서버가 쿼리를 전달받으면 만약 테이블이 파티셔닝이 되어있다면 아래와 같은 형태로 쿼리를 다시 작성하게 됩니다.
R은 각 노드의 쿼리 실행 결과를 의미하고 아래를 의미합니다.
궁극적으로 쿼리는 각 리프 서버에서 병렬로 처리되고, 중간 서버에서 부분 결과의 병렬 집계를 수행합니다.
Query dispatcher
드레멜에는 또 쿼리 디스패처라는 중요 기능이 있는데요. 크게 아래의 핵심 역할을 수행합니다.
•
scheduling: 드레멜은 기본적으로 멀티 유저 시스템이기 때문에 여러 쿼리가 동시에 실행될 수가 있습니다. 쿼리 디스패처는 이런 쿼리의 스케줄을 우선순위와 로드 밸런싱에 기초하여 배정합니다.
•
fault tolerance: 한 서버가 다른 서버보다 느려지거나 복제본에 접근할 수 없을 때 이러한 역할을 수행합니다.
위의 기능들은 슬롯보다 더 큰 쿼리가 실행될 때 동작하는데요. 여기서 슬롯은 각 리프 서버에서 실행할 수 있는 스레드를 뜻합니다. 예를 들어, 3000개의 리프 서버가 8개 스레드를 가지고 있다면 24000개의 슬롯이 있다는 의미인 것이죠.
7. EXPERIMENTS
이 부분은 드레멜의 퍼포먼스를 직접 테스트한 것을 기술해놓았는데요. 실험에 대한 요약이 바로 다음 섹션인 OBSERVATIONS에 잘 나와있어서 이 부분은 생략하려고 합니다. 드레멜과 MR의 비교, 다양한 환경에서의 성능 등이 궁금하시다면 한번 읽어보는 것을 추천드립니다. (나중에 시간이 된다면 다시 정리해볼게요)
)8. OBSERVATIONS
드레멜은 월 1000조개의 레코드를 스캔합니다. 아래 그림에서 보면 쿼리 시간 분포를 지수 스케일로 볼 수 있습니다.
우리는 실험으로부터 몇가지 관찰을 할 수가 있었습니다.
•
스캔 기반 쿼리는 최대 1조 개의 레코드로 구성된 디스크 저장 데이터를 인터렉티브한 속도로 실행할 수 있습니다
•
수 천개의 노드를 포함하는 시스템에서 컬럼과 서버를 선형에 가깝게 확장할 수 있습니다
•
레코드 집계와 파싱은 굉장히 비쌉니다
•
멀티 유저 환경에서, 대규모 시스템일 수도록 규모의 경제의 이점을 누리는 동시에 질적으로 더 나은 사용자 경험을 제공할 수 있습니다
•
스피드를 대신해서 정확도를 조금 희생할 수 있다면 보이는 데이터보다 빠르게 실행을 종료할 수 있습니다
•
웹 규모의 데이터셋을 빠르게 스캔할 수 있습니다. 하지만 촉박한 시간 내에 마지막 몇 퍼센트까지 스캔하는 것은 어렵습니다.
9. CONCLUSIONS
드레멜은 큰 규모의 데이터셋을 인터렉티브하게 분석할 수 있는 분산 시스템입니다. 드레멜은 간단한 컴포넌트로 구성된 커스텀 가능하고, 확장가능한 데이터 매니지먼트 툴입니다. 드레멜은 MR의 보완재 역할을 해줍니다. 우리는 수조개의 레코드와 테라바이트 데이터에 대한 성능에 대해 이야기 했습니다. 우리는 스토리지 포맷, 쿼리 언어, 실행을 포함한 드레멜의 핵심 기능에 대해 간략히 설명했습니다. 향후에는 형식적 대수 사양, 조인, 확장성 매커니즘 등의 영역을 더 깊이 있게 다룰 계획입니다.
Reference
개인적으로 이번에 라이너를 사용해서 논문 정리를 해보았는데 아주 도움이 많이 되더라구요 ㅎㅎ 중요 내용에 하이라이팅 하고, 잘 이해가 되지 않는 부분은 논문 기반으로 검색도 가능해서 큰 도움을 받았습니다. 정리한 내용도 링크 첨부합니다!
LinerDremel: Interactive Analysis of Web-Scale Datasets 논문 정리