트위터 시스템 디자인 생각해보기

* 해당 글은 계속 수정 예정입니다.
최초 작성일 2023.04.30
마지막 수정일 2023.05.10

 

 

 

 

# 오픈소스 트위터의 추천 알고리즘

트위터의 추천 알고리즘이 오픈소스로 공개되었다고 한다. 추천 알고리즘은 트위터의 핵심기술이라 생각하기에 이를 분석해보면 무척 재미있을 것 같다. 하는김에 트위터의 시스템 디자인도 같이 생각해보자.

 

* 해당 글은 공부가 목적인 글이므로. 부정확한 내용이 있을 수 있으니 참고바랍니다.

 

---

# 의식의 흐름대로 진행

우선은 블로그에 글로 옮기는데 시간이 소요되므로, 의식의 흐름대로 나열 및 참고할만한 다른 블로그의 링크를 달아놓는다.

 

---

A. 트위터의 추천 알고리즘 원본 (영어)

https://blog.twitter.com/engineering/en_us/topics/open-source/2023/twitter-recommendation-algorithm

 

 

B. 트위터의 추천 알고리즘 요약 (한글)

https://careerly.co.kr/comments/81821?utm_campaign=user-shareh

요약하면 다음과 같다.

STEP 1) For You에 보여줄 1,500개의 트윗을 추출해서 보여준다.
STEP 2) 사용자가 팔로잉하는 In-Network 소스와 팔로잉하고 있지 않은 Out-of-Network 소스 두가지에서 50:50 비율로 가져온다. 
STEP 3) In-Network 소스에서는 두 사용자(로그인 사용자와 트윗 올린 사용자)의 상호 참여 가능성을 예측하는 모델인 Real Graph를 통해 트윗의 순위를 정한다 
STEP 4) Out-Network 소스에서는 소셜 그래프로 팔로잉하는 사람들과 비슷한 관심사를 가진 사람들을 통해 실시간으로 상호작용 그래프를 유지하는 그래프 처리 엔진 GraphJet을 개발해서 사용한다. 
STEP 5) 소셜 그래프보다 큰 비중을 차지하는 임베딩 스페이스는 사용자의 관심사와 트윗의 관련도를 수치로 만들어서 145,000개의 커뮤니티를 3주마다 업데이트한다. 
STEP 6) 이렇게 순위가 정해진 트윗을 필터링하고 정제한 후(블록이나 너무 같은 사람 트윗이 나오지 않도록) 사용자에게 보여준다.
STEP 7) 이 파이프라인은 하루에 50억번 실행되고 평균 1.5초 이내에 완료된다. 

 

---

C. DB설계

STEP 1) For You에 보여줄 1,500개의 트윗을 추출해서 보여준다.
STEP 2) 사용자가 팔로잉하는 In-Network 소스와 팔로잉하고 있지 않은 Out-of-Network 소스 두가지에서 50:50 비율로 가져온다. 

추천 알고리즘을 설계하려면 In-Network 소스와 팔로잉하고 있지 않은 Out-of-Network 를 구분해야 한다.

즉, 회원들과 팔로잉 관계를 나타내는 DB의 설계가 우선이다.

 

---

C-1. 팔로잉 관계 DB의 설계

( 참고 : 인스타그램 분석 https://velog.io/@evelyn82ny/instagram-follow )

 

* 팔로우 관계 예상
=> (X) 팔로우(FOLLOW TABLE) 객체와 유저(USERS TABLE) 객체 간의 상태 ? X
=> (X) 연관 관계를 설정 ? X
=> (X) FOLLOW TABLE : ID(PK), toUser_id(FK:USERS TABLE), fromUser_id(FK:USERS TABLE) ? X
=> (X) FOLLOW와 USERS 는 서로 참조하는 상태 ? X

 

 

---

C-2. 정규화를 통해 회원/팔로잉 테이블을 분리하도록 DB를 설계한다.

* 팔로우 관계 예상
=> (O) toUser와 fromUser 간의 상태로 인해 결정 ? O
=> (O) 복합키를 사용 ? O
=> (O) FOLLOW TABLE : toUser_id, fromUser_id (PK:toUser_id,fromUser_id)

( 참고 : 정규화 https://code-lab1.tistory.com/48 )

 

 

---

C-3. 결론, DB와 트위터 API 관계도 예상

* 테이블 목록

1) USER TABLE : 회원ID와 회원정보 (User_id, 그 외 User 정보)
2) FOLLOW TABLE : 팔로우 관계에 있는 회원ID (FOLLOWER=toUser_id / FOLLOWEE=fromUser_id)

3) TWEET TABLE : 트위터에 작성되는 글의 ID, 작성자(회원ID), 작성시간, 수정시간 등

( * FOLLOWEE : FOLLWER 에게 FOLLW 받는 회원 )

 

* 트위터 API 예상
1) 팔로잉(FOLLOWING/UNFOLLOWING) : 회원간의 팔로우, 언팔로우 기능
2) 트윗(TWEET) : 회원의 트위터 글 작성, 수정, 삭제 기능
3) 타임라인(TIMELINE In-Network) : FOLLOWEE 회원에게 FOLLOWER 회원의 글을 실시간으로 트윗해주는 기능
4) 추천 타임라인(TIMELINE Out-of-Network) : 회원이 FOLLOW 하고있지 않은 회원의 글을 실시간 트윗해주는 추천 기능

 

 

---

D. API 흐름 예상

- 위 "테이블 목록" 참고

- 위 "트위터 API 예상" 참고

 

---

D-1. API 흐름 예상 v1.0

1) CAT 회원이 DOG 회원을 팔로우 한다. ( 1) 팔로잉(FOLLOWING/UNFOLLOWING) )
  => FOLLOW 테이블에 INSERT

2) DOG 회원이 트위터에 새로운 글을 트윗한다. ( 2) 트윗(TWEET) )
  => TWEET 테이블에 INSERT

이후, 
3) CAT 회원이 타임라인을 갱신한다. ( 3) 타임라인(TIMELINE In-Network) )
  => a) CAT 회원의 ID를 이용해, FOLLOW 테이블에서 FOLLOWEE 회원 ID를 찾는다. 그 결과 DOG 회원이 검색된다. (USER-FOLLOW 테이블 연관관계)
  => b) 위에서 찾은 DOG 회원의 ID를 이용해, TWEET 테이블을 조회한다. 그 결과 최신글이 검색된다. (FOLLOW-TWEET 테이블 연관관계)
  => c) 검색된 최신글을 타임라인에 갱신한다.
  => d) a에서 FOLLOWEE 회원이 여럿이면 b가 각자 여러번 수행된다.

4) CAT 회원이 타임라인을 갱신한다. ( 4) 추천 타임라인(TIMELINE Out-of-Network) )
  => a) CAT 회원의 ID를 이용해, FOLLOW 테이블에서 FOLLOWEE 회원 ID을 모두 찾는다. (USER-FOLLOW 테이블 연관관계)
  => b) 위에서 찾은 회원의 ID 그룹에 속하지 않는 회원을 특정하여, TWEET 테이블을 조회한다. 그 결과 최신글이 검색된다. (FOLLOW-TWEET 테이블 연관관계)
  => c) 이후 위와 동일

* 결론
- USER-FOLLOW-TWEET 테이블을 JOIN하여 데이터를 보여줌
- 트위터를 작성하는 것은 빠르지만, FOLLOWEE 회원에게 실시간으로 트윗해주는 기능은 시간이 오래 소요될 것으로 예상

 

---

D-2. API 흐름 예상 v2.0(개선안)

- 타임라인(TIMELINE In-Network) 기능을 개선해보자
- 2)와 3)은 개선 필요

2) DOG 회원이 트위터에 새로운 글을 트윗한다. ( 2) 트윗(TWEET) )
  => a) TWEET 테이블에 INSERT
  => b) 해당 TWEET을 작성한 DOG 회원의 ID를 이용해, FOLLOW 테이블에서 FOLLOWER 회원 ID를 찾는다. 그 결과 CAT 회원이 검색된다. (TWEET-FOLLOW 테이블 연관관계)
  => c) 캐시 서버(Redis)를 두고, 위에서 찾은 CAT 회원의 ID에 대해, a에서 작성된 TWEET 테이블의 글의 ID를 미리 입력해놓는다

이후, 
3) CAT 회원이 타임라인을 갱신한다. ( 3) 타임라인(TIMELINE In-Network) )
  => a) 캐시 서버(Redis)에서, CAT 회원에 대한 VALUE 값(저장된 글의 ID)를 이용해 TWEET 테이블을 조회한다. 그 결과 DOG 회원의 글이 검색된다.
  => b) CAT 회원이 FOLLOWING 중인 회원이 다수여서, VALUE 에서 저장된 글의 ID가 여럿이면 각자 여러번 수행된다.

* 결론
- USER-FOLLOW-TWEET 테이블을 JOIN하여 데이터를 보여줌
- 트위터를 작성하는 것은 조금 느려졌지만, FOLLOWEE 회원에게 실시간으로 트윗해주는 기능이 개선됨
- 그러나, FOLLWEE가 많은 인플루언서의 경우 트위터 작성속도가 매우 느려질 수 있음

---

D-3. API 흐름 예상 v3.0 (최종 개선안)

- 인플루언서의 트윗(TWEET) 기능을 개선해보자
- 추천 타임라인(TIMELINE Out-of-Network) 기능을 개선해보자
- 2), 3) 개선 필요

1) CAT 회원이 DOG 회원을 팔로우 한다. ( 1) 팔로잉(FOLLOWING/UNFOLLOWING) )
  => ASIS 유지

1-1) CAT 회원이 인플루언서인 PIG 회원을 팔로우 한다. ( 1) 팔로잉(FOLLOWING/UNFOLLOWING) )
  => FOLLOW 테이블에 INSERT 
  => FOLLOW 테이블에서 인플루언서 여부를 구분하는 컬럼이 따로 존재

2) DOG 회원이 트위터에 새로운 글을 트윗한다. ( 2) 트윗(TWEET) )
  => ASIS 유지

2-1) 인플루언서인 PIG 회원이 트위터에 새로운 글을 트윗한다. ( 2) 트윗(TWEET) )
  => TWEET 테이블에 INSERT
  => 캐시 서버에 넣는 기능은 처리되지 않음(v1.0과 동일)

이후, 
3) CAT 회원이 타임라인을 갱신한다. ( 3) 타임라인(TIMELINE In-Network) )
  => ASIS 유지

3-1) CAT 회원의 타임라인 중 인플루언서의 글을 갱신한다. ( 3) 타임라인(TIMELINE In-Network) )
  => (v1.0과 동일)
  => a) CAT 회원의 ID를 이용해, FOLLOW 테이블에서 FOLLOWEE '인플루언서' 회원 ID를 찾는다. 그 결과 PIG 회원이 검색된다. (USER-FOLLOW 테이블 연관관계)
  => b) 위에서 찾은 PIG 회원의 ID를 이용해, TWEET 테이블을 조회한다. 그 결과 최신글이 검색된다. (FOLLOW-TWEET 테이블 연관관계)
  => c) 검색된 최신글을 타임라인에 갱신한다.
  => d) a에서 FOLLOWEE '인플루언서' 회원이 여럿이면 b가 각자 여러번 수행된다.

* 결론
- USER-FOLLOW-TWEET 테이블을 JOIN하여 데이터를 보여줌
- 트위터를 작성하는 것은 조금 느려졌지만, FOLLOWEE 회원에게 실시간으로 트윗해주는 기능이 개선됨
- FOLLWEE가 많은 인플루언서의 경우 트위터 작성속도가 개선됨

---

D-4. 추천 타임라인(TIMELINE Out-of-Network) 기능의 개선?

- 인플루언서만 받거나, 혹은 본인이 트윗하는 유저들의 데이터를 기반으로 보는 협업 필터링(Collaborative Filtering) 으로 추천 모델을 개선한다.

- 아래에 있는 "F. 추천 트윗의 정렬 순서 (추천도 우선순위)" 에서 추가 서술한다.

 

 

---

E. In-Network, Out-of-Network 각각 750건씩 조회

STEP 1) For You에 보여줄 1,500개의 트윗을 추출해서 보여준다.
STEP 2) 사용자가 팔로잉하는 In-Network 소스와 팔로잉하고 있지 않은 Out-of-Network 소스 두가지에서 50:50 비율로 가져온다. 

위에서 예상해본 API 기능대로 진행시 동일 할 것으로 예상되며

 

결론적으로, 

USER-FOLLOW-TWEET 테이블을 JOIN하여 In-Network 소스 750건, Out-of-Network 소스 750건 추출한다.

예외사항으로 팔로잉 중인 숫자가 적을 경우 In-Network 소스는 750건 이하로 추출 될 수 있을 것 같다.

초기모델에서는, 이 경우에 대해 750건 이하를 보여주는 것으로 진행하고. 추후  Out-of-Network 게시물의 개수를 늘려 1500개를 채우는 방향을 고려해보자.

 

 

---

F. 추천 트윗의 정렬 순서 (추천도 우선순위)

STEP 3) In-Network 소스에서는 두 사용자(로그인 사용자와 트윗 올린 사용자)의 상호 참여 가능성을 예측하는 모델인 Real Graph를 통해 트윗의 순위를 정한다 
STEP 4) Out-Network 소스에서는 소셜 그래프로 팔로잉하는 사람들과 비슷한 관심사를 가진 사람들을 통해 실시간으로 상호작용 그래프를 유지하는 그래프 처리 엔진 GraphJet을 개발해서 사용한다. 

추천 시스템은 콘텐츠 기반 필터링(content based filtering) 과 협업 필터링(Collaborative Filtering) 이 있다.
전자는 잘 사용하지 않으므로, 후자 중에서도 아이템 기반 협업 필터링(item based collaborative filtering)을 적용하도록 한다.

유저(user)와 게시물(item)의 관계가 있는 데이터를 PIVOT을 통해 item - user 행렬로 만든다.

 

초기모델에서는 위와같이 진행하고, 추후 트위터에서 사용중인 Real Graph와 GraphJet으로 개선하도록 하자

( 참고 : 협업 필터링 https://lsjsj92.tistory.com/563 )

 

 

---

G. 추가 시스템

(..작성중..)

 

G-1. 임베딩 스페이스

STEP 5) 소셜 그래프보다 큰 비중을 차지하는 임베딩 스페이스는 사용자의 관심사와 트윗의 관련도를 수치로 만들어서 145,000개의 커뮤니티를 3주마다 업데이트한다. 

G-2. 사용자에 노출 전, 데이터 필터링 및 정제 작업

STEP 6) 이렇게 순위가 정해진 트윗을 필터링하고 정제한 후(블록이나 너무 같은 사람 트윗이 나오지 않도록) 사용자에게 보여준다.

G-3. 파이프라인

STEP 7) 이 파이프라인은 하루에 50억번 실행되고 평균 1.5초 이내에 완료된다. 

 

 

---

H. 로직설계

로직설계 부분은 어느정도 생략해야 될 것 같다.

 

SQL Mapper(JDBC)로 작성시 join으로 처리한다.

 

jpa 사용시, 위 설계상 필연적으로 jpa n+1 문제가 발생할 것이고. 이는 querydsl을 통해 fetchjoin 으로 해결 가능하다.

( 참고 : fetch join vs join  https://velog.io/@heoseungyeon/Fetch-Join-vs-%EC%9D%BC%EB%B0%98-Joinfeat.DTO )

 

 

(..작성중..)

 

 

---

I. 그 외

사용자의 요청이 들어온 뒤에서야 알고리즘이 돌고, 조회하여 게시글을 렌더링하는 것은 너무 오래걸리고 비효율적이라 생각된다.

 

앱이나 게임에서 시작(실행) 후 로딩시간이 있는 것 처럼(위 내용을 미리 돌려서 성능을 최대한 올리는 것 처럼), 애플리케이션에서 이를 개선 할 수 있는 효율적 방법이 무엇이 있을지 고민이 필요 할 것 같다.

=> 캐시 서버를 이용하여, 트윗을 작성함과 동시에 비동기로 Write 진행

 

우선 국가별/사용자별로 사용이 적은 시간을 기록하여, 해당 시간에 배치성으로 게시물 1500개를 미리 만들어 놓을 수도 있을 것 같다.

 

이 경우 최신 내용에 대해서만 게시글을 조회하도록 알고리즘/DB 파티셔닝/인덱싱 등을 통해 최적화 해놓으면 좋을 것 같다.

 

배치가 도는 서버를 따로 구현할지 여부와 몇건씩 돌지, 스케줄링 시간은 얼마나 설정할지 등에 대해서도 고민이 필요해 보인다.

 

(..작성중..)