Code Sprint 2014 의 광고 스케줄러 최적화에 대해

안녕하세요, 한민호입니다. 올해 Code Sprint 2014의 두 번째 라운드 광고 스케줄러 최적화 문제를 출제하게 되면서 느꼈던 점들과 기술적인 부분들에 대해 말씀 드리려고 합니다.

문제 출제 에피소드

Code Sprint는 SK 플래닛의 역사와 함께하고 있는 코딩 경진대회입니다. 그럼에도 불구하고 저희 팀에서 문제를 내기 전까지는 큰 관심을 갖지는 않았던 것이 사실입니다. 🙂

올해 SK 플래닛은 Commerce 중심의 사업구상을 하고 있습니다. 그러한 회사의 방향에 맞추어 Code Sprint의 문제 중 하나 정도는 Commerce 개발본부에서 출제해 줬으면 좋겠다는 의견이 있었습니다. 본부의 요청에 응한 것이긴 하지만 문제를 제안하면서도 “설마 채택이 될까?” 하는 생각이 앞섰습니다. 그런 고민이 기우였는지 몇 개의 문제 중 최종 후보까지 채택이 되는 행운을 얻었습니다.

광고플랫폼 문제는 제가 회사에서 발명한 스케줄링 알고리즘 특허에서 착안한 것입니다. 해당 특허는 현재 국제출원까지 되어있습니다. 그러나 특허 알고리즘을 단순히 구현하는 것이 아닌 경진대회의 문제로 바꾸는 것이 쉽지만은 않았습니다.

먼저 공동 출제자인 신진철 매니저님과 직무발명 신고서 몇 건을 토의하며 가닥을 조금씩 잡아갔습니다. 신 매니저님은 2013년 입상자로서 알고리즘에 관심이 많은 분이어서 저의 아이디어와 결합하여 문제화가 가능했습니다.

문제화는 했지만 이것을 어떻게 채점할 것이며 문제 시스템을 어떻게 구성할 것인지, 데이터 셋을 파일로 제공할 것인지 등등 여러 난관에 봉착했습니다. 각종 해킹이나 보안적인 문제들을 고려할 때 라이브러리와 파일 형태로 진행하고, 코드 업로드에 의한 실시간 컴파일 방식을 취하는 것이 나아 보였습니다. 그럴 경우 라이브러리가 Programming Language에 따라 의존성을 갖는 문제도 있기는 했지만, 요즘의 open API 트렌드에 따라 API 방식을 취하는 쪽이 의미가 있다고 판단했습니다. 결국 오랜 고민 끝에 API 방식으로 결정했고 개발 관련한 사항들에 대해 많은 고민도 함께 진행이 되었습니다.

그리고 문제화 단계에서 대회 기획하시는 쪽과 대회 운영상의 이슈에 대해 토의를 진행했는데요, 토의 결과 문제 난이도가 높다는 우려가 제기됐습니다. 저희도 이점을 깊이 고민하여 광고 플랫폼에 대한 배경 지식이 없는 참가자들이 광고 플랫폼만의 고유 용어와 공식을 사용하지 않고도 문제를 쉽게 이해하고 알고리즘에만 집중할 수 있는 환경이 되도록 몇 번이고 수정했습니다.

또한 기존 open API 해커톤 경진과는 달리, 코딩 대회로서는 국내 최초로(?!) API를 사용한 대회방식의 특징을 살리고자 자동 채점 시스템을 통해서 개발자들의 경쟁적 재미를 부여했습니다. 그리고 많은 참여를 유도하고자 API를 쉽게 사용 가능할 수 있도록 단순화하는데 노력을 기울였습니다.

이렇게 서버단이 구성되고 테스트를 하면서 몇 가지 버그들이 도출되었지만 워낙 견고하게 설계가 되어서인지, 아니면 개발을 워낙 잘 한 것인지(!) 성능 문제만큼은 발생하지 않았습니다. 또한 서버 설계과정에서 성능에 문제가 없도록 RDBMS와 NoSQL DB에서 관리할 데이터를 구분하여 설계하였고 이를 MySQL과 Redis DB를 이용하여 적절히 처리했으며 성능에 문제가 발생할 만한 곳에 대해서는 토의하고 보완했습니다.

오픈 전에는 각 DB나 WAS의 Connection 수와 예상되는 Load에 대해 Load Runner를 이용한 성능 테스트를 진행했습니다. 이는 “서비스를 하는 회사가 대회를 하다 장애가 났다”라는 오명을 쓰지 않기 위한 준비 활동 중 하나였습니다. 사실 이 부분이 저희가 가장 걱정한 부분입니다. ^^

문제를 출제하면서 가장 중요한 곳은 문제 출제를 담당하는 “문제 출제 API 서버” 입니다. 문제 출제 API 서버는 광고를 노출하는 미디어를 모델로 만들었습니다. 광고에서 미디어란 광고를 노출하는 매체이며 해당 매체를 통해 노출, 클릭과 같은 이벤트를 다시 광고 플랫폼으로 전송하는 역할을 담당합니다. 즉, 문제 출제 API 서버는 클릭이라는 이벤트를 가상으로 생성하여 참가자들에게 응답 값으로 전달하는 기능을 합니다.

모바일 광고에서는 이러한 매체들이 다양합니다. 모바일 웹이 될 수도 있고 앱이 될 수도 있습니다. 이러한 매체들은 각각 고유한 속성을 갖고 있고 해당 속성에 따라 특정 광고가 노출됐을 때 클릭(광고 수신자의 반응)도 각기 다르게 나타날 수 있습니다.

이러한 속성들을 문제에 녹여 내기 위해 Data Set Generator라는 것을 API에 넣었습니다. Data Set Generator는 광고에 대한 응답 값을 생성합니다. 미디어 속성에 따른 Group을 4개로 나누고 CTR(노출 대비 클릭율)과 광고를 한번에 노출할 수 있는 크기(매체 사용자의 수)에 제약을 설정했으며 CTR은 Group 별로 유동적으로 변하도록 설계했습니다. 또한 매체들이 Group을 Rotate 하도록 구성했고 재미(?) 요소로서 Critical Click Section 구간을 배치하여 Request 시 해당 구간 내에 들어오면 Click을 더 많이 주도록 설계했습니다.

Group의 속성인 CTR의 변화는 행운 요소가 다분히 존재합니다. 따라서 대회 참가자들에게 공정한 기회를 주기 위해 해당 부분을 테스트하는데 많은 시간을 할애했고 동일한 요청 1만번의 요청에 대해 수익금의 표준편차를 최소하는 튜닝작업을 시행했습니다.

그림 1. Code Sprint 2014 Round 2 문제 서버 구성도

문제 풀이 방법

문제를 풀기 위해선 요청에 대한 응답값을 실시간으로 분석하고 다음 Request에 광고를 어떻게 미디어에 분배 할지 알고리즘을 설계해야 합니다. 이것은 곧 앞서 소개했던 Data Generator의 속성을 찾아내는(Reverse Engineering) 분석 작업에 해당합니다.

요령이 있다면 고득점을 얻기 위한 Fillrate(유무료 광고비율, 사실 광고플랫폼에서는 유료광고 Request/전체 Request의 식을 사용합니다)를 잘 맞추는 것이 가장 중요합니다. 이는 가장 큰 감점 요소이기 때문입니다. 그 다음으로는 광고 수익율을 높이는 알고리즘이 필요합니다. 광고는 매체의 속성에 맞추어 다양한 단가와 광고 물량이 있습니다. 이것은 사실 사전에 치밀하게 계산된 단가와 물량입니다. 이것을 어떻게 스케줄링 하느냐에 따라 광고 수익의 차이가 크게 납니다. 클릭이 많이 들어오는 곳에 비싼 광고를 넣어야 하는 것은 문제를 읽는 순간 모든 대회 참가자들이 알았을 것입니다. 그러나 Request를 할 수 있는 횟수는 1만번으로 제한되어 있습니다. 제한된 횟수에 맞춰 광고를 너무 일찍 소진해 버리면 나중에 Critical Click Section을 만나지 못할 수도 있습니다.

점수가 잘 나오려면 확률적으로 접근했을 때 1만번의 Request동안 광고 물량을 전구간에 걸쳐 골고루 모두 소진할 수 있도록 스케줄링 해야 하며 이 과정에서 매체가 최대한으로 허용하는 요청 한도 안에서 광고물량을 잘 분배해야 합니다. 그리고 나서 CTR의 변화량에 대한 철저한 분석이 요구됩니다. 해당 예측은 요청을 통해 누적된 Click Data로 할 수 있습니다. 사실 이는 매우 어려운 작업입니다. 또한 이 CTR의 변화량에 따라 광고 단가가 높은 것들을 Click이 많은 곳에 적절히 배분하여 집행 할 수 있도록 해야 합니다. 얼마나 스케줄링을 잘 하느냐에 따라 받을 수 있는 Click량이 충분히 다를 수 있습니다.

기존 광고가 집행되면서 발생했던 Click을 문제 출제 API 시스템과 동일하게 관리하는 것이 문제를 풀기 위해 중요한 요소이자 어려운 문제 입니다.

또한 Group이 바뀌는 시점, 바뀌었다는 사실을 판단하기 위해서는 실시간 응답값에 대한 과학적인 분석을 시행한 다음, 분석된 내용을 기반으로 한 스케줄러 알고리즘이 적용하는 것이 필요합니다.

이를 위해 광고, 매체별 CTR을 관리해야 하고 매체도 Group별로 관리해야 어느 정도 정확한 수익 예측도 가능합니다.

아래에 Data Set Generator의 기능 정의서를 첨부합니다. 이것을 알아내기 위한 방법들은 무수히 많이 존재할 수 있습니다. 그리고 정답 역시 없을 수도 있습니다. 하지만 최적의 알고리즘으로 최고의 수익을 낼 수 있도록 하는 것이 본 문제의 출제 의도였습니다.

Data Set Generator 기능정의서

  1. data set generator는 참가자가 put 한 각 광고에 대해 random한 CTR을 부여한다.
  2. 부여한 CTR은 모두 DB에 저장하여 채점 후 증빙 시 사용한다.
  3. put_ad의 JSON은 전체 저장하여 채점 재현을 할 수 있도록 한다.
  4. CTR은 다음과 같이 부여된다.
    1. CTR = seed CTR * CTR변화율 + seed CTR
  5. Click은 Round(CTR * putCount / 100) 이다.
  6. critical click 구간이 존재함
  7. 전체 시간 중 15% 영역에 대해 다음과 같이 critical click 구간을 배정함
    1. 전체 media 중 30%에 대해 critical click 시간에 들어왔을 경우
    2. 일괄적으로 CTR을 +30%(CTR * 1.3)를 부여함
    3. turn 별로 랜덤하게 구간이 변경됨
  8. 미디어 그룹 & 초기데이터
    • 미디어

Media Group

max_impression_per_request

FR

seed CTR

CTR 변화율(%)

초기 소속 media_no

Media1

2000

80

5%

-20% ~ +20%

1~10

Media2

5000

85

2.5%

-15% ~ +15%

11~20

Media3

10000

90

1%

-10% ~ +10%

21~30

Media4

20000

95

0.5%

-5% ~ +5%

31~40

  • 위 미디어들은 아래 Rule 에 의해 미디어 그룹간이 이동된다.
      1. 그룹 간 이동
        1. 그룹간 이동은 대회참가자에게 비공개되는 정보이다.
        2. 2,500 Request 주기로 각 미디어 그룹의 50%로 서로 교환된다.
          (교환될 50%는 Random 하게 추출)
        3. Media1->Media2, Media2->Media3, Media3->Media4, Media4->Media1 로 이동
      2. 그룹 간 이동으로 영향 받는 값들
        1. 이동된 Media 의 CTR 변화율값은 이동된 그룹의 값을 참조한다. (그룹 이동 후 CTR 계산시 변경된 변화율 값을 적용한다.)
        2. default CTR 값은 초기 그룹의 default CTR로 누적되어 계산되어 오고 있기에 그룹 이동과 관련이 없다.
        3. max_impression_per_request 는 미디어의 특성이고 대회참가자에게 공개되는 정보이기에 그룹 이동에 영향을 받지 않도록 한다. (즉, 초기에 Media 가 가지는 max_impression_per_request 는 1 game 이 끝날 때까지 변하지 않는다)

위와 같은 방식으로 문제 출제 API가 동작하고 있는 것을 알고 있는 분이 1등을 했을 것이라 생각됩니다.

참가자들이 문제를 풀면서 초반에는 왜 이렇게 수익금이 계속 달라지나 의문을 품었을 것입니다. 그렇다면 아마도 본인의 알고리즘이 좋지 못하다는 증거일 수 있습니다. 하지만 어느 정도 균일하게 많은 수익금이 나온다면 최적의 수익금을 내는 알고리즘을 고안했다고 볼 수 있습니다.

Critical Click Section을 찾지 못한 분이나 FR를 지키지 못한 분들 그리고 그룹간에 매체 속성을 파악하지 못한 분들은 꽤 들쭉날쭉한 수익금을 경험했을 것입니다.

트레이닝 기간에 예상보다 참가자분들께서 많은 Request를 하지 않으셨습니다. 사실 이 기간에 많은 Request를 수행하여 많은 Click 통계를 확보하는 것이 가장 중요한 사항이었습니다. 또한 테스트 기간에 10회의 턴을 주었는데 이는 확률적으로 발생할 수 있는 Click차이를 감안한 기회였습니다. 트레이닝 기간에 충분히 API의 CTR의 변화 범위를 분석하고 최대 수익금이 얼마나 나올지 예측한 후(그래서 트레이닝 기간 동안 무제한 턴을 제공하였습니다.) 10회의 기회를 수행하면서 최대 수익금에 근접하면 더 이상 턴을 진행할지를 본인이 결정할 수 있습니다.

또한 위의 규칙들을 정확히 분석했다면 1회의 Request만으로도 매체가 현재 어느 그룹에 포함되었는지 파악이 가능합니다. 이것을 찾을 때 방해 요소가 있다면 Critical Click Section일 수 있습니다. 때문에 조금이라도 찾기가 쉽도록 30% 비율로 CTR을 일정 기간 증가하도록 하였습니다.

저희가 사전 시뮬레이션 할 때 10회의 표본값들은 모든 응시자에게 동일한 평균의 수익을 낼 수 있도록 하였고 최대/최소에 대한 편차는 역시 거의 없도록 하였습니다. 이는 사전 자체 베타 테스트 기간에 1만번 충분한 Request를 제공했을 때 턴마다 매체들의 평균 CTR을 측정하여 신뢰할 만한 결과를 얻었습니다. (최초엔 10만번을 제공하려고 했으나 이는 게임기회가 하루에 5턴을 넘지 못하는 단점이 있고 5,000번 미만은 표준편차를 증가시키는 문제가 있어 적정한 수치인 1만번으로 결정하였습니다. )

상기의 관점에서 문제를 접근 하신 참가자들은 아마도 테스트 기간엔 최고 수익금을 낸 다음 다른 응시자가 본인의 점수를 갱신하는지 보면서 갱신을 했다면 다시 턴을 수행하는 식으로 마치 게임을 하듯 즐기셨으리라 생각됩니다.

대회 참가자들 중 상위권에 포진된 분들은 저희가 높은 Click을 유도하기 위해 CTR과 putCount를 이용한 Click 계산 시 결과값을 정수화 하기 위해 반올림 하는 로직이 있었는데 이를 파악하여 Request시 putCount을 최대한 분할하여 요청을 수행을 하였습니다. 이는 주최측에서도 사실 예상치 못한 부분이었습니다. 하지만 부정한 방식의 abusing이 아닌 정당하며 요청을 통한 방식이었고 반올림되는 최소값에 대해서도 Reverse Engineering 해서 이를 스케줄링에 반영한 노력은 인정 할만한 부분이었기 때문에 해당 부분들은 인정이 되었습니다.

대회를 마치며…

대회를 준비하면서 천재들만 풀 수 있는 문제를 만들었으면 좋겠다라는 의도로 시작했지만 만들다 보니 처음보다는 눈높이가 낮아졌습니다. 이번 문제가 회사의 Mission인 Unique에 부합한 문제였으면 했고 그 목표를 달성하기 위해 많은 노력했습니다.

참가자들이 게임을 즐기듯 재미있게 대회에 참여하고 Code Sprint를 통해 창의적인 인재들이 두각을 드러내는 계기가 되었으면 합니다.

감사의 글

올해 저희 팀도 Smart Wallet (이제는 syrup이 되었습니다^^)과 신규 서비스 준비로 굉장히 바빴기 때문에 문제를 출제하고 관련된 해당 문제출제 시스템까지 개발하기엔 너무나도 시간이 부족했습니다. 하지만 정말 좋은 분들의 도움으로 문제 출제, 서버 개발 및 구성을 마칠 수 있었습니다. 문제 출제 및 서버 구성을 마친 후 회식 자리에서 다들 “마치 큰 프로젝트 하나 끝낸 거 같다”고 했는데, 정말 크게 공감이 갔습니다.

저와 같은 Commerce SW 개발1팀에 계시는 Code Sprint 2013 Round 2의 입상자인 신진철 매니저님은 문제화하는데 큰 도움을 주었고 Platform Software 개발1팀의 권운근 매니저님은 문제 출제 서버와 채점 시스템 개발업무를 전담했습니다. 대회 웹페이지와 채점결과 리포트 모듈을 담당했던 윤정민 매니저님께도 감사드립니다. 이 외에도 안정적인 운영을 위한 서버 인프라, 보안 및 성능 점검도 중요했는데, 관련 팀 모두 도움 주셔서 감사합니다.  🙂

한민호 Commerce SW개발1팀

Daum 통합검색플랫폼팀에서 검색플랫폼 개발을 했었고
SK Planet에서는 Tad 광고 플랫폼을 개발하고 있습니다.
다양한 플랫폼 개발을 경험하며 회사의 발전에 기여하고 싶은 개발자 입니다.
머지않아 한국에도 Software Engineer가 최고의 직업이 될 것 입니다.

Facebook Twitter LinkedIn Google+ 

공유하기