틴더(Tinder) 시스템 디자인

Problem Statement

틴더와 같은 위치 기반 데이팅 어플리케이션을 디자인해본다. 틴더는 오른쪽 스와이프를 통해 좋아요를 보내거나 왼쪽 스와이프를 통해 싫어요를 보낼 수 있고 매칭된 유저와 채팅할 수 있는 기능들을 제공한다.

Gathering Requirements

In Scope

이 어플리케이션은 아래의 요구사항을 충족시켜야 한다.

• 유저는 간략한 프로필과 사진을 업로드하여 자신의 프로필을 생성할 수 있다.
• 유저는 지리적으로 근접해있는 지역의 유저를 추천받을 수 있다.
• 유저는 추천받은 유저에게 오른쪽으로 스와이프하여 좋아요를 보내거나 왼쪽으로 스와이프하여 싫어요를 보낼 수 있다.
• 유저는 타 유저와 매칭된 경우 알림을 받을 수 있다.
• 유저가 다른 지역으로 이동해도 해당 지역과 근접한 지역의 유저를 추천받을 수 있다.

Out of Scope

• 다른 유저에게 메시지를 보내거나 받을 수 있다.

High Level Design

Architecture

게이트웨이 뒤에는 유저의 요청을 처리하는 몇개의 마이크로 서비스가 존재한다. 프로필 생성 서비스는 유저가 프로필을 생성했을 때 호출된다. 이 서비스는 유저의 정보를 데이터베이스에 저장하고 유저의 위치에 해당하는 위치 기반 샤딩 인덱스에 추가하여 유저가 근처에 있는 다른 유처를 추천받을 수 있게 한다. 위치 인덱스는 다른 유저가 추천 기능을 요청할 때 추천 서비스를 통해 쿼리된다.

유저가 추천 시스템을 통해 스와이프를 시작하면 스와이프 서비스는 전달받은 데이터를 Kinesis/SQS와 같은 데이터 스트림으로 전송한다. 추가적으로 매칭 워커들은 매칭을 생성하기 위해 스트리밍된 데이터를 읽어간다. 워커들은 유저 간 매칭되었는지 확인하기위해 Likes Cache를 조회하며 매칭된 경우 웹 소켓을 통해 알림을 전송하게 된다. 

Component Design

User Profile Creation

위 다이어그램은 유저가 프로필을 생성했을 때의 흐름을 나타낸다. 동기 프로세스에서 유저의 사진과 같은 미디어 파일은 파일 서버로 업로드되며 유저의 위치를 포함한 정보들은 Key-Value 저장소인 AWS DynamoDB에 저장된다. 추가적으로 위치 샤딩 인덱스에 유저를 추가하기 위해 큐에 추가된다.

비동기 프로세스에서는 유저의 정보를 큐에서 읽어가며 GeoShardingIndexer에게 데이터를 전달한다. GeoShardingIndexer는 구글 S2 라이브러리등을 사용하여 유저의 위치를 위치 샤딩 인덱스에 매핑하고 해당 샤드와 연결된 인덱스에 유저를 추가한다. 이 작업을 통해 유저가 근처 유저의 추천에 뜨게 된다. 예를 들어 아래 이미지에서는 북미 유저가 해당 인덱스에 매핑된 근처 유저의 추천 항목에 표시되는 방법을 보여준다. 

참고: https://medium.com/tinder/geosharded-recommendations-part-1-sharding-approach-d5d54e0ec77a

UserProfileInfo - Sample Data Model

유저 프로필 정보를 저장하기위한 JSON BLOB 타입의 데이터가 아래에 나와있다. 우리는 아래 데이터를 저장하기위해 DynamoDB 또는 Riak와 같은 Key-Value 저장소를 사용할 수 있다.

{ “userId”(PK) : “AWDGT567RTH”, “name” : “Julie”, “age” : 25, “gender” : “F”, “location”: { “latitude” : “longitude” : }, “media”: { “images”: [ “https://mybucket.s3.amazonaws.com/myfolder/img1.jpg”, “https://mybucket.s3.amazonaws.com/myfolder/img2.jpg”, “https://mybucket.s3.amazonaws.com/myfolder/img3.jpg” ] }, “recommendationPreferences”: { “ageRange”: { “min”: 21, “max”: 31 }, “radius”: 50 } }

Fetch User Recommendations

이전 섹션에서 어떻게 유저가 위치 샤드 인덱스에 추가되는지 살펴봤다. 이제 유저가 다른 유저의 추천 항목에 어떻게 뜨게 되는지 살펴보자. 추천 엔진은 유저의 요청이 오는 경우 이 요청을 GeoShardedIndexer로 전달한다. 그리고 GeoShardedIndexer는 구글 S2와 같은 라이브러리를 통해 유저 위치 및 반경을 기반으로 어떤 샤드로 요청할 지 결정한다. 그런 다음 GeoShardedIndexer는 S2에서 반환한 샤드에 매핑된 모든 위치 샤딩 인덱스를 쿼리하여 해당 인덱스에 존재하는 모든 유저 목록을 가져오고 해당 목록을 RecommendationEngine에 반환한다. RecommendationEngine은 유저의 설정에 따라 필터링을 적용하여 최종 추천 목록을 유저에게 반환한다.

Geo-Sharded Index

인덱스를 관리하는 간단한 방법 중 하나는 하나의 인덱스와 기본 개수의 샤드를 갖춘 ElasticSearch 클러스터를 운영하는 것이다. 그러나 이 방법은 틴더와 같이 어느정도 규모가 있는 어플리케이션에는 적합하지 않다. 우리는 틴더의 추천 시스템이 위치 기반이라는 것을 활용해야한다. 예를 들어 인도 유저에게 미국 유저를 추천해줄 필요는 없다. 이 사실을 통해 최적의 인덱스 크기를 유지함으로써 보다 나은 성능을 가져갈 수 있다. 

활성 유저의 위치를 기반으로 샤딩함으로써 인덱스의 크기를 최적화할 수 있다. 아래에 언급된 것 처럼 샤드 전체의 활성 유저의 표준 편차를 통해 N개의 샤드로 구성된 위치 샤드 인덱스의 균형을 나타낼 수 있다.

Balance(Shard1, Shard2,…, ShardN) = standard-deviation(Active User Count of Shard1, Shard2,…, ShardN)

표준 편차에 의한 위치 샤드 설정은 최적의 밸런스를 갖는다. Quad-Trees를 사용하여 구를 Cell로 분해하는 방식의 라이브러리인 구글의 S2와 같은 위치 라이브러리를 사용할 수도 있다. 아래 그림을 통해 각 유즈케이스에 맞게 생성된 위치 기반으로 분할된 지도를 확인할 수 있다.

아래 그래프를 보면 활성 유저수가 적은 지역의 경우 위치 샤드가 물리적으로 더 크게 생성된 사실을 볼 수 있다. 예를 들어 아래 이미지에서 바다/해변가의 샤드는 굉장히 큰 모습을 볼 수 있는데 이는 유저의 수가 적기 때문이다. 반면 육지의 경우 유저 수가 많기 때문에 비교적 작은 샤드를 가진다. 

아래 이미지를 보면 북아메리카는 3개의 샤드를 가지고 있지만 영국/그린랜드 전체와 대서양의 상당 부분은 활성 유저 수가 적기 때문에 단일 샤드를 가진 모습을 확인할 수 있다. 참고: https://medium.com/tinder/geosharded-recommendations-part-2-architecture-3396a8a7efb

S2 라이브러리는 다음과 같은 2가지 주요 기능을 제공한다.

• point(lat, lng)가 주어지면 이를 포함하는 S2 Cell을 반환한다.
• circle(lat, lng, radius)이 주어지면 원을 덮는 S2 Cell을 반환한다. 

각 S2 Cell은 시스템에 매핑된 위치 샤드 인덱스를 나타낸다. 프로필이 생성되면 유저는 해당하는 S2 Cell의 검색 인덱스에 추가된다. 유저 추천 정보를 가져오려면 아래 이미지와 같이 원 반경에 따라 근처 S2 Cell의 인덱스를 쿼리한다.

Swipes and Matches

위 그림은 유저가 왼쪽/오른쪽으로 스와이프했을 때 발생하는 흐름에 대해 나타내고 있다. 스와이프 수집기는 스와이프를 처리하고 왼쪽 스와이프 데이터를 S3와 같이 저렴한 저장소에 저장한다. 이렇게 적재된 데이터는 데이터 분석 목적으로 사용할 수 있다.

반면 오른쪽 스와이프는 분리된 스트림으로 전송되며 매칭 워커 스레드에 의해 읽히게 된다. 매칭 워커 스레드는 스트림을 통해 좋아요 메시지를 읽고 해당 데이터가 LikesCache에 존재하는지 확인한다. 예를 들어 위 이미지에서 Alice가 Bob에게 좋아요를 보내면 매칭 워커는 Bob이 Alice를 좋아한다는 정보가 캐시에 있는지 확인한다. 만약 Alice와 Bob이 서로 좋아요를 보낸 경우 이를 매칭되었다고 표현하며 웹 소켓을 통해 각 유저에게 푸시 알림을 전송하게된다. 만약 Bob이 아직 Alice에게 좋아요를 보내지 않았다면 Alice가 Bob을 좋아요했다는 정보가 LikesCache에 저장된다. 

Matches Data Model

우리는 매칭 정보를 저장하기 위해 DynamoDB와 같은 Key-Value 저장소를 사용할 수 있다. 이 데이터의 해시 키는 서로 좋아요를 누른 유저들의 고유 식별자의 복합키이다. 값은 매칭에 관련된 메타 데이터들을 포함한다.

User Switching Locations

유저가 위치를 변경하는 경우 변경된 위치 근처에 있는 유저를 추천해줘야 한다. 이를 위해 유저 위치가 새 위치로 업데이트되고 해당 위치를 통해 추천 정보를 가져온다. 또한 유저와 매핑된 위치 인덱스또한 업데이트되어 새로운 위치에서 유저가 추천 정보에 표시되도록 한다. 이 프로세스는 비동기적으로 실행된다. 

위치 샤드 인덱스를 포함하고 있는 ElasticSearch 클러스터는 큐에서 메시지를 읽고 유저 인덱스를 업데이트한다. ElasticSearch의 탄력적인 노드는 사용자의 정보를 기존 매핑된 인덱스에서 새 위치에 매핑된 인덱스로 이동시킨다. 이를 통해 유저가 위치를 옮겼을 때 새로운 위치의 추천목록에 뜰 수 있도록 한다.

ElasticSearch Cluster

클러스터는 여러개의 마스터 노드로 구성되며 각 마스터 노드에는 두개의 Auto Scaling Group이 존재한다. 하나는 모든 요청이 보내지는 Coordinating Node에 대한 것이고 다른 하나는 모든 노드에 대한 것이다. 각 노드에는 무작위로 분산된 샤드의 인덱스가 포함된다. Coordinating Node는 각 유저에 맞는 노드에 쿼리하도록 조정하는 역할을 수행한다. 신뢰성과 견고함을 높이기 위해 지리적 위치를 사용하여 유저 데이터를 샤딩하고 각 샤드의 복제본 또한 생성한다. 

Optimization

틴더와 같은 어플리케이션의 가장 중요한 측면 중 하나는 유저에게 제공되는 추천 정보이다. 위에서 유저 근처 위치에 해당하는 샤드에 인덱스를 쿼리하여 추천 정보를 생성하는 방법에 대해 살펴봤다. 여기에 머신러닝을 적용하여 추천에 대한 랭킹을 만들 수 있다. 머신 러닝 모델은 유저의 오른쪽 스와이프 확률을 최적화한다. 유저가 왼쪽 또는 오른쪽으로 스와이프를 결정하기에 영향을 미칠 수 있는 몇가지 기능은 다음과 같다.

• 인구 통계: 연령, 성별, 인종, 위치, 직업 등
• 틴더 사용 기록: 왼쪽/오른쪽 스와이프, 위치 기록, 하루 사용 시간
• 프로필에서 추출된 정보: 좋아요, 싫어요, 선호도
• 사진에서 추출된 정보: 얼굴 특징, 머리 색, 체형

이러한 기능을 사용하여 유저가 오른쪽으로 스와이프할 확률을 높일 수 있다. 그런 다음 회귀 분석과 같은 알고리즘도 활용할 수 있다. 추가적으로 유저가 다른 유저를 오른쪽으로 스와이프했다는 정보를 미리 가져온 후 유저에게 매칭 알림을 보내도록 흐름을 최적화할수도 있다. 정보를 미리 가져오면 추가적인 네트워크 호출없이 즉시 유저에게 매칭 정보를 알릴 수 있다. 예를 들어 Alice가 Bob의 추천 목록에 나타났고 Alice가 이미 Bob에게 좋아요를 보낸 경우 Bob도 Alice에게 좋아요를 보내는 경우 Bob은 추가적인 네트워크 호출없이 즉시 매칭 알림을 받을 수 있다.

Reference

https://highscalability.com/designing-tinder/