출처 : http://blog.naver.com/naverdev/120113715336


Large Scale Data를 처리하기 위한 네 가지 접근법

인터넷 서비스는 전 세계를 고객으로 한다.
고객이 요구하는 데이터의 양도 많다.
이렇게 많은 양의 데이터 처리는 RDBMS로는 역부족이다. 
이렇게 많은 양의 데이터를 처리하는 새로운 방법이 필요하다. 
Large Scale Data를 다루기 위한 접근법 네 가지를 다루어보도록 하겠다.



“The End of Architectural Era”
우리가 흔히 접하고 있는 다양한 웹 서비스는 전세계의 사용자를 대상으로 언제 어디서나 접근 가능하게 되면서 사용되는 데이터의 규모가 눈깜짝할 사이에 엄청난 규모로 늘어 나게 된다. 최근에 스마트폰의 확산으로 버스 정보 앱이 퍼지면서 버스 정보 제공 사이트에 감당 못할 트래픽이 몰렸다는 사실은 이러한 점을 뒷받침하기도 한다.
더불어서, 급속도로 발전하는 웹 서비스 기술들은 전통적인 데이터베이스 이론들에 대한 반론들을 불러왔다. 더 이상 몇 대의 DB 서버가 SAN 스토리지를 사용하는 물리적인 환경에 국한되지 않고, 더 이상 트랜잭션 하나 하나와 레코드 하나 하나의 처리 결과보다 전체적인 효율과 서비스 가용성이 더 중요하게 되면서, 흔히 말하는 Big Data, 즉 Large Scale Data를 관리하고 사용하는 방식은, 전통적인 데이터베이스 이론과 현재의 RDBMS에는 적합하지 않다는 주장이 많이 제기되고 있다.
데이터베이스 계의 거장인 Michael Stonebraker가 2007년 VLDB에 기고한 논문인 “The End of Architectural Era”는 이러한 사실들을 지적하고 있다. 70년대 후반부터 발전하기 시작해 80년대 말에 꽃을 피운 relational DBMS 관련 기술은 “one size fits all” 형태의 범용 DBMS, 즉 OLTP이건, DW이건, Scientific이건, Web이건 어떠한 유형의 응용이건 데이터 저장 관리라면 무조건 사용될 수 있는 시스템을 만드는 것이 목표였으나 (그리고, 그 동안 어느 정도 잘 해오고 있었으나) 이제는 25년이 넘은 낡은 코드를 버리고 새로 시작해야 할 때라고 주창한다.
현재의 RDBMS는 다음과 같은 특징들로 규정될 수 있다.
  • 관계형 데이터 모델 (Relational Data Model) – 모든 데이터는 테이블 형태로 보여지며 상호 관계를 표현할 수 있다.
  • SQL의 사용 – 선언적 (declarative) 언어이기 때문에 질의 최적화기 (query optimizer) 기술이 많이 발달했다.
  • 디스크 기반의 저장 – 레코드들을 연속된 디스크 블록에 차례로 저장하고, 디스크 기반 색인 기법인 B-tree를 구현했다.
  • 동시성 제어 및 로그 기반의 복구 – 잠금(lock)이나 다중 버전(multi version)을 통해 한 데이터에 대한 동시 조작을 허용하면서도 무결성(integrity)를 보장한다.
이러한 특성을 모두 만족하며 “one size fits all”을 추구하는 범용 DBMS들은 텍스트 처리나 DW 등의 특정 영역에 특화된 시스템에 비해 성능은 떨어지고 기능도 부족하다고 여겨지고 있다. 특히나, 대량의 데이터를 다루는 웹 로그 분석이나 BI, 혹은 전세계 IDC들을 통해 운영되기 때문에 데이터 응답 속도가 더욱 중요한 대형 웹 서비스들의 경우, 기존 데이터베이스 기술의 총아인 상용 RDBMS만으로는 부족하다. 하루에 수백 기가에 해당하는 로그를 제 시간 내에 분석하기 위해서, 미국에 있는 사용자가 (DB 서버에) 저장한 블로그를 데이터를 영국에 있는 (웹 서버를 통해) 사용자가 실시간으로 읽을 수 있게 하기 위해서 새로운 데이터베이스 기술들이 연구되고 있다.

Database Technology for Large Scale Data
최근 5년 동안 각각의 영역별로 특화된 DBMS들이나 새로운 형태의 저장 구조를 갖는 데이터베이스 시스템들이 많이 연구 개발되고 있는데[1], 이들을 기술 유형으로 나누어보면 다음과 같다.

  • Massively Parallel Processing or Parallel DBMS – DBMS의 질의 수행을 병렬화하고, 질의를 쪼개 여러 대의 DBMS 노드에 분배해 동시에 수행하는 방식의 대량 연산이 가능한 시스템
  • Column-Oriented Database – 데이터를 디스크에 저장하는데 기존의 ow 방식, 즉 레코드 단위의 저장이 아니라 column 방식, 즉 같은 필드의 값들을 모아서 저장하는 시스템
  • Streaming Processing (ESP or CEP) – 시간의 흐름에 따라 데이터베이스의 내용이 계속 변한다는 개념으로, 끊임없이 입력되는 데이터를 대상으로 자료 처리(혹은 이벤트 처리)를 하는 시스템
  • Key-Value Store (with MapReduce programming model) – 관계형 데이터 모델보다 더 단순한 Key-Value 데이터 모델을 채택해서 단일 레코드 읽기 성능에 더욱 집중하는 저장 시스템


Massive Parallel Processing / Parallel DBMS
80년대부터 단일 프로세서에서 수행되는 DBMS로는 테라 바이트(TB) 규모에서 10,000 TPS 수준의 데이터 처리는 어려우니, SMP 하드웨어에서 “병렬 질의 처리 (Parallel Query Processing)”을 구현하는 기술들이 많이 발전하였다. 예를 들어 DB에서 항상 많은 시간이 걸리는 sort나 아니면 hash join은 자주 병렬 처리로 변경되고는 한다. 복잡 난해하고 긴 SQL 질의를 차례 차례 수행하는 것 보다는 pipelining 형태로 각 단계를 병렬화하는 것도 중요하게 사용되는 테크닉 중 하나이다. 병렬 처리 기술은 BI와 같은 데이터 분석에 많이 사용되고 있다.

이러한 병렬 DBMS 기술은 단일 노드 SMP 하드웨어를 넘어 shared-nothing 구조의 클러스터를 기반으로 하는 Massively Parallel Database 시스템으로 발전하고 있다. 예를 들어 6.5 PB 규모의 eBay의 DW DB나 10 규모의 데이터 분석을 위한 Yahoo의 Everest Architecture 등이 MPP 구조와 기술에 기반하고 있다. 

MPP DBMS의 또 다른 예로 오픈 소스 DBMS인 PostgreSQL을 이용하여 개발된 Greenplum과 Aster Data를 들 수 있다. Greenplum 시스템은 DW 시장에 강점을 보이고 있으며, eBay에 적용되어[2] 유명세를 탄 적이 있다. Greenplum과 Aster Data는 모두 기존의 관계형 데이터 모델과 SQL이라는 사용자에게 친숙한 도구를 그대로 살리면서 병렬 클러스터를 이용해서 대용량 데이터 처리를 수행한다. 데이터는 각 DB 노드에 적절하게 분할(partition 혹은 shard)되어 있고, 데이터 분석 SQL을 각 노드에서 병렬로 수행하는 구조이다.
이는 최근 많이 사용되는 MapReduce 프로그래밍 모델과 유사하며, Greenplum과 Aster Data 모두 SQL과 MapReduce를 결합해서 사용하는 기능을 제공한다. 다음은 Greenplum에서 사용하는 SQL과 처리 단계를 보여준다. 각 조건에 따라 데이터들이 분할되어 있으므로 각 DB 노드는 로컬 데이터에 대해서 SQL을 수행하고 (Map 단계로 생각할 수 있다.), 그 결과를 차례로 병합한다. (Reduce 단계로 생각할 수 있다.)



이러한 MPP 혹은 Parallel DBMS와 마찬가지로 대용량의 데이터 분석에 사용되는 기술이 구글이 발표한 MapReduce[3] 방식이다. Yahoo에서 MapReduce 방식의 프레임워크를 구현한 것이 Hadoop이다. 표 1은 Parallel Database와 Hadoop 시스템의 특징을 비교한  것이다.


Hadoop과 RDBMS의 결합 중의 주목할 만한 오픈 소스 프로젝트로 HadoopDB가 있다. HadoopDB는 SQL과 RDBMS를 기본으로 하고 MapReduce를 추가한 Greenplum이나 Aster Data와 달리 Hadoop 시스템을 기본으로 하고 HDFS 대신에 RDBMS를 사용하는 방식이다. HadoopDB가 SQL과 MapReduce를 결합하는 방식 중에 MapReduce 엔진 위에 SQL 기능을 얹은 방식이라면, Aster Data는 In-Database MapReduce라는 개념으로 불리며 SQL 질의에서 MapReduce 함수를 사용하는 방식이다. 좀 더 상세하게는 HadoopDB는 HDFS/Hadoop 시스템에 SQL-like 질의를 해주는 스크립팅 엔진인 Hive(Facebook이 개발하였다.)의 기능을 사용하면서 Map 함수의 입력을 HDFS 파일이 아닌 RDBMS 사용하는 방식이다.



Aster Data에서 사용되는 SQL/MR의 예는 다음과 같다. Java로 sessionize() MR 함수를 구현하고 이를 SQL 질의에 사용한 예이다.


Microsoft에서는 SCOPE라는 프로젝트를 발표한 적이 있는데, Windows와 .NET 환경에서 Hadoop과 같은 MapReduce 처리를 구현한 것이다.

Column-Oriented Databases
Column-oriented DBMS는 데이터를 row 순으로 저장하지 않고 column 순으로 저장하는 시스템이다. 일반적으로 RDBMS의 저장 시스템[4]은 아래 그림과 같이 테이블의 row 즉 레코드를 저장 관리한다. 하나의 디스크 페이지에 여러 레코드가 저장되는 구조이다. 

column store는 테이블의 동일 column 값들을 연속해서 저장 관리한다. 컬럼 별로 파일이 생성되고 디스크 페이지에는 동일 컬럼의 값들이 연속으로 저장되는 구조이다.




다음 표에서 나타낸 row store와 column store의 특징을 보면 column store는 읽기 위주의 대용량 데이터베이스인 DW나 BI, 혹은 IR 응용에 적합한 것을 알 수 있다. 그러나, 쓰기가 빈번한 경우에는 적합하지 않으며, 여러 조건이 주어지더라도 컬럼 하나씩 처리하게 되므로 질의 수행 중의 중간 결과의 크기가 row 방식의 질의 처리에 비해 크고 여러 단계를 거치게 되는 비효율적인 부분도 있다.



Column store의 단점을 보완하기 위해서 (1) Compression, (2) Late materialization[5], (3) Block iteration[6], (4) Invisible join 등의 기법이 사용된다. 그림 5 는 column store에서 SQL이 수행되는 과정을 표현한 것이다.

이상에서 살펴본 바와 같이 column store와 row store가 특성이 다르므로 일반적으로 어느 한 쪽이 일방적으로 좋다고 할 수는 없고 상호 보완적인 관계로, 실질적으로는 둘을 병합하여 사용하는 경우가 많다. Write 오퍼레이션은 row store DBMS에서 수행하고 어느 정도 모아서 column store로 옮긴 후 (이 때 컬럼 압축 등을 수행한다.) read 위주의 분석 작업 등을 수행하는 방식이다.



Stream Processing / ESP or CEP
Stream Processing 혹은 Event Stream Processing 혹은 Complex Event Processing은 실시간으로 변화되는 성격의 데이터를 데이터베이스 형태로 처리하고자 하는 데서 시작되었다. 이를 위해 SQL을 확장한 StreamSQL 표준이 제시되고 있으며, 대표적인 업체인 Truviso는 Continuous Analysis라는 개념으로 snapshot query와 continuous query 기능을 지원한다.[7] 반면에 일반적인 데이터 처리 방식은 외부 이벤트를 데이터베이스에 (변환을 거쳐) 저장하고, 저장이 완료되면 분석 질의를 수행하고, 이후 결과를 얻는 store-first-query-later 방식이라고 할 수 있다.
SQL이 일정 개수의 레코드가 있는 테이블에 대한 연산이라고 한다면 StreamSQL은 테이블을 튜플이 끊임없이 생산되는 (즉 일정 시간에 모든 데이터가 존재하지 않는다.) 스트림으로 보고 처리하는 SQL이다. 다음 그림은 StreamSQL의 시초라고 할 수 있는 Aurora 시스템의 구조를 나타낸 것이다.

요즘은 Stream Processing의 개념을 웹 서비스에 적용하기도 한다. 보통 웹 서비스는 미리 준비된 서비스 DB의 내용을 제공하거나 UCC 데이터를 DB에 저장하고 조회하게 되는데, 이 경우 DB의 변경이 그리 빈번하지는 않다. (아래 그림의 첫 번째) 그러나, 검색이나 로그 분석과 같은 대용량 데이터를 다루는 경우, 실시간 처리를 지향하면서 입력 데이터가 다 주어질 때까지 기다리는 것이 아니라 데이터 입력과 처리가 끊임없이 계속되는 시스템을 만들기도 한다. (아래 그림의 세 번째) 나아가서 웹 서비스의 경우도 센서 디바이스를 통해 데이터가 끊임없이 생산되거나 스마트 폰과 같은 다수의 사용자가 데이터를 생산하고 소비하는 모델에서는 stream processing이 필요하게 된다.




Key-Value Store / MapReduce
요즘의 Key-Value Store의 대명사는 Google의 BigTable 혹은 Amazon의 Dynamo (simpleDB) 일 것이다. 그러나, key-value store는 RDBMS가 있기 전부터 존재하던 아주 전통적인 저장 시스템이다. 예를 들어 UNIX의 dbm 라이브러리라든지 좀 더 발전된 BerkelyDB 등은 꽤 오래 전부터 존재했고 어찌 보면 RDBMS의 전신이라고 할 수도 있다. 요즘은 UNIX의 dbm 라이브러리를 새로 구현한 Tokyo Cabinet이 새로이 주목을 받기도 한다.
전통적인 key-value store와 최근에 웹 서비스 분야에서 각광을 받는 key-value store의 차이는 아마 DFS 기반인가 아닌가 일 것이다. BigTable이나 Dynamo 그리고 Yahoo의 PNUT 등도 모두 분산 환경을 지원한다.  단일 하드웨어 서버(혹은 SAN 같은 스토리지 시스템)로는 필요한 데이터 용량을 감당하지 못하고, 다량의 서버를 사용하는 분산 스토리지가 요구되었고, 분산 스토리지는 서비스 가용성과 부하 분산, 그리고 비용 효율 측면에서 RDBMS에 비해 경쟁력이 있는 저장 시스템이다. 따라서, 웹 서비스 혹은 단수 자료 처리 등에서 사용하기 위해 single key – value pair 정도의 기능을 갖는 extendible hash 형태의 distributed key-value store가 등장하였고 주목을 받고 있다.
Key-value store는 그 특성상 SQL과 같은 강력한 선언적 (declarative) 질의를 사용할 수 없으므로, 이를 보완하고자 MapReduce라는 형태의 프로그래밍 모델도 제안되어 많이 사용되고 있다. 그리고, Amazon의 Dynamo (simpleDB)나 Yahoo의 PNUT (Sherpa)의 예에서 볼 수 있듯이 key-value store는 웹 서비스 개발을 위한 클라우드 DB 서비스로 적합한 구조를 가지고 있다. 대부분 single value 조회이므로 Get/Set 함수와 같은 기본 조작 함수만으로도 사용이 충분하며, HTTP나 REST와 같은 웹 서비스 프로토콜로 인터페이스를 제공하기도 편리하기 때문이다. Key-value store는 단순한 조작과 빠른 성능, 그리고 확장성(scalability)과 가용성(availability)가 중요한 경우에 아주 유용한, RDBMS와는 확연히 다른 영역에 대한 데이터베이스 기술이라고 할 수 있다.
마치며
데이터베이스의 규모가 커짐과 동시에 더욱 빠른 성능이 요구되면서 기존의 전통적인 데이터베이스 기술을 넘어서는 다양한 노력이 진행되고 있다. 하지만, 아직은 Oracle과 같은 상용 RDBMS나 MySQL과 같은 오픈 소스 RDBMS 들이 좀 더 넓은 영역에서 사용되고 있다는 사실만으로도 RDBMS의 몰락을 섣불리 논의할 수는 없다. 오히려 RDBMS를 기반으로 하는 다양한 해법들이 제시되고 있다고 할 수도 있다. 다만, Google의 BigTable이나 Amazon의 Dynamo, 그리고 BerkelyDB나 Tokyo Cabinet 같은 다양한 key-value store, 특히 distributed key-value store의 경우 기존에 없던 다양한 활용 가치가 있는 것은 사실이다. 


1 물론 연구 단계를 넘어 오픈 소스화 하거나 상용화에 성공한 케이스도 많이 있다. 또, 큰 회사들이 자체적으로 만들어 사용하는시스템 들도 많이 있다. 그렇지만, 아직까지는 대표적인 상용 RBDMS인 Oracle을 이겼는가에 대한 답은 하기가 어렵다.

2 Greenplum 자료에 의하면 DB 96 노드로 6.5 PB 크기에, 17 trillion 레코드 규모(매일 150 billion 레코드가 새로 생김)를 처리하고 있다고 한다.

3 MapReduce를 새로운 기술이나 시스템으로 보기 보다는 일종의 프로그래밍 모델 혹은 패턴과 프레임워크라고 하는 것이 적절하다. MapReduce 논문이 특허로 채택되었을 때 컴퓨터 과학에서 수십 년 된 Divide & Conquer 알고리즘 방식과 무슨 차이냐는 논란이 일었었다.

4 DBMS는 저장 시스템(Storage System)과 질의 수행기(Query Processor)로 이루어진다고 볼 수 있다. 저장 시스템은 디스크에 데이터를 효율적으로 저장하는 파일 구조와 일관성을 보장하기 위한 트랜잭션 로깅 및 동시성 제어 등의 기능을 가지고 있다.

5 질의 처리 중간 결과를 매번 생성하지 않고 position (컬럼 내에서의 해당 값 위치) 리스트를 생성해 다음 단계로 넘기는 방식으로 materialization, 즉 디스크에서 실제 데이터를 읽는 비용을 줄이는 기법

6 Vectorized processing 이라고도 함

7 Truviso 역시 PostgreSQL 오픈 소스 DBMS를 확장하여 사용하고 있다. 

[참고 자료]
Massive Parallel Processing / Parallel DBMS
Aster nCluster In-Database MapReduce, Aster Data Systems
SQL/MapReduce: A practical approach to self-describing, polymorphic, and parallelizable user-defined functions, Eric Friedman (Aster Data), VLDB 2009
Greenplum DW Appliance 소개: Technical View, Sun
Sun Oracle Exadata and Database Machine Overview, Oracle, 2009
MAD Skills: New Analysis Practices for Big Data, Jeffrey Cohen (Greenplum), VLDB 2009
HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads, Azza Abouzeid (Yale), VLDB 2009
Osprey: Implementing MapReduce-Style Fault Tolerace in a Shared-Nothing Distributed Database, Christopher Tang (MIT), http://www.dbms2.com
Parallel Database Systems: The Future of Database Processing or a Passing Fad?, David J. DeWitt (UW), 1991
Parallel Database Systems: The Furture of High Performance Database Processing, David J. DeWitt (UW), 1992
Hive - A Warehousing Solution Over a Map-Reduce Framework, Ashish Thusoo (Facebook), VLDB 2009 
HIVE Data warehousing using Hadoop, Facebook Data Team
Column-Oriented Databases
C-Store: A Column-oriented DBMS, Mike Stonebraker (MIT), VLDB 2005
Column-Oriented Database Systems, VLDB 2009 Tutorial
Column-Stores vs. Row-Stores: How Different Are They Really?, Daniel J. Abadi (Yale) , SIGMOD 2008
A Comparison of C-Store and Row-Store in a Common Framework, Alan Halverson (UW), VLDB 2006
Read-Optimized Databases, In Depth, Allison L. Holloway (UW), VLDB 2008
Integrating Compression and Execution in Column Oriented Database Systems, Daniel J. Abadi (MIT), SIGMOD 2006
Query Execution in Column-Oriented Database Systems, Daniel J. Abadi (MIT), MIT 2008
Performance Tradeoffs in Read-Optimized Databases, Stavros Harizopoulos (MIT), VLDB 2006
Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct, Stefan Manegold (CWI), VLDB 2009
MonetDB/SQL Meets SkyServer: the Challenges of a Scientific Database, M. Ivanova (CWI), SSDBM 2007
Sybase IQ, An Evaluation paper by Bloor Research, 2006
The Vertica® Analytic Database Technical Overview White Paper, Vertica Systems Inc, 2008
Key-Value Store / MapReduce
MapReduce: Simplified Data Processing on Large Clusters, Google, OSDI 2004
BigTable: A Distributed Storage System for Structued Data, Google, OSDI 2006
Hive - A Warehousing Solution Over a Map-Reduce Framework, Ashish Thusoo (Facebook), VLDB 2009 
HIVE data warehousing using Hadoop, Facebook Data Team
Hadoop Architecure and its Usage at Facebook, Dhruba Borthakur (Apache), 2009
Data Intensive Super Computing, Randal E. Bryant (CMU)
Cloud Architecture, Jinesh Varia (Amazon Web Services)
GAIA & Neptune, Joon Kim
Hadoop과 오픈소스 소프트웨어를 이용한 비지니스 인텔리전스 플랫폼 구축, 김영우 (다음 커뮤니케이션)
Stream Processing
Toward a Streaming SQL Standard, Namit Jain (Oracle), VLDB 2008
Big Data and Real-time Structured Data Analytics, Ben Lorica (O'Reilly), 2009
Aurora: A New Model and Architecture for Data Stream Management, Daniel J. Abadi (Brandeis University), VLDB 2003
Continuous Analytics technical whitepaper, Truviso, 2010
기타
Handling Large Datasets at Google: Current Systems and Future Directions, Jeff Dean (Google)
Challenges in Building Large-Scale Information Retrieval Systems, Jeff Dean (Google), WSDM 2009
A Large Scale Search Engine System in 2010, Shihua Ming (Yanbian), 2010
PNUTS: Yahoo!’s Hosted Data Serving Platform, Brian F. Cooper, (Yahoo! Research), VLDB 2008
Sherpa: Cloud Computing of the Third Kind, Raghu Ramakrishnan (Yahoo! Research and Platform Engineering Team)
PNUTS - Platform for Nimble Universal Table Storage, http://research.yahoo.com/project/212
Sherpa: Hosted Data Serving | Yahoo! Research, http://research.yahoo.com/node/2139
http://www.microsoft.com/windowsazure/sqlazure
Overview of Microsoft SQL Azure Database, Microsoft, 2009
Simiarities and Differences of SQL Azure and SQL Server, Microsoft, 2009
Introducing the windows azure platform, David Chappell, 2009
http://cassandra.apache.org

+ Recent posts