DB 타임라인 최적화

트위터, 페이스북, 인스타그램 등 SNS에서 팔로워들의 게시물을 보여주는 피드

• 회원이 팔로우한 회원들이 작성한 포스트를 시간 순으로 조회하여 보여주는 기능

Fan Out On Read (Pull Model)

팔로우 회원 포스트 조회 예시

Cursor 기반 페이지네이션을 이용하여 포스트 조회 코드

• 팔로우한 회원들의 포스트를 제공
• 회원의 ID를 기반으로 내림차순 정렬
• 한번에 보여줄 페이지의 크기 지정

public List<Post> findAllByInMemberIdAndOrderByIdDesc(List<Long> memberIds, int size) {
    // memberIds가 비었을 경우 빈 리스트 반환
    if (memberIds.isEmpty()) {
        return List.of();
    }
    var sql = """
            SELECT *
            FROM Post
            WHERE memberId in (:memberIds)
            ORDER BY id desc
            LIMIT :size
            """;
    var params = new MapSqlParameterSource()
            .addValue("memberIds", memberIds)
            .addValue("size", size);

    return namedParameterJdbcTemplate.query(sql, params, POST_ROW_MAPPER);
}

시간 복잡도

지금까지의 방법은 **Fan Out On Read (Pull Model)**이다. 이 방법은 조회 시점에 부하가 발생하게 된다.

위와 같은 방법으로 팔로우한 회원들의 포스트를 조회할 경우의 시간 복잡도를 알아보자

시간 복잡도 = 
log(follow 전체 레코드) + 해당 회원의 Following * log(Post 전체 레코드)

따라서, 위와 같은 방법의 경우 열심히 팔로우 하고 활동하는 회원일 수록 서비스의 질이 떨어지는 현상을 맞이하게 된다.

Fan out On Write (Push Model)

Write 시점에 Fan out을 하는 부하가 발생하는 모델에 대해서 알아보겠습니다.

해당 모델은 게시물 작성시, 해당 회원을 팔로우하는 회원들에게 데이터를 배달합니다.

1. 게시물 작성 시점에 나를 팔로우하는 회원들을 찾는다.
   • 1번 유저가 작성 하였을때 팔로우 하는 유저 3번을 찾는다.
2. Timeline 테이블에 팔로워의 Id와 함께 포스트 Id를 넣어서 Insert 해준다.
3. 이렇게 만들게 되면 게시물 조회시 내가 팔로잉한 회원들을 조회하고 해당 회원의 게시물들을 조회하는 것에서 ⇒ Timeline 테이블만을 이용해 게시물들을 조회할 수 있다.
4. 즉, Pull 모델에서의 조회 시점의 부하를 쓰기 시점의 부하로 치환
   • 게시물은 작성보다는 조회가 더 많이 발생하기 때문이다.
   • Facebook은 Pull 모델, 트위터는 Pull 모델을 이용하는 만큼 각각의 장단점이 있다.

정합성과 성능

Push Model (Write 부하)은 공간복잡도를 희생

Pull Model (Read 부하)은 시간 복잡도를 희생

Pull Model은 원본 데이터를 직접 참조하므로 정합성에 이점이 있으나 Follow 수가 많은 회원일수록 처리 속도가 느려진다.

• Facebook(Pull Model)에서는 친구 수를 최대 5000명으로 제한하고 있다.
• Twitter(Push Model)에서도 팔로우의 수를 5000명으로 제한하나, 내 계정을 팔로우하는 사람이 많다면 팔로우를 더 많이 할 수 있게 해준다.

Push Model에서는 게시물 작성과 타임라인 배달의 정합성 보장에 대한 고민이 필요하다

• 비동기, 다른 저장소의 사용등을 통해 Write 부하 해결을 위한 노력이 필요
• Pull Model에 비해 시스템 복잡도가 높다.
• 비즈니스, 기술 측면에서 유연성을 확보시켜준다.

상황, 자원 정책 등 여러가지를 고려해 트레이드 오프 해야한다.

---

CAP 이론

• Consistency, 일관성 일관성은 사용자가 분산 데이터베이스 상의 어떤 노드와 통신하는지 상관없이 같은 데이터를 조회할 수 있는 것을 의미한다. 일관성은 금융이나 개인정보와 같이 모든 사용자가 일관성 있는 데이터를 조회해야할 때 중요하다.
  
• Availableity, 가용성 가용성은 모든 요청이 응답을 받을 수 있어야 한다는 것을 의미한다. 즉, 시스템이 중단되는 일 없이 언제든지 사용 가능한 상태여야 한다.
  
• Partition Tolerance, 분할 허용성 분할이란 노드 간 통신이 끊어지는 것을 의미한다. 분할 허용성은 시스템 내 분할이 생겼을 때 시스템이 계속 작동하는 것을 의미한다. 즉, 한 노드가 다른 노드와 통신할 수 없을 때, 다른 복제 노드가 사용자 요청에 응답할 수 있어야 한다.
  

CAP 이론이란

분산 데이터베이스 시스템은 분할이 생겼을 때 일관성과 가용성 중 하나를 희생하야 한다는 뜻이다. 분산 데이터베이스 시스템은 네트워크 장애나 다른 이슈들에 대처하기 위해서 분할 허용성이 반드시 필요하다. 이로인해 일관성과 가용성 중 하나를 포기해야 할 수 있다.

---