2022년 초, 멜론뮤직어워드(MMA) 2022 행사를 준비하는 과정에서 기존 MMA 생중계 시 사용되는 댓글 시스템이 사용자 참여에 불편함이 있었고, 이를 해소하기 위해 '실시간 채팅 플랫폼'의 필요성이 대두되었습니다. 그래서 '실시간 채팅 플랫폼' 도입을 위한 3가지 방안을 검토했는데요.
자체 구축 채팅 플랫폼
카카오톡 소스 활용
외부 채팅 플랫폼
어떤 방안을 선택할지 논의가 이어졌고, 복잡하고 다양한 내부 서비스(시스템)의 요구사항을 수렴하는 것이 가장 중요했기에 '자체 구축 채팅 플랫폼'으로 최종적으로 결정하게 되었습니다. 그 당시 플랫폼개발실 산하 플랫폼개발2팀(현 파트너플랫폼개발팀)에서 개발을 맡게 되었고, 결정된 '실시간 채팅 플랫폼'의 사전 요구사항은 다음과 같았습니다.
✔️ 동시 접속자 200,000 명 처리 ✔️ 채팅 메시지 전송/수신 max 1000ms(1초) ✔️ 금칙어 관리(추가/제거) 실시간 적용 ✔️ 실시간 도배 탐지 ✔️ 채팅 메시지 영구 저장 ✔️ 실시간 채팅 지표 모니터링 ✔️ 채팅 meta정보 관리
위 요구사항을 5개월 정도의 짧은 시간 안에 분석/설계/구현/성능검증(테스트)까지 모두 완료해야 하는 매우 도전적인 프로젝트였는데요.
Jace, Umid, Probe!3명의 개발자가 '라이브채팅'이라는 프로젝트명을 확정한 시점부터 고군분투하며 플랫폼을 구현하고, 멜론뮤직어워드(MMA) 2022와 고막소년단 Live를 성공적으로 완수했을 때까지의 노력과 경험을 소개해보려고 합니다.
Umid / Probe / Jace
[Chapter 1] 개발 언어 및 기반기술 조사
1. 개발 언어 선정
가장 먼저 라이브채팅 플랫폼의 다양한 애플리케이션을 구현하기 위한 개발 언어를 선정했는데요.
후보군으로 Java, Kotlin, Go Lang, Erlang을 선정하고, 어떤 언어를 사용할지 개발자 입장에서 검토했습니다.
언어
장점
단점
Java
◽️ 참여 개발자 모두 익숙한 보편적인 언어 ◽️ 별다른 Study없이 바로 구현 가능
◽️ 지겨운 NullPointerException 처리 ◽️ 불필요한 행사 코드 다수 필요 ◽️ Modern한 언어들의 기본적인 지원사항 지원이 늦음 - String Template - Null Safety
◽️ CPU 연산에서 Java, Kotlin 대비 빠른 처리 성능 ◽️ Java, Kotlin에 비해 보다 다 적은 Resource를 사용
◽️ 개발 경험 없음 ◽️ 제대로 된 구현을 위한 일정 수준 이상의 Learning curve 발생 ◽️ Go Lang 기반 Eco system에 대한 경험 부족
Erlang
◽️ Facebook의 Erlang을 활용한 Chat 성능 개선 사례 보유🔗 ◽️ 동시성 및 분산 시스템 개발에 유리
◽️ 개발 경험 없음 ◽️ 제대로 된 구현을 위한 일정 수준 이상의 Learning curve 발생 ◽️ 참여 개발자에게 익숙지 않은 언어 패러다임 - Erlang은 FP(Funtional Programing)언어 ◽️ Java/Kotlin/GoLang 대비 상대적으로 적은 Documents & Reference
4가지 언어를 비교 검토한 결과, Go Lang, ErLang은 많은 BMT(BenchMarking Test) 문서 상에서 Java, Kotlin 대비 높은 성능을 보여주긴 했지만 한정된 개발 인원과 개발 기간을 고려하면 Learning curve가 커서 리스크가 발생할 수 있다고 판단되어 제외했고, Java는 Kotlin 대비 개발하기 익숙하다는 것 외에 큰 장점을 찾기 힘들었습니다. 무엇보다 Kotlin이 지원하는 비동기 로직을 매우 간단한 형식으로 구현할 수 있는 Coroutine은 Java 대신 Kotlin을 선택하는 데 있어서 충분한 설득 요소가 되었고, 결국 저희는 만장일치로 Kotlin을 주 언어로 선택하게 되었습니다.
2. Framework
서버 구동에 필요한 Framework은 언어 선정 초기부터 큰 고민의 영역은 아니었습니다. 모두에게 너무나 익숙한 Spring Boot Framework의 대안을 찾는 것이 사실상 무의미하지 않을까 생각됐기 때문이죠.
그러나 개발언어를 Kotlin으로 정한 만큼 Kotlin과 핏이 조금 더 잘 맞을 것 같은 Ktor [케이토르]에 대해 찾아보게 되었고, 비교적 간단한 HTTP, Websocket 통신을 처리하는 채팅 플랫폼 특성으로 보면 Spring Boot의 대안으로 사용해도 큰 문제는 없어 보였습니다.
그러나,
아직까지 Production level에 적용한 사례를 거의 찾아볼 수 없다는 점
Ktor기반 서버의 신뢰도 및 Ktor 운영 시 겪게 될 Trouble Shooting을 위한 Documents 부족
을 감당하기엔 리스크가 크다고 판단하여 Spring Boot Framework로 결정하게 되었습니다. 하지만 차후 간단한 프로젝트를 진행하게 된다면 Ktor 도입을 적극 검토해 볼 생각이 들 만큼 가볍고 확장성이 뛰어나며 직관적인 설정과 간단한 구현 방식이 굉장히 매력적이라고 생각합니다.
🔍 Ktor [케이토르] 🏠 Kotlin의 개발사인 JetBrains가 만든 Kotlin 기반으로 동작하고, 비동기 서비스를 지원하기 위해 내부적으로 Coroutine을 사용하는 Framework입니다. Ktor는 Application 간 연결을 쉽게 만들어주기 위한 Framework로, Web Application, HTTP Service, Mobile 및 Browser Application 등을 지원합니다.
3. 채팅 서버 메시지 처리 방식
채팅 서버 메시지 처리 방식은 크게 2가지 방식을 검토했습니다.
1️⃣ HTTP Polling
다양한 타 서비스들의 구현 방식을 찾아보던 와중에 'Youtube LIVE'가 'HTTP Polling'방식을 이용해서 구현을 한 것임을 알게 되어 검토하게 되었습니다. HTTP Polling 방식은 WebSocket과 다르게Connection을 맺고 있지 않아도 돼서, 서버 리소스를 상당히 절약할 수 있었고, API 서버 개발만으로 간단하게 기능 구현이 가능하다는 점에서 우선적으로 고려하게 되었었습니다. 그러나 일정 주기로 메시지를 클라이언트에서 가져가는 방식이기 때문에 다른 사용자가 작성한 메시지가 전달되는 데까지 일정 시간 지연이 발생할 수 있고, 클라이언트 별로 Polling 되는 시점에 따라 서로 보고 있는 메시지가 다르기 때문에 실시간으로 보이는 라이브 영상과 대화 내용이 수초 가량 불일치하는 문제가 발생할 수 있다는 단점이 있었습니다.
2️⃣ WebSocket
대부분의 라이브채팅 플랫폼에서는 가장 많이 사용되는 메시지 전달 방식으로, 유저와 서버 간의 Connection이 맺어져 있는 상태이기 때문에 메시지가 발생하는 즉시 전달할 수 있다는 장점이 있으나, 서버와 연결이 지속되어야 하므로 서버당 처리할 수 있는 클라이언트의 수의 제한이 있다는 단점이 있습니다. 하지만 HTTP Polling 방식에서 발생하는 단점이 거의 완벽에 가까운 수준으로 발생하지 않습니다.
HTTP Polling vs WebSocket
실시간 라이브채팅의 특성상 1:1 대화가 아닌 많은 사용자가 동시에 진행하는 채팅이기 때문에 일부 메시지의 순서가 섞이거나 서로 다른 메시지를 보고 있다 하여도 대화의 맥락을 이해하는 데에는 크게 문제는 없다고 생각하여 두 방식 모두 저희의 서비스에 사용은 가능하다는 결론을 내렸고, 그렇다면 우리 서비스의 관점으로 장/단점을 정리해 봤습니다.
Type
장점
단점
HTTP Polling
◽️ 서비스 구현이 간단하고 편리함
◽️ 유저가 작성한 메시지의 전달 속도가 Polling 주기에 따라 결정됨 ◽️ Polling된 시점에 따라 사용자가 보고 있는 채팅의 내용이 상이 할 수 있음 ◽️ 메시지의 Sync를 위해 많은 클라이언트에서 Polling 주기를 짧게 조정하면 서버의 부하가 심해짐
Web Socket
◽️유저가 작성한 메시지의 전달을 서버에서 진행하므로 즉각 전달이 가능함 ◽️ 모든 시점에서 사용자가 보고 있는 채팅의 내용이 일치함
◽️ 구현 방식이 HTTP Polling에 비해 복잡함 ◽️ 서버당 연결 가능한 클라이언트 수가 제한됨 ◽️ 서버와 Connection을 유지하기 위한 리소스가 낭비됨
이렇게 HTTP Polling과 WebSocket 모두 각각의 장단점이 있었지만, 최종적으로 WebSocket을 선택하게 되었습니다. 구현에는 HTTP Polling 방식이 조금 더 편리하고 간단했지만, 대화형 라이브 영상 서비스에서 메시지의 전달 지연이 부정적인 사용자 경험을 줄 수 있다는 의견이 있었고, 따라서 메시지 처리 방식으로 WebSocket을 결정하게 되었습니다.
4. 채팅 메시지 영구 저장소
채팅 메시지에 대한 영구 저장소를 선택하기 위해서 다음과 같은 요소를 고려하였습니다.
채팅 메시지는 타입별로 메시지(유저/아티스트/공지 등)의 구조가 다르고, 기능적인 메시지의 추가가 빈번할 수 있을 것으로 예상
사용자가 작성한 메시지의 수정/삭제는 사실상 이루어지지 않고, 저장/조회 Operation만 발생할 것으로 예상
이와 같은 요인들을 고려했을 때, 메시지에 대한 영구 저장소는 RDMS 보다는 NoSQL이 더 잘 맞다고 판단되었고, 다양한 NoSQL 중 다음과 같은 장점들 때문에 MongoDB 선택하게 되었습니다.
✔️ Schemaless 한 특성을 통해 다양한 형식의 메시지를 유연하게 저장/관리할 수 있음 ✔️계층적인 도큐먼트 형태로 저장되기 때문에 메시지 내의 다양한 객체를 포함하여 한 번에저장할 수 있으며, 효과적으로 메시지 내의 모든 객체 관계를 저장/탐색 가능함 ✔️Cloud 형태로 제공하는 서비스를 사용할 수 있기 때문에 DB 시스템에 대한 관리 리소스가 별도로 필요하지 않음
5. Message Broker
라이브채팅 플랫폼에서는 대량의 채팅 메시지가 유저와 서버, 서버와 서버 사이에 오고 가게 됩니다. 이런 메시지들을 효율적으로 전달하고 관리할 메시지 브로커로 Redis Pub/Sub, Google Cloud Pub/Sub, Apache Kafka를 비교 검토했습니다.
1️⃣ Redis Pub/Sub
Google Cloud의 Memorystore 사용 시 Redis 클러스터를 간단하게 생성하여 운영 가능하다는 점과 기본적으로 메시지 전달이 매우 빠르다는 점 때문에 Redis Pub/Sub을 메시지 브로커로 우선 고려하게 되었습니다.그러나 대규모 트래픽 부하 테스트를 진행하면서 Redis Pub/Sub으로 인한 성능 저하를 발견하게 되었는데, 요인은 다음과 같았습니다.
✔️ Redis Pub/Sub으로 메시지 발행 시 모든 Redis 클러스터의 노드에 메시지를 발행합니다. 그래서 클러스터의 노드를 확장할수록 Pub/Sub 속도 저하가 발생하게 됩니다. 이 특성은 Redis 7.x 에서 제공하는 Sharded Pub/Sub을 통해 개선 가능하지만, Google Cloud Memorystore에서는 개발 시점인 2022년까지 Redis 6.x만 지원하고 있었습니다.
✔️ 특정 채널에 메시지 발행 시, 채널을 구독하는 모든 subscriber를 순회하며 메시지를 발행합니다. 즉, 채널의 subscriber 수가 많아질수록 linear 하게 메시지 발행 속도도 지연되게 됩니다.
대량의 채팅 메시지가 오고 가는 라이브채팅 플랫폼 특성상 Redis 클러스터의 노드 확장은 불가피하고, 채널 단위로는 확장성(scalability)이 떨어지며, 채널을 여러 개로 분리하고 subscriber들을 각각 다른 채널로 분리하는 형태로 확장성(scalability)을 확보하더라도 애플리케이션 레벨에서 채널 분리를 컨트롤해야 합니다. 이 외에도 subscriber가 존재 여부와는 상관없이 발행된 메시지가 사라지게 되는 메시지 휘발성 및 메시지 전처리, 후처리 등을 위한 파이프라인을 직접 설계하고 구축해야 한다는 단점 때문에 스트림(Stream)으로 눈길을 돌리게 되었습니다.
2️⃣ 스트림(Stream): Google Cloud Pub/Sub vs Apache Kafka
메시지 비휘발성으로 인한 복구 용이, 스트림 프로세서를 활용한 메시지 처리 용이, 무엇보다 뛰어난 수평 확장성(scalability)을 이유로 스트림(Stream)을 사용하게 되었습니다. Google Cloud에는 지정 옵션에 따라 스트림으로 활용 가능한 Cloud Pub/Sub이 있어 먼저 고려하게 되었고, 스트림 중 널리 사용되고 있는 Apache Kafka도 같이 검토 및 구현을 진행하였고, 이론적인 부분과 실제 성능 테스트를 통한 비교를 진행하여 다음과 같은 결과를 얻을 수 있었습니다.
1) 글로벌 대응성 : Cloud Pub/Sub 승!
Cloud Pub/Sub은 글로벌 단위로 관리되며 서울 리전에서 발행한 Pub/Sub 메시지가 유럽 리전까지 전달되는 데 있어 특별하게 신경 쓰지 않아도 됩니다. Kafka의 경우, 글로벌 대응 시 Kafka 클러스터 위치와 클러스터 간 메시지 전달 등 여러 부분의 고민이 필요합니다.
2) 메시지 전달 속도(Latency) : Kafka 승!
아래 테스트는 서울 리전에 애플리케이션 서버를 둔 상태에서 이뤄졌고 Kafka의 Latency가 좋았습니다. 아무래도 모든 데이터 센터에 전파되도록 설계된 Cloud Pub/Sub이 지정된 클러스터를 사용하는 Kafka 대비 Latency가 떨어질 수밖에 없을 거라 생각합니다.
저희는 Cloud Pub/Sub을 Pull 방식으로 사용했는데, StreamingPull 방식 사용 시 다른 통신 방식들(Push or Pull) 대비 짧은 Latency를 제공한다고 하니 참고 바랍니다.
통계기준
Cloud Pub/Sub
Apache Kafka
p90
45ms ~ 180ms
30ms ~ 65ms
p99
500ms ~ 1,000ms
60ms ~ 100ms
3) 처리량(Throughput) : Cloud Pub/Sub 승! Cloud Pub/Sub은 별도의 파티션/샤드 관리 없이 petabyte(=1,000 terabyte) 이상의 데이터 처리가 가능합니다. Kafka는 높은 처리량 달성을 위해 파티션을 계속해서 늘려야 하며, 클러스터를 확장해야 등 일반적으로 Cloud Pub/Sub 보다 높은 처리량 달성이 힘듭니다.
4) Stream Processing : Kafka 승! 두 방식 간 스트림 프로세싱에 관한 내용은 하단 '6.Stream Processing' 항목에서 다루도록 하겠습니다.
5) Message Broadcast : Kafka 승!
동일 메시지를 여러 Subscriber/Consumer에 전달하기 위해 Cloud Pub/Sub에선 subscription을 중복 메시지 수만큼 생성해야 하고, Google Cloud 콘솔 혹은 API 호출을 통해서만 생성 가능합니다. 그러나 Kafka는 다른 Consumer Group ID를 가진 클라이언트(Consumer Group)를 띄움으로 인해 중복된 메시지 수신이 가능합니다. 동일 메시지 처리를 수평 확장해 나갈 때, Kafka 대비 Cloud Pub/Sub의 편의성이 떨어졌습니다.
6) 부가적인 특성 : Cloud Pub/Sub 승!
Cloud Pub/Sub은 스트림 특성 외에 메시지 큐 등 옵션 설정에 따라 다양한 메시지 브로커 성격을 지니고 사용할 수 있었으나, Kafka는 스트림에 한정된 프로그램입니다.
이렇게 비교 검토한 결과, 최종적으로 Apache Kafka를 선택하게 되었습니다. Kafka가 Cloud Pub/Sub에 비해 다소 아쉬웠던 글로벌 대응성 측면은 라이브채팅 플랫폼을 사용하는 유저가 우선 국내 한정이라는 이유로 상쇄되었고, 높은 처리량(throughput) 달성은 여러 파티션을 두고 메시지를 처리하는 방향으로 설계하여 해결하였으며, 또한 라이브채팅 플랫폼은 스트림 특성만 필요했기 때문에 Cloud Pub/Sub과 다르게 다양한 메시지 브로커 형식을 사용할 수 없다는 점도 문제가 되지 않았습니다.
6. Stream Processing
라이브채팅 플랫폼은 유저가 입력한 채팅 메시지를 같은 방의 다른 유저들에게 전달하기 전 다양한 처리를 수행합니다. 유저 메시지로부터 욕설, 광고 등의 문구를 감지하는 금칙어 감지 기능, 특정 유저가 다수의 금칙어를 입력했을 때 채팅 입력을 차단하도록 하는 스팸 방지 기능, 한 채팅에 많은 수의 유저가 참여하였을 때 채팅 방을 나눠 방마다 적절한 수의 유저수를 유지하게 하는 기능, 지표 수집 플랫폼으로 채팅 메시지를 전달하는 기능, 채팅 방의 최근 메시지를 캐싱하는 기능, 전체 채팅 메시지를 영구 저장소로 전달하는 기능 등 다양한 기능들이 수행되는데, 이런 기능들을 각각의 스트림 프로세서(stream processor)로 만들어 수행하고 있습니다.
유저 클라이언트와 Connection을 맺고 직접 메시지를 주고받는 WebSocket 서버가 아닌, 스트림 처리 과정에서 위 기능들을 수행하는 이유는 WebSocket 서버의 워크로드와 별개로 각각 스트림 프로세서마다 워크로드를 할당할 수 있기 때문입니다. 대규모 이벤트 시 가장 많은 워크로드를 사용하는 곳은 아무래도 각 클라이언트와 상시로 WebSocket Connection을 유지하고 있는 WebSocket 서버입니다. WebSocket 서버에서 부가적인 처리를 분리시킴으로 WebSocket 서버 워크로드의 부담을 덜어 줄 수 있습니다. 또한, 기능마다 필요로 하는 자원의 양과 종류가 다른데 각각 별도 프로세서와 워크로드로 운영할 수 있어 WebSocket 서버와 프로세서마다 개별적인 워크로드 운영이 가능해짐으로 인해 기능별 수직/수평 확장이 가능해지게 되고 이 때문에 전체 워크로드의 효율적 사용이 가능해지게 됩니다.
이렇듯 스트림 프로세싱은 채팅 부가 기능을 효율적으로 처리하는 핵심이며, 어떻게 스트림 프로세싱을 구현하고 운영할 수 있는지가 스트림 플랫폼(Cloud Pub/Sub vs kafka)을 결정함에 중요 요소가 되었습니다. 그래서 Cloud Pub/Sub 채택 시 사용 가능한Dataflow와 kafka 채택 시 사용 가능한 Kafka Streams를 이론적으로, 또 실제 구현 및 테스트함으로써 신중하게 비교하게 검토하였습니다.
✔️ Dataflow는 Google Cloud에서 제공하는 데이터 프로세싱을 위한 매니지드 서비스로, 매니지드 서비스이기 때문에 스트림 프로세싱 시 필요한 워크로드를 알아서 관리해 줍니다. 라이브채팅 플랫폼은 트래픽이 급격하게 증가하거나 유휴 상태가 오래 지속되는 등 일정한 트래픽을 유지하는 서비스가 아닌데요. 이런 서비스 특성에서 워크로드를 알아서 관리해 주는 것은 아주 큰 장점입니다.
✔️ 또한, 스트림 프로세싱뿐만 아니라 배치 프로세싱도 지원하는데 하나의 플랫폼으로 스트림과 배치 둘 다 처리 가능한 점이 매력적입니다. Dataflow 플랫폼은 오픈 소스로 공개된 Apache Beam 프로그래밍 모델을 통해 사용 가능한데, 'Dataflow를 스트림 프로세싱에 사용한다라는 것은 Beam을 이용한 프로그래밍을 한다'라고 볼 수 있습니다. Beam도 Dataflow의 특성과 같이 스트림과 배치 프로세싱 둘 다를 지원하는 프로그래밍 모델이며, Python, Java, go 등 다양한 언어를 지원합니다.
✔️ 그러나 이러한 Beam의 다양성은 스트림 프로세싱 프로그래밍만 한정해서 봤을 때 다른 플랫폼 대비 사용성을 떨어뜨리는 요소입니다. 비슷한 맥락이지만 스트림과 배치는 엄연히 구분되는 영역입니다. 또한, 전혀 다른 성격의 프로그래밍 언어들을 공통된 인터페이스로 지원하려다 보니 언어적 특성을 저해하는 경우가 많습니다. 주 언어로 Kotlin(Java)을 선택하여 Beam 프로그램을 만들어 보았는데 Java스럽지 않은 인터페이스 때문에 코드 가독성이 굉장히 떨어졌습니다. Beam의 Python API는 그나마 Java 보다 괜찮았지만 아무래도 Apache Beam이 구글에서 만든 오픈 소스이다 보니 Python을 메인으로 삼은 것 같습니다.
이 외에도 스트림 프로세싱에 필요한 세세한 부분까지 저수준에서 다뤄야 하므로 여러 가지 행사 코드들이 많이 발생합니다.Scala언어에 거부감이 없으시다면 Beam을 래핑 하여 추상화한Scio프로젝트를 눈여겨 볼만합니다.Spotify에서 만든 프로젝트이고 Beam 보다 잘 추상화된 형태의 API를 Scala 언어로 제공하는 프로젝트입니다. 저희는 직접 사용해보지 않았고예제 코드들만 살펴봤는데 Beam의Java 예제 코드들 대비 훨씬 잘 추상화된 깔끔한 코드들을 확인하실 수 있습니다.
2️⃣ Kafka Streams
Kafka 스트림에 대한 스트림 프로세싱이 필요할 때 기본 선택지는Kafka Streams입니다. Kafka Streams는 Kafka에서 제공하는 Java 프로그래밍 인터페이스이자 라이브러리입니다.
✔️ Kafka Streams는 스트림 프로세싱을 저수준에서 프로그래밍할 수 있는 Processor API를 제공합니다. Beam과 비슷한 API라고 보시면 됩니다. 또한 Kafka Streams DSL이라는 Processor API를 고도로 잘 추상화한 프로그래밍 API를 제공합니다. Java 개발자라면 익숙한 Fluent 인터페이스로 구성되어 있어 쉽게 학습할 수 있고 작성된 코드의 결과물도 깔끔하게 유지 가능합니다.
✔️ Kafka Streams는 쉽게 접근 가능한 관련 자료가 풍부합니다. Kafka Streams를 주제로 출간된 국내 서적들도 있고, 인터넷에서 다양한 자료들과 실전 경험담들을 찾을 수 있습니다. 반면 Dataflow와 Beam은 Kafka Streams 대비 자료가 아주 빈약합니다. Apache Beam은 사실상 공식 문서와 오픈 소스 Github 프로젝트 내 issue 탭 내 글들만을 의지하고 사용해야 합니다.
✔️Kafka Streams는 프로그래밍 API이며 서비스는 아닙니다. 심지어 Kafka 유료 플랫폼인 Confluent Cloud에서조차 Kafka Streams를 돌릴 수 있는 매니지드 서비스를 제공하고 있지 않습니다. 그래서 Kafka Streams를 사용하기 위해선 워크로드를 직접 구축하고 관리해야 합니다.
저희는 Kafka를 최종 채택하게 되었는데요. 워크로드를 직접 관리해야 하는 단점이 있지만, k8s 상에 구축하여 조금이나마 워크로드 관리의 부담을 덜 수 있었습니다. 또한, 라이브채팅 프로젝트의 주 언어인 Kotlin으로 간결하게 스트림 프로세싱 프로그래밍을 할 수 있어 프로젝트를 효율적으로 운영하는 데에 도움이 될 것으로 판단하였습니다. 그러나 Dataflow와 Cloud Pub/Sub이 주는 장점들이 있어 앞으로 해당 서비스와 Beam, Scio를 지속해서 관심 있게 지켜볼 예정입니다.
7. 금칙어 처리
채팅 중 일부 유저들이 욕설, 광고 등이 담긴 메시지를 입력하는 경우가 있습니다. 50만 개 이상의 욕설, 광고 등의 문구들로 구성된 금칙어 사전 데이터가 개발팀에 전달되었으며, 금칙어가 포함된 메시지들을 실시간으로 차단해야 하는 요구사항이 주어졌습니다. 유저들로부터 입력된 모든 메시지에 대해 이런 처리가 이뤄져야 하므로 신속하게 금칙어를 찾고 처리할 수 있는 기술에 대한 리서치가 필요하였습니다.
필요 공간 : 글자 노드(node) 간 포인터 및 최종 노드 표시를 위한 공간이 해시 테이블에 비해 추가적으로 필요합니다. 그러나 단어 수가 늘어나서 prefix가 겹치는 경우가 많아질수록 해시 테이블 대비 차지하는 용량이 적어집니다.
검색 속도 : 단어의 길이가 n 인 경우 O(n)이 소모되며, 글자 별로 노드 간 이동이 필요하기 때문에 해시 테이블 대비 약간의 오버헤드가 더 발생합니다. 그러나 찾으려는 단어가 사전의 없는 경우 즉시 종료가 가능한 반면 해시 테이블은 항상 해시 값을 구해야 하기 때문에 찾으려는 단어가 없는 경우에는 트라이가 조금 더 빠릅니다.
일반적으로 채팅 메시지 대다수는 금칙어가 포함되지 않는다라고 볼 수 있고, 그런 경우 트라이가 해시 테이블 대비 검색 속도면에서 유리하다고 판단하였고, 트라이에 대한 실질적인 테스트를 진행하게 되었습니다.
1) 필요 공간 확인
📄 테스트 코드
import com.github.javafaker.Faker;
import org.apache.commons.collections4.trie.PatriciaTrie;
import org.openjdk.jol.info.GraphLayout;
public class TestTrie {
static Trie<String, Boolean> trie;
@BeforeAll
static void setup() {
trie = new PatriciaTrie<>();
Faker faker = new Faker(new Locale("ko"));
IntStream.range(1, 10000).forEach(
i ->
{
var words = faker.lorem().words(getRandomNumber(1, 4));
var sentence = String.join(" ", words);
trie.put(sentence, true);
}
);
trie.put("exampleA", true);
printObjectSize(trie);
}
@Test
public void testTrie() {
var resultA = trie.get("exampleA");
assertNotNull(resultA);
var resultB = trie.get("exampleB");
assertNull(resultB);
}
private static int getRandomNumber(int min, int max) {
return (int) ((Math.random() * (max - min)) + min);
}
private static void printObjectSize(Object object) {
System.out.println("@@@@@@@@@ Object type: " + object.getClass() +
", size: " + humanReadableByteCount(
GraphLayout.parseInstance(object).totalSize()));
}
private static String humanReadableByteCount(long bytes) {
if (-1000 < bytes && bytes < 1000) {
return bytes + " B";
}
CharacterIterator ci = new StringCharacterIterator("kMGTPE");
while (bytes <= -999_950 || bytes >= 999_950) {
bytes /= 1000;
ci.next();
}
return String.format("%.1f %cB", bytes / 1000.0, ci.current());
}
}
📄 결과 - Trie 오브젝트의 크기
글자 수
2단어 조합
1~4단어 조합
100
9.9 kB
9.7 kB
1,000
91.8 kB
76.4 kB
10,000
539.7 kB
628.4 kB
100,000
896.4 kB
4.3 kB
200,000
-
7.7 kB
위 테스트로부터 몇십만 개의 금칙어로 트라이(Trie)를 구성하더라도 메모리에 올려서 사용하는 데 전혀 문제가 없다는 것으로 결론 내렸습니다.
2) 검색 속도 확인
단어 사전으로부터 특정 단어를 검색하는 속도는 단어의 길이가 n 인 경우 O(n)입니다. 그런데 금칙어 처리는 단어 사전으로부터 하나의 단어를 찾아내는 것으로 끝이 아닙니다. 채팅 메시지 문장 속에는 많은 단어가 포함되어 있기 때문에 단순하게 문장으로부터 단어들을 추출할 시 문장 속에 있는 글자들을 모두 순서대로 조합하면 되는데, 다음과 같은 형태의 단어 조합이 나오게 됩니다.
문장
단어 조합
AB
A, B, AB
ABC
A, B, C, AB, BC, ABC
ABCD
A, B, C, D, AB, BC, CD, ABC, BCD, ABCD
ABCDE
A, B, C, D, E, AB, BC, CD, DE, ABC, BCD, CDE, ABCD, BCDE, ABCDE
ABCDEF
A, B, C, D, E, F, AB, BC, CD, DE, EF, ABC, BCD, CDE, DEF, ABCD, BCDE, CDEF, ABCDE, BCDEF, ABCDEF
즉, 문자열 길이가 n일 때 n * (n+1) / 2 만큼의 단어 조합이 나오게 되며, 100자 길이의 메시지가 넘어올 경우 5,050개의 단어 조합에 따라 최대 5,050번 금칙어 사전과 비교가 필요하게 됩니다. 이는 매우 비효율적이며 실시간으로 금칙어를 발견하여 처리해야 하는 요구사항을 만족하게 하기 어려울 수 있습니다.
3️⃣아호-코라식(Aho-Corasick) 알고리즘
앞서 문장 내 가능한 모든 단어 조합을 추출하여 단어 사전과 비교하는 것은 매우 비효율적인 방식입니다. 해당 방식이 아닌 주어진 문장을 단 한 번만 순회하면서 차례대로 단어를 만들어가며 사전과 비교한다면 검색 속도를 높일 수 있습니다. 바로 트라이(trie) 기반에서 돌아가는아호-코라식(Aho-Corasick) 알고리즘으로 다음과 같은 극적인 속도 향상을 이끌어 낼 수 있습니다.
import org.ahocorasick.trie.Emit
import org.ahocorasick.trie.Trie
import org.apache.commons.lang3.time.StopWatch
import java.io.File
fun main(args: Array<String>) {
val tokenizer = MessageTokenizer("words-ko.wikipedia.org.txt")
tokenizer.parseMessage("동해 물과 백두산이 마르고 닳도록")
tokenizer.parseMessage("하느님이 보우하사 우리나라 만세")
tokenizer.parseMessage("무궁화 삼천리 화려 강산")
tokenizer.parseMessage("대한 사람, 대한으로 길이 보전하세")
tokenizer.parseMessage("남산 위에 저 소나무, 철갑을 두른 듯 바람 서리 불변함은 우리 기상일세. 무궁화 삼천리 화려 강산 대한 사람, 대한으로 길이 보전하세")
tokenizer.parseMessage("가을 하늘 공활한데 높고 구름 없이 밝은 달은 우리 가슴 일편단심일세. 무궁화 삼천리 화려 강산 대한 사람, 대한으로 길이 보전하세. 이 기상과 이 맘으로 충성을 다하여 괴로우나 즐거우나 나라 사랑하세. 무궁화 삼천리 화려 강산 대한 사람, 대한으로 길이 보전하세")
}
class MessageTokenizer(dictionaryPath: String) {
private val stopWatch = StopWatch()
private val trie: Trie
init {
stopWatch.start()
val words = File(dictionaryPath).bufferedReader().readLines()
trie = Trie.builder()
.ignoreOverlaps()
.addKeywords(words)
.build()
stopWatch.stop()
println("@@ initial time @@: ${stopWatch.time} ms")
}
fun parseMessage(message: String) {
stopWatch.reset()
stopWatch.start()
val emits: Collection<Emit> = trie.parseText(message)
emits.forEach { emit ->
run {
println("${emit.keyword}: [${emit.start}:${emit.end}]")
}
}
stopWatch.stop()
println("@@ parse message time @@: ${stopWatch.time} ms")
}
}
📄 수행결과
@@ initial time @@: 4955 ms
동해: [0:1]
물: [3:3]
... 생략 ...
@@ parse message time @@: 5 ms
하느님: [0:2]
이: [3:3]
보우: [5:6]
... 생략 ...
@@ parse message time @@: 0 ms
무궁화: [0:2]
삼천리: [4:6]
화: [8:8]
... 생략 ...
@@ parse message time @@: 0 ms
대: [0:0]
한 사람: [1:4]
대한: [7:8]
... 생략 ...
@@ parse message time @@: 0 ms
남산: [0:1]
위: [3:3]
에: [4:4]
... 생략 ...
@@ parse message time @@: 1 ms
가을: [0:1]
하늘: [3:4]
공: [6:6]
... 생략 ...
@@ parse message time @@: 2 ms
아호-코라식(Aho–Corasick) 알고리즘을 사용한 경우 사전 로드 후 첫 파싱 때 4~5 ms, 그 이후 파싱 때는 1~2 ms 시간이 소모되었고, 이는 채팅 메시지 하나하나에서 금칙어를 찾아내는데 충분히 이른 시간으로 결론 내렸습니다. 그래서 최종적으로 라이브채팅 플랫폼 금칙어 처리 프로세스에 아호-코라식(Aho–Corasick) 알고리즘을 적용하게 되었습니다.
