꼼삐에서 식물 검색을 할 때 실시간 인기 식물 순위가 노출되면 좋겠다는 요구사항이 있었다. 사실 복잡한 로직을 요하는 기능은 별로 개발해본 적이 없었어서, 요구사항을 듣고서 바로 구현방안이 떠오르지 않았다. 어떤 자료구조를 활용해서 어떻게 구현할 지 조금 고민하다가 금방 구현을 하긴 했다. 그런데 최근에 어떤 회사 채용 과정에서 관련 내용을 묻는 질문이 있었는데, 까먹어버려서 뭔가 뚜렷하게 답을 하지 못했다. 잊지 않도록 상세하게 구현 내용을 좀 적어두려고 한다.
1. 기능 요구사항
'인기 순위' 라는 기능을 개발하기 위해서는 생각보다 여러 조건들이 필요했다. 우선 '인기' 라는 것을 어떤 지표로 판단할 것인지를 정해야 했다. 직관적으로 떠올릴 수 있는 지표는 조회수, 관련 게시글 수(이 경우에는 관련 게시글의 기준도 있어야 함) 등이 있을 텐데, 지표가 많아질수록 이를 위한 리소스가 더 필요해질 것이다. 만약 조회수라는 단일 지표로 인기도를 측정한다고 해보자, 그러면 조회수를 어느 정도의 기간 동안 집계할 것인지도 정해야한다. 단순히 전체기간으로 집계하게되면 순위 변동이 현재의 트랜드? 를 잘 반영하지 못하게 되어 실시간적인 인기 순위를 보여주자는 목적에 부합하지 않는다. 그리고 인기 순위를 조회 할 때마다 조회 데이터를 집계해서 인기 순위를 계산하는 것은 DB 에 상당한 부하를 줄 것이기 때문에, 한번 인기 순위를 계산해서 캐싱해두어서 부하를 줄여야 할텐데, 그러면 자연히 갱신 주기는 어느정도가 될 지도 정해야한다. 따라서 요구사항을 구체화 하기 위해서는 기본적으로 인기도의 지표, 인기 지표 집계 기준, 인기 순위 갱신 주기 같은 요소가 필요하다. 꼼삐에서는 요구사항을 다음과 같이 정리했다.
1. 최근 24시간 동안의 조회수가 많은 순으로 식물의 인기 순위를 정한다.
2. 인기도 갱신 주기는 1시간으로 한다.
3. 한 명의 유저가 중복 요청을 할 수 없도록 제한 한다. (1시간에 1회로 제한)
2. 구현을 위한 자료구조 및 로직
1) Sorted Set
우선, 조회 로그를 별도 테이블에 기록을 하는 것은 불필요 하다고 판단했다. 현재로서 식물 도감의 조회 기록은 인기 순위 집계용으로만 쓰이고 그 외의 목적이 없기 때문이다. (인기 순위를 집계하는 과정에서 도출되는 통계 기록을 저장하는 것은 의미가 있을수도 있을 것 같다.) 게다가 식물 도감은 꼼삐의 핵심 기능 중 하나이기 때문에 조회 빈도가 매우 빈번할 것이므로 조회 기록을 일일이 DB 에 기록하는 것은 DB 에 큰 부하를 야기할 것이기 때문이다. 이러한 측면들을 고려해 보았을 때, 조회 기록은 Redis에 임시로 저장해두기로 했다.
다음으로, 조회 기록을 어떤 형태로 저장을 할 것인지를 생각해야 한다. RDB를 기준으로 생각했을 때는, 식물 조회할 때마다 조회시간을 컬럼으로 가지는 로그 테이블에 계속 쌓아두고, 현재 시간을 기준으로 24시간 이내에 작성된 자료를 모두 count 하는 방법을 고려할 수 있다. Redis 에서는 보통 이러한 기능을 Sorted Set 을 이용해서 구현한다. Sorted Set 은 글자 그대로 내부 원소들이 정렬된 Set 자료구조로, 중복을 허용하지 않는다는 Set 의 특성과 내부의 원소들이 정렬 상태를 유지한다는 두가지 특성을 갖는다. 자바의 경우 TreeSet 이 비슷한 역할을 한다. 그러나 Sorted Set 의 원소는 Score 와 Member 두 가지 변수를 가지는데, Score 는 Sort 의 기준이 되는 값이며, Member 값은 중복을 체크하기 위해 사용된다.
+)
Sorted Set 은 내부적으로 Skip List 와 Hash Table 두가지 자료구조를 갖는다. Hash Table 은 원소 삽입시 중복검사를 위한 테이블이며, Skip List 는 B-Tree 거의 비슷한 구조의 인덱스 테이블(?) 이다. B-Tree 랑 데이터 접근방식에서 약간의 차이를 보인다. Redis 가 단일 스레드 기반이라 로직이 더 단순한 Skip List 를 쓴다고 한다. 데이터 삽입과 읽기에 O(logN) 이 소요된다.
2) HyperLogLog
Redis 는 값이 비싼 메모리(DRAM) 에 저장하기 때문에 용량 관리에 매우 유의해야 한다. 때문에 인기식물 집계에 어느정도의 용량이 쓰이게 될지 또한 로직을 구현하는데에 있어 고려 요소가 된다.
1. 상위 20개 정도의 식물이 많은 조회수를 얻으며, 나머지 식물은 유의미한 용량을 차지 하지 않는다고 가정
2. 평균적으로 시간당 10만명의 사람이 식물 도감을 조회한다고 가정
3. 식물마다 단위 시간당 중복이 없어야 하므로, 1시간 마다 Set 자료구조에 memberId 를 넣어 중복 검사 수행
4. 10만개의 데이터를 저장하는데에 Set 마다 5MB 정도를 사용한다고 가정 (10바이트 문자열, HashTable, Redis 오버헤드 고려)
단순히 계산해보았을 때
총 데이터 = 20(식물수) * 24(시간) * 5MB = 2GB 의 데이터를 사용하게 된다.
여기서 시간마다 Set 의 크기를 계산해서 초기화하는 등 최적화를 하게되면 100 MB 로 최적화 할 여지는 있다. 그런데 엄밀한 정확성을 요구하는 데이터가 아니라고 판단하여 간단하게 HyperLogLog 자료구조를 이용하여 2~3 % 의 오차를 허용하고 메모리 사용을 확 줄이기로 했다. (추가적인 로직을 만드는데 귀찮기도 하고 ...)
HyperLogLog 는 1.5kB 의 고정된 용량을 가지고 수억 개의 데이터의 중복여부를 검사할 수 있다. 대신 오차율이 2~3 % 발생한다. 이러한 오차율은 데이터 수가 많으면 많을 수록 더 적어지는데, 대충 1만개의 데이터부터 2~3% 의 안정적인 오차율이 확보된다고 한다. 그런데 Redis 의 HLL 는 sparse presentation 이라는 기법을 도입하여 적은 데이터 수에서도 2~3% 의 오차율을 보일 수 있다고도 한다.
+)
HLL 의 원리는 사실 좀 복잡해서 깊게는 모르는데 핵심 아이디어는 이렇다. HLL 는 원소를 저장할 때, 해당 원소를 0과 1로 이루어진 랜덤한 해시 값으로 변환한다. 이 해시값은 매우 랜덤하게 변환되기 때문에 해시값이 0으로 시작할 확률과 1로 시작할 확률이 동일하다고 가정한다. 같은 논리로 00 으로 시작할 확률은 1/4 가 되고, 000 으로 시작할 확률은 1/8이 된다. HLL 은 이러한 확률을 기반으로 몇 개의 데이터가 삽입 되었는 지를 셈한다.
HLL 은 단순히 앞에 0 이 가장 많이 등장하였을 때 0의 개수만을 기억한다. 만약 10개의 데이터가 삽입(시도) 되었을 때, 1로 시작하는 데이터가 4개, 0으로 시작하는 데이터가 3개 00으로 시작한 데이터가 1개 000으로 시작한 데이터가 2개 등장했다고 가정하면 HLL 은 '3' 만을 저장한다. 그리고 '000 으로 시작되는 원소가 삽입 되었으니까 적어도 8개 정도는 넣은 거 같아요' 라고 응답하는 셈이다.
이게 매우 신뢰도가 낮을 것 같지만 HLL 은 데이터를 여러 개의 버킷으로 나누어 저장하여 조화 평균을 내는 방식으로 오차를 줄이기도 하고... 뭐 내가 모르는 여러 기법을 통해 상당히 오차를 줄이다고 한다. 이보다 깊은 수준의 내용은 수학자의 몫으로 두도록 하겠다.
여튼 HLL 은 1.5kB 만을 사용하므로 1MB 이하의 거의 무시할만한 수준의 메모리를 차지하게 된다.
이와 관련된 읽을 만한 포스트 (수학적 접근이 있기 때문에 읽으려면 수학 공부를 좀 해야한다.)
https://d2.naver.com/helloworld/711301
위 상황과 같이 Unique Visitor, Unique Browsers 를 구하는 문제에 대한 해법(자료구조)으로 HLL 을 사용했는데 Bloom Filter, Count-min Sketch 라는 것도 있다는데 각 자료구조의 특성과 장단점에 대해서 언젠가 분석해보면 좋을 것 같다.
3. 구현 (코드)
1) 조회 기록 저장
@Override
public void recordPopularPlant(Long plantId, Long memberId, LocalDateTime now) {
LocalDateTime currentHour = now.withMinute(0).withSecond(0).withNano(0);
long epochSecondOfCurrentHour = currentHour.toEpochSecond(offset);
final String plantIdTimeKey = String.format("%s:%s:%s", RedisKey.popularity, plantId, epochSecondOfCurrentHour);
final String plantIdKey = String.format("%s:%s", RedisKey.popularity, plantId);
// TTL 설정
if (Boolean.FALSE.equals(redisTemplate.hasKey(plantIdTimeKey))) {
redisTemplate.opsForHyperLogLog().add(plantIdTimeKey, memberId.toString());
redisTemplate.expire(plantIdTimeKey, Duration.ofHours(25));
} else {
redisTemplate.opsForHyperLogLog().add(plantIdTimeKey, memberId.toString());
}
redisTemplate.opsForZSet().add(plantIdKey, plantIdTimeKey, epochSecondOfCurrentHour);
}
식물 조회 시 HLL 에 저장하는데, 이때 Key 는 해당 시간의 epochSecond 로 하여 특정 시간 구간마다 HLL 을 할당해주고, 25 시간의 TTL 을 부여한다. 그리고 해당 Key 를 식물의 Sorted Set 에 저장하고 Score 를 epochSecond 를 그대로 저장해서 시간 순으로 나열 될 수 있도록 한다. 참고로 Sorted Set 은 기본적으로 오름차순으로 정렬되기 때문에 더 과거의 자료가 앞에 오게 된다.
2) 조회 기록 업데이트
@Override
public void updatePopularPlantStat(LocalDateTime now) {
double epochCurrentHour = getEpochMillis(now.minusHours(1).withMinute(0).withSecond(0).withNano(0));
double epochPastHour = getEpochMillis(now.minusHours(24).withMinute(0).withSecond(0).withNano(0));
Set<String> plantIdWithinTimePeriod = redisTemplate.opsForZSet()
.reverseRangeByScore(RedisKey.recentPlantDetails, epochPastHour, epochCurrentHour);
Map<String, Long> plantViewStat = new HashMap<>();
for (String plantId : plantIdWithinTimePeriod){
String plantIdKey = String.format("%s:%s", RedisKey.popularity, plantId);
redisTemplate.opsForZSet().removeRangeByScore(plantIdKey, Double.NEGATIVE_INFINITY, epochPastHour);
Set<String> plantIdTimeKeys = redisTemplate.opsForZSet()
.rangeByScore(plantIdKey, epochPastHour, epochCurrentHour);
long views = 0L;
for (String plantIdTimeKey : plantIdTimeKeys){
views += redisTemplate.opsForHyperLogLog().size(plantIdTimeKey);
}
plantViewStat.put(plantId, views);
}
popularityRecordRepository.updateRecord(plantViewStat);
}
1시간 마다 스케줄러로 트리거되는 업데이트 로직이다. 우선 24 시간 내에 조회된 적이 있는 식물ID 를 가져온다. 해당 값은 다른 목적으로 유지하고 있던 건데 ('다른 유저들이 본 식물들' 같은 기능) 여기서 딱 쓰기 좋은 데이터였다. 해당 식물 ID 를 순회하면서 총 조회수를 구한다. 이 때 Sorted Set 을 거꾸로 정렬해서 24시간 이전의 자료는 전부 삭제하고 최근 24 시간 동안의 데이터(HLL) 의 총 사이즈를 전부 더한다. 이렇게 하면 24시간 동안의 조회수가 계산된다. 상기했다시피 오차율이 2 ~ 3% 발생한다.
4. 결론
Redis 의 Sorted Set 과 HLL 를 써봤는데, Sorted Set 은 실시간 순위 뿐만아니라 여러모로 쓸모가 많은 자료형을 보인다. 그런데 사실 HLL 의 경우 메모리를 매우 적게 쓰기 때문에 유용할 것 같지만, 2 ~ 3% 의 오차가 용인되는 상황이 얼마나 있을까 좀 의문이 들기도 한다. 모 회사의 면접에서 '광고 클릭 수 집계 시 중복 처리를 어떻게하면 좋겠냐' 고 물었었는데 HLL 로 답했다가 '그건 오차율이 존재하기 때문에 쓰지 않고있다' 라는 말을 들은 적이 있다. (근데 지금 생각해보면 중복 처리라는게 '따닥' 상황에서의 중복 처리를 물었던 것 같다. 왜냐면 광고 송출시 광고에 고유한 id 를 생성해서 이를 Redis 로 읽기 처리를 한다... 뭐 이런식으로 첨언을 해주셔가지고 핀트를 잘못 잡았다고 생각했었다.) 여튼 Redis 의 여러 자료구조를 써볼 수 있는 좋은 기회였다
