MAB 알고리즘을 이용하여 효율적으로 정렬하기

MUSINSA tech

Published in

MUSINSA tech

12 min readAug 6, 2021

Apache Druid를 활용한 실시간 MAB 정렬 시스템 구축

안녕하세요. 무신사 전시개발팀에서 데이터 기반의 MAB 정렬과 이벤트 버스(Event Bus) 개발을 담당하고 있는 홍승표입니다.

무신사는 콘텐츠 기반의 커뮤니티로 스토어를 운영하면서 고객이 쇼핑하는데 필요한 다양한 정보를 제공하고 있습니다. 실시간 이벤트를 확인 할 수 있는 ‘배너’, 원활한 검색을 돕는 ‘태그’, 상품의 정보와 아이덴티티를 확인할 수 있는 ‘브랜드’ 등 페이지마다 수많은 정보가 배치되어 있는 것을 확인할 수 있습니다. 문제는 무신사 스토어가 제공할 수 있는 정보의 양 대비 노출할 수 있는 웹/앱의 공간은 제한적이라는 것입니다.

무신사 전시개발팀은 공간 제약이 있는 상황에서, 고객이 최대한 유의미한 결과를 얻을 수 있도록 정보를 노출하고 정렬하는 방식을 지속 개선하고 있습니다. 이번 글에서는 실시간 인기 브랜드를 확인할 수 있는 브랜드숍 페이지를 기준으로, 무신사가 어떻게 정렬 방식을 고도화하고 있는지 소개해 드리겠습니다.

문제 개선 방향

과거에는 인기 브랜드의 정렬을 수동으로 관리했습니다. 브랜드 수가 적을 땐 관리가 용이했으나, 브랜드 수가 많아질수록 관리의 효율성이 떨어집니다. 또한 수동 관리시 노출 순서가 하위로 내려간 브랜드는 다시 상위로 올라오는 것이 어렵다는 문제점도 있습니다. 브랜드가 하위에 있을수록 고객에게 노출되는 횟수는 줄어들고, 클릭까지 이어질 확률도 낮아지기 때문입니다.

이에 무신사는 브랜드 정렬을 고착화하지 않으면서도 고객이 유의미한 정보를 찾을 수 있는 정렬 방식을 찾게 됩니다. 바로 클릭률(CTR)이 높은 브랜드를 상위로 노출시키는 것입니다. 클릭률은 실시간으로 사용자들의 트렌드를 반영할 수 있고, 사용자들의 성별/연령에 따라 분류가 가능하다는 장점이 있습니다.

어떻게 효율적으로 자동화할 것인가?

클릭률 기반의 정렬을 개발하기에 앞서, 자동화 개발 기준을 다음과 같이 설정하였습니다.

고객이 관심있어 할 정보를 실시간으로 상위 노출시킨다.
특정 순서로 고착되지 않게 한다.
성별/연령에 따라 다른 순서가 부여 될수 있게 한다.

위 목표로 자동화를 진행한다면 관리자의 상위 노출에 대한 불필요한 에너지 소모를 줄이고 고객에게 더 집중 할 수 있게 될 것입니다.

처음 클릭률 통계를 기준으로 순서 정렬을 테스트 하였더니 관심있는 정보가 상위로 노출됐으나 순서의 변화가 적고 하위 정보는 상위로 올라올수가 없었습니다. 이후 판매순 통계를 기준으로 순서 정렬을 테스트 한 것 역시 클릭률과 비슷하게 순서의 변화가 적고 할인 이벤트에 따라서 순서가 급격하게 변경되었습니다.

이를 해결하기 위해 MAB(Multi-Armed Bandit) 알고리즘을 적용하여 정렬에 리프레쉬(Refresh) 성을 추가하였습니다. 구체적인 적용 방법을 설명하기에 앞서, MAB의 개념을 간단히 소개해 드리겠습니다.

MAB(Multi-Armed Bandit) 알고리즘

MAB란 카지노의 여러개(Multi)의 레버(Arm)를 가진 슬롯머신(Bandit)에서 유래되었습니다. 각 슬롯머신마다 승률이 다르기에 어떤 머신을 당겨야 최대한 많은 수익을 낼 수 있는지를 파악하기 위해 만들어진 알고리즘입니다.

MAB의 핵심 개념은 ‘탐색(Exploration)’과 ‘수확(Exploitation)’인데요. ‘탐색’은 각 슬롯머신의 승률을 확인하는 과정, ‘수확’은 가장 높은 승률로 예상되는 슬롯머신을 선택해 수익을 만드는 과정을 의미합니다. 탐색과 수확 둘 다 비용이 발생하고, 횟수가 정해져있기 때문에 좋은 결과(최대한의 수익)를 내기 위해서는 적절한 조화가 필요합니다. 둘 중 하나만 해서도 안되고, 필요 이상의 탐색이 오히려 나쁜 결과를 유발하기도 합니다.

MAB를 적용하는 알고리즘엔 여러 종류가 있는데, 그중 대표적인 세 종류와 각각의 장단점을 소개합니다.

1. ε-Greedy 알고리즘

ε-greedy는 매우 직관적인 알고리즘입니다.

ε 비율로 랜덤한 arm을 선택(Exploration)
1-ε 비율로 보상이 가장 좋은 arm을 선택(Exploitation)
성과 좋은 곳에 몰아서 수확

각 대상이 공평한 기회를 얻고 간단한 방식으로 속도를 빠르게 낼 수 있습니다. 하지만 탐색을 위해 ε만큼의 리소스가 소모되며 성과 신뢰도가 낮은곳에 편중될 수 있어 선택하지 않았습니다.

2. UDB(Upper Confidence Bound) 알고리즘

UDB는 ε-greedy의 튜닝 버전 알고리즘 입니다.

시도 횟수가 고려되지 않는 단점을 보완
적은 시도 중에 높은 성과 값을 가지는 bandit을 선택

계산이 까다로워 연산 비용이 크고, 확률이 아닌 연산 후 최고의 조건에서만 수확(Exploitation)하여 환경적 요인이 반영되기 어려워 선택하지 않았습니다.

3. Thompson Sampling 알고리즘

Thompson Sampling은 구글 애널리틱스에서도 활용할 만큼 좋은 성능을 보여주는 확률적 알고리즘 입니다. 늦게 들어오는 피드백도 수용할 수 있다는 장점이 있습니다.

과거 성과에 기반하여 성공/실패의 확률 분포를 추론
이 확률 분포에서 확률적으로 샘플링(sampling)을 추출
확률 기반으로 탐색(Exploration)과 수확(Exploitation)을 분배 하는 방식

무신사는 이 중 Thompson Sampling 알고리즘을 사용하였습니다. Thompson Sampling 알고리즘은 실시간 누적되는 로그 데이터를 기반으로 적용할 수 있다는 장점이 있습니다. 또한 다른 알고리즘에 비해 연산이 빠르고, 대상군이 많아도 컴퓨팅 부하가 적어서 빠른 성능을 보여줍니다. 때문에 새로운 대상을 추가하고 삭제하는 작업에도 용이할 것이라 판단했습니다.

성과 데이터 수집/저장

무신사는 실시간으로 기본 정보와 사용자의 행동(페이지뷰, 노출, 클릭 등)을 수집하고 있습니다. 수집된 데이터는 Apache Kafka(이하 Kafka)라는 데이터 스트리밍 플랫폼에 저장되는데요. 정렬 시스템의 기반이 되는 ‘실시간 사용자 데이터’를 이 Kafka에서 스트리밍 하게 됩니다.

Kafka에서 스트리밍한 정보를 MAB에 적용하기 위해서는 시간 기준으로 집계한 데이터를 별도로 저장해야 하고, 이 작업을 위해서는 시계열 데이터 저장소가 필요합니다.

시계열 데이터 저장소는 데이터를 저장하고, 특정 기간 동안의 데이터를 조회하기 위한 역할을 하는데요. 시중에 다양한 데이터베이스가 있지만, 저희 팀은 가장 빠르고 안정적으로 활용할 수 있는 Elasticsearch와 Apache Druid(이하 Druid)로 선택지를 좁혔습니다.

먼저 Elasticsearch는 텍스트, 숫자, 위치 기반 정보, 정형 및 비정형 데이터 등 모든 유형의 데이터를 위한 루씬(Lucene) 기반의 검색 및 분석 엔진으로, 대시보드까지 지원하는 오픈소스입니다. Druid는 스트림 프로세서가 포함되어 있으며, 데이터에 대한 롤업을 지원함으로써 스토리지를 절약하고 질의에 대한 빠른 속도를 지원하는 오픈소스입니다.

Elasticsearch는 기존에 사용해본 경험이 있어 다루는 데 익숙하다는 장점이 있지만, 결과적으로 서버 구성과 스토리지 관리 비용을 줄여 효율적으로 사용할 수 있는 Druid를 선택했습니다.

Druid 서버는 Master, Data, Query를 활용해 클러스터(Cluster) 형태로 구성 했습니다. Master는 메타데이터 관리와 코디네이터 역할을 하고, Data는 스트림 데이터를 인덱싱하여 세그먼트(Segment) 관리를 하며, Query는 데이터 질의응답과 웹 콘솔을 지원합니다. 무신사는 당시 최신 버전이였던 Druid 0.18.1을 사용했습니다. (최근에는 0.21.1까지 릴리즈 되었습니다.)

Druid의 장점은 웹콘솔을 통하여 데이터 스트림과 SQL을 조회하고, 세그먼트 관리를 할 수 있다는 것입니다. 또한 롤업(Rollup) 기능을 통해 로그 데이터를 시간 단위(day, hour, minute, second, none), 필드 단위로 집계할 수 있으며 이를 필요 데이터로 함축 저장하는 것도 가능합니다.

알고리즘 적용

MAB는 아래 5단계에 걸쳐 적용하였습니다.

Druid에서 롤업된 로그 데이터 조회

2. 로그 데이터를 Thompson Sampling 알고리즘에 적용하여 샘플링 값 추출

public static double thompsonSampling(double impression, double click) {
        BetaDistribution betaDistribution = new BetaDistribution(click, impression);
        return doubleRound(betaDistribution.sample(), DEFAULT_SCALE_LIMIT);
    }public static double doubleRound(double number, int scaleLimit) {
        BigDecimal bd = new BigDecimal(number);
        return bd.setScale(scaleLimit, BigDecimal.ROUND_HALF_UP).doubleValue();
    }

3. 추출된 샘플링 값 기준으로 로그 데이터를 역정렬

{
  "score": 0.1522362897,
  "brand": "wvproject",
  "impCnt": 160,
  "clkCnt": 63
},
{
  "score": 0.1520419833,
  "brand": "travel",
  "impCnt": 160,
  "clkCnt": 32
},
{
  "score": 0.151580471,
  "brand": "vans",
  "impCnt": 60,
  "clkCnt": 10
},
{
  "score": 0.1514003295,
  "brand": "newbalance",
  "impCnt": 118,
  "clkCnt": 21
},
{
  "score": 0.1513682931,
  "brand": "drawfit",
  "impCnt": 84,
  "clkCnt": 10
},
{
  "score": 0.1509618558,
  "brand": "mindbridge",
  "impCnt": 182,
  "clkCnt": 35
}
......

4. 정렬된 데이터를 Redis에 저장

5. 서비스 API에서 Redis 데이터를 메모리 캐싱 & 서비스

이렇게 5단계를 각 콘텐츠에 맞춰 반복하면서 MAB 정렬 데이터를 변경하고 있습니다. 처음 MAB를 적용하였을때는 수집된 성과(노출, 클릭)가 낮은 콘텐츠도 상위 노출 될 수 있었지만, 시간이 지나면서 노출, 클릭 등 성과 기반의 데이터를 기준으로 정렬하게 됩니다.

지금까지 설명드린 MAB 정렬 시스템의 전체적인 아키텍처를 정리해보면 아래 그림과 같습니다.

MAB 알고리즘 적용 후 변화된 점

인기 브랜드 리스트 기준으로 MAB 정렬 시스템 적용 결과를 살펴보겠습니다.

기존에는 인기 브랜드가 고정된 순서로 노출되다보니 모든 유입이 상위에 있는 브랜드로 집중되었습니다. 그러나 MAB 정렬 시스템을 적용한 후에는 실시간 성과와 사용자 관심도를 복합적으로 고려하여 브랜드를 노출할 수 있게 되었습니다. 또한 상위 노출되었던 브랜드도 시간의 흐름과 성과에 따라 순위가 재정렬 되도록 하여, 더 많은 브랜드가 상위 노출의 기회를 가질 수 있게 되었습니다.

특히 효과(클릭율)가 낮은 브랜드도 일정 수준의 노출 기회(탐색)를 갖게 되고, 무신사는 Druid에 저장된 로그 데이터의 기간을 조정하면서 노출 영역별 특성에 맞게 정렬을 조정하는 것이 가능해졌습니다. 이에 따라 무신사 스토어에서 해당 영역의 클릭률이 상승하는 결과를 얻을 수 있었습니다.

마치며

무신사의 MAB 정렬 시스템은 위에서 설명한 인기 브랜드 리스트 외에도 캠페인, 기획전 등 다양한 페이지의 상품과 브랜드를 정렬하는 데에도 적용되고 있습니다.

나아가 이번 작업을 기반으로 성별 집합 구성과 시간의 흐름에 따라 과거 관찰한 성과에 낮은 가중치를 적용하는 Discounted Thompson Sampling 알고리즘 적용도 병행하고 있으며, 가산점 기능(구매, 좋아요, 장바구니 등)도 계획하고 있습니다. 향후 연령별 집합 구성과 가산점 기능이 추가되면 성별, 연령, 가산점 등 다양한 조합을 활용하여 보다 다양하고 관심도 높은 MAB 정렬 시스템을 만들 수 있을 것으로 기대합니다.

감사합니다.

참고

- https://medium.com/data-reply-it-datatech/what-is-apache-druid-ad67bb8cd7f7
- https://wonyong-jang.github.io/bigdata/2021/02/12/BigData-Apache-Druid.html
- https://ichi.pro/ko/apache-druid-hyeondae-big-deiteo-bunseog-ui-pilsu-yoso-54897805342
- https://en.wikipedia.org/wiki/Multi-armed_bandit
- http://sanghyukchun.github.io/96/
- https://seing.tistory.com/65