안녕하세요. Demand Product 팀의 Ad Management 파트에서 서버 개발자로 일하고 있는 Kay입니다.

제가 팀에 합류한 지도 어느덧 2년이 되어가는데요, Ad Management 파트(이하 AdM)은 무슨 일을 하는지 간단하게 소개하고 재미있게 했던 과제에 관해 이야기해볼까 합니다.

스프린트와 애자일

AdM은 2주 주기의 sprint 단위로 업무를 진행하고 있어요. 제가 들어오기 전 옛날 옛적 호랑이 담배피던 시절의 버즈빌은 펑션팀 단위로 일했다고 들었는데, 지금은 미션팀 단위로 일하고 있습니다. AdM팀은 PM, 디자이너, QA 매니저, 2명의 서버개발자와 1명의 프론트 개발자로 이루어져 있어요. 2주의 스프린트 단위가 길다면 길고, 짧다면 짧은 기간인데요, 이 기간동안 내가 어떤 일을 얼마나 할 수 있을지에 대한 판단이 정말 중요하게 작용하는 것 같아요. 스프린트 기간 동안 자신이 할 수 있는 범위의 일을 정의하는 것. 그게 애자일 방식의 핵심인 것 같다고 느꼈습니다.

자유로운 커뮤니케이션

버즈빌은 정말 자유로운 커뮤니케이션 문화가 있습니다. 제가 신입이거나 시니어인 것은 상관이 없어요. 내 과제에 대해선 내가 의견을 낼 수 있고, 내 의견이 존중되는 문화입니다. 당연히 의견에 허점이 있거나 보완이 필요하면 상대방도 의견 제시를 할 수 있겠죠? 버즈빌에서는 더 나은 결과를 위한 의견 제시를 할 수 있는 모습과 받아들일 수 있는 모습, 두가지가 모두 필요합니다.

오늘부터 1인분!

아직도 생생하게 기억납니다. 월요일에 입사하고 정신없는 입사절차를 밟고, 각종 온보딩을 듣고 난 후 화요일에 첫 파트 스크럼을 들어갔어요. 당시 팀에서 처리해야 하는 굉장히 쉬운 과제가 하나 있었는데, 팀 EM께서 눈을 반짝이며 이 과제는 케이가 진행하실 수 있을 것 같은데 어떤가요? 허허 라고 하시더라구요. 지금 생각해보면 온보딩용으로 적합한 과제였다는 생각이 들지만, 그 당시에는 조금은 당황스러웠던 기억이 있습니다. 당장 입사 다음날부터 실무에 뛰어들어야 하는 스타트업도 재밌지 않나요?

이쯤에서 제가 입사한 지 한달만에 맡아서 진행했던 과제에 대해 이야기해볼까 하는데요.
어떤 문제가 있었고 어떻게 해결했으며, 그 과정에서 팀 커뮤니케이션은 어떻게 했나 소개해 드리려고 합니다.

문제 발견

버즈빌의 광고는 여러가지 항목을 타겟팅할 수 있습니다. 특정 나이대의 유저를 타겟팅할수도 있고, 특정 앱에만 광고를 내려줄 수도 있죠. 여러가지 타겟팅 방법 중 하나는 지역 타게팅입니다. 원하는 지역에만 광고를 내려줄 수 있는 기능인데요, 어느 날 이 기능에 결함이 있다는 제보가 들어옵니다.

먼저 지역타게팅을 어떻게 쓰고있는지 파악했습니다.

대한민국을 시,군,구 단위로 나눠보면, 약 250개의 지역이 있습니다. 약 70개의 시, 80개의 군, 100개의 구로 나뉘게 됩니다. 이 과정에서, 지역 타게팅 기능에 수십 개 군,구를 등록하게 되면 당시 사용하던 ElasticSearch 5(이하 ES5)라는 라이브러리의 packet size 제한을 넘어버리게 되는 문제가 발생했습니다.

지역타게팅에 사용하는 정보는 아주 정교한 좌표들의 모음이었는데, 지역을 많이 선택하니 데이터의 크기가 너무 커서 기본 설정인 1메가바이트를 넘겨버렸던 것이죠. 예시를 들어볼게요. 서울시 양천구의 지도는 좌측 하단의 사진처럼 생겼어요. 이걸 좌표로 나타내면 우측 하단처럼 생겼습니다. 양천구는 197개의 점으로 이루어져 있네요.

좌표 하나에 40바이트가 조금 안되는데, 주먹구구식으로 양천구만 계산해봐도 8천바이트가 나오네요. 양천구보다 데이터가 큰 지역도 많았기에, 1mb로 250개 지역을 모두 선택하기엔 부족한 수치라고 결론지을 수 있었습니다.

해결책

가장 쉬운 방법은 역시 ES5의 패킷 제한을 늘려버리는 방법이었습니다. 하지만 광고시스템에서 가장 중요한 요소 중 하나는 빠른 시간내에 유저에게 광고를 전달하는 것입니다. 아무래도 아주 큰 데이터가 아니다보니 영향도는 미미하겠지만, 지역 정보의 통신 사이즈가 늘어나면 성능 저하의 가능성이 존재한다고 판단했습니다. 덤으로, ES5는 서비스를 종료하고 ES8으로 마이그레이션을 하는 계획도 있었습니다. 설정과 같은 다른 요소에 관계 없이 문제를 근본적으로 해결할 수 있어야 했다고 생각했고, 결국 해결책의 핵심은 저장하는 데이터의 크기를 줄이는 데 있다고 생각했습니다. 여러 가지 방법을 신중하게 검토해보았는데요, 약간의 트레이드 오프를 동반한다면 데이터의 크기를 획기적으로 줄일 방법이 있었습니다.

외접다각형

convex hull을 한글로 표현하면 외접다각형입니다. 내부적으로는 Graham Scan(그레이엄 스캔)이라는 알고리즘을 사용해서, 점들의 집합에 대한 모든 점을 포함하는 외접다각형을 구하는 알고리즘이죠. 위에 예시로 든 양천구의 경우, convex hull을 적용한다면 197개의 점에서 약 20개의 점으로 줄어들게 됩니다. 데이터의 크기가 굉장히 많이 개선될 수 있는 수치였죠.

외접다각형을 구하는 원리를 모두 글로만 설명하려면 조금 복잡하고 어려울 수 있으니, 그래픽을 통해 Graham Scan을 최대한 간단하게 설명해보겠습니다.

그래픽으로 들어가기에 앞서 원리를 한 줄로 설명해보자면, 모든 점이 “가장 바깥쪽에 있다”라는 것을 증명하기 위해서는 이어지는 세 점의 집합이 모두 “좌회전”하면 됩니다. 수학적으로 설명하는 것보다, 실제로 알고리즘이 어떤 식으로 작동하는지 한번 살펴보는게 이해가 훨씬 쉬울 것 같아요. 함께 보시죠.

위 그림을 보면 알고리즘 진행순서를 한눈에 알 수 있는데요, 어떤 방식으로 저 선들이 정해지는지 step by step으로 설명해 드리고자 합니다.

먼저, 한 점을 기준으로 잡고 반시계방향으로 모든 점을 넘버링합니다. 보통 기준점은 y축의 가장 밑에 위치한 점으로 잡습니다. 그리고 스택이 하나 필요합니다. 일단 시작으로 기준점을 스택에 넣습니다.

그 후, 1번 점을 스택에 넣습니다. 그리고 0에서 1로 이어지는 선을 그어줍니다.

이제 2번 점을 비교할 차례입니다.

0에서 1로 이어지는 직선을 A, 1에서 2로 이어지는 직선을 B라고 할 때, A에서 B로 가는 것이 “좌회전”을 한다면 해당 점들은 외접다각형의 일부라고 볼 수 있습니다. 0,1 그리고 2는 모두 저희가 찾는 외접다각형의 일부네요. 그렇다면 2를 스택에 넣고, 1->2와 2->3의 비교로 넘어갑니다.

마찬가지로, 1->2와 2->3 직선의 각도의 방향을 계산합니다. 우리의 조건에 맞으니 3도 스택에 밀어 넣어줍니다. 이런 식으로 계속 번호를 바꾸면서 진행하면 됩니다. 똑같은 경우를 모두 설명할 필요는 없다고 생각되어서, 좌회전이 아닌 우회전을 하는 경우를 살펴보도록 하겠습니다. 다음 사진은 그레이엄 스캔을 쭉 진행하다가 4,5,6에 대한 직선 판별을 하는 경우입니다.

스택에는 이미 5까지 들어가 있고, 6에 대해 판별을 할 차례입니다. 그러나 4→5의 직선과 5→6의 직선을 비교했을 때 각도가 바깥쪽으로 향하므로 우회전을 하네요. 그렇다는 것은 스택의 맨 위에 존재하는 5가 우리가 찾는 외접다각형의 일부가 아니라는 뜻입니다. 그러므로 5를 스택에서 빼줘야 합니다.

이번에도 3→4의 직선과 4→6의 각도가 바깥으로 향하고 있네요. 그렇다면 4도 우리가 찾는 외접다각형의 일부가 아니라는 의미입니다. 스택에서 4를 제거합니다.

이번에는 2→3, 3→6을 보니 각도가 안쪽으로 향해있는 것을 볼 수 있습니다. 그러면 6을 스택에 추가하고, 다음 점인 7로 넘어갑니다. 이후부터는 설명 없이 스텝별로 진행만 공유하도록 할게요.

이렇게 모든 점을 다 판별하고 시작점으로 돌아왔을 때 알고리즘은 종료가 됩니다. 그리고 원하던 외접다각형의 점들의 집합 [0, 1, 2, 3, 6, 7]이 완성이 되었네요.

사실 이 알고리즘을 직접 작성할 수도 있지만, 파이썬의 Shapely라는 라이브러리를 사용하신다면 이미 구현되어 있는 convex hull 함수를 사용하실 수 있습니다. 이런 식으로 대한민국의 모든 지역구에 convex hull을 적용하였는데요, 변경점을 한 눈에도 쉽게 알아볼 수 있는 상태가 되었습니다.

이렇게 적용해보니, 대한민국 지역을 모두 저장해둔 데이터베이스 파일의 크기가 4.9mb에서 262kb로 약 94.7% 감소하였습니다. 가장 큰 지역의 데이터 크기도 3kb로 줄어들었기 때문에, 처음 문제가 되었던 1mb의 제한을 감안한다면 300개 이상의 지역을 타게팅에 추가할 수 있었습니다. 앞에서도 언급했듯이, 대한민국은 250개의 시군구로 이루어져 있기 때문에 사실상 제한이 없어졌다고 볼 수 있었습니다.

문제점

한가지 분명한 단점도 존재했습니다. 사진에서도 보이다시피 지역별로 겹치는 부분이 있다는 점이었습니다. 겹치는 부분이 있다면 지역 타게팅이 정확히 동작하지 않을 수 있고, 광고 타게팅에 오차가 생길 수 있었습니다. 사실 지방의 경우 인구 밀도가 높지 않아 큰 문제가 되지는 않았는데, 서울은 조금 달랐습니다.

파일 크기를 90% 넘게 최적화했다고 하더라도 오차가 너무 커 기능에 문제가 생긴다면 소용이 없는 일이라서, 검증이 필요하다고 판단했습니다. 마침, 서초,강남,송파지역을 타게팅하던 광고가 있어 새로운 버전의 지역타게팅을 적용해보았습니다.

해당 광고는 총 445,185번 할당이 되었는데, 그 중 타게팅이 아닌 지역인 강동구에서 발견된 할당이 약 29,419건이었습니다. 6.6%에 해당하는 수치였습니다. 또 다른 ‘대전’타게팅이 걸려있던 광고에 대한 할당 지역정보를 확인해보니 대전이 아닌 지역의 할당이 0.5%수준의 오차만 존재하는 것도 확인할 수 있었습니다. 이전에 집행되었던 다른 광고들을 살펴보니, 기존에도 지역이 아닌 곳에서 할당되는 경우는 약 1~2퍼센트정도는 존재했습니다. 즉, 최대 4~5%정도의 오차율을 가지는 수준이었습니다. 팀에서는 그 오차율이라면 95%의 저장공간 및 성능개선에 대해서 용납할 수 있는 수준이라고 생각했고, 제품에 무사히 적용될 수 있었습니다.

마치며

아쉬웠던 점이 분명 존재합니다. 시간이 조금 더 주어졌더라면, convex hull의 겹치는 부분들을 조금 더 잘 정리할 수 있었을 것이라고 생각합니다. 물론 데이터의 크기라던지, 그 사이에 분명 애매하게 걸리는 공간들이라던지에 대한 결정이 필요하므로 생각보다 많은 시간이 필요할 것을 알고 있지만, 개발자로서 어쩔 수 없이 아쉬운 부분인 것 같아요.

테스트 환경의 중요성 또한 뼈저리게 느낄 수 있었습니다. 처음으로 할당 관련된 작업을 했던 프로젝트인데요, QA를 위해서 여러 가지가 부족했어요. 지역데이터 서비스의 스테이징 환경도 제대로 설정되어 있지 않았고, 어떻게 설정을 해야 테스트폰에서 할당받을 수 있는지조차 어려웠습니다. 다행히 팀에 QA 매니저가 계셔서 잘 도와주셨고 무사히 마무리할 수 있었지만, 빠르고 정확한 프로젝트의 완성을 위해서는 테스트 환경이 잘 갖추어져야 한다는 것도 배울 수 있었습니다.

진짜로 마치며…

이 글을 테크 블로그에 기고하겠다고 다짐한 지 어느덧 1년이 넘어버렸습니다. 이 글을 읽으시는 독자분들 모두 저처럼 마음에 오랫동안 품은 무언가가 있으실 것이라고 생각합니다. 저도 오랜기간 짐을 가지고 있다가 이제야 홀가분해지는 처지에서 부끄럽지만, 모두 올해는 꼭 그 짐 벗어 던지시길 기원할게요! 읽어주셔서 감사합니다!

버즈빌 개발자 지원하기 (클릭)

버즈빌 테크 리크루터와 Coffee Chat하기 (클릭)