대규모 시스템에서 발생하는 데이터 처리 (feat. 패스트캠퍼스 온라인 'THE RED : 4천만 MAU를 지탱하는 서비스 설계와 데이터 처리 기술')

이번 글에서는 강의에서 다뤄진 2번째 주제인 '대규모 시스템에서 발생하는 데이터 처리' 부분을 살펴보겠습니다. 역시 이전 글과 같이 넓은 시각에 대한 공유는 존재하나, 전체적인 구조와 디테일에 있어서 정리가 잘 되어 있지 않은듯 하여 주제별로 다른 리소스를 참고하였습니다.

• 이전글: 확장성 및 안정성 있는 시스템에 관하여 (feat. 패스트캠퍼스 온라인 'THE RED : 4천만 MAU를 지탱하는 서비스 설계와 데이터 처리 기술')
  
  

아래와 같은 구조로 데이터의 종류에서부터 저장, 처리와 같은 방향성을 가지고 전달드려 보겠습니다:

 

• 데이터 종류
• 데이터 모델과 쿼리 언어
• 데이터 저장
• 데이터 처리

---

데이터 종류

데이터의 종류는 다양한 관점으로 구분해볼 수 있습니다. 단순히 파악을 위해서만이 아니라 특정 상황에서 그러한 분류의 기준이 필요하기에 데이터를 분류하는 다양한 관점을 살펴볼 필요가 있습니다. 예로, 개인정보와 관련한 사항을 처리하는 상황이라면 익명, 가명, 개인정보라는 3가지 분류를 가지는 관점으로 데이터를 나누고 분류하여 데이터 환경을 바라보아야 할 것입니다. 

 

아래에서는 여러 데이터 분류 관점을 통해 데이터의 종류를 알아보겠습니다.

 

데이터 원천에 따른 분류

먼저, 데이터는 데이터가 어디서 발생 또는 입수되었느냐에 따라 분류될 수 있습니다.

 

Data sources of Big data - Image from [2]

SNS, 파이낸셜, ERP, IoT 등 다양한 원천이 존재하며 데이터를 원천에서 저장소로 이동시키는 '입수' 계획 단계에서 이러한 원천과 그로 인한 여러 특성들을 이해할 수 있게 됩니다.

 

 

데이터 구조에 따른 분류

정형 및 비정형의 구분으로 정형은 row와 column으로 구성된 관계형 데이터베이스로 나타낼 수 있는 데이터입니다. 반대로 비정형은 그러한 구조로 나타낼 수 없는 데이터가 속하게 되는데요. 크게 아래와 같은 특징을 가지고 있습니다:

 

	표현방식	데이터타입	일반적인 규모	필요 저장소 사이즈	처리
정형	row와 column이나 관계형 데이터베이스로 나타낼 수 있음	숫자, 날짜, 스트링	20%	비교적 적은 크기의 사이즈 필요 (압축률이 높음)	예전 도구들로도  쉽게 다룰 수 있음
비정형	정형방식으로 안됨	이미지, 오디오, 비디오, 이메일 등	80%	비교적 큰 사이즈 필요	예전 도구로는 비교적 어려움

 

데이터 생성방식에 따른 분류

데이터가 실시간으로 입수되는 스트리밍 형태와 일정 시간 동안 저장되어 모아져서 한꺼번에 입수되는 배치 형태가 존재합니다.

 

데이터의 통계학적 분류

데이터의 특성에 따라 아래와 같이 분류될 수 있습니다:

 

• 범주형
  • 명목형: 성별, 혈액형 등 단순히 분류된 데이터
  • 순서형: 순서 관계로 존재하는 데이터
• 수치형
  • 이산형: 이산적인 값을 갖는 데이터
  • 연속형: 연속적인 값을 갖는 데이터
    

특히 텍스트 데이터에서 이러한 관점이 데이터를 분류하는데 중점적으로 사용되게 됩니다.

 

이외에도 개인정보여부(개인, 가명, 익명), 형태(텍스트, 이미지, 동영상 등)의 관점으로 구분할 수 있습니다. 

 

 

데이터 모델과 쿼리 언어

데이터 모델은 작성되는 소프트웨어 뿐만 아니라 해결하고자 하는 문제를 어떻게 바라볼지에 영향을 미치기에, 소프트웨어 개발 시 가장 중요한 요소라고 할 수 있습니다.

 

대부분의 애플리케이션들은 하나의 데이터 모델을 다른 데이터 모델 위에 쌓아올리면서 만들어지게 됩니다. 각 레이어에서의 핵심 질문은 '어떻게 다음 레이어의 관점에서 현재 레이어의 데이터 모델이 표현되는가?'라고 할 수 있습니다. 예로:

 

• 애플리케이션 개발자의 관점에서는 실제 세상을 바라보고 객체, 데이터 구조, API 등으로 모델링을 진행하게 됨
• 그러한 데이터 구조를 저장하는 레이어의 관점에서, JSON, XML, Table과 같은 일반적인 데이터 모델로 표현하게 됨
• 그러한 데이터 모델을 저장할 데이터베이스를 만드는 레이어의 관점에서는, JSON / XML 과 같은 데이터를 메모리 또는 디스크 상의 바이트로 표현하게 됨. 그러한 바이트로 표현된 데이터는 간단한 쿼리나, 검색 등 다양한 방법으로 조작되고 처리될 수 있도록 함.
• 그 아래 레이어의 로우 레벨에서는 하드웨어 엔지니어의 관점에서는, 어떻게 위에서 표현된 바이트가 전자기적 흐름 등으로 나타내질 수 있는지 연구하게 됨

 

더 복잡한 생태계에서는 더 많은 레이어의 형태로 이뤄질 수 있으나 본질은 각 레이어가 해당 레이어의 복잡성을 숨기며 정리된 데이터 모델을 보여준다는 점에서 동일합니다.

 

이러한 다양한 데이터 모델은 그러한 데이터 모델이 어떻게 사용될지에 대한 가정을 구현하고 있습니다. 아래에서는 일반적인 데이터 모델과 그렇게 구현된 데이터 모델이 어떠한 형태의 사용을 가정하고 만들어졌는지 알아보겠습니다.

 

관계형 모델 vs 다큐먼트 모델

관계형 모델은 수많은 모델 중 가장 널리 알려진 데이터 모델입니다. 데이터는 관계로 구조화 되고(SQL의 테이블) 그러한 관계는 순서가 없는 여러 튜플의 묶음(SQL의 Rows)으로 나타내게 되는데요. 그러한 관계성을 잘 보여주는 것은 자주 볼 수 있는 아래와 같은 테이블 관계 이미지입니다:

 

Image from [3]

관계형 모델은 1960, 70년대에 원형이 탄생되었습니다. 시기의 중간중간에 다양한 데이터 모델 (네트워크, 수직적 등)이 있었으나, 관계형 모델은 현재까지도 많이 이용되는 데이터 모델로 남았습니다. 

 

2010년에 다큐먼트 모델이 탄생하며 관계형 모델의 대안으로 많이 사용되기 시작되었습니다. 트위터에 nonrelational이라고 적었던 것이 고착되어 사용되고 있는 NoSQL에 해당되는 데이터베이스들 중 대부분이 그러한 다큐먼트 모델에 기반하고 있습니다. 그러한 NoSQL이 많이 사용되는 이유는 아래와 같습니다:

 

• 관계형 데이터베이스보다 더욱 확장성 있는 저장소에 대한 필요성
• 상업용 데이터베이스 상품에서의 오픈 소스 이용의 대중화
• 관계형 모델에서 특별한 종류의 쿼리가 지원되지 않음
• 관계형 모델을 벗어나 좀 더 동적인 데이터 모델에 대한 요구

 

특히 특정 데이터 추출을 위해 관계형 모델과 다큐먼트 모델 기반에서 어떻게 접근을 하게 되는지 살펴보면 더욱 더 '데이터 모델 - 사용패턴' 간의 깊은 연관성을 이해할 수 있게 됩니다.

 

One-to-Many 형태 추출을 위한 관계형 모델 및 다큐먼트 모델의 접근 비교

LinkedIn에서 빌게이츠 프로필을 저장한다고 할 때, 그러한 프로필 데이터는 아래와 같은 json 형태를 가지게 됩니다:

 

{
  "user_id": 251,
  "first_name": "Bill",
  "last_name": "Gates",
  "summary": "Co-chair of the Bill & Melinda Gates... Active blogger.", "region_id": "us:91",
  "industry_id": 131,
   "photo_url": "/p/7/000/253/05b/308dd6e.jpg",
  "positions": [
    {"job_title": "Co-chair", "organization": "Bill & Melinda Gates Foundation"}, {"job_title": "Co-founder, Chairman", "organization": "Microsoft"}
  ], 
  "education": [
    {"school_name": "Harvard University", "start": 1973, "end": 1975},
    {"school_name": "Lakeside School, Seattle", "start": null, "end": null} 
  ],
  "contact_info": {
    "blog": "http://thegatesnotes.com",
    "twitter": "http://twitter.com/BillGates"
  }
}

 

위와 같이 json의 다큐먼트 모델로 한곳에 모든 정보가 저장되어 있다면, 한 번의 쿼리로 필요한 모든 데이터를 가지고 올 수 있게 됩니다. 반면에 만약 이러한 데이터를 관계형 모델에 기반한 데이터베이스에 저장한다고 하면, 아래와 같은 구조를 가지고 접근 시에 수많은 join을 통해 데이터를 가져와야 할 것입니다. 그렇기에 주요한 접근 형태가 one-to-many이고, 아래에서 설명드릴 데이터 중복이 많지 않다면 다큐먼트 모델이 적절한 선택일 것입니다.

 

Image from Author inspired by [1]

 

반대로 위와 같은 다큐먼트 모델로 모든 사용자의 정보를 저장한다면, 똑같은 정보도 중복적으로 저장하게 됩니다. 예로 관계형 모델에서는 정규화를 통해 같은 정보의 중복 저장을 최소화할 수 있지만, 다큐먼트 모델에서는 매 레코드마다 중복으로 저장합니다. 

 

 

데이터를 위한 쿼리 언어

관계형 모델이 소개되면서, 그러한 모델에 기반한 새로운 형태의 쿼리 언어도 도입되었습니다. 먼저, 관계형 모델의 쿼리 언어 이전의 쿼리 언어는 주로 imperative 코드 [4]로 아래와 같은 형태입니다:

 

function getSharks() {
    var sharks = [];
    for (var i = 0; i < animals.length; i++) {
        if (animals[i].family === "Sharks") {
            sharks.push(animals[i]);
        }
    }
    return sharks;
}

 

다양한 종의 동물이 있는 리스트에서 상어만을 추출하는 경우 위와 같은 형태로 구성됩니다. 대부분의 프로그래밍 언어는 위와 같은 imperative한 형태입니다. 명시적으로 어떤 실행을 해야하는지 작성하게 됩니다.

 

반면에, 관계형 모델에 기반한 쿼리 언어는 똑같은 목적을 위해서 아래와 같은 형태로 표현됩니다:

 

SELECT * FROM animals WHERE family = 'Sharks';

 

이러한 형태는 declarative 코드입니다. 이와 같은 declarative 코드에서는 원하는 데이터에 대한 패턴을 명시하지만 어떻게 그러한 목적을 이루기 위해 실행되는지에 대해서는 언급되지 않습니다. 그러한 부분은 쿼리 언어를 파싱하고 실행을 담당하는 데이터베이스 시스템의 쿼리 옵티마이저 등이 결정하게 됩니다. 

 

웹 상의 CSS와 같은 경우도 이러한 declarative 코드의 일종이며, MapReduce와 같은 경우는 일부는 imperative, 일부는 declarative적 성격의 코드라고 할 수 있겠습니다. 

 

 

데이터 저장

위의 '데이터 모델과 쿼리 언어'라는 레이어에서 한 단계 더 내려가면 그러한 상위 레이어의 데이터 모델을 저장하는 데이터베이스와 같은 저장소의 레이어가 존재합니다. 저장소는 크게 데이터의 저장과 데이터 IO를 수행하게 됩니다. 

 

저장소 엔진은 크게 2종류로 log-structured와 page-oriented가 존재합니다 [5]. 아래에서 각 종류에 해당되는 다양한 엔진을 살펴보겠습니다.

 

먼저 기초적인 형태의 key-value 스토리지는 아래와 같이 만들 수 있습니다:

 

#!/bin/bash

db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

 

database라는 파일에 콤마로 구분된 키-밸류의 데이터 모델은 db_set, db_get과 같은 API를 통한 간단한 데이터베이스에 접근을 가능하게 합니다. 그렇기에 아래와 같은 데이터 IO가 가능합니다:

 

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

 

그러나 위와 같은 데이터베이스의 경우 42의 키에 해당되는 값을 찾기 위해서는 database에 존재하는 모든 행을 읽어야 하기에 O(n)의 성능을 가집니다. 그렇기에 레코드가 추가됨에 따라서 소요시간도 직선적으로 증가하게 됩니다. 

 

데이터베이스에서 특정 키에 해당되는 값을 빠르게 찾기 위해서는, index라는 다른 데이터 구조가 필요합니다. index는 primary 데이터에서 얻어지는 추가적인 데이터구조입니다. 추가적인 데이터 구조를 유지하는 것은 특히 write 시에 overhead를 동반하게 됩니다. 대신 read 시에 index를 통해 빠르게 접근할 수 있다는 trade-off를 가지게 됩니다. 

 

 

Hash Indexes

키-밸류 데이터에 사용되는 인덱스는 매우 자주 사용되고, 더욱 복잡한 인덱스를 만들기 위한 빌딩 블록이기도 합니다. 이러한 키-밸류 저장소는 딕셔너리 타입과 유사하며 그렇기에 대부분의 프로그래밍 언어에서 딕셔너리가 해시맵으로 구현되있는 것을 볼 수 있습니다. 

 

만약 데이터 저장소가 오직 파일에 append만으로 이뤄져 있다면 인메모리 해시맵을 사용하여 데이터 파일 상의 바이트 오프셋을 키에 매핑하여 가지고 있을 수 있습니다. 새로운 키-밸류를 파일에 더하거나, 해시맵을 업데이트하여 write으로 변경된 파일의 데이터를 반영할 수 있게 됩니다. 

Image from Author inspired by [1]

이러한 경우 모든 키들은 가용한 RAM에 들어갈 수 있어야 하고, 밸류는 디스크에 저장되어 존재(log-structured 형태)하기에 상대적으로 큰 값도 저장할 수 있으며 접근 시 해시맵에서 byte offset을 얻어 한번의 disk seek으로 찾을 수 있게 됩니다. 

 

같은 키에 대한 반복적인 update를 하게 되면, 앞에서의 가정으로 append-only인 형태이기 때문에 과거의 모든 동일 키에 대한 밸류는 잔존하게 됩니다. 그렇기에 디스크 용량은 점점 커지게 됩니다. 그러한 부분을 해결하기 위해 과거에 잔존하는 키에 대한 밸류는 삭제하는 compaction 작업을 수행하여 효율화를 이룰 수 있습니다. 

 

Performing compaction and segment merging simultaneously - Image from [1]

 

위와 같이 비견 간단해보이는 해시맵을 실제로 구현하기 위해서는 여러 중요한 이슈를 고려하여야 합니다:

 

• 파일 포맷
• 레코드 삭제: 보통 삭제된 레코드에 특별한 표식을 해두고, 위와 같은 segment 머지 시점에서 해당 레코드를 제외하고 compaction하여 삭제하게 됩니다. 
• Crash Recovery: 데이터베이스가 재시작되면, 인메모리의 해시맵을 잃어버리게 됩니다. 원칙적으로는, 디스크의 모든 값을 읽어들여 해시맵을 메모리에 재구성할 수 있지만 매우 오랜 시간이 걸릴 수 있습니다. 그러한 경우, 주기적으로 스냅샷을 저장해두어 메모리에 로드를 좀 더 빠르게 만들 수 있습니다. 
• Partially written 레코드
• Concurrency control: 보통 write은 시퀀셜하기에 하나의 쓰레드를 가지는 등을 통해 동시성이 제어되고, read는 여러 쓰레드를 통해 동시적으로 읽을 수 있도록 합니다. 

 

Append-only 형태의 구현은 제한되어 보이나 위와 같은 부분에서 여러 장점도 가지고 있습니다(시퀀셜 write operation이라는 점, 동시성과 crash recovery가 보다 간단함, 오래된 세그먼트 머징이 데이터 파일이 fragmented되는 것을 방지). 

 

또한, 해시 index는 아래와 같은 단점도 존재하기에 목적에 따라 이어질 다른 형태의 indexing을 고려하게 됩니다:

 

• 해시 테이블이 반드시 메모리에 모두 들어갈 수 있어야 함
• range 쿼리가 효율적이지 않음. 0 ~ 1000 스캔 시, 모든 키를 각각 접근하여 byte offset을 찾고 값을 얻게 됨

 

 

SSTables와 LSM-Trees

위의 해시맵에서의 log-structured storage segment에서는 키-밸류들은 write된 순서대로 존재하고 각 키의 맨 마지막에 쓰여진 키-밸류가 유의미한 데이터로 존재하게 됩니다. 그 부분을 제외하고 키의 순서는 중요하지 않습니다.

 

이제 Segment 파일의 키-밸류 데이터를 키를 통해 소팅(sorting)한 형태로 저장할 수 있습니다. 이러한 형태는 SSTables(Sorted String Tables)로 불립니다. 각 키는 각 세그먼트에서 단 한번만 등장하게 됩니다. SSTables은 해시 index 대비 아래와 같은 장점을 가지게 됩니다:

 

1. 세그먼트 머징이 파일들이 가용 메모리보다 크더라도 단순하고 효율적입니다. 이러한 접근법은 주로 mergesort 알고리즘에서 사용됩니다. input 파일들을 하나씩 읽어서 각 파일의 첫 키를 확인하고 가장 낮은 키를 output에 복사하며 이런 작업을 반복합니다. 이러한 작업의 최종 산물로 키로 소팅된 합쳐진 세그먼트 파일이 생성되게 됩니다.

 

만약 동일한 키가 여러 세그먼트에서 발견되면, (하나의 세그먼트의 모든 레코드는 언제나 다른 세그먼트의 모든 레코드보다 이전이나 이후의 시점이기에) 가장 최근에 생성된 세그먼트의 키-밸류 데이터를 선택하여 복사하게 됩니다.

 

2. 파일에서 특정 키를 찾기 위해서, 모든 키를 메모리에 들고 있을 필요가 없습니다. handiwork에 대한 read 시 handiwork가 메모리 상의 Sparse index에 없지만 주변의 handbag과 handsome이 있는 것을 확인하여 각각의  byte offset을 알 수 있습니다. 그렇기에 소팅된 세그먼트에서 두 byte offset 사이에 handiwork가 존재하게 되며 둘 사이 일부 데이터만 스캔하여 밸류를 얻을 수 있습니다. 

 

비록 메모리에 index를 보관해야한다는 점은 동일하지만, 디스크 상의 몇 KB는 빠르게 스캔 가능하기에 몇 KB 세그먼트 당 하나의 키만 메모리에 들고 있어도 충분하게 됩니다.

 

3. read 요청은 몇개의 키-밸류 데이터를 스캔해야 하기에, 그러한 레코드들을 하나의 블록에 모으고 디스크에 쓰기 전에 압축할 수 있게 됩니다. Sparse 인메모리 index는 이어 각 압축 블록의 시작을 포인트합니다. 이를 통해, 디스크 용량을 줄임과 동시에 IO 대역폭 사용량도 줄일 수 있게 됩니다. 

 

SSTables를 만들고 유지하기

소팅된 구조를 디스크에 보관 및 유지하는 것은 가능하지만, 메모리 상에서 그러한 점을 유지하는 것이 더욱 쉽습니다. Red-black tree나 AVL 트리와 같은 많이 알려진 트리 데이터 구조를 통해 그러한 부분을 구현할 수 있습니다. 

 

그러한 트리를 적용 시에 저장소 엔진은 아래와 같이 동작합니다:

 

1. Write 요청이 전달된 후 데이터는 인메모리 균형 트리 데이터 구조(memtable로 불림)에 추가됩니다. 

2. memtable이 특정 역치보다 커졌을 때(주로 몇 MB), SSTable 파일로 디스크에 write하게 됩니다. 트리는 이미 키를 통해 소팅된 키-밸류 구조를 유지하고 있기에 이러한 작업은 매우 빠르게 실행됩니다. 새로운 SSTable 파일은 데이터베이스의 가장 최신의 세그먼트가 됩니다. SSTable이 디스크에 write되는 동안 발생하는 write은 새로운 memtable 인스턴스에 반영되게 됩니다.

 

3. read 요청을 처리하기 위해 키를 memtable에서 찾고, 가장 최신의 디스크 세그먼트, 그리고 2번째로 최신의 디스크 세그먼트 순으로 접근하여 밸류를 찾습니다.

 

4. 때때로 백그라운드에서 머징과 컴팩션 작업이 실행됩니다.

 

이러한 형태는 데이터베이스 실패 시 인메모리에만 존재하는 최신의 write을 잃어버린다는 점 외에 매우 잘 작동합니다. 그러한 문제를 피하기 위해서, 매 write 요청 발생 시 바로 append 되는 분리된 로그를 디스크에 보관할 수 있습니다. 그러한 로그는 소팅되어 있지 않으며 오직 crash 이후에 memtable 복원에만 사용되게 됩니다. 

 

SSTables로부터 LSM-tree 만들기

아래에 기술된 알고리즘은 LevelDB와 RocksDB에 사용되는 알고리즘입니다. 그와 유사한 저장소로는 Cassandra와 HBase가 있고 둘은 Google Bigtable(SSTable과 memtable이라는 용어가 만들어진)의 영향을 받았습니다.

 

이러한 인덱싱 구조는 Patrick O'Neil에 의해서 LSM-Tree(Log-Structured Merge-Tree)라고 정의되었습니다. 이러한 원칙에 기반한 저장소 엔진은 LSM 저장소 엔진이라고 불립니다. 

 

엘라스틱서치와 Solr의 인덱싱 엔진인 Lucene도 term dictionary 저장을 위해 유사한 방법을 사용하고 있습니다. Full-text 인덱스는 키-밸류 인덱싱보다 조금 복잡하지만 기본적인 아이디어는 같습니다. 검색 쿼리의 단어를 받아서, 단어를 포함한 모든 문서를 검색하는 것이며 키는 용어(term)이고 밸류는 그러한 용어를 가진 모든 문서의 id들을 가지게 됩니다. 

 

성능 최적화

역시 다양한 관점에서 위와 같은 저장소 엔진에 대한 최적화가 이뤄지게 됩니다. 예로, LSM-tree 알고리즘은 데이터베이스에 존재하지 않는 키를 검색할 때 매우 느릴 수 있습니다. memtable에 존재하지 않고, 최신부터 가장 오래된 세그먼트까지 차례대로 계속 스캔하게 됩니다. 이러한 형태의 접근을 최적화하기 위해, 저장소 엔진은 주로 추가적인 블룸 필터 [6]를 사용합니다. 

 

또한, SSTables이 compated되고 머징되는 시점과 순서를 결정하는데에 다양한 전략이 사용되기도 합니다(size-tiered vs leveled)

 

 

B-Trees

사실 가장 폭넓게 사용되는 인덱싱구조는 앞의 여러 log-structued 인덱스가 아니라 B-Tree 인덱스입니다. 1970년데에 소개되어서, 현재까지도 B-Tree 인덱스는 많은 관계형 데이터베이스와 NoSQL에서의 스탠다드 인덱스로 남아있습니다. 

 

SSTables과 같이 B-trees는 키로 소팅된 키-밸류 데이터를 가지고 있지만 그 외에는 매우 다른 관점으로 구현되었습니다. 

 

위에서 살펴본 Log-structured 인덱스는 데이터베이스를 변경가능한 크기의 세그먼트(주로 몇 MB)로 나누고 세그먼트를 시퀀셜하게 write합니다. 반면 B-trees는 데이터베이스를 고정된 크기의 블록이나 페이지(주로 4KB)로 나누고 한번에 하나의 페이지를 읽거나 씁니다. 이러한 디자인은 디스크가 고정된 크기의 블록으로 구성되니 것과 같이 좀 더 하드웨어와 상응하는 형태를 가집니다.

 

각 페이지는 주소나 위치를 사용하여 식별될 수 있으며, 하나의 페이지가 다른 페이지를 참조(디스크 상에서)할 수 있도록 합니다. 이러한 참조들을 통해서 페이지 트리를 만들 수 있게 됩니다. 

 

하나의 페이지는 B-trees의 루트로 임명되며 탐색 시작 시의 시작점이 됩니다. 페이지는 몇개의 키와 child 페이지에 대한 참조값을 가지며, 각 child는 연속된 범위의 키를 담당합니다. 두 개의 키 사이의 참조들은 그러한 범위의 경계가 어디에 존재하는지 나타내게 됩니다. 

 

최종적으로 각 키를 포함하는 leaf page에 도달하고, 각 키에 대한 밸류를 가지거나 밸류가 포함된 페이지에 대한 참조값을 가지고 있습니다. 

 

하나의 B-trees에 속하는 child 페이지의 참조수는 branching factor라고 불립니다. 

 

만약 B-trees에 존재하는 키에 대하여 밸류를 업데이트하려고 하면, 키를 가진 leaf 페이지를 찾고, 밸류를 변경하고, 그 페이지를 다시 디스크에 write하게 됩니다. 새로운 키를 더하려고 하면, 새로운 키의 범위를 포함하는 페이지를 찾고, 더하게 됩니다. 만약 해당 페이지에 충분한 여유 공간이 없다면 반씩 나누어 페이지를 만들고 부모 페이지의 참조를 업데이트하고 나누어 새로 만들어진 페이지에 더하게 됩니다. 

 

컬럼형 저장소

분석 쿼리 성능에 있어서 컬럼형 저장소는 전반적인 디스크 IO나 디스크로부터의 데이터 로딩 사이즈를 급격하게 줄여주기에 최적화에 매우 중요한 요소입니다.

 

먼저 전통적인 관계형 데이터베이스에 해당되는 row-oriented의 경우 여러 필드의 값을 가진 각 row는 아래와 같은 형태로 저장됩니다. 데이터 블록은 값을 한 row의 여러 필드를 시퀀셜하게 저장하며 구성됩니다. 블록 사이즈가 레코드 사이즈보다 작다면 한 레코드 저장을 위해 여러 블록이 사용됩니다. 블록 사이즈가 레코드 사이즈보다 크다면, 일부 블록 공간은 사용되지 않는 비효율이 발생하게 됩니다. 

 

OLTP 애플리케이션에서 대부분의 트랜잭션은 빈번한 read, write과 함께 한 레코드의 모든 필드에 주로 접근합니다. 그렇기에 row-oriented 저장소는 OLTP 데이터베이스에 적합합니다.

 

Row-oriented data structure - Image from [7]

 

반대로, 아래의 column-oriented 저장소는 한 컬럼의 여러 row의 값을 시퀀셜하게 저장합니다. OLAP 애플리케이션의 주된 접근 형태는 수많은 컬럼에서 일부의 특정 컬럼에 대한 접근을 대용량의 수많은 레코드에 대한 데이터에 행하는 것이 빈번합니다. 그렇기에 아래와 같은 컬럼형 저장소의 형태일 때에 많은 이점을 가지게 됩니다.

 

예로, 모든 레코드의 SSN값에 접근한다고 할 때에 column-oriented에서는 SSN 값들이 나란히 저장되어 있기에 1번의 IO를 통해 모든 정보를 얻어올 수 있습니다. 하지만, row-oriented에서는 3곳의 블록에 접근하여 SSN값을 추출할 수 있기에 3배의 IO를 요구하게 됩니다.

 

또한, column-oriented는 하나의 컬럼에 속한 여러 레코드의 값을 나란히 저장하기에 유사한 형태, 값을 가진 데이터를 포함할 확률이 높습니다. 그렇기에 압축 시에 높은 압축률을 보일 수 있게 됩니다. 

 

분산 데이터

데이터는 아래와 같은 주요 목적으로 여러 머신에 분산되어 저장되어 IO될 수 있습니다:

 

• 확장성: 데이터의 볼륨, 읽기 부하, 쓰기 부하가 하나의 머신이 처리할 수 있는 것보다 커지면서, 분산 데이터 환경을 통해 그러한 부하를 여러 머신에 나눌 수 있게 됩니다.

 

• Fault Tolerance / high availability: 하나의 머신이 고장나도 애플리케이션이 영향을 받지 않고 실행되기 위해서, 여러 머신에 저장함으로써 다중화를 이룰 수 있습니다.

 

• Latency: 사용자가 세계 여러 지역에 존재한다면, 다양한 지역에 서버를 두고 각 사용자에게 가장 가까운 곳에서 데이터를 제공하여 지연속도를 낮출 수 있게 됩니다. 

 

이러한 분산 데이터와 관련한 개념으로는 복제 및 파티셔닝, 트랜잭션, CAP Theorem 등이 존재하는데요. 이 주제는 글이 너무 길어질 수 있어서 추후 다른 글을 통해 정리해보도록 하겠습니다. 

 

데이터 처리

HTTP/Rest-based APIs가 증가해온 웹의 관점에서 보면 데이터 처리는 요청과 응답을 중심으로 이루어져 있습니다. 시스템-시스템 또는 사용자-시스템의 요청과 응답 간에는 여러 데이터 처리가 포함되게 되는데요.

 

여러 시스템을 구성하는 다양한 데이터 처리는 위와 같은 데이터 처리 말고도 여러 형태가 존재합니다:

 

• 서비스(online): 서비스의 데이터 처리 형태는 요청이나 지시를 받으면 최대한 빠르게 데이터를 처리하고 응답을 보내는 형태입니다. Latency와 availability의 부분은 매우 중요합니다.

 

• 배치 프로세싱(offline): 배치 프로세싱에서는 대량의 데이터를 받아서 job을 실행하여 그러한 데이터를 처리하고 결과물 데이터를 만들어내는 형태로 이뤄집니다. 배치 프로세싱은 latency보다는 throughput에 중점을 두어, 대부분 그러한 결과물을 기다리는 사용자를 갖지 않고 주기적으로 실행되는 집계 등의 목적으로 사용되게 됩니다.

 

• 스트림 프로세싱(near-realtime): 스트림 프로세싱은 online과 offline의 중간의 형태입니다. 배치 프로세싱과 비슷하게 인풋을 받아 아웃풋을 만들지만, 스트림 job은 이벤트가 발생한 직후에 수행됩니다. 그렇기에 배치 프로세싱보다는 낮은 latency를 목적으로 합니다. 

 

위의 처리의 형태 이외에, 데이터의 처리와 관련된 주요 개념 중 하나는 '스토리지-컴퓨팅의 분리'입니다. 여기서의 분리는 기존의 하나의 머신에서 또는 시스템에서 강하게 결합되어 있던 스토리지와 컴퓨팅을 분리하는 것입니다.

 

웹 서비스 개발과 같은 분야에서는 AWS EBS와 EC2와 같은 클라우드 환경의 분리가 연관되는 부분일 수 있습니다. 그렇지만 빅데이터와 같은 부분의 분산 환경에서는 좀 더 연관성이 깊은 '처리(컴퓨팅)'라고 할 수 있는 부분과 스토리지가 분리되어 이뤄지게 됩니다. AWS S3와 EMR, 하둡의 HDFS와 YARN & MapReduce와 같은 대비가 그런 예시가 될 수 있겠습니다.

 

분산 처리 

분산 처리에 있어서 MPP와 같이 자원 관리와 처리 엔진이 강하게 결합한 형태가 있는 반면 분산 자원 관리(YARN, Kubernetes, Apache Mesos)와 분산 처리 엔진(MapReduce, Tez, Spark 등)과 같이 분리된 형태로 존재하는 형태가 존재합니다. 

 

YARN이란? (하둡분산자원관리)

 

상세한 사항별로 조금씩 다르겠지만, 여러 노드에 존재하는 컴퓨팅 자원을 사용해 요청된 데이터 처리를 진행한다는 공통점에서 스케쥴링, 쿼리 플래닝, 최적화 등과 같은 유사점을 가지게 됩니다. 

 

Reference

[1] Designing Data-Intensive Applications

[2] https://www.researchgate.net/figure/Data-sources-of-Big-Data_fig1_336028940

[3] https://www.researchgate.net/figure/Relational-model-design-of-the-database-On-a-conceptual-level-the-database-is_fig3_237832917

[4] https://en.wikipedia.org/wiki/Programming_language

[5] https://edward-huang.com/distributed-system/database/2021/03/30/two-families-of-storage-engine-that-powers-modern-day-database/

[6] https://en.wikipedia.org/wiki/Bloom_filter

[7] https://docs.aws.amazon.com/redshift/latest/dg/c_columnar_storage_disk_mem_mgmnt.html