무한 대댓글 실제로 구현해보기 O(N^2)

⚠️ 이 게시물의 내용은 매~우 비효율적인 무한대댓글 구현을 다룬다.
⚠️ 익혀가는 과정을 적은 것일 뿐이고, 참고만 하는 것이 좋다 ! !

구현 결과부터 보여주자면 이렇게 잘 작동한다.

백, 프론트 둘 다 직접 구현해봤다.
예전에 작성했던 https://hwangjiwon1.tistory.com/64, https://hwangjiwon1.tistory.com/66 의 기억을 살려서 구현해보았다. 역시 생각만 해볼 때와 직접 구현해볼 때와의 난이도 차이는 천차만별이다. 링크드 리스트 + 트리 느낌.. 으로 해보았는데 힘들었다.
 

백엔드

가장 먼저 게시물과 댓글의 스키마를 알아야 추후의 내용을 이해하기 쉬울 것 같다.

// 게시물
const Post = new Schema({
  title: String,
  body: String,
  createdAt: {
    type: Date,
    default: Date.now
  },
  account: {
    type: mongoose.Types.ObjectId,
    ref: 'Account'
  },
  comments: [
    {
      type: mongoose.Types.ObjectId,
      ref: 'Comment'
    }
  ]
})

// 댓글
const Comment = new Schema({
  body: String,
  username: String,
  createdAt: {
    type: Date,
    default: Date.now
  },
  account: {
    type: mongoose.Types.ObjectId,
    ref: 'Account'
  },
  parent: {
    type: mongoose.Types.ObjectId,
    ref: 'Comment',
    default: null
  },
  children: [
    {
      type: mongoose.Types.ObjectId,
      ref: 'Comment'
    }
  ],
  depth: {
    type: Number,
    default: 0
  }
})

1. 게시물에는 바로 달린 댓글(depth 0짜리)을 담는 comments 배열이 있다.
2. 대댓글의 구현을 위해, 각 댓글에는 자신의 조상 댓글의 id를 담는 parent, 대댓글의 id를 담는 children 배열이 있다.

따라서 댓글이 하나의 게시물로부터 트리처럼 뻗어나갈 수 있다.
댓글과 그 대댓글들은 각자 참조하고 있는 id값을 통해서, 대댓글의 대댓글들을 무한히 확인할 수 있는 방식으로 구현되어있다.
 
이건 Post의 댓글, 대댓글들을 재귀적으로 찾아주는 메소드이다. getRepliesRecursively() 내부의 populate()가 핵심이다. 댓글 1에 달린 대댓글 1-1이 있다면, 그 녀석은 댓글 2보다 상위노출 되어야한다. 따라서 DFS처럼 구현했다.
백엔드에서 주는 _id 값을 통해서 해당 _id에 해당하는 댓글이나 대댓글에 대댓글을 작성할 수 있다.

Post.methods.getComments = async function () {
  const comments = [];

  // 재귀적으로 댓글과 대댓글들을 뽑아내는 함수
  const getRepliesRecursively = async (commentId) => {
    
    const comment = await Comment.findById(commentId)?.populate('children');

    if (!comment) {
      return;
    }

    console.log(comment.body);

    comments.push({
      _id: comment._id,
      body: comment.body,
      username: comment.username,
      createdAt: comment.createdAt,
      depth: comment.depth,
    });

    for (const childId of comment.children) {
      await getRepliesRecursively(childId);
    }
  };

  // Post의 댓글들을 차례대로 순환하며 재귀적으로 대댓글 가져오기
  for (const commentId of this.comments) {
    await getRepliesRecursively(commentId);
  }

  return comments;
};

구현의 한계점

게시물의 댓글 배열, 댓글의 대댓글 배열에 실제 데이터가 아닌 id값만 갖고 있다. 이에 대한 단점은 아래와 같다.

• Comment.findById(commentId)?.populate('children');에서 모든 댓글을 순환하며 탐색한다. 엄~~~~~~~청 느리다.
  • 모든 게시물의 모든 댓글을 가져올 때 O(모든 댓글 수^2)의 시간복잡도를 갖는다.
  • 댓글이 1만개만 되더라도 1억번의 연산을 거쳐야한다.
  • 훨씬 빠른 방법을 샤워하다가 생각해냈다. (나중에)
• Model.findOne()은 O(N), Model.findOneById()는 O(1) 짜리 함수인 줄 알았다. 모델의 데이터마다 고유한 id를 가지니까… O(1)로 생각했다. 이는 오해였다.

What is the difference between Model.findOne() & Model.findById() in Mongoose?

프론트

백엔드에서 가공을 전부 해줬다. 따라서 배열 하나에 모든 댓글이 다 들어있다.
프론트에서는 이런 값을 받는다.

[   // 댓글이 많이 달린 게시물
    {
      _id: new ObjectId("64ce154c7bbfe751997449fe"),
      body: '이건 2번째',
      username: '1234',
      createdAt: 2023-08-05T09:24:28.499Z,
      depth: 0
    },
    {
      _id: new ObjectId("64ce15607bbfe75199744a04"),
      body: '뎁스는?',
      username: '1234',
      createdAt: 2023-08-05T09:24:48.790Z,
      depth: 1
    },
    {
      _id: new ObjectId("64ce15687bbfe75199744a09"),
      body: '뎁스는?',
      username: '1234',
      createdAt: 2023-08-05T09:24:56.058Z,
      depth: 2
    },
    {
      _id: new ObjectId("64ce15747bbfe75199744a0e"),
      body: '이번에도 2겠죠?',
      username: '1234',
      createdAt: 2023-08-05T09:25:08.121Z,
      depth: 2
    },
    {
      _id: new ObjectId("64ce304a3454d9f34a4b8d48"),
      body: '중간에다가 depth 3 끼워넣기',
      username: '1234',
      createdAt: 2023-08-05T11:19:38.594Z,
      depth: 3
    },
    {
      _id: new ObjectId("64ce305c3454d9f34a4b8d4d"),
      body: 'depth 4 끼워넣기',
      username: '1234',
      createdAt: 2023-08-05T11:19:56.397Z,
      depth: 4
    },
    {
      _id: new ObjectId("64ce30633454d9f34a4b8d52"),
      body: '5 끼워넣기',
      username: '1234',
      createdAt: 2023-08-05T11:20:03.153Z,
      depth: 5
    },
    {
      _id: new ObjectId("64ce19595388b4089868fec8"),
      body: '이번에도 2겠죠?',
      username: '1234',
      createdAt: 2023-08-05T09:41:45.864Z,
      depth: 2
    },
    {
      _id: new ObjectId("64ce268605331dafbbac3928"),
      body: '정렬은 대댓글의 부모가 1순위',
      username: '1234',
      createdAt: 2023-08-05T10:37:58.591Z,
      depth: 1
    },
    {
      _id: new ObjectId("64ce26dd3640bcedce3e976a"),
      body: '그래서 여기에 대댓글 달면 아래보다 위에 생성됨',
      username: '1234',
      createdAt: 2023-08-05T10:39:25.009Z,
      depth: 2
    },
    {
      _id: new ObjectId("64ce269705331dafbbac392c"),
      body: '생성 시각이 2순위',
      username: '1234',
      createdAt: 2023-08-05T10:38:15.386Z,
      depth: 1
    }
]

depth를 토대로 사용자에게 보여주기만 하면 된다.
 
JSX에서 렌더링할 때, 연속된 공백은 하나의 공백으로 치환된다. 따라서 밑의 코드에서 2번 방식으로 작성해줘야 띄어쓰기를 제대로 출력할 수 있다.

// 안 되는 코드
const generateCommentForm = (comment) => {
    const space = '     '.repeat(comment.depth); // 여러개의 공백이 무시된다.

    return (
      <div className='flex justify-between'>
        <div>
          {space} {comment.username} : {comment.body}
        </div>
        <div className='text-xs'>
          {comment.createdAt.slice(5, 16)}
        </div>
      </div>
    )
  }

// 되는 코드
const generateCommentForm = (comment) => {
    const space = '\\u00A0\\u00A0\\u00A0\\u00A0'.repeat(comment.depth);

    return (
      <div className='flex justify-between'>
        <div>
          {space} {comment.username} : {comment.body}
        </div>
        <div className='text-xs'>
          {comment.createdAt.slice(5, 16)}
        </div>
      </div>
    )
  }