채팅에 브랜치(Branch)를 도입해 여러 갈래로 대화하기

우리는 AI 캐릭터 채팅 서비스를 운영하면서, 사용자들이 자신이 원하는대로 이야기를 끌고 갈 수 있었으면 하는 니즈가 많다는 것을 발견했다.

그들은 자신이 원하는 캐릭터와 대화하면서 자신이 머릿속에 그리는 최상의 시나리오로 대화를 끌고가고자 하였다.

그리고 자신이 원하는 방향 아래, 다양한 상황에서 자신이 원하는 방향으로 끌고 가는 니즈도 있었다.

예를 들어 고백하여 사귀는 방향 아래에서, 공원 벤치에서 고백을 해보고, “오 괜찮네?” 하고 다음엔 멋진 바다 앞에서 고백을 하는 느낌이다.

그러면 이걸 어떻게 구현할 수 있을까?

원래라면 사용자는 자신이 원하는 상황을 또 겪고 싶으면 새로운 채팅방을 만들어 처음부터 그 상황까지 오기 위해 또 열심히 채팅을 해야 한다.

호감도 80으로 만드는 것이 목표라면 다시 호감도 0에서부터 시작해야 하는 것이 문제였다.
충분히 호감도 50 정도에서 다시 시작하면 좋은 부분만 반복할 수 있는데 말이다.

사용자 입장에서 호감도 0에서 50으로 끌어올리는 채팅은 이제 지루하게 느껴질 것이다.
그래서 우리는 채팅에 브랜치의 개념을 넣어서 자신이 원하는 곳에서 분기시킬 수 있는 기능을 넣기로 하였다.

아래 예시를 보자.
채팅을 시작하고 캐릭터랑 사이가 좋아져서 고백을 했는데 차였다.

사용자는 자신의 고백 멘트가 별로라고 생각해서(…) 그 부분으로 돌아가 그 전까지의 기억과 대화 내용을 보존한 채 고백한 타이밍으로 다시 돌아가서 끝내주는 고백 멘트로 다시 고백을 했더니 성공하게 되었다!

컨셉 자체는 매우 이해하기 쉽다.
특히 개발자라면 Git을 쓰기 때문에 더 잘 와닿는 기능이기도 하다.

다른 서비스는 브랜치를 어떻게 제공하고 있을까?

다른 AI 채팅 서비스도 브랜치 기능을 제공하는 곳이 있다.
하지만 모두 Create Branch를 누르면 새 채팅방으로 복제가 되는 것이었다.

같은 페이지에서 브랜치가 생기는 것이 아니고, 분기점까지의 채팅이 복제되며 새 채팅방이 생기는 방식이었다.

우리는 한 채팅 페이지 안에서 우리가 생각하는 진짜 브랜치처럼 동작하게 하는 것이 목표였고, 사용자에게 브랜치 맵을 보여줘서 자신이 현재 어디에 있는지 보여주는 기능도 넣으려고 하였다.

아래는 실제 완성된 브랜치 맵이다.

채팅 구조

우리는 채팅을 ChatGroup – ChatContentGroup – ChatContent 계층으로 관리하고 있다.
Chat Group이 우리가 보는 하나의 말풍선 개념이고, 그 안에 Chat Content Group과 Chat Content로 나뉘어져 있다.

Chat Content는 Regenerate 했을 때 한 말풍선 안에 추가되는 방식이다.

상당히 많은 고민의 흔적

브랜치 기능은 채팅 기능 자체의 프레임이 바뀌는 것이라서 개발 할 때 한 번에 잘 짜야 한다.
채팅의 관리가 이제 브랜치를 기반으로 될 것이기 때문에, 시간이 더 걸리더라도 효율적으로 좋은 구조를 만드는 것이 더 좋은 선택이라고 생각했다.

다행히 이전 사이클이 금요일에 끝나서 주말 동안 브랜치 구조를 생각해볼 시간이 생겨서 어떤 구조가 좋을까 하며 계속 구상을 했던 것 같다.

최소 공통 조상 (LCA) 부터해서 지금까지 공부해 온 알고리즘이 머릿속에서 떠돌면서 최대한 좋은 구조를 찾기 위해 생각을 많이 했다.

브랜치를 어떻게 구현할까 : 1. 단순 복제

첫 번째 접근은 다른 서비스가 하는 것처럼 모든 채팅을 단순 복제하는 것이다.
브랜치가 만들어지는 순간, 시작부터 분기점까지의 채팅을 복제한다고 생각해보자.

이러면 문제가 하나 발생하는데, 아래 예시를 보자.

“내 전공은 컴퓨터 공학이야.” 라는 부분에서 분기를 했다고 하자.
그러면 처음부터 이 채팅까지는 기존과 똑같고 그 다음 흐름이 달라져야 한다.

만약 사용자가 아래와 같이 “내 전공은 산업 공학이야.” 라고 메시지를 수정하면 브랜치 1의 같은 채팅은 내용이 안 바뀐다는 것을 알 수 있다.

그래서 사용자가 만약 브랜치 1로 되돌아갔을 때 다시 컴퓨터 공학을 전공하는 사람이 되어버리는 문제가 있다.

브랜치를 어떻게 구현할까 : 2. 브랜치를 선(Line)으로

다음 접근은 브랜치를 직관적으로 하나의 선으로 보고 갈라진 지점부터 새로운 Branch Line이 생기는 개념으로 접근해보았다.

BranchLine에는 StartChatGroup이 있어서 Root까지 그대로 타고 올라가면 거의 상수 시간안에 현재 브랜치에 속한 채팅들을 알 수 있다.

부모를 타고 올라가서 조회하는 것도 번거롭다면,
Chatroom과 1 : 1로, 현재 선택된 브랜치 흐름을

BranchLineFlow = ['노랑', '보라', '빨강']
이런 식으로 반정규화해서 저장하는 것도 생각을 해보았다.

이 방법의 장점은 Create Branch Operation이 매우 효율적이라는 것이다.
이전 채팅은 별개의 Branch Line으로 관리되기 때문에 새로운 Branch Line만 만들어주면 되기 때문이다.

그리고 채팅 추가 시에도 currentSelectedBranchLine 이런 상태로 추가하면 돼서 매우 편하다.

하지만 몇 가지 단점이 있다.

우선 Branch Switching이 조금 불편하다.
위 그림에서 13번 채팅에서 8번 채팅으로 갈 때, 8번 채팅부터 시작해서 부모로 타고 올라가며 BranchLineFlow를 다시 계산해야 한다.

그리고 이게 더 큰 단점인데, 채팅 조회가 매우 불편하다.

채팅 기록 조회는 Cursor 기반 페이징 조회인데, 13번에서 위로 조회를 한다고 가정해보자.

페이징 조회를 할 때, 내가 속해있는 브랜치의 BranchLine 을 조회했을 때 [11, 13]으로 Limit을 다 채우지 못 했으면 부모 Branch Line에서 조회를 계속해야 한다는 점이다. [6, 9, 11, 13]만으로도 Limit이 다 채워지지 않으면 또 부모 Branch Line에서 조회를 계속해야 한다.

즉, 조회가 최대 Limit번 만큼 일어날 수도 있고, 그 과정도 매우 불편하다.

그리고 브랜치 이동 기능을 고려하여 이제 중간에서 채팅 조회가 가능해야 하는데, 초록색 Branch Line을 선택한 상태로 5번 채팅을 Cursor로 위아래로 채팅을 조회했을 때 5번 채팅은 초록색 Branch Line과 어떤 관계가 있는지 찾기가 매우 어렵다.

자식에서 부모로는 참조가 쉽지만, 부모에서 자식에서 참조가 어렵다.
그래서 Branch Line에도 Child에 대한 정보를 넣는 것을 고려해보았는데, 더 구조가 복잡해지는 거 같다고 생각했다.

Edge Case를 생각해볼 수록 더 구조가 복잡해지는 거 같아 다른 방법을 고려하기 시작했다.

브랜치를 어떻게 구현할까 : 3. 브랜치를 점(Dot)으로

브랜치 구조는 1번 방법(채팅 전체 복제)이 가장 편하다.
그러면 1번 방법이 가졌던 문제인, 공유해야 되는 채팅의 수정이 일어났을 경우 한 쪽만 수정되는 현상을 해결하기 위해 나는 BranchChatGroup이라는 개념을 도입했다.

포인터 느낌으로 BranchChatGroup은 branchId와 chatGroupId을 가리키고 있어서, 이 BranchChatGroup이 어떤 브랜치에 속하고, 어떤 채팅을 가리키는지 알 수 있도록 하였다.

내부적으로는 BranchChatGroup으로 관리되지만, 가리키는 실제 ChatGroup은 똑같기 때문에 사용자가 Chat Group을 수정했을 때 다른 브랜치에도 변경 사항이 자연스럽게 적용된다.

이렇게 하면 장점이 위에서 언급한 대로 변경 사항 등 이전 채팅 변경이 자연스럽게 같이 적용된다는 것이다.

1번 방법에서 브랜치를 만들 때 ChatGroup을 모두 복사하는 것은 상당히 무거운 작업이다.
ChatContentGroup, ChatContent도 모두 복사해야 하기 때문이다.

하지만 BranchChatGroup들만 만드는 것은 참조만 넣는 것이기 때문에 성능적으로도 더 빠르게 복사할 수 있다.
실제로 테스트한 결과 3,000개의 BranchChatGroup을 처리하는 시간이 2,500ms (2.5초) 정도 밖에 안 되었다.

그래서 위 예시를 Branch Chat Group으로 나타내면 아래 그림과 같다.

그리고 2번 방법의 가장 큰 문제였던 Branch Switching과 채팅 조회도 매우 쉽게 된다.

브랜치의 채팅들이 BranchChatGroup으로 모두 복제된 상태이기 때문에 브랜치 전환 시 채팅방에 설정된 현재 선택된 브랜치 아이디만 변경해주면 된다.

그리고 채팅 조회의 경우, BranchChatGroup의 branch_id로 필터링하면 부모 / 자식 상관없이 자신의 브랜치에 해당하는 채팅만 나오게 된다.

그래서 최종적으로 아래 문제들을 모두 원하는 수준으로 해결할 수 있다고 판단하고 BranchChatGroup 기반 브랜치 구조를 채택하게 되었다.

1번 방법이 가지는 문제
- 공유되는 채팅의 경우, 수정이 복잡함
- 전체 복제 시간이 오래걸림
2번 방법이 가지는 문제
- 브랜치 스위칭이 복잡함
- 채팅 조회가 매우 복잡함

생각보다 고려해야 할 점이 많다

하지만 Regeneration 관련해서 고려해야 하는 점이 또 있다.

아래 예시를 보자.
두 번째 채팅에서 Regeneration을 해서 Chat Content 가 Chat Group에 새로 생겼다고 하자.

이때 중간 채팅에서 새로운 흐름이 생겼으니 바로 브랜치를 만들고 BranchChatGroup을 만들어서 진행하면 될 거 같지만, 그렇게 하면 Regeneration 개수만큼 브랜치가 생기는 문제가 있었다.

실제로 한 채팅에 Regeneration을 20번까지 하는 유저도 있고, Regenerate를 한다는 것은 채팅이 마음에 안 들어서 재생성한 것이므로 그 중 1개의 채팅만 선택해서 진행하게 된다.

즉, 브랜치 18개는 그냥 생성만 되고 버려진다는 것이다.
그리고 사용자는 그걸 브랜치라고 생각하지도 않을 것이다.

이 문제를 해결하기 위해 나는 브랜치로서 의미를 가지는 순간 BranchChatGroup을 만들기로 하였다.

Regeneration 만으로는 이 브랜치가 분기되었다고 할 수 없고, 아래 사진과 같이 Regenerated 된 채팅을 선택하고 채팅을 진행했을 때 그때서야 두 갈래로 갈라지므로, 그 채팅이 브랜치로서 의미를 가진다.

사용자 입장에서도 Regeneration 한 채팅에서 이야기를 계속할 때 새로운 분기점이 만들어졌다고 생각할 것이다.

그러면 메모리는?

메모리도 BranchMemoryGroup이라는 Wrapper를 하나 더 만들어서 MemoryGroup을 가리키도록 하였다.

이렇게 하면 채팅의 경우와 마찬가지로, 공통되는 부분은 같은 메모리를 가지게 할 수 있고, 메모리를 수정해도 BranchMemoryGroup은 실제 메모리를 가리키고만 있기 때문에 변경 사항은 역시 자연스럽게 같이 반영된다.

프론트에서는 `BranchChatGroup`을 사용하지 않는다

프론트 단에서는 이미 모든 채팅 로직이 ChatGroup 기반이었기 때문에, 이걸 모두 BranchChatGroup으로 바꾸는 것은 상당히 위험한 일이라고 생각하였다.

그래서 프론트에서는 BranchChatGroup을 전혀 사용하지 않고, 여전히 ChatGroup을 사용한다.
어차피 프론트에서는 여러 브랜치의 채팅은 한 번에 보이지 않고, Branch Switching 을 해야 다른 브랜치의 채팅을 볼 수 있기 때문에 상관이 없다.

대신 ChatContentGroup에 branchIds: string[] 라는 필드가 추가되어서 현재 채팅에서 스위칭 할 수 있는 브랜치 리스트를 보여줄 수 있도록 하였다.

현재 브랜치에서 다른 브랜치의 채팅이 보일 필요는 없지만, 다른 브랜치에 대한 정보는 보여야 한다.
그래야 현재 채팅에서 이전에 생성한 브랜치로 이동할 수 있을 것이다.

그래서 branchIds는 BranchChatGroup이 해당 ChatGroup을 가지는 지의 여부를 필드 하나로 판단할 수 있도록 한 것이다.

그리고 모든 채팅 관련 API에 branchId 라는 요청 파라미터가 추가되어서 현재 선택된 브랜치에 대한 내용만을 가져올 수 있도록 변경되었다.

기능 자체가 구조도 굉장히 복잡하고 플로우도 많기 때문에 문서를 자세히 써두려고 하였다.
문서를 잘 써두면 프론트 짤 때 굉장히 편하고, 백엔드에서도 후에 수정이 있을 때 참고하기 매우 좋다.

아래는 Branch Docs의 일부이다.
백엔드 입장에서 케이스 별로 나누어 동작을 정의했고, 프론트 입장에서도 브랜치가 생성되는 모든 플로우를 플로우 차트로 나타냈다.

마무리

브랜치 기능은 현재 페이지에서 브랜치가 스위칭되는 형태로는 다른 서비스에서 제공하지 않기 때문에 우리에게 있어서 굉장히 도전적인 퀘스트였다.

우선 좋은 브랜치 구조를 고민해보는 과정이 재미있었다.
알고리즘과 문제 해결을 좋아해서 더 좋은 구조를 위해 고민하는 과정이 내게는 하나의 게임이었다.

그리고 비록 버려진 아이디어 였지만 알고리즘 문제에서 밖에 못 써먹어 본 심화 알고리즘을 활용할 기회가 있어서 의미가 있었다.

성능 걱정을 많이 했지만 배포 후에도 열심히 좋은 구조를 생각해서 개발했기 때문에 성능 이슈는 전혀 없었다.

지금 생각해보면 데이터베이스 최적화 영역은 테이블 설계와 인덱스 설계만 잘해도 80%는 먹고 들어간다고 느꼈다.

인덱스가 세게 걸려있고 중요한 테이블에 Update가 많을 때는 테이블을 분리해서 Update 쿼리를 날리거나, 아니면 Soft Delection을 고려하거나…
무거운 연산이 필요한 쿼리의 경우, 필터링으로 Rows를 최대한 줄여서 Full Scan을 막는다던가…
100%의 정확성을 요구하지 않지만 필요한 기능이라면 반정규화를 고려한다거나…

결국 성능에도 큰 문제없이, 기능적으로도 Edge Case를 다 잡기 위해 QA를 엄청나게 많이 했기 때문에 성공적으로 배포할 수 있었다.

여담이지만 백엔드와 프론트엔드를 모두 했는데, 이 기능은 프론트엔드 개발이 과장 없이 4배 이상 어려웠다… (다른 글에서 다룰 예정)

아래와 같이 브랜치를 몇 십개 만들어도 문제가 없었다!

무엇보다 사용자분들께서도 매우 좋아해주셔서 큰 보람을 느꼈다.