#Day 3 - 채팅 시스템 트래픽이 너무 많이 발생해요!!!

책상에서 꾸벅꾸벅 졸고 있는데 다시 전화가 왔다.

전화 : "안녕하세요 시스템팀 김미영 팀장입니다. 어제 신규 패치된 채팅 서버가 추가 될때 마다 IDC 내부 트래픽 그래프가 기하급수적으로 상승하고 있습니다. 아직은 괜찮지만 이대로라면 조만간 최대 허용 트래픽을 초과 할것 같습니다. 확인 부탁 드립니다."

(읭?! 김미영 팀장 어디서 많이 듣던 이름인데...기분 탓이겠지..) 


이 사실을 팀장님께 보고 드리니 아무래도 어제 투입된 채팅 시스템의 브로드캐스팅이 이런 문제를 발생 원인인것 같다고 말씀하시며 팀장님의 생각을 설명 해주셨다.

팀장 : "머신당 수용가능 최대 인원을 1000이라고 가정해보자. 그리고 머신 대수를 M 이라는 변수로 대채 해보자. 사용자 한 명당 한 개의 메시지를 보낸다면 자신을 제외한 모든 채팅 서버에게 메시지를 보내야 하니까...1000 x (M-1) 의 메시지 트래픽이 한 대의 머신에서 발생하겠지? 그런데 이게 총 M 대의 서버에하고 모든 사용자가 동시 채팅 메시지를 보내는 경우 M x (1000 x (M -1)) 의 메시지 트래픽이 발생하게 되는거지. 이게 뭘 의미하는지 알겠니?"

나 : "...음...글쎄요..."

내가 쉽게 답을 하지 못하고 우물거리고 있자 팀장님은 아무 말씀도 하지 않고 담배를 하나 물며 기다리셨다.. 거의 반 개피가 타들어 갈무렵 갑자기 수식 중 한부분이 눈에 들어 왔다.

나 : "아... 위 식을 정리 해보면 1000*M^2 -1000*M 이 되는 군요..여기서 M이 제곱이니까 변수 M이 증가 할때 마다, 즉 서버 머신이 추가 될때 마다 그래프는 기하급수적으로 증가하는 거군요.."

팀장님은 이제 알겠냐는 듯한 웃음을 지으며 저 M의 차수를 줄일 수 있는 방법을 찾아 오라 하신다.

자리로 돌아와 지금의 문제점에 대해 곰곰히 생각해 보았다.

머신 대수를 나타내는 항에서 에서 제곱이 발생한다. 이런 구조라면 사용자가 늘어나 머신이  추가 된다면 트래픽 그래프는 다시 한번 더 기울기가 가파라진다. 원인은 브로드캐스팅이다. 서버간 메시지 전달에 브로드캐스팅 방식을 사용 하면서 전체 머신 만큼의 메시지 트래픽이 발생하고, 모든 머신에서 브로드캐스팅을 하고 있으므로 M^2이라는 항이 생긴 것이다.

그렇다면 브로드캐스팅을 하지 않는다면? 메시지 전달에 유니캐스팅을 사용한다면 최대 그래프의 증가는 제곱이 아니라 선형 그래프를 그릴 것이다. 대상 사용자가 접속해 있는 머신을 알 수만 있다면 해당 머신에 유니캐스팅으로 메시지를 전달하면 된다라는 결론이 났다. 그런데 어떡게 대상사용자가 접속해 있는 머신을 알아내는가가 문제 였다. 그래서 다음 두 가지 방법을 생각해 보았다.

 1. 아직 전달 대상 머신이 어디인지 모르는 경우 전체 채팅 머신을 대상으로 사용자를 찾는 메시지를 브로드캐스팅 한다. 사용자를 가지고 있는 머신에서 응답이 오면 다음 부터는 그 머신에만 메시지를 유니캐스팅 하는 방식.

 2. 사용자가 어느 머신에 접속해 있는지 매핑 테이블을 유지하는 센트럴 시스템을 추가하고 사용자가 채팅 시스템에 접속하면 이 센트럴 시스템에 아이디와 위치를 등록한다. 모든 채팅 메시지는 이 센트럴 시스템으로 보내지고, 센트럴 시스템은 사용자가 있는 경우 해당 머신으로 메시지를 릴레이 하는 방식.

1번 방식의 경우 일단 위치를 알아내고 난 다음 부터는 해당 머신으로 바로 메시지를 전달하므로 메시지 전달 트래픽이 1밖에 되지 않지만 최악의 경우 브로드캐스팅과 똑같은 비용이 든다는 단점이 있다. 예를 들자면 모든 사용자가 현재 접속하지 않은 사용자에게 계속 메시지를 보낸다거나, 채팅 시스템이 방금 시작해 아무런 위치 정보가 없는 시점에 사용자들이 채팅을 시작한다던가 하는 시나리오 말이다,

2번 방식은 센트럴 시스템에 메시지를 보내는 트래픽과 센트럴 시스템이 릴레이 하는 트래픽, 이렇게 매 메시지마다 2의 트래픽 비용이 발생하지만 최대 트래픽이 (1x1000+1x1000)xM 만큼으로 일정한 선형 그래프를 그린다는 장점이 있다.

1번과 2번 모두 각자의 장단점이 있긴하지만 나는 최악의 경우 트래픽이 선형 증가를 하는 시스템이 더 안정적이라고 판단 2번 방식을 택하기로 했다.

그래서 다음과 같은 디자인이 나왔다 :
 


팀장님이 트래픽 사용으로 회사에서 지불하는 비용도 무시할 수 없이 크므로 오늘 내로 패치를 해야 한다고 하신다.
오늘도 뜨는 아침 해를 보며 센트럴 시스템과 기존 채팅서버에 센트럴 서버와 통신하는 인터페이스를 완성 했다.

입사 삼 일째, 집에 가지 못한 시간도 삼일째..피곤하다..책상이 아닌 이불에서 자고 싶다...ㅠㅠ

[발로 그리는 분산 시스템] - 발로 그리는 분산 시스템 #Day 1 - 발로 그리는 채팅 시스템 
[발로 그리는 분산 시스템] - 발로 그리는 분산 시스템 #Day 2 - 채팅 서버에 접속이 안되요!!

Posted by kukuta

댓글을 달아 주세요

  1. BlogIcon 김경모 2012.02.20 23:34  댓글주소  수정/삭제  댓글쓰기

    아 지나가던 쪼그만한 학생입니다 ㅎㅎ.
    실제로 입사하자마자 시스템을 개발해라 하고서 (비록 채팅 서비스지만 ㅎㅎ...)
    오늘 안에 되겠니? 하고 하는 무서운 경우가...
    있을거라는 무서운 생각을 하면서 3일차까지 보고있습니다 ㅎㅎ.

    사내 에서 브로드 캐스팅을 하더라도 트래픽이 많이 발생하는군요 ㄷㄷㄷㄷ....
    역시 사람을 찾기위해서 그때 마다 서버를 찾기에는..... 무리가 따르죠 ㅎㅎ
    (물론 . 색인 작업을을위한 사용자를 알파벳 순(이름순)으로 정리해서 서버에 차곡 차곡 쌓을수있다는 무식한 생각도해보지만 ㅎㅎ..서버가 역시 효율적으로 유저관리를 하기가.. 알고리즘을 다시짜야하니 ㅎㅎ)

    센트롤 시스템을 통한 (사용자가 접속하고 나갈때마다 센트롤 테이블의 유저 테이블을 업데이트하면 ㅎ..)
    게 좋다고 생각이되네요 ㅎㅎ..
    사용자별로 n번 브로드 캐스팅을 한다면은

    1000명의 유저가 10개의 서버에있는 사용자를 찾기위해서는 ...
    최대10000 번의 메시지를보내야겠죠.... 물론... 첫 메시지에만 한정이 되겠지만 ㅎㅎ..
    엄청난 트래픽이.... n*m*1/2 의 복잡도란 ㄷㄷ

    하지만 두번째 방법은 첫메시지 2n의 시간 복잡도를 갖고 . 이후에 상대편이 나갔을때에만
    그유저가 있는 머신에 메시지를 보내서 다시 접속 확인을 할수있는 시스템이 구축...이 될라나요 ㅋㅋ앜...
    (수식은 틀렸지만 이게 효율적이라고 생각함니다 ㅎㅎ!!)

    물론 두번째 경우든 첫번때 경우든 메시지가 전송이 됬다는 ask 메시지나 확인 법
    그리고 그후에 유저를 다시 검색하고 이사람이 없다면은 접속이 실패했다는 메시지도 메시지를 전송한 사람에게 알려줘야하는 부담이있네요 ㅎㅎ.

    물론 리니지의 장사 채팅 같은 경우는 브로드 캐스트로 ^^.~!!

    괜히 니자가다가 주저리 주저리 해봄니다 ㅎㅎ..

    흥미 진진하고 재밌네요 ㅋㅋㅋ...

  2. Favicon of http://kukuta.tistory.com BlogIcon kukuta 2012.02.23 23:22  댓글주소  수정/삭제  댓글쓰기

    1번 방식은 사실 한번으로 끝나는 것이 아닙니다. 없는 사용자에 대해서 계속 검색을 하게 된다면 결국 지속적으로 브로드캐스팅을 하는 것이나 다름 없습니다. 최악의 경우를 고려한다면 브로드캐스팅 정도의 비용이 지불 됩니다.
    2번 경우엔 사용자 로긴과 로그아웃을 처리해주면 보낼 수 없는 사용자에 대한 처리도 보다 쉬워지지요.

    다만 여기서 빠진 이야기가 있는데 결국 센트럴 릴레이 서버가 병목이 될 수도 있습니다. 이에 대한 분산 정책도 나중에 다룰 예정입니다ㅎㅎ

    관심있게 지켜봐 주셔서 감사합니다.

    • BlogIcon 김경모 2012.02.27 13:17  댓글주소  수정/삭제

      아 ㅋㅋ
      중앙에서 처리해주는 중앙 릴레이 서버 녀석도 고려해야되는군요 이런 ㅋㅋ

      저도 안드로이드 메신저 서버에대해서 생각해보다가 수천만이나되는 ㄷㄷㄷ 유저에게 메시지를 보내는 대규모 메신저 서버에대해서 궁금했었거든요 ㄷㄷㄷㄷ ㅋㅋ 비슷할라나 ㅋㅋㅋ...앜 ㅋㅋㅋ

      곧 개강이니 ㅠㅠ 네트워크 교수님한테 물어봐야지요 ㅎㅎㅎ

      재밌게 보고감니다 ^^*