NoSQL 데이타 모델링 #2- 데이타 모델링 패턴

NoSQL 데이타 모델링 #2

Facebook Server Side Architecture Group
http://www.facebook.com/groups/serverside
조대협

NoSQL 데이타 모델링 패턴

NoSQL 데이타 모델링 패턴[1]은 Key/Value 저장 구조에 Put/Get 밖에 없는 단순한 DBMS에 대해서 다양한 형태의 Query를 지원하기 위한 테이블을 디자인하기 위한 가이드 이다.

특히 RDBMS에는 있는

“ Order by를 이용한 Sorting, group by를 이용한 Grouping, Join등을 이용한 개체간의 relationship 정의, 그리고 Index 기능”

들을 데이타를 쿼리하는데, 상당히 유용한 기능인데, NoSQL은 이러한 기능들을 가지고 있지 않기 때문에, NoSQL 내에서 데이타 모델링을 통해서 이러한 기능들을 구현하는 방법에 대한 가이드를 제공한다.

1. 기본적인 데이타 모델링 패턴

NoSQL의 데이타 모델링을 할때, 가장 기본적으로 많이 사용되는 패턴들이다.

1)    Denormalization

Denormalization은 같은 데이타를 중복해서 저장하는 방식이다.
Denormalization을 하면, 테이블간의 JOIN을 없앨 수 있다. NoSQL에서는 JOIN을 지원하지 않기 때문에, 두 테이블을 조인해서 데이타를 가지고 오는 로직을 구현하려면, 각 테이블에서 데이타를 각각 가져와서 애플리케이션에서 합쳐야 하기 때문에, 2번의 IO가 발생한다.

Denormalization을 적용하여, 하나의 테이블에 JOIN될 데이타를 중복 저장하게 되면 1번의 IO로도 데이타를 가지고 올 수 있다.

예를 들어서 사용자 정보를 저장하는 User 테이블과, 도시 이름을 저장하는 City 테이블이 있다고 하자,

이런 테이블 구조에서 “사용자별로 이름,나이,성별,우편번호” 를 출력하는 쿼리는 다음과 같다.

select u.name,u.age,u.sex,c.zipcode from user u,city c where u.city = c.city

이 테이블 구조를 그대로 해서, NoSQL에서 구현하면

select $city,name,age,sex from user where userid=”사용자ID”

select zipcode from city where city=$city

식으로 구현해야 하는데, User 테이블에서 city값을 읽어온 후에, City 테이블에서 앞서 읽어온그래city값을 키로 해서 다시 zip code를 찾아와야 한다. 두번 쿼리를 발생 시킨다. 단순한 예이지만, Join을 해야 하는 테이블 수가 많을때는 NoSQL로의 IO수가 훨씬 더 늘어난다. 이 IO 수를 줄이려면, 아예 처음부터 Join이 되어 있는 테이블을 하나 더 만들어 버리면 된다.

이런식으로 새로운 테이블을 추가하면 된다.

Denormalization을 이용하여 중복을 허용하였을 경우에 장단점은 다음과 같다.

장점은

Ÿ   성능 향상 – Join을 위해서 몇번씩 쿼리를 하지 않아도 되기 때문에, 당연히 쿼리 성능이 올라간다.

Ÿ   쿼리 로직의 복잡도가 낮아짐 – Join에 대한 로직이 필요 없이, 한번에 데이타를 가지고 오기 때문에, 쿼리 로직이 단순해 진다.

   반대로 다음과 같은 단점을 불러온다.

Ÿ   데이타 일관성 문제 발생 가능 – age,sex,zip code등을 insert하거나 update하였을때, User, City 테이블뿐만 아니라 UserZipCode 테이블도 업데이트 해줘야 한다. 만약에 같은 User 테이블을 업데이트 하다가 에러가 났을 경우, UserZipCode 테이블은 업데이트가 안된 상태이면, 양쪽 테이블에 데이타 불 일치성이 발생할 수 있다.

Ÿ   스토리지 용량 증가 : 데이타를 중복해서 저장하는 만큼 스토리지 용량이 증가 된다.

사실 보면 단점도 있지만, NoSQL의 경우 Join이 어렵고, 애플리케이션 적으로 구현을 한다고 해도 성능이 안나오거나 구현이 어려운 경우가 많기 때문에, Denormalization을 통한 중복은 상당히 효과적인 모델링 패턴이 된다.

2)    Aggregation

드롭박스나, 슈가싱크처럼 파일을 저장하는 개인 스토리지 서비스가 있다고 가정하자. 이 서비스는 파일에 대한 정보를 저장하고, 음악,동영상,사진 등의 파일의 종류에 따라서 추가적인 메타 정보를 저장한다. ERD를 기준으로 개체를 표현해보면 다음과 같다.

NoSQL의 재미있는 특성중의 하나가 Scheme-less 또는 Soft Scheme라는 특성인데, RDBMS의 경우 테이블에 데이타를 넣을때, 반드시 테이블의 구조에 맞도록 넣어야 한다. 컬럼수와 이름도 지켜야 하고, 각 컬럼에 해당 하는 데이타 타입도 준수해야 한다 또한 모든 ROW는 같은 컬럼을 가져야 한다.  반면 NoSQL의 경우에는 Key만 똑같다면, 각 Row는 제멋대로라도 상관없다. 꼭 같은 컬럼을 가질 필요도 없고, 데이타 타입도 각기 틀려야 한다. Value에 저장되는 Row 데이타들은 한줄의 Row 구조를 가지기는 하지만, 전체 테이블에 대해서 그 Row 구조가 일치할 필요가 없다. 이를 데이타가 구조는 가지고 있지만, 구조가 각각 틀리는 것을 허용한다고 해서 Soft-Scheme 또는 Schemeless 라고 한다.

이 특성을 이용하면, 위의 데이타 모델을 하나의 테이블로 합칠 수 있다

1:N과 같은 복잡한 엔터티들의 관계를 손쉽게 하나의 테이블로 바꿀 수 있고, 이는 결과적으로 Join의 수를 줄여서 Query 성능을 높이는 방법이 된다.

3)    Application Side Join

NoSQL은 Join이 거의 불가능하다. (지원하는 제품도 있지만). 그래서 Denormalization이나 Aggregation 그리고 앞으로 설명할 데이타 모델링 패턴을 사용하는 것인데, 그래도 어쩔 수 없이 Join을 수행해야할 경우가 있다. 이 때는 NoSQL의 쿼리로는 불가능하고, NoSQL을 사용하는 클라이언트 Application단에서 로직으로 처리해줘야 한다.

예를 들어서 TABLE 1,2 두개의 테이블이 있고, TABLE 1의 컬럼중 하나가 Foreign Key로써 TABLE 2의 데이타를 가르키고 있다면, Application Join을 하려면, Table 1에서 Primary Key로 한 Row를 읽어온 후에, Table 2를 가르키는 컬럼의 값을 Key로 해서, 다시 Table 2에서 쿼리를 해온다.

Application Side Join은 Join이 필요한 테이블 수 만큼 NoSQL로의 Request/Response IO가 발생하는 만큼 다소 부담 스럽기는 하지만, 반대로 Denormalization등에 비해서는 스토리지 사용량을 절약할 수 있다.

참고 : Map & reduce 기능을 이용한 Server Side Join

Application Side Join이 있다면, 반대로 Server Side Join 기능도 있다. NoSQL에는 Join 기능이 없다고 했는데, Server Side Join은 무엇인가?

Riak이나 MongoDB와 같은 일부 NoSQL DB들은 RDBMS의 stored procedure [2]를 지원한다. Map & Reduce [3]라는 이름으로 이 기능을 지원한다. 즉 위에서 Application에서 수행한 로직을 NoSQL 서버들 내에서 수행해서 리턴하는 방식이다. 이 로직들은 NoSQL에서 지원하는 언어를 통해서 구현된후, NoSQL 엔진위에서 수행된다.

이렇게 하면, Application에서 NoSQL로의 호출이 Map & Reduce function 한번만 호출하면 되기 때문에, 네트워크 IO를 줄여서 성능을 향상 시킬 수 있다. 반면, Join에 대한 로직이 NoSQL 서버 쪽에서 수행되기 때문에, 반대로 NoSQL에 대한 부담이 가중된다.

2. 확장된 데이타 모델링 패턴

1)    Atomic aggregation

NoSQL에서 고민해야할 것 중의 하나의 두 개이상의 테이블을 업데이트 할때, 트렌젝션에 관리에 대한 문제이다. 그림과 같이 두개의 테이블을 업데이트 하는 시나리오에서, 1번 테이블을 업데이트 한 후에, 애플리케이션 로직이나 NoSQL의 장애로 인해서 2번 테이블이 업데이트가 되지 않는 문제가 발생할 수 있다.

이 경우 데이타의 일관성 문제를 야기하는데, 이에 대한 해결 방안으로 생각할 수 있는 것은, TABLE 1,2를 하나의 테이블로 합쳐 버리는 것이다.

하나의 테이블에 대해서는 NoSQL도 atomic operation(원자성)을 보장하기 때문에, 트렌젝션을 보장 받을 수 있다. 구현 패턴상으로는 Aggregation과 동일한데, Aggregation은 1:N의 relationship을 aggregate해서 join을 없애기 위함이고, Atomic Aggregation은 트렌젝션 보장을 통한 데이타 불일치성을 해결하기 위함이다.

예를 들어 사용자 정보가 UserAddress,UserProfile,UserId라는 이름의 3개의 테이블로 분산이 되어 있을때, 사용자를 생성하는 경우, 이 3개의 테이블에 Insert를 해줘야 한다. 그러나 테이블이 3개로 분산되어 있기 때문에, 앞에서 언급한 장애시 트렌젝션에 대한 보장이 되지 않는다. 이를 해결하기 위해서 atomic aggregation 패턴을 적용하여, 이 3개의 테이블을 User 테이블의 필드로 집어 넣게 되면, 하나의 테이블이기 때문에, 장애나 에러로 인한 트렌젝션 불일치 문제를 방지할 수 있다.

2)    Index Table

NoSQL을 RDBMS 처럼 Index가 없기 때문에, Key 이외의 필드를 이용하여 Search를 하면, 전체 Table을 Full Scan 하거나 아니면 Key이외의 필드에 대해서는 아예 Search가 불가능하다. 이 문제를 해결하기 위해서 Index를 위한 별도의 Index Table을 만들어서 사용할 수 있는데, 상당히 사용 빈도가 많은 방법이다.

예를 들어, 파일 시스템을 NoSQL에 저장한다고 했을때, 파일 테이블은 다음과 같은 구조를 갔는다.

여기서 특정 디렉토리에 있는 파일만을 리스트업 하고 싶다면, 별도의 Index Table을 다음과 같이 만들면 된다.

Cassandra나 Riak과 같은 일부 NoSQL에는 제품적으로 secondary Index라는 이름으로 Key 이외의 필드를 Index로 지정하는 기능을 가지고 있는데, 이 기능들은 아직까지 성숙되지 못해서, 여기서 설명하는 Index Table을 사용하는 것보다 성능이 나오지 않는다. 만약에 NoSQL에 있는 Secondary Index 기능을 사용할 예정이라면, 반드시 이 Index Table 패턴과 성능을 비교해보기를 추천한다. 당연히 Secondary Index를 이용하면 구현은 조금 편리해질 수 있지만, 성능 차이가 많이 날 수 있다.

3)    Composite Key

이 글을 읽으면서 눈치가 빠른 사람이라면, Key를 정의하는데, “:” deliminator를 이용하여 복합키를 사용하는 것을 눈치 챘을 것이다. NoSQL에서는 이 Key를 어떻게 정의하느냐가 매우 중요하다. 특히 Ordered KV Store 의 경우에는 이를 이용하여 order by와 같은 sorting 기능이나 grouping을 구현할 수 있다. Composite Key는 하나 이상의 필드를 deliminator를 이용하여 구분지어 사용하는 방법으로 RDBMS의 복합키 (Composite primary key)와 같은 개념이라고 생각하면 된다. 단지 RDBMS의 경우에는 여러개의 컬럼을 묶어서 PK로 지정하지만 NoSQL은 한컬럼에 deliminator를 이용하여 여러개의 키를 묶어서 넣는다.

아래의 예제를 보자, PC의 디렉토리를 Ordered KV Store에 저장한다고 하자.
 windows 하위 디렉토리를 가지고 올때, “windows:etc” 부터 쿼리를 해서, 다음 row를 반복적으로 쿼리해서, key가 windows로 시작하지 않을때 까지 읽어오면, windows 디렉토리의 하위 디렉토리를 모두 가지고 올 수 있다.

노드가 추가,삭제되더라도, 내부적으로 sorting이 되기 때문에, 문제없이 사용이 가능하다.

단, Key값을 선택할때 주의해야할 사항은 “특정 서버로의 몰림 현상” 을 들 수 있다. NoSQL은 특성상, N개의 서버로 구성된 클러스터이다. 그리고 데이타는 Key를 기준으로 N개의 서버에 나눠서 저장이 된다. 예를 들어 Key Range가 A~Z 26개라고 가정하고, 클러스터의 서버 수가 26대라고 하면, 각 서버는 Key의 시작으로 사용되는 알파벳 키들의 데이타를 저장한다. 1번은 A로 시작되는 Key 데이타들, 2번은 B로, 3번은 C로 등등.

이 Key 값을 “City:User Name”으로 했다고 가정하자, 우리나라에서는 5000만 인구중, 1/5인 1000만이 서울에 살고 있다. 그래서 데이타중 약 20%의 키는 “Seoul:xxx”로 시작할 것이고 26대의 서버중에서 S로 시작하는 키를 저장하는 한대의 서버는 20%의 부하를 처리하게 될것이다. 서버가 26대이니까는 각 서버는 1/26 (약 3.8%)의 부하를 처리해야 하는데, 이건 예상치 보다 5배 이상 많은 로드를 처리하기 때문에 성능 저하를 유발할 수 있다. 이런 이유로, Key를 선정할 때는 전체 서버에 걸쳐서 부하가 골고루 분산될 수 있는 Key를 선정하는 것이 좋다.

4)    Inverted Search Index

검색엔진에서 많이 사용하는 방법인데, 검색엔진은 사이트의 모든 페이지를 검색 로봇이 검색해서 문서내의 단어들을 색인하여 URL에 맵핑해서 저장해놓는다.

검색은 단어를 키로 검색이 되기 때문에, 위의 테이블 구조에서는 value에 검색 키워드들이 들어가 있기 때문에, 효과적인 검색을 할 수 없다. 이 검색 키워드를 키로 해서 URL을 value로 하는 테이블을 다시 만들어 보면, 아래와 같은 식으로 표현되고, 검색 키워드로 검색을 하면 빠르게, 검색 키워드를 가지고 있는 URL을 찾아낼 수 있다.

이렇게 value의 내용을 key로 하고, key의 내용을 반대로 value로 하는 패턴을 inverted search index라고 한다.

5)    Enumerable Keys

NoSQL 솔루션에 따라서, RDBMS의 Sequence와 같은 기능을 제공하는 것들이 있다. 이 기능들은, 키에 대해서 자동으로 카운터를 올려주는 기능을 가지고 있다. (예를 들어 첫번째 키는 1, 두번째 키는 2,다음은 3,4,5 식으로 순차적으로 연속된 키를 부여해주는 기능).

이 기능은 데이타에 대한 traverse 기능을 제공한다. 즉, 100번 키를 가지고 왔는데, 이 앞뒤의 값을 알 수 있다. Sequential한 키를 사용했기 때문에, 당연히 앞의 키값은 99, 다음 키값은 101로 해서 값을 가지고 올 수 있다.

3. 계층 데이타 구조에 대한 모델링 패턴

NoSQL들은 데이타 모델이 KV,Ordered KV,Document들 여러가지가 있기는 하지만, 기본적으로 row,column을 가지고 있는 테이블 구조 저장구조를 갖는다. 애플리케이션 개발중에는 이런 테이블 구조뿐만 아니라 Tree와 같은 계층형 데이타 구조를 저장해야 할 경우가 있는데, 테이블 구조의 저장 구조를 갖는 NoSQL의 경우 이러한 계층형 구조를 저장하는 것이 쉬운일은 아니다.

RDBMS의 경우에도 이런 계층형구조를 저장하기 위해서 많은 고민을 했는데, RDBMS 솔루션에서 기능적으로 자체 지원할 수 도 있고, 데이타 모델링을 통해서도 이러한 계층형 구조를 저장할 수 있다.

여기서 소개하는 NoSQL에서 계층형 구조를 저장하는 기법은 RDBMS에서 사용하는 기법들을 많이 참고하였다. 추가적인 기법은 RDBMS의 Tree구조 저장 기법을 참고하기 바란다.

1)    Tree Aggregation

Tree 구조 자체를 하나의 Value에 저장하는 방식이다. JSON이나 XML 등을 이용하여, 트리 구조를 정의 하고, Value에 저장하는 방식이다.

Tree 자체가 크지 않고, 변경이 많이 없는 경우에는 사용하기 좋다. “계층형 게시판의 답글 Tree 구조” 등을 저장하기에 용이하다.

2)    Adjacent Lists

Adjacent List 구조는, 전통적인 자료 구조에서 사용하는 Linked List와 같은 자료 구조형을 사용하여, 각 Tree의 노드에 parent node에 대한 포인터와 child node들에 대한 포인터를 저장하는 방식이다.

Tree의 내용을 검색하려면, root 노드에서 부터 child node를 child node 포인트를 이용하여, 값을 가져오는 방식이다. (이를 Tree traversing 이라고 한다.)

특정 노드만 알면, 해당 노드의 상위, 하위 노드를 자유롭게 traversing할 수 있어서 traversing에는 장점을 가지고 있지만, 반대로, 하나의 노드를 이동할 때마다, 포인터를 이용해서 매번 쿼리를 해와야 하기 때문에, Tree의 크기가 크다면 NoSQL로의 IO가 엄청나게 많이 발생한다. (트리의 노드 수가 N이면, N번 쿼리를 해야 한다)

아래 그림을 보자, 파일 디렉토리를 저장하는 자료 구조를 만든다고 했을때, Directory라는 테이블을 정의하고, 이 테이블에는 directory 명과, 해당 directory의 상하위 디렉토리 이름을 저장하도록 한다.

이를 바탕으로 테이블에 저장된 데이타를 보면 아래와 같다.

구현이 쉬운 편이긴 하지만 Tree 구조 traverse에 많은 IO를 유발하기 때문에, 큰 Tree구조를 저장하거나 잦은 read가 있을때는 권장하지 않는다.

※     RDBMS 의 경우에는 이런 Tree 구조 traversing을 지원하기 위해서 recursive 쿼리에 대해서 native recursive function을 지원함으로써, tree 구조 저장을 지원하는 경우도 있다.

3)    Materialized Path

Materialized Path는 Tree 구조를 테이블에 저장할때, root에서 부터 현재 노드까지의 전체 경로를 key로 저장하는 방법이다.

이 방법은 구현에 드는 노력에 비해서 매우 효율적인 저장 방식이다. 특히 Key에 대한 Search를 할때, Regular Expression을 사용할 수 있으면, 특정 노드의 하위 트리등을 쿼리해 오는 기능등 다양한 쿼리가 가능하다. 일반적은 KV나 Ordered KV에서는 적용하기는 힘들지만, MongoDB와 같은 Document DB는 Regular Expression을 지원하기 때문에, 효과적으로 사용할 수 있다.

4)    Nested Sets

Netsted Set의 기본원리는 Node가 포함하는 모든 Child Node에 대한 범위 정보를 가지고 있다. 먼저 예를 보고 설명하자. 각 Node는 배열이나 리스트에 Sorting된 형태로 저장되어 있다.

각 Node는 자신이 포함하는 모든 Sub Tree (Child Node)들이 포함된 start와 end index를 저장한다.

아래 A는 전체 Sub Tree를 포함하기 때문에 2~9번에는 A Sub Tree의 내용이 된다.
C 노드의 경우 자신이 포함하는 모든 Child Node는 4~9에 포함되어 있기 때문에, Index를 4~9로 저장한다.

각 노드만 안다면, Sub Tree를 start,end index만 있으면 쭈욱 읽어오면 되기 때문에 매우 빠른 성능을 보장할 수 있다. 단 이 데이타 구조 역시 update에 취약하다. update가 발생하였을 경우, Index를 다시 재배열해야 하기 때문에 이에 대한 로드가 매우 크다.

위의 예제에서 B 노드 아래에 J 노드를 추가해보자, J 노드의 index는 3이 되어야 하고, 3번 Index부터는 모두 +1 씩 더해져야 하며, Child Node의 값 역시 모두 변화 되어야 한다.

트리 생성 후에, 변화가 없는 대규모 트리등을 저장하는데 유용하게 사용할 수 있다

.

결론

지금까지 몇가지 NoSQL 적용시 사용할 수 있는 데이타 모델링 패턴에 대해서 살펴보았다. 기본 패턴은 대부분의 NoSQL 솔루션에 적용할 수 있으며, 확장된 모델링 패턴의 경우에는 NoSQL이 지원하는 기능이나 데이타 구조 (KV, Ordered KV,Document etc)에 따라서 적용할 수 있다.

NoSQL을 이용한 시스템을 개발할때는

1.     데이타 모델링이 80% 이상이다. 선정한 NoSQL과 애플리케이션의 특성에 맞는 데이타 모델링에 집중하자.

2.     NoSQL은 어떤 솔루션이 좋다, 나쁘다가 없다. 어떤 솔루션이 특성이 어떻다는 것만 있기 때문에 반드시 데이타 모델과 내부 아키텍쳐 두 가지를 파악한 후에, 애플리케이션의 특성에 맞는 NoSQL을 선정해야 한다.

3.     하나의 NoSQL로 전체 데이타를 저장하려고 하지 마라. NoSQL은 데이타 구조가 매우 다눈하지만, 애플리케이션들은 하나의 단순한 데이타 구조로 저장할 수 없는 데이타가 반드시 존재한다. RDBMS와 혼용하거나, 다른 NoSQL과 혼용하거나 성능면에서는 캐슁 솔루션과 혼용하는 것을 반드시 고려 해야한다.

NoSQL은 놀라온 성능과 확장성을 제공하지만, 많은 연구와 노력이 필요하다. Oracle과 같은 데이타베이스를 사용할때도, 전문 DBA를 두고, 튜닝에 시간을 두고, 데이타 모델을 가꾸고, 튜닝을 하지 않는가? NoSQL이 오픈소스를 중심으로 사용되고 있지만, 오픈 소스라서 쉬운게 아니다. 그만큼 많은 투자와 연구와 노력이 필요한 만큼, 신중하게 검토하고 도입을 결정하기를 바란다.

---

[1] 참고 자료
http://highlyscalable.wordpress.com/2012/03/01/nosql-data-modeling-techniques/
http://www.allbuttonspressed.com/blog/django/2010/09/JOINs-via-denormalization-for-NoSQL-coders-Part-2-Materialized-views

http://www.ebaytechblog.com/2012/07/16/cassandra-data-modeling-best-practices-part-1/

 

[2] RDBMS에서 프로그래밍 언어를 이용해서 구현된 사용자 정의 데이타 Query 함수. 예를Oracle 들어 RDBMS의 경우에는 PL/SQL이라는 프로그래밍 언어를 이용하여, 데이타 베이스에 대한 비지니스 로직을 구현해서 저장해놓고, 클라이언트에서 이 함수를 호출해서 사용하게 할 수 있다.

[3] Map & Reduce는 Input 데이타를 여러 조각으로 쪼갠 후, 여러대의 서버에서 각 데이타 조각을 처리한후(Map), 그 결과를 모아서 (Reduce) 하나의 결과를 내는 분산 처리 아키텍쳐 이다.

링크 

NoSQL 데이타 모델 및 데이타 모델링 절차 : http://bcho.tistory.com/665

참고 자료 http://www.pearltrees.com/#/N-u=1_752336&N-p=53126547&N-play=1&N-fa=5793524&N-s=1_5827086&N-f=1_5827086