원글 링크 : https://brunch.co.kr/@kakao-it/305
그래프 DB
- 그래프 DB에서는 모든 데이터가 버텍스(Vertex)와 엣지(Edge)로 표현된다.
- 버텍스는 객체의 정보를 담고 있으며,
- 객체 간의 관계(relation)은 엣지로,
- 엣지에 속성(property)을 추가하여 의미 있는 정보를 표현할 수 있게 된다.
그래프 DB의 특징
- 가장 큰 장점은 인덱스를 이용하지 않아도 연결된 노드를 찾는 것이 빠르다는 것
- index free adjacency - 노드와 노드간의 관계를 이용해 인접한 관계를 찾는 기능
- 관계를 이용한 정보를 탐색하는데 강력하고, 관계형 데이터베이스보다 관계를 표현하는데 있어 더 직관적이며, 왜곡 없이 표현할 수 있음
- RDBMS에서 10개 이상의 테이블을 조인하게 되면 테이블의 사이즈, 데이터 양, 조인 순서들 등 많은 부분을 고려하여도, 성능저하가 발생하는 것을 막을 수가 없지만, GraphDB는 이런 복잡한 연산을 처리하는데 적합한 그래프 이론을 알고리즘으로 채택하고 있음
- 다른 NoSQL과 마찬가지로 스키마가 없는 구조로 되어있으며, 반정규화된 데이터를 처리하는데 적합함
- 노드는 RDBMS의 테이블과 비교할 수 있는데, 노드는 테이블이 행/열의 데이터를 가지고 있는 것과 같은 속성을 가지고 있음
그래프 DB를 사용하면 좋은 경우
- 4 ~ 6개 이상의 테이블을 이용하는 복잡한 질의를 해야한다면 GraphDB가 좋은 대안이 될 수 있음
- index free adjacency를 이용해 해당 노드에 연결된 관계들만 탐색함. (패턴이 일치하지 않는 것들은 무시하고 넘어가기 때문에 연결된 패턴을 찾는데 있어서는 매우 빠른 속도를 보장)
- 노드의 데이터 크기와 쿼리의 성능이 독립적이기 때문에 데이터 사이즈가 늘어난다고 해서 성능의 저하가 발생하지 않음
- 대부분의 연산이 시작과 끝 점에 대한 정보만 알면 그래프 이론을 적용하기만 하면 됨
그래프 DB를 사용하지 말아야 하는 경우
- GraphDB에서 피해야하는 작업은 대규모 집합지향 쿼리, 글로벌 그래프 작업, 간단한 집계 중심 질의
- 여러 항목을 확인하는데 있어 많은 조인과 집계 연산이 필요하지 않고 단순히 데이터를 취합하는데 사용한다면 관계형 데이터베이스보다 나은 성능을 제공한다고 할 수 없음
- 로컬 그래프를 처리하는데 있어서는 뛰어나지만, 노드 클러스터를 찾고, 노드 사이의 알려지지 않은 관계 패턴을 발견하고 그래프 구성요소의 중심 및 구역 사이를 정의하는 작업, 즉 그래프 전체를 보는 글로벌 그래프 작업에는 성능적으로 많은 자원과 시간을 소모함
- 앞서 말했듯 GraphDB는 복잡한 연산에 최적화 되어 있는데, 반대로 복합성이 낮은 단순한 구조의 간단한 질의들이 GraphDB에서는 상당히 비효율적으로 처리됨
S2Graph
- S2Graph는 카카오의 서비스에 적용되고 있는 대용량 분산 그래프 데이터베이스
- 스칼라 언어 기반
- Hbase, Kafka, Spark 등의 기술이 적용
- 이전에는 MySQL을 사용했으나, 늘어나는 서비스를 기존 구조로 유지하는데 한계가 있어 도입한 그래프 DB
마스터 그래프
- 마스터 그래프
- 사용자의 활동에 따라 데이터가 누적되고, 엣지에 속성을 적용하여 그래프로 구성 한 것을 뜻함
- 사용자의 활동 - 액션 타입(action type)으로 정의
- 활동에 따라 묶어내어 액티비티(activity)라고 칭함
- 모델(model)
- 데이터를 사용하여 어떤 질의에 답을 줄 수 있는 프로그램
GraphQL
- 페이스북이 개발하여 발표한 데이터 쿼리 언어
- 사용자가 데이터에 대해 쿼리를 보낸 내용은 서버 사이드에서 동작하여 처리해 줌
- 특정 DB나 엔진에 종속되지 않는 시스템
- 데이터와 모델을 한 번에 쿼리로 처리할 수 있다.
직관적인 쿼리 구성
- 처음에는 아파치 하이브 쿼리로 모든 작업을 처리하였지만, 구성이 아주 비효율적
- GraphQL을 사용하여 쿼리를 지원하게 되었고, 쿼리를 보내는 측에서는 출력되는 값이 드루이드(apache druid, 통계 시스템)에서 온 자료인지, 또는 다른 모델에서 계산되어 출력된 값인지 구분할 필요가 없도록 구성
- 데이터 단과 쿼리 단을 완전히 분리하여 개발 자유도를 높이기 위한 설계
- GraphQL을 지원하고 모델 embedding을 지원하게 되면서 표준화된 interface로 데이터와 모델의 결과를 함께 조회 가능하게 됨
원글 링크 : https://brunch.co.kr/@yoondoyung/4
그래프 DB를 만들게 된 이유
피드(feed: 수많은 컨텐츠 중에서 특정 사용자에게 보여줄 것만 골라서 구성한 컨텐츠 목록)
메이저 SNS 서비스들은 그 핵심에 피드를 서비스하고 있죠.
이 글에서는 이러한 피드 시스템을 어떻게 구성할 수 있는지 Push, Pull 방식에 대해 알아보도록 하겠습니다.
- Push
- write하는 시점에 모든 피드들이 미리 계산되어 그 결과가 저장되어 있는 방식(Write Fanout)
- Pull
- 사용자의 피드들이 read하는 시점에 새로 계산되는 방식(Read Fanout)
두가지 방식은 각자 장단점을 가지므로 적절히 섞어 사용해야합니다.
기본적인 Push 방식
크게 write와 read로 나뉘어져 있는데 먼저 write부터 살펴봅시다.
write
사용자의 좋아요 이벤트들은 메시지 큐에 전달되고, 이 메시지 큐를 subscribe하고 있는 워커들이 큐에 들어온 이벤트들을 빼서 처리하는 구조를 많이 사용함
- 장점
- 실제 이벤트의 처리와 이벤트를 받는 부분을 분리함으로써 이벤트 처리에 장애가 생겨도 유실되지 않음
- 큐에 이벤트가 쌓이는 속도 > 워커가 이벤트를 처리하는 속도일때 워커를 늘릴 수 있음(throughput 조절이 쉬움)
- 이벤트 처리와 저장소 부분 - 중요
- 저장소에 있는 모든 사용자는 피드 사서함(그림의 빨간 박스)을 가지고 있음.
- 해당 좋아요를 실제로 한 사용자(진한 갈색)의 친구들(보라색)을 저장소에서 read해서, 좋아요 이벤트를 친구들(보라색)의 피드 사서함에 저장해 놓는 것을 말함
- 저장소에서 저장해야할 데이터가 친구 수만큼 증폭되서 저장이 됨
read
이후에 보라색으로 표시된 Login user가 서비스에 접속 했을 때는 해당 사용자의 feed 사서함에 있는 피드들을 보여주게 됩니다.
- 이 때 단순히 login user를 key로 하는 key/value lookup을 통해서 사용자의 feed를 한번의 read로 구성할 수 있기 때문에 속도가 빠름
- 따라서 사용자에게 보여줄 피드를 다시 계산할 필요가 없고, 서버 쪽에서 크게 할일이 없음
- 저장소 자체가 제공하는 throughput을 거의 그대로 얻을 수 있는 장점이 있음
문제는 이벤트를 처리해서 저장소에 넣어 놓는 부분입니다.
사용자가 들어왔을 때 대부분의 일을 이벤트 처리와 저장소가 도맡아서 해줘야하는 구조입니다.
기본적인 push 방식의 문제점
- 위의 방식은 대부분의 사용자가 로그인을 자주 해서 actie user 수 / 전체 user 수의 비율이 높을 경우 효율적
- 방문하지도 않을 사용자의 피드 사서함까지 모두 데이터를 만들고 저장해 놓는 방식이기 때문
- 리소스 낭비가 우려됨
- 페이스북 정도의 서비스가 아니라면 좋아요 하나의 사용자 행동만 가지고서는 피드를 충분히 만들어내지 못함
- 결과적으로 사용자들이 피드에 노출 되는 컨텐츠가 충분치 않음
- 사용자의 액티비티 종류(좋아요 등)도 줄어들어 악순환 구조가 만들어짐
개선된 Push 방식
문제를 해결하기 위해 다른 행동, 공유, 체크인 등등 이벤트들을 피드에 추가하게 됩니다.
write
- 기존에는 좋아요 한개가 발생 했을 때 저장소에는 사용자의 친구 수(ex. 10명)만큼의 데이터가 추가 됩니다.
- 한 사용자가 세 가지 이벤트를 생성했을 때는.. 친구 수 만큼의 데이터가 추가 된다는 얘기입니다.
- 따라서 필요한 저장소의 크기는 발생하는
(좋아요 + 공유 + 체크인 이벤트들의 합) * 각각의 이벤트를 발생한 사용자의 친구 수가 됩니다. 여기서 제일 중요한건 이벤트 수와 친구 수의 곱하기라는 것입니다.
더 많은 사용자 행위를 피드에 반영할 수록, 저장소에 데이터를 저장하는 worker도 증가 하게 되고 가장 큰 문제는 저장소의 부담이 기하급수적으로 증가하게 됩니다.
보통 이 구조를 변경하기 보다는 피드에 포함될 사용자 행위 자체를 보수적으로 선택하게 되고, 결국 큐레이션된(연령/성별별 인기글) 같은 방식으로 사용자 피드를 구성하게 됩니다.
read
변하는게 없습니다.
기본적인 Pull 방식
- Push와의 차이점
- worker가 친구 관계를 아예 read하지 않는다는 점
- write에 하던 일을 read할 때 해야한다는 점
- 친구 관계 데이터를 write 할 때 참조하는 것이 아닌, 사용자가 login 했을 때, 즉 read할 때 참조 한다는 점
- 좋아요를 여러 사용자의 친구들의 피드 사서함에 저장하는 것이 아닌 한 사용자의 activity로 한 개만 저장함
- 피드 사서함이 없어져 저장해야하는 부담 저하, 사용자가 로그인 했을 때 서버가 해야할 일이 많아짐
write
"어떤 사용자가 좋아요 이벤트를 수행했다"라는 의미로 해당 이벤트(사용자의 좋아요) 한 개의 데이터만 저장해놓음
read
- Push
- "내가 좋아요를 했는데, 내 친구들한테 다 배달해줘"
- Pull
- "내 친구들이 좋아요 한걸 다 읽어줘"
단순 key/value lookup에서 아래와 같이 두 가지 작업을 동시에 실행 해야 하기 때문에 서버에 부담이 많이 가게 됩니다.
- stage1 - 제일 먼저 로그인 한 사용자의 친구 리스트를 가져오고
- stage2 - 각각의 친구들이 좋아요 한 activity들을 가져온다.
1번이 끝나야 2번을 실행 할 수 있고, 이 행동을 그림으로 그리면 아래와 같은 모양을 가지게 됩니다.
Pull 방식에서의 관건은 위의 read Path를 얼마나 빠르게 처리할 수 있느냐가 됩니다.
Push 방식에 비해서 read 속도를 확보하기가 어렵다는 건 당연한데 왜 이런 방식이 존재할까요?
Pull 방식의 특징
1. 사용자가 피드를 요청할 때 feed를 계산하기 때문에 Push에 비해 저장소 사용을 비약적으로 줄일 수 있음
피드에 포함할 사용자의 행동이 다양해 졌을 때를 도식화 하면 다음과 같이 표현할 수 있습니다.
- 기존에 좋아요 이벤트 한개를 저장하던게 공유, 체크인을 포함한 3개로 늘어난 거 밖에 없습니다.
- 다양한 행동을 feed에 추가하기 위해서 필요한 worker의 수도 실제 이벤트가 일어나는 횟수 만큼만 증가하면 되고, 무엇보다 저장소가 저장하는 데이터 사이즈가 기존 3 * 친구수였던 거에 비해 그냥 3인 것을 알 수 있습니다.
- 어떤 행동을 feed에 포함할 지 자유로워 지게 되고 관계 자체에도 자유도가 생기게 됩니다.
feed에 친구들의 행동들 뿐만 아니라 follwer의 좋아요나 다른 행동들도 보여 주고 싶다면
- push의 경우
- Follower라는 관계가 추가 됨
- 실제 wirte는
(좋아요 + 공유 + 체크인) * (친구 수 + follower 수, 친구와 follwer가 전부 다르다면) - 스토리지와 worker의 증가가 부담스러움
- pull의 경우
- 추가된 관계 외에는 외에는 저장할 것이 없음
- 대신 로그인한 사용자가 feed를 구성하기 위해 읽어들여야 하는 데이터가 많아짐
2. Time decay나 dynamic ranking의 제공이 편함
- Push 방식에서는 write 할 때 있는 데이터만 가지고 정렬 로직을 결정하기 떄문에, dynamic한 score를 제공하기가 힘듬
- 반면 Pull 방식에서는 read 시에 정렬 로직을 선택하기 때문에 scoring에 유연성이 생김
Pull 방식의 문제점
- 서버에서 read할 때 해야 일들이 많아져서 서비스 하는데 만족스러운 response time을 확보하기가 어려움
- 동시성(Concurrency)을 극대화 해야지만 Pull 방식에서의 읽기 속도가 보장되는데 동시성 프로그래밍에 익숙하지 않은 개발자들에게 어려움
결론
Push, Pull 두 가지를 다 적절히 사용해야하지만 Pull 방식이 충분하다면 Pull 방식을 사용하는 것이 좋다.
1. 방문하지도 않은 사용자들의 feed를 만들기 위해 낭비되는 resource를 줄일 수 있다.
2. 저장소 사용량을 줄일 수 있다.
3. dynamic scoring을 통해 여러 식을 실험 해 볼 수 있고, 사용자의 행동의 종류를 추가하기 쉽다.
Pull 방식의 문제를 해결하기 위해서는?
GraphDB를 사용하시면 됩니다.
친구 관계와 사용자들의 행동들을 하나의 큰 그래프 네트워크로 표현해보면 아래와 같습니다.
- 보라색 별 - Login user
- 별에 바로 연결된 노란색 점 - Login user의 친구들
- 주황색 선으로 연결된 파란색 점들 - 친구들이 최근에 한 행동들
GraphDB를 사용하게 되면 복잡한 Push, Pull의 그림이 아닌 점과 그들의 연결로 된 그래프로 데이터를 저장하고, 쿼리해 볼 수 있게 됩니다.
"어떻게 저장소에 저장하는가"가 아닌 "누구랑 누구랑 관계를 만들어 놓을 것인가"를 고민하면 됩니다.
여기서 중요한건 추상화의 단위를 그래프로 변경 해도 직접 Push, Pull 방식으로 스토리지에 특화된 형태보다 성능 저하가 있으면 안되다는 점인데요, 이런 부분을 처음부터 염두에 두고 만들어진 GraphDB가 바로 Apache S2Graph입니다.
추상화 단위를 그래프로 하기 시작하면, 많은 것들이 결국 그냥 관계를 만들어 놓고, 그 연결된 관계들을 이동하면서 필요한 데이터를 필요한 형태대로 가공하는 거라는 걸 느끼게 됩니다.
