네이버 데뷰 2015에서 흥미로웠던 세션들 정리

2일차 세션 6. 코끼리 냉장고에 집어넣기 - 실시간 추천엔진을 머신 한대에 구겨넣기

발표자: 하용호(넘버웍스)

슬라이드: http://www.slideshare.net/deview/261-52784785

이 날 들은 세션 중에 가장 흥미롭고 재미있었던 세션이었다. 내용이 어려워서 전체적인 얼개를 중심으로 40% 정도만 이해한 것 같지만 한 번 정리해본다. 세션 내용은 코끼리 한 마리를 냉장고에 집어넣는 것이다. 즉, 수십-수백 대의 서버가 필요한 실시간 추천엔진을 노트북 하나에 집어넣어 구동해보겠다는 야심찬 프로젝트다. 그리고 실제로 성공했다!

협력필터 엔진

추천엔진은 내용기반 엔진과 협력필터 엔진으로 나뉜다. 내용기반 엔진은 다루기 어렵기 때문에 많은 경우 협력필터 엔진을 사용한다. 그 예로는 아마존의 상품 추천 기능을 들 수 있다.

협력필터 엔진은 다시 메모리 기반과 모델 기반이 있는데, 보통 둘 다 조합해서 쓰인다. 이 세션이 다룬 내용은 메모리 기반 모델이다.

협력필터 엔진의 원리는 한 사람이 선택한 상품들을 다른 사람과 비교해 가장 비슷한 상품을 선택한 사람이 고른 상품 중에서 빠진 상품을 찾는 것이다. 즉, 가장 닮은 꼴을 찾는 것이다. 이 닮은 꼴을 찾기 위한 알고리즘이 자카드 유사도(Jaccard similarity)다.

규모의 문제

자카드 유사도는 이해하기 간단한 알고리즘이지만 규모가 문제가 된다. 사용자가 3명, 상품이 10개라면 비교할 횟수는 그렇게 많지 않다. 하지만 상품이 1백만 개, 사용자가 10만 명이라면 어떨까? 엄청난 횟수를 비교해야 하며, 수십-수백 대의 서버를 구동해야 하는 사태가 벌어진다. Hadoop과 같은 도구를 사용하면 대규모 데이터를 처리하는데 도움을 받을 수 있지만, 이건 Hadoop에게도 감당하기 힘든 너무 큰 계산이다.

미리 비교 대상을 줄여놓으면 계산량을 줄일 수 있다. 이를 위한 방법으로 샘플링과 클러스터링이 있는데 이 때는 특정 유형으로 사람들을 묶는 클러스터링을 쓴다.

그런데 클러스터링을 할 때도 여전히 규모가 문제가 된다. 평범한 방법으로 클러스터링을 하게 되면 클러스터링 자체를 위한 계산량도 여전히 많게 되는 것이다. 계산량을 줄이려고 클러스터링을 하려는데 클러스터링을 하는 계산량이 많으면 안 된다. 그래서 좀 더 가벼운 클러스터링 방법이 필요하다.

MinHASH

구글은 MinHASH를 이용해 이 문제를 해결했다. MinHASH란 해시를 만들 때 일부러 버킷을 적게 잡아서 비슷한 것들끼리 충돌하게 만드는 방법이다. 이렇게 비슷한 것들이 충돌해 뭉치게 되면 클러스터가 구성되는 것이다. 클러스터링은 원래 O(n^2)의 연산량증가를 갖지만, MinHASH를 사용하면 O(n)의 연산증가량을 갖게 돼 비교할 수 없이 훨씬 효율적이다.

MinHASH는 매우 역발상적인 방법으로, 일반적인 해시와 비교하면 다음과 같은 차이가 있다.

해시 충돌 확률 민감도
좋은 해시 넉넉한 버킷 / 충돌이 적다 값이 비슷해도 해시값은 전혀 다르다
좋은 MinHASH 협소한 버킷 / 일부러 충돌시킨다 값이 비슷하면 해시값도 비슷하다

MinHASH의 결과값은 자카드 유사도의 결과값과 비례한다. 다만 정확도는 조금 떨어지는데, 사용할 해시함수를 늘려서 결과값의 길이를 늘려 정확도를 높일 수 있다.

I/O 작업 피하기

그런데 MinHASH를 이용해 클러스터링을 하더라도 정석적인 방법을 쓰면 여전히 느리다. 대량의 데이터에 작업을 하다보면 I/O가 발생하여 느려지는 것이다.

I/O가 발생하는 이유는 상품과 유저의 부익부 빈익빈 현상 때문에 일어난다. 대부분의 서비스는 라이트 유저와 헤비 유저가 많고, 중간적인 유저는 별로 없다. 상품도 마찬가지다. 조금씩 팔리는 상품이 다양하게 존재하거나 히트상품에 많은 판매가 일어난다. 소셜 미디어를 예로 들면, 아이유는 130만 명이 팔로우하지만 평범한 사람은 100여명이 팔로우하는 것이다.

문제는 100여명만 팔로우하는 사람의 데이터를 읽을 때조차 그가 팔로우한 아이유의 데이터를 읽기 위해 130만 건의 데이터를 추가로 조회하게 된다는 것이다. 이 때마다 엄청난 메모리를 소모하며 I/O가 발생해 시스템이 느려지게 된다. 그런데 심지어 아이유는 너도나도 팔로우를 하고 있어 수없이 많이 조회되기까지 한다!

따라서, 인기 아이템과 보통 아이템의 데이터 길이를 똑같이 맞춰버리면 대량 I/O로 인한 속도 하락을 막을 수 있다. 이 길이를 맞추는 데에도 MinHASH를 이용할 수 있다. MinHASH를 이용해 스트림의 길이를 통일시켜 버린 후, 시그니처 값이 겹치는 비율이 곧 자카드 유사도 값이 된다.

물론 자카드 유사도와는 어느 정도 오차가 난다. 하지만 해시 함수를 늘려서 시그니처 값의 길이를 늘려버리면 오차가 줄어든다. 용량과 정확도 사이에서 어느 정도 균형을 잡아 사용하면 되는 것이다.

이 방법은 구글의 접근방법과 정반대의 방법이라고 한다. 구글은 시그니처를 소량 생성해 적절히 충돌시켜 미리 클러스터링하는 방법이다. 새로운 방법은 시그니처를 대량 생성해 충돌을 피하는 방법이다. 두 번째 역발상인 셈이다.

이렇게 하면 다량의 건수를 메모리상에 올려둔 채로 작업할 수 있어 훨씬 빠르게 동작한다. 게다가 메모리가 얼마나 필요한지를 예측하는 것도 가능하다. 상품 하나당 4바이트짜리 시그니처 100개가 있다고 계산하면, 메모리 1GB당 180만 개의 상품을 담을 수 있다. 엄청난 효율이다.

분할 상환 (청소는 조금씩 미리미리)

또 다른 성능 문제가 발생하는 구간이 있다. 바로 대량의 정보를 갱신해야 할 때다. 데이터가 쌓이다 보면 언젠가 변화를 반영해 시그니처를 새로 개인해야 한다. 이걸 대량으로 처리하게 되면 많은 성능 비용이 들 것이다.

하지만 이걸 틈틈이 그때끄때 처리한다면 그리 큰 비용이 들지 않는다. MinHASH는 min 함수와 마찬가지로 결합법칙과 멱등법칙이 성립한다. 따라서 새 데이터가 들어와도 기존에 계산한 값을 버릴 필요 없이 그대로 새 계산을 누적해 나가는 것이 가능하다. 따라서 새로운 값이 갱신될 때마다 간단히 연산해버리면 그만이다.

Secondary Index

지금까지 설명한 방법은 자료의 길이를 짧게 줄여서 비교를 용이하게 한 것이다. 하지만 이 줄어든 자료의 비교를 비교하려면 여전히 O(n^2)의 연산증가량을 갖는 막대한 비용이 든다. 이를 해결하기 위해 Secondary Index를 쓸 수 있다.

Key-Value 저장소에 상품별로 계산해놓은 각 시그니처의 값들을 키로 하고 그 값을 시그니처로 가진 상품들을 값으로 집어넣는 것이다. 그러면 이 저장소를 검색하는 비용만으로 자카드 유사도를 계산할 수 있다.

사용하는 도구

새로운 값이 갱신될 때마다 MinHASH 계산값도 갱신하며, 따라서 Secondary Index도 갱신한다. 매우 잦은 갱신 처리를 속도 저하 없이 해결하려면 반드시 I/O를 피하고 메모리에서 모든 걸 처리해야만 한다. 이걸 하기 위한 적절한 도구는 Redis다.

Redis는 여러 가지 자료구조를 제공하는데 그 중 Strings(문자열 저장소)가 가장 좋다. 언뜻 보면 다양한 집합 연산을 지원하는 Sets(집합 저장소)가 더 좋아 보이지만 실제로는 아니다. Redis에서 값을 가져오는 Order! 연산비용이 Strings는 O(1)이지만 Sets는 O(n)이기 때문이다. 게다가 Redis는 Mget 명령을 지원하기 때문에 여러 요청을 모아서 한 번의 요청으로 처리하는 것도 가능하다.

Strings는 압축을 적용하기도 용이하다. Snappy를 쓰면 압축효율은 좀 낮지만 속도가 거의 압축하지 않는 때와 비슷한 수준으로 빠르다.

코끼리는 냉장고에 들어갔는가?

지금까지 설계한 구조를 실제 적용해보면 필요한 서버 사양은 다음과 같다.

필요한 CPU 필요한 메모리
REDIS 1 core MinHash 1GB
MinHASH 계산 1 core Secondary Index 2G
추천 계산 1 core 기타 1GB

합계 3 core, 4 GB 다. 노트북 한 대면 충분한 사양이다.

진정한 추천엔진은 이보다 좀 더 많은 요소와 기능이 들어가야 하며, 이건 매우 단순한 메모리 기반 방식이라고 할 수 있다. 하지만 정확도는 약간 낮다 하더라도 훨씬 큰 효율을 취할 수 있기 때문에 유용한 방법이다. 고용량의 BMP도 가치가 있지만, 약간 손실이 있다 하더라도 훨씬 적은 용량으로 압축된 JPEG 파일도 가치가 있는 것이다. 99.9%의 정확도로 다른 큰 이익을 취하는 것이다.