Tinder의 지리 기반 추천 Part 1
Tech Review of Tinder #1
Geosharded Recommendation Part 1: Sharding Approach
Tinder는 소셜 디스커버리 서비스로 사용자의 위치를 기반으로 하는 소셜데이팅 어플리케이션입니다. 사용자 주변에 있는 소셜데이팅의 대상이 될 사용자들을 추천하고, 매칭시켜주는 서비스입니다. 사용자는 swipe, like, super like 등을 통해 feedback을 줄 수 있으며, 이러한 사용자의 preference와 위치 정보를 기반으로 소셜데이팅 서비스를 제공합니다.
이번 리뷰에서는 전세계에서 발생하는 수억건의 쿼리를 처리하고, 수많은 사용자들을 서비스에서 다루는데 있어 어떠한 방식으로 추천을 실시간에 효율적으로 하는지 알아보겠습니다. 추천 알고리즘 그 자체라기 보다는 조금은 시스템적으로 어떻게 대용량 데이터를 잘 처리할 수 있을지에 대한 글 입니다. Tinder라는 서비스의 특성과 그 특성을 기반으로 한 문제 해결점을 잘 제시하여 주었다는 생각이 듭니다.
Introduction
Tinder의 폭발적인 성장의 초기단계에서, engineering 팀은 검색은 실시간 추천을 하는 데 있어 중요한 요소라는 것을 확인하였다. 그 이후로 그것은 Tinder 추천 시스템의 중요한 요소가 되었다.
Tinder의 검색 아키텍처는 간단하다. 하나의 인덱스가 있는 Elasicsearch 클러스터와 5개의 기본 shard이. 우리는 이렇게 몇 년 동안 운영하며, 필요에 따라 몇 개의 replica와 node들을 추가하였다. 시간이 지남에 따라, shard를 늘리고 더 많은 replica를 추가하여 대기 시간을 줄였다. 우리는 CPU 활용률과 높은 인프라 비용을 살펴보았을 때, 우리의 디자인이 더 이상 확장 기대치를 충족시키지 못할 것이라는 것을 알고 있었다.
Tinder의 추천은 위치 기반이며, 최대 100마일까지 지원한다. California에서 사용자가 사용하는 경우, 우리는 런던의 사용자를 포함할 필요가 없다. 또한 인덱스의 크기는 인덱싱, 검색 용량과 대규모 테스트에서의 성능에 대해 영향을 미친다는 것을 알게 되었다. 인덱스 크기가 감소하면, 성능은 선형적으로 증가하였다. 우리가 지역을 기반으로 한 더 많은 shard들(geosharded)를 생성한다면, 그것들은 각각의 작은 sub-index를 생성하고 성능을 증가시킬 것이다. 이러한 지식을 가지고 우리는 다음과 같은 질문을 했다. 우리는 어떻게 이것을 해낼 수 있을까?
추천 시스템을 비롯한 데이터 기반의 서비스 시스템을 구축하는데 있어 가장 중요한 점은 그 서비스의 본질을 파악하는 것이라는 생각이 듭니다. 그렇게 해야 그 데이터 특성에 맞추어 시스템을 효율적으로 설계할 수 있기 때문입니다. Tinder는 무조건 사용자의 입력으로 위치를 받고 있기 때문에 이 특성을 가장 깊게 고려하여 시스템을 잘 설계하였다는 생각이 듭니다.
우선 간단한 용어 설명을 하나 하겠다. Elasticsearch는 shard라 불리는 다중 데이터 노드를 가지고 있다. 이번 글에서는 우리는 "geoshard"라는 용어를 위에 덧붙인 sharding을 나타내기 위해 사용하고, "shard"는 일반적인 shard를 설명하는 데 사용할 것이다.
Sharding Approach
Sharding은 같은 형태의 데이터를 여러 개로 나누어 저장하는 방법을 의미합니다. 정확히는 같은 스키마를 지닌 데이터를 다수의 데이터베이스에 분산하여 저장하는 방법입니다. 데이터 파티셔닝 기술 중 하나이지요. 데이터가 너무 클 때, 검색 속도가 느려지는 경우 사용하게 됩니다. 데이터를 나눔으로써 필요한 데이터만 검색하게 하여 속도를 더 빠르게 할 수 있습니다.
간단한 경우부터 생각해보자. 모든 전 세계 사용자를 하나의 검색 인덱스에 넣는 경우를 생각해보자. LA에 살고 있는 사용자에 대해, 하나의 검색 쿼리는 이 단일 인덱스를 살펴보아야 하고, 전체 사용자를 살펴보아야 한다. 동부 해안이나 심지어 다른 나라에 사는 사람들은 인덱스 크기를 증가시킬 것이고, 이것은 LA에 사는 사용자에게 아무런 가치를 주지 못하고 쿼리 성능에 부정적인 영향만 끼칠 것이다.
이것은 최적화의 방향성을 제시한다. 만약 우리가 데이터를 쿼리에 중요한 최소 문서를 포함하는 인덱스에 접근할 수 있는 방법으로 데이터를 나눈다면, 계산 양은 훨씬 더 줄어들 것이며 쿼리는 더 빨라질 것이다.
Tinder의 경우에 운이 좋게도, 쿼리는 지리를 기반으로 하며, 100 마일에 제한이 있다. 이것은 자연스럽게 지리를 기반으로 한 해결책을 제시하며, 물리적으로 서로 가까운 사용자들을 같은 shard에 저장하는 방식을 제안한다.
좋은 sharding approach는 geoshard 간의 균형을 제공해야 한다. 그렇지 않으면, hot-shard 이슈가 발생한다. 만약 우리가 각 geoshard의 부하 (load score)를 정량화 할 수 있다면, 각 geoshard의 load score는 대략 같아야 할 것이다. 명백하게, 우리의 shard 수가 너무 적거나 많다면 그 숫자를 조절하여 적절하게 해야 할 것이다.
Balance Issue
하나의 간단한 접근 방식은 세계 지도를 위도와 경도를 활용하여 균등하게 간격을 나누어 그리드로 구성하는 것이다.
이것은 분명히 잘 동작하지 않을 것이다. 바다와 같은 사용자가 없는 geoshard도 있고, Europe과 같은 몇 개의 큰 도시를 포함한 geoshard도 있을 것이다. Geoshard들은 굉장히 unbalance 되어 있으며, 그 결과 실제 서비스에서 hot shard들이 발생할 것이다. 이 world map projection은 지구의 극 근처에 매우 치우쳐 있으며, 적도와 극 사이의 영역과 실제 지리적 영역의 차이는 몇천 배가 될 수 있으므로 더 나은 projection 방식을 찾아야 한다.
Load Score
어떻게 geoshard의 균형을 맞출 수 있을까? 무언가를 측정해야만 최적화 방식을 고민할 수 있다.
몇 가지 load를 계산할 수 있는 방법이 있다.
Unique user count
Active user count
User's queries count in an hour
Combination of the above
간단하게 unique user count를 사용한다고 해보자. 이것은 계산하기 쉬우며, 집계하기 쉽다(합계만 계산하면 되므로). 이제 N개의 shard를 지닌 geosharding configuration의 balance를 load의 표준편차(standard deviation)로 나타낼 수 있다.
Balance(Shard1, Shard2, …, ShardN) = Standard-deviation(Load-score-of-shard1, …)
표준 편자가 최소인 geosharding configuration이 가장 잘 균형 잡혀 있는 경우이다. 위의 간단한 geosharding 예시를 보면, 바다에 있는 geoshard들을 조합함으로써 더 잘 균형 잡힌 geoshard를 만들 수 있을 것이다. 더 나은 접근방식은 아래에서 geosharding 알고리즘을 통해 설명하겠다.
Shard Size
우리는 주어진 sharding mechnism에 대해 얼마나 많은 shard가 필요한지 어떻게 결정할 수 있을까? 아래의 몇 가지 요소를 고려해야 한다.
Geoshard migration : 사용자들이 이동을 하거나(걸어 다니거나, 통근을 하거나, 여행을 하거나 등) geoshard의 경계를 넘나드는 경우. 시스템은 사용자를 새로운 인덱스로 이동시키고 이전 인덱스에서 해당 사용자를 제거할 필요가 있다. 게다가, 이러한 작업들은 atomic하지 않으므로, 많은 이동들은 시스템에 inconsistency들을 야기할 것이다. 우리는 그것들은 일관성이 있게(consistent)하게 만들 필요가 있다. 하지만 거대한 양의 inconsistency들은 문제가 될 수 있다.
Querying multiple geoshards : Tinder는 사용자들의 검색 범위를 100 마일로 한정시킨다. 즉, 한 geoshard가 100 제곱 마일이면, 하나의 쿼리는 314개의 geoshard에 수행될 것이다. 한 사용자의 요청에 대한 parallel index search으로 인해, P99 혹은 P90 지연시간이 발생할 수 있다. 그렇기에 geoshard는 너무 작으면 안 된다.
User density : 뉴욕이나 런던과 같은 어떠한 지역에는, 사용자들은 밀집해 있을 것이다. 이러한 영역에서는 물리적으로 작은 geoshard에서도 load score가 클 것이다.
For these reasons, finding the right geoshard size is also a challenge
부하 테스트(Load test)와 부하 점수의 분포(Load score distribution)을 기반으로, 우리는 전 세계의 40~100개의 geoshard가 P50, P90, P99의 균형을 적절하게 이루어낸다는 것을 확인했다. 이 분석은 fanout과 parallelization을 고려하여 수행되었다.
S2 Cell & Geosharding Algorithm
Geo Library들에 대한 많은 연구를 한 이후, 우리는 Google S2를 사용하기로 했다. S2는 Hibert curve를 기반으로 한다. Hilbert curve는 공간적 위치성을 보존하는 space-filling curve로, Hilbert curve 상에서 가까운 두 점은 물리적 공간에서도 가까이 위치해 있다. 각각의 가장 작은 Hilbert curve clone은 cell이라 불리며, 4개의 인접한 cell은 하나의 큰 cell을 구성하기 때문에, 이것은 quadtree structure를 지닌다고 할 수 있다.
한번 지구의 중심에 빛이 있다고 생각해보자. 그 빛은 지구의 표면을 각 면이 Hilbert curve로 가득 찬 cube에 투영할 것이며, 각각의 가장 작은 cell은 지구의 작은 영역을 나타낼 것이다. 이 방법이 S2가 S2 cell을 mapping 하는 방법이다. 가장자리, 특히 모서리 부분에 있어서는 왜곡이 있다. 더 자세한 방법은 Google의 S2 slide에서 살펴보기 바란다.
S2 has the following advantages:
지구 표면의 영역과 대략 같은 크기로의 cell의 mapping. Geohash는 극쪽으로 갈수록 편향된다.
Tinder의 backend server인 Java와 NodeJS에서 하용하는 주요 언어에 대한 지원이 가능한 안정적인 library다.
2D Hilbert curve는 quad tree로서 aggregation에 용이하다. 이것은 부하 점수(load score)를 낮은 수준으로 유지하고 높은 수준으로 집계하는 것을 계산하는데 편리하다.
Library는 위도와 경도를 S2 cell로 mapping 하는 built-in function을 제공하고, 원이나 polygon과 같은 지리적 영역을 S2 cell로 덮는 기능을 제공한다.
S2는 다양한 크기의 cell을 지원한다. 센티미터 제곱부터 마일 제곱까지 그 크기를 지원한다.
S2는 Level 0(33만 평방 마일)부터 Lebel 30(1 평방 센티미터)까지 cell level을 가지고 있다. Tinder 사용 통계를 평가한 후, 우리는 대부분의 사용자 선호도가 50 마일 내에 있음을 확인하였다. 이 결과로, S2 level 7이나 level 8이 Tinder의 경우에 가장 잘 맞음을 알 수 있었다.
Now how do we create geoshards?
S2를 사용하면, 지구 전체는 S2 cell의 line에 mapping 될 수 있다. 이제 각 cell이 부하 점수(load score)에 비례하는 물을 포함하고 있다고 가정해보자. (예 : 부하 점수 10은 10ml의 물을 포함하고, 부하 점수 100.5인 cell은 100.5ml를 포함한다.) 1000ml 크기의 용기를 들고, cell의 line을 따라 걸으며, 용기에 물이 넘칠 만큼 충분한 물을 가진 cell을 만날 때까지 line을 따라 걸으며 만난 cell의 물을 용기에 담아보자.
이제 용기의 물을 모두 가방에 쏟아붓고 다시 시작해보자. 이러한 과정을 line이 끝날 때까지 계속해보자. 가방의 수는 충분해야 할 것이며, 각각의 가방은 geoshard를 의미한다고 할 수 있다. 왜냐하면 S2(및 Hilbert curve)는 locality를 보존하기 때문에, 이런 방식으로 생성된 shard는 geographically 함께 있을 것이다.
Given all the cells with precalculated load scores, the container size is the only factor that affects the sharding results.
가능한 모든 용기 크기를 열거하고, 각 sharding configuration의 standard deviation을 계산해보자. 그때, 가장 작은 standard deviation의 sharding configuration이 가장 균형 잡힌 configuration일 것이다.
위에서 설명한 알고리즘의 pseudo code는 원문에서 자세히 보실 수 있습니다.
S2의 Level 8에 대해서도 동일한 작업을 반복하였다. 이 프로세스의 끝에서, 우리는 주어진 방법에서의 최적의 geosharding configuration을 알 수 있을 것이다. 생성된 geoshard의 그래프는 아래와 같이 보일 수 있다. Hilbert curve는 locality를 잘 보존하고, geoshard는 대부분 물리적으로 함께 있으며, 적은 부하가 걸리는 지역에 대해 geoshard가 물리적으로 넓은 것을 확인할 수 있다.
생성된 geoshard는 shard mapping json을 생성하며, 그것은 원문에서 그 예시를 볼 수 있습니다.
Using the geoshard mapping
반드시 고려해야 할 두 가지 사용 예시가 있다.
Indexing : 사용자로부터 위도, 경도가 주어졌을 때, geoshard로 mapping 해야 하는 경우
Quary : 위도, 경도, 반경이 주어졌을 때, 필요한 모든 geoshard들을 알아야 하는 경우
S2 libraries provides two functions :
위치 정보(위도, 경도)가 주어졌을 때, 위치를 포함하는 S2 cell을 제공하는 function
범위 정보(위도, 경도, 반경)가 주어졌을 때, 범위에 속한 모든 S2 cell을 제공하는 function
우리는 이미 S2 cell을 geoshard로 주어진 shard mapping configuration하에서 mapping 하는 방법을 알 고 있다.
Indexing 요청에 대해, 서비스는 우선 S2 cell로 변환하고, shard mapping을 활용하여, S2 cell을 geoshard로 mapping 한다.
Query 요청에 대해, 서비스는 우선 범위를 모두 포함할 수 있는 S2 cell들을 추출하고, S2 cell들을 geoshard들로 mapping 한다.
아래 그림은 어떻게 qury mapping이 동작하는지를 보여준다. 100 마일 짜리 원을 가지는 이 query는 55개의 geoshard들 중 3개만 살펴볼 것이다.
(Query : Circle -> S2 Cells -> Geoshards)
About Resharding
우리는 아직 충분한 여유 공간을 지니고 있기 때문에 당분간은 reshard를 할 필요가 없다. 하지만 필요하다면, 동시에 두 개의 shard를 mapping 하여 두 개의 parallel index set을 수행하여 수동으로 resharding 할 수 있다. 그다음 오프라인으로 모든 존재하는 docs들에 대하여 새로운 geoshard index들로 re-index 할 수 있다.
Takeaways
실제 서비스에서 performance를 측정해보면, geosharde search index는 single index의 경우보다 20배 더 많은 연산을 처리할 수 있다. 위에서 제시한 방법의 장점은 모든 위치 기반과 집계의 목적을 가진 동작에 적용할 수 있다는 점이다.
Key takeaways :
위치 기반 서비스의 경우, 부하(load)를 고려해야 하며, 이때 geosharding을 떠올리자.
S2는 geosharding에 있어 좋은 library이며, Hilbert curve는 locality를 보존하는 훌륭한 방법이다.
어떻게 부하(load score)를 측정할지 생각하는 것은 shard 간의 더 좋은 load balance를 유발한다.
이 글은 아래의 원문을 번역/의역 및 요약하였습니다. 중간중간 파란색으로 표시된 글씨는 번역자의 견해입니다.
지난 리뷰 보기
https://brunch.co.kr/@sonjoosik/8
https://brunch.co.kr/@andrewhwan/57
