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
2. 은 같은 데이타를 중복해서 저장하는 방식이다.
   Denormalization을 하면, 테이블간의 JOIN을 없앨 수 있다. NoSQL에서는 JOIN을 지원하지 않기 때문에, 두 테이블을 조인해서 데이타를 가지고 오는 로직을 구현하려면, 각 테이블에서 데이타를 각각 가져와서 애플리케이션에서 합쳐야 하기 때문에, 2번의 IO가 발생한다.
3. 을 적용하여, 하나의 테이블에 JOIN될 데이타를 중복 저장하게 되면 1번의 IO로도 데이타를 가지고 올 수 있다.

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

 

 

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

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

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

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이 되어 있는 테이블을 하나 더 만들어 버리면 된다.

 

 

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

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

장점은

• 성능 향상 – Join을 위해서 몇번씩 쿼리를 하지 않아도 되기 때문에, 당연히 쿼리 성능이 올라간다.
• 쿼리 로직의 복잡도가 낮아짐 – Join에 대한 로직이 필요 없이, 한번에 데이타를 가지고 오기 때문에, 쿼리 로직이 단순해 진다.

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

• 데이타 일관성 문제 발생 가능 – age,sex,zip code등을 insert하거나 update하였을때, User, City 테이블뿐만 아니라 UserZipCode 테이블도 업데이트 해줘야 한다. 만약에 같은 User 테이블을 업데이트 하다가 에러가 났을 경우, UserZipCode 테이블은 업데이트가 안된 상태이면, 양쪽 테이블에 데이타 불 일치성이 발생할 수 있다.
• 스토리지 용량 증가 : 데이타를 중복해서 저장하는 만큼 스토리지 용량이 증가 된다.

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

 

2. Aggregation

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

 

 

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

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

 

 

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

 

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

예를 들어서두개의 테이블이 있고의 컬럼중 하나가로써의 데이타를 가르키고 있다면을 하려면에서로 한를 읽어온 후에를 가르키는 컬럼의 값을로 해서다시에서 쿼리를 해온다

 

 

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

 

참고기능을 이용한

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

 

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

 

 

 

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

 

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

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

 

 

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

 

 

하나의 테이블에 대해서는도원자성을 보장하기 때문에트렌젝션을 보장 받을 수 있다구현 패턴상으로는과 동일한데은 의 을해서을 없애기 위함이고은 트렌젝션 보장을 통한 데이타 불일치성을 해결하기 위함이다

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

 

 

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

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

 

 

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

 

 

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

 

3. Composite Key

이 글을 읽으면서 눈치가 빠른 사람이라면를 정의하는데를 이용하여 복합키를 사용하는 것을 눈치 챘을 것이다에서는 이를 어떻게 정의하느냐가 매우 중요하다특히의 경우에는 이를 이용하여와 같은기능이나을 구현할 수 있다는 하나 이상의 필드를를 이용하여 구분지어 사용하는 방법으로의 복합키와 같은 개념이라고 생각하면 된다단지의 경우에는 여러개의 컬럼을 묶어서로 지정하지만은 한컬럼에를 이용하여 여러개의 키를 묶어서 넣는다

아래의 예제를 보자의 디렉토리를에 저장한다고 하자하위 디렉토리를 가지고 올때부터 쿼리를 해서다음를 반복적으로 쿼리해서가로 시작하지 않을때 까지 읽어오면디렉토리의 하위 디렉토리를 모두 가지고 올 수 있다

 

 

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

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

이값을 으로 했다고 가정하자우리나라에서는만 인구중인만이 서울에 살고 있다그래서 데이타중 약의 키는 로 시작할 것이고대의 서버중에서로 시작하는 키를 저장하는 한대의 서버는의 부하를 처리하게 될것이다서버가대이니까는 각 서버는약의 부하를 처리해야 하는데이건 예상치 보다배 이상 많은 로드를 처리하기 때문에 성능 저하를 유발할 수 있다이런 이유로를 선정할 때는 전체 서버에 걸쳐서 부하가 골고루 분산될 수 있는를 선정하는 것이 좋다

 

4. Inverted Search Index

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

 

 

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

 

 

이렇게의 내용을로 하고의 내용을 반대로로 하는 패턴을라고 한다

 

5. Enumerable Keys

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

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

 

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들에 대한 포인터를 저장하는 방식이다.

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

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

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

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

 

 

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

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

 

3. Materialized Path

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

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

 

 

4. Nested Sets

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

각는 자신이 포함하는 모든들이 포함된와를 저장한다

아래는 전체를 포함하기 때문에번에는의 내용이 된다노드의 경우 자신이 포함하는 모든는에 포함되어 있기 때문에를로 저장한다

 

 

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

위의 예제에서노드 아래에노드를 추가해보자노드의는이 되어야 하고번부터는 모두씩 더해져야 하며의 값 역시 모두 변화 되어야 한다

 

 

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

•  

결론

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

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

1. 데이타 모델링이 80% 이상이다. 선정한 NoSQL과 애플리케이션의 특성에 맞는 데이타 모델링에 집중하자.
2. NoSQL은 어떤 솔루션이 좋다, 나쁘다가 없다. 어떤 솔루션이 특성이 어떻다는 것만 있기 때문에 반드시 데이타 모델과 내부 아키텍쳐 두 가지를 파악한 후에, 애플리케이션의 특성에 맞는 NoSQL을 선정해야 한다.
3. 하나의 NoSQL로 전체 데이타를 저장하려고 하지 마라. NoSQL은 데이타 구조가 매우 다눈하지만, 애플리케이션들은 하나의 단순한 데이타 구조로 저장할 수 없는 데이타가 반드시 존재한다. RDBMS와 혼용하거나, 다른 NoSQL과 혼용하거나 성능면에서는 캐슁 솔루션과 혼용하는 것을 반드시 고려 해야한다.

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