Graph Database 101

Apache S2Graph

개인적으로 그래프 디비라는 분야에 관심을 가지게 된지도 1년이 되었습니다. 그동안 카카오라는 회사에서 처음에는 Titan이라는 그래프 디비로 테스트 해보다가 문제가 있어서 만들게 된 S2Graph도 개발한지 1년이 되가고, 최근에는 아파치 재단의 인큐베이팅에도 선정 되는등 많은 일이 있었습니다. 카카오라는 회사에서 여러 서비스들에 S2Graph를 적용하면서 가장 힘든 점은 대부분의 개발자들이 그래프 디비가 무엇인지, 어디에 어텋게 사용해야 하는지 낯설어해서 일일히 컨설팅 해주고, 함께 고민해야 한다는 점이였다. 아파치 재단의 소속이 된 기념으로 앞으로는 카카오에 적용했었던 다양한 사용 사례들을 이 블로그에 공유 하도록 하여, 외부에서도 카카오와 같은 환경을 만들수 있게 도움을 주려고 소개 글들을 작성해 보도록 하겠습니다. 이글에서는 가장 처음으로,  개인적으로 그래프 디비를 만들게 된 사용사례인 피드(feed: 수많은 컨텐츠 중에서 특정 사용자에게 보여줄 것만 골라서 구성한 컨텐츠 목록: 이하 피드)라는 문제를 정확히 정의하고, 왜 그래프 디비가 필요하고, 어텋게 문제를 해결 했는지 공유 하겠습니다.

요새 가장 잘 나가는 서비스는 누가 뭐라해도 Facebook일거 같습니다.  그 Facebook의 핵심인 뉴스피드, 사실 Facebook말고도 Pinterest, Twitter 등등의 서비스들은 그 핵심에 피드를 서비스 하고 있죠. 이 글에서는 이러한 피드 시스템을 어떻게 구성 할 수 있는지 크게 Push, Pull방식에 대해서 설명해 보도록 하겠습니다.

Pull: 사용자의 피드들이 read하는 시점에 새로 계산 되는 방식(Read Fanout).

Push: write하는 시점에 모든 피드들이 미리 계산되어 그 결과가 저장 되어 있는 방식(Write Fanout이라는 용어도 사용).

위의 2가지 방식은 각자 장/단점을 가집니다. 이글의 논지 자체가 Push + Pull, 두 가지 다 적절히 사용해야 한다이지만, 상대적으로 Pull방식에 중심을 두고 있는 걸 감안하고 읽어 보길 바랍니다. 

먼저 하나의 사용자 행동 이벤트가 발생 했을 때 그 이벤트를 서비스에서 사용가능하게 어떻게 가공하고, 어떤 형태로 저장해 놓는지 살펴보면 아래와 같습니다. 저장을 어떻게 해놓는지 먼저 살펴 보는 이유는 이 부분이 나중에 서비스에서 사용자가 로그인 했을 때 로그인 한 사용자의 피드를 어떻게 구성하는지를 결정 하기 때문입니다.

기본적인 Push방식

먼저 Push방식에서의 이벤트 처리 및 저장 방식을 살펴 보면 아래 그림과 같은 형태를 가지게 됩니다.

기본적인 Push방식의 workflow

크게 write와 read로 나뉘어져 있는데 먼저 write쪽을 살펴 보면 아래와 같습니다.

Write

사용자의 좋아요라는 이벤트들은 먼저 메세지 큐에 전달되고, 이 메세지 큐를 subscribe하고 있는 워커들이 큐에 들어온 이벤트들을 빼서 처리하는 구조를 많이 사용합니다. 얻어 지는 장점으로는 실제 이벤트의 처리와 이벤트를 받는 부분을 분리 함으로써 이벤트 처리가 장애가 생기거나해도 유실되지 않게 할 수도 있고, 큐에 이벤트가 쌓이는 속도가 워크가 이벤트를 처리하는 속도보다 빠르면 워크를 늘리는등 전체 적인 시스템 throughput을 조절 하기 쉽게 됩니다. 

중요한건 이벤트 처리와 저장소 부분인데요, 저장소에는 일단 모든 사용자는 피드 사서함(그림의 빨간 박스)을 가지고 있습니다. 해당 좋아요를 실제로 한 사용자(진한 갈색)의 친구들(보라색)을 저장소에서 read해서, 친구들(보라색)의 피드 사서함에 저장해 놓는걸 말합니다. 저장소에 저장해야 할 데이터가 친구 수만큼 증폭되서 저장이 되겠죠.

Read

이후에 보라색으로 표시된 Login user가 서비스에 접속 했을 때는 해당 사용자의 feed사서함에 있는 피드들을 보여주게 됩니다. 이때는 단순히 login user를 키로 하는 key/value lookup을 통해서 사용자의 feed를 한번의 read로 구성할 수 있기 때문에 read속도가 빠르게 됩니다. 또 다른 장점으로는 key/value storage는 선택의 폭이 넓다라는 장점이 있습니다. 

단순히 key value lookup이 되기 때문에 사용자에게 보여줄 피드를 다시 계산할 필요가 없어지고, 자연히 서버쪽에서는 크게 할일이 없습니다. 따라서 별도의 처리 없이, 저장소의 클라이언트로써 저장소 자체가 제공하는 throughput을 거의 그대로 얻을 수 있는 장점이 있습니다. 이런 단순한 key value 저장소들은 오픈소스 진영에서 선택해볼 솔루션도 많고, 특히 대부분 초당 처리할 수 있는 lookup이 어마어마하게 좋습니다. 

무슨 솔루션을 사용하던지 쉽게 성능을 보장 할 수 있지만, 문제는 이벤트를 처리해서 저장소에 넣어 놓는 부분입니다. 세상에는 공짜는 없고, 사용자가 들어왔을 때 일을 해야할 대부분의 일을 이벤트 처리와 저장소가 도맡아서 해줘야 하는 구조입니다.

기본적인 Push 방식의 문제점

극단 적으로 말해서 위의 방식은 대부분의 사용자가 로그인을 자주 해서 active user수 / 전체 user수의 비율이 높을 경우 효율적입니다. 왜냐하면 방문하지도 않을 사용자의 피드 사서함까지 모두 데이터를 만들고, 저장해 놓는 방식이기 때문이죠. active user수 / 전체 user수가 10%정도다 라고 하면 90%의 리소스를 방문하지도 않을 사용자들의 피드 사서함을 채우는 일(불필요하지만 위의 구조에서는 어떤 사용자가 방문 할지 모르기 때문에 제거 할 수가 없는)을 하는데 낭비하게 됩니다.

위와 같이 시스템을 만들어서 사용자들이 좋아요를 많이 하고, 그게 피드에 많이 노출 되고...그러면 더 고민할 필요가 없겠죠. 하지만 제 경험상 단일 서비스에서 좋아요 하나만을 가지고 대부분의 사용자의 피드가 구성하기는 상당히 어렵습니다. 이유는 단순히 좋아요라는 행위가 단일 서비스 내에서 잘 발생하지 않기 때문이죠. 페이스북이 like버튼을 외부에 오픈한것도 페이스북 정도의 scale에서도 페이스북 내부에서 발생하는 좋아요만 가지고는 충분한 피드를 구성하기 힘들기 때문이 아니였을까 하는 개인적인 생각입니다. 

다시 본론으로 돌아와서 페이스북 정도의 서비스가 아니라면 좋아요 하나의 사용자 행동만 가지고서는 피드를 충분히 만들어 내지 못하는 문제가 생깁니다. 결과적으로 사용자들의 피드에 노출 되는 컨텐츠가 충분치 않게 되고, 따라서 사용자의 활동(좋아요 등)도 줄어들어 악순환 구조로 들어가게 됩니다.

개선된 Push방식

이 문제를 해결 하기 위해 대부분 다른 행동, 공유, 체크인등등 좋아요 외에 사용자들의 행동중 의미있다고 생각하는 이벤트들을 피드에 추가 하게 됩니다. 기존과 무엇이 달라지는지 이해를 돕기 위해 아래 그림을 참조해 주세요. 

바뀐 점은 사용자들에게 더 많은 피드가 생길 가능성이 생깁니다. 

Write

이벤트를 처리하는 worker가 하는일이 기존에 좋아요 한개에서 좋아요 + 공유 + 체크인으로 늘어났으니 1에서 3으로 증가하게 됩니다. 피드에 반영하고자 하는 사용자의 행동들이 일어나는 횟수만큼 worker는 저장소에 데이터를 저장하는 `일`을 해야 하죠. 여기까진 예상 대로 인데요, 중요한건 저장소 입장에서의 변화입니다. 

기존에는 좋아요 한개가 발생 했을 때 저장소에는 사용자의 친구 수(10명이라고 예를 들어 보죠)만큼의 데이터가 추가 됩니다. 한 사용자가 (좋아요 + 공유 + 체크인), 세 가지 이벤트를 생성 했을 때는...이 사용자의 친구들에게 좋아요도, 공유도, 체크인도 피드 사서함에 저장되어야 하겠죠. 이 말은 3 x 친구 수 만큼의 데이터가 추가 된다는 얘기 입니다. 단지 3개가 추가되는게 아니라는 점이 중요하죠. 예를들어 하루에 100만건의 좋아요가 발생하고, 20만건의 공유, 10만건의 체크인이 일어나는 서비스에서는 친구가 모두 100명이라고 하면 하루에 저장해야 할 데이터는 (100만 + 20만 + 10만) x 100이 되어 1억 3천만개가 되지요. 

좀 더 general하게 얘기 하면 저장소는 위의 그림에서도 볼 수 있듯이 하루에 발생하는 좋아요, 공유, 체크인 이벤트들의 합 x 각각의 이벤트를 발생한 사용자의 친구 수가 됩니다. 여기서 제일 중요한건 이벤트 수와 친구수의 곱하기라는 것입니다. 더하기가 아니라.

또 저장소에 저장되는 데이터 사이즈는 공유 행위 한개를 친구 수만큼, 체크인도 친구수 만큼 저장하게 되니 친구 수가 10명이라고 하면 2 x 10만큼 증가 하게 되죠. 

더 많은 사용자 행위를 피드에 반영하면 할 수록, 저장소에 데이터를 저장하는 worker도 증가 하게 되고 가장 문제는 저장소 자체의 부담이 기하 급수적으로 증가 하게 됩니다. 보통 이 구조를 변경하기 보다는 여기서 피드에 포함될 사용자 행위 자체를 보수적으로 선택하게 되지요. 역시 세상엔 공짜가 없으니 보수적으로 데이터를 조금만 만들어 놓으면 사용자의 피드에 다른 종류의 사용자 액션들이 포함될 확률이 줄어 들겠죠.

피드에 다양한 데이터가 노출되야 다양한 사용자들의 행동이 늘어나고, 그래야만 피드가 다양하고 풍부해 지는데, 피드 자체가 풍부하지 못하다면 이 선순환 고리가 끊기게 되고, 결국 큐레이션된(연령/성별별 인기글) 같은 방식으로 사용자 피드를 구성하게 됩니다. 

Read

변하는게 없습니다. 

기본적인 Pull방식

그럼 Push와 반대(??) 되는 개념인 Pull방식에 대해서 설명해 보도록 하겠습니다.

Push와 차이점은 worker가 친구관계를 아예 read하지 않는 다는 점입니다. 더 중요한 차이점은 write에 하던 일을 read할 때 해야 한다는 점일거 같습니다. 위의 그림에서 가장 중요한 점은 친구 관계 데이터를 write할 때 참조 하는것이 아닌, 사용자가 login했을 때, 즉 read할 때 참조 한다는 점입니다. 그리고 좋아요를 여러 사용자의 친구들의 피드 사서함에 저장하는 것이 아닌, 좋아요를 한 사용자의 activity로 한 개만 저장한다는 점도 중요합니다. Push방식에 비해 저장해야 하는 부담이 훨씬 줄게 되었지만, 사용자가 로그인 했을 때 서버가 해야할 일이 많아진걸 확인 할 수 있습니다. 한마디로 피드 사서함이 없습니다!

Write

해당 이벤트(사용자의 좋아요) 한개를 "이사용자가 이 좋아요를 했다" 라는 의미로 한개만 저장해 놓습니다. 

Read

Push방식에서는 "내가 좋아요를 했는데, 내 친구들한테 다 배달해줘" 였다면, Pull방식에서는 "내 친구들이 좋아요 한걸 다 읽어줘"로 변하게 됩니다. 단순 key/value lookup에서 아래와 같이 두 가지 작업을 동시에 실행 해야 하기 때문에 서버에 부담이 많이 가게 됩니다.

1. stage1: 제일 먼저 로그인 한 사용자의 친구 리스트를 가져오고

2. stage2: 각각의 친구들이 좋아요 한 activity들을 가져 온다.

1번에 끝나봐야 2번을 실행 할 수 있고 이 행동을 그림으로 그려보면 대충(??) 아래와 같은 모양을 가지게 됩니다.

Pull방식에서의 관건은 위의 read path를 얼마나 빠르게 처리 할 수 있느냐가 됩니다. 

Push방식에 비해서 read 속도를 확보하기가 어렵다는 건 당연한데 왜 이런 방식이 존재할 까요?

Pull방식의 특징

1. Push에비해 Pull은 사용자가 피드를 요청할 때 feed를 계산 하기 때문에 저장소사용을 Push에 비해 비약적으로 줄일 수 있습니다.

Push방식과 마찬 가지로 피드에 포함할 사용자의 행동이 다양해 졌을 때 어떻게 되는지 살펴보면 아래와 같은 그림으로 표현 할 수 있습니다.

Pull Basic에 비해서 변경 된 점은 저장소에 기존에 좋아요 이벤트 한개를 저장 하던게 3개(좋아요 + 공유 + 체크인)으로 늘어 난거 밖에 없습니다. 즉 다양한 행동을 feed에 추가 하기 위해서 필요한 worker의 수도 실제 이벤트가 일어나는 횟수 만큼만 증가 하면 되고, 무엇보다 저장소가 저장 하는 데이터 사이즈가 기존에 3 x 친구수였던 거에 비해 그냥 3인 것을 알 수 있죠. 행동 이벤트의 주체가 친구수를 얼마나 가지던, 저장소는 친구수와 상관 없이 이벤트 수만큼만 데이터를 저장 하면 됩니다.

어떤 행동을 feed에 포함할 지 자유로워 지게 되고 관계 자체에도 자유도가 생기게 됩니다.

만약 서비스에서 feed에 친구들의 행동들 뿐만이 아니라 follower의 좋아요나 다른 행동들도 보여 주고 싶다고 예를 들어 보죠. 

Push: 여러 사용자 행동과 여러 관계일 경우

위의 그림에서 Follower라는 관계가 추가 되었고, 기존 (좋아요 + 공유 + 체크인) x 친구 수 만큼의 write가 발생 했다면 여기에 follower라는 관계가 추가 되면 실제 write는 (좋아요 + 공유 + 체크인) x (친구 수 + follower수)가(친구랑 follower가 전부 다르다면) 되겠죠. 

실제로 제가 서비스를 하면서 경험 한 경우는 톡의 친구, 스토리의 친구, 브런치의 follower관계등, 여러 관계들에 사용자들의 행동을 feed로 보여주고자 하는 경우들이 있었습니다. 이럴 경우 Push방식이라면 스토리지와 worker의 증가가 부담 스럽기 때문에 주저 하게 될텐데요, Pull방식일 경우 이런 부담이 적게 됩니다.

Pull: 여러 사용자 행동과 여러 관계일 경우

관계가 추가 된다 하더라도 실제 그 관계를 저장하는 거 외에는 저장소에 추가적으로 저장해야 할게 없습니다. 대신 login 사용자가 feed에 요청을 보내면 그때 읽어들여야 하는 데이터가 많아지게 되죠.

2. Time decay나 dynamic ranking의 제공이 편하게 됩니다.

실제 사용자의 좋아요가 몇일 전에 발생한지에 따라 최근순에 더 높은 점수를 준다던지, video type을 좋아요 했으면 점수를 20점 주고, 이미지면 10점, 텍스트면 1점을 준다던지, 실제로 서비스를 고도 화 하기 위해서는 정렬 로직의 변경이 빈번히 일어 나야 합니다. Push방식에서는 데이터를 write할 때 있는 데이터만 가지고 정렬 로직을 결정해버리기 때문에, dynamic한 score를 제공하기가 힘듭니다. 그래서 대부분의 push방식은 가장 직관적인 score인 최신순을 제공하는데 머물게 됩니다(물론 Push에서도 하려면 할 수 는 있지만 보통 그렇게 까지 develop되는 시스템을 잘 못봤습니다. 세상일이란게 하면 다 할 수 있지만 얼마나 효율적으로 하느냐가 문제이겠죠). 

반면 Pull방식에서는 scoring에 flexibility가 생깁니다. video type이면 몇점을 줄지, 하루 전에 좋아요와 방금전 좋아요를 어떻게 weighting할지, 이런 부분 들이 read에 결정 되기 때문이죠. 대신 read할 때 서버에서 구현해야 하는 복잡도가 증가 됩니다. 흔히 많이 언급되는 Facebook의 초창기 feed모델인 EdgeRank(https://en.wikipedia.org/wiki/EdgeRank)이 대표적인 Pull방식인데요, 최근의 좋아요 일수록, 좋아요 보다는 공유에 더 높은 점수를, 또 좋아요의 대상이 되는 컨텐츠의 type이 비디오면 text보다 더 높은 점수를 받는 식의 scoring방식입니다. 따지고 보면 굉장히 일반적인 얘기 인데, 식만 저런식으로 만든것이죠. 개인적인 의견으로는 식 자체는 너무 당연한 식이고, 실제 저걸 시스템으로 구성하는게 challenge였다고 생각합니다(일반적인 scale이 아닌, Facebook scale에서는 굉장히 challenge한 일이였을 거라고 생각합니다). 이 식에서 각각의 factor들의 weight들은 개인별로도 다를 수도 있고, 이런 것들은 실험을 통해 사용자 feedback(클릭)을 잘 수집해 놔야지만 고도화 할 수 있지 않을까 싶고, 이 부분이 가장 중요하고 어려운 부분이라고 생각합니다. 한번 만들고 끝나는 것이 아닌 끊임없이 실험 해볼 수 있는 환경을 만들어야 한다는 의견입니다. 

Pull방식의 문제점 

위의 까지 설명만 들어 보면 Pull방식이 리소스 사용 효율 측면에서 Push방식에 비해 좋다는걸 알수 있습니다. 그런대도 주변에 Pull방식을 사용하는 곳이 많지는 않은데요, 그 이유는 의외로 간단합니다. 바로 서버에서 read할 때 해야할 일들이 많아져서 서비스 하는데 만족스러운 response time을 확보 하기가 어렵기 때문입니다. concurrency를 극대화 해야지만 Pull방식에서의 읽기 속도가 보장 되는데, 이게 concurrent programming에 익숙하지 않은 개발자들에게는 상대적으로 어려움인거 같습니다. 

결론

Push와 Pull방식 두 가지 다 살펴 보았지만, 실제로 서비스에서는 Push, Pull두 가지 다 적절히 사용해야 한다는게 개인적인 주장입니다. 하지만 개인적으로 Pull방식이 충분하다면(read가 느려져도, 여기서 느리다는 얘기는 10ms ~ 1s) Pull방식이 주가 되어야 한다고 감히(?) 주장합니다.

이유는 위에서도 언급 했듯이       

1. 방문하지도 않을 사용자들의 feed를 만들기 위해 낭비되는 resource를 줄일 수 있다. 

2. 저장소 사용량을 줄일 수 있다 

3. dynamic scoring을 통해 여러 식을 실험 해 볼 수 있고, 사용자의  행동의 종류를 추가 하기 쉽다라는 점을 들 수 있습니다.

개발할 것도 많고, 상대적으로 서버에서 할 일이 많은 Pull방식의 문제를 해결 하기 위해서는 어텋게 해야 할까요?

Graph Database를 사용하시면 됩니다.

위의 친구 관계와 사용자들의 좋아요/공유/체크인 행동들을 하나의 큰 그래프, 차트 그릴 때 나오는 그 그래프가 아닌 점(vertex)과 점들의 연결(edge)로 표현 되는 네트워크로 표현 해 보면 아래와 같습니다.

점과 점들의 연결로 표현 된 사용자 피드

보라색 별이 위의 그림들에서 Login user가 되고, 별에 바로 연결된 노란색 점들이 Login user의 친구들이고, 이 친구들이 최근에 한 행동들(좋아요/공유/체크인)들은 각각의 친구들(노란색 점들)과 주황색 선으로 연결된 파란색 점들로 표현 됩니다.

만약 그래프 디비를 사용하게 되면 처음에 복잡한 Push, Pull의 그림이 아닌, 바로 위의 점과 그들의 연결로 된 그래프로 데이터를 저장하고,  쿼리해 볼 수 있게 됩니다. 

Push나 Pull방식, low level의 구현을 그대로 사용할 수 있겠지만, 성능이 보장 되는 그래프 디비를 사용한다면 “어텋게 저장소에 저장하는가” 가 아닌 “누구랑 누구랑 관계를 만들어 놓을 것인가"를 고민하면 됩니다. 물론 내부적으로 저장 되는 모양은 Push, Pull에서 설명 드린 형태로 저장 되게 되지만요. 

여기서 중요한건 추상화의 단위를 그래프로 변경 해도 직접 Push, Pull방식으로 스토리지에 특화된 형태보다 성능 저하가 있으면 안된다는 점인데요, 이런 부분을 처음부터 염두에 두고 만들어진 그래프 디비가 바로 Apache S2Graph입니다.

추상화 단위를 그래프로 하기 시작하면, 많은 것들이 결국 그냥 관계를 만들어 놓고, 그 연결된 관계들을 이동하면서 필요한 데이터를 필요한 형태대로 가공하는 거라는 걸 느끼게 됩니다.

아직 무슨 말인지 명확히 개념이 안오시는 분들은 직접 적용 사례들을 보시면 이해가 쉬우실거 같아, 앞으로 그래프 디비를 어디에 어텋게 사용할 수 있는지에 대한 시리즈를 카카오에 적용된 서비스들의 예를 통해 알아보고, 그 효과들을 공유 하는 글들을 연재 하도록 하겠습니다.