유저 목록을 Redis Bitmap 구조로 저장하여 메모리 절약하기

안녕하세요, 리멤버 플랫폼 서버 파트의 노아론입니다.
이번 글에서는 특정 유저군을 타겟팅하는 과정에서 Redis의 SET 구조 대신 Bitmap 구조를 이용하여 어떻게 메모리를 절약할 수 있었는지에 대해 이야기하려고 합니다.

리멤버 리서치에선 설문 조건에 맞는 유저를 타겟팅하여 응답을 수집하고, 참여한 유저에겐 소정의 리워드를 지급하고 있습니다.
특정 유저에게 맞는 설문만을 제공하기 위하여 내부의 타겟 시스템을 이용해 설문마다 참여할 수 있는 유저의 고유 ID를 보관하고 있습니다.

이 과정에서 Redis에는 설문에 참여할 수 있는 유저 ID 목록을 SET 구조로 저장하였는데요,
보관해야 하는 유저의 수에 비해서 Redis에서 차지하는 메모리 크기가 지나치게 비대한 문제가 있었습니다.

리멤버 리서치에서는 Redis를 이렇게 사용합니다.

리서치 운영을 위한 사내 어드민 페이지에서 설문 생성을 마치면 지정된 조건에 맞는 유저의 고유 ID를 가져오고,
설문 대상이 되는 유저 목록은 리멤버 내의 광고 서버에 요청하여 가져오고 있습니다

리서치 서버는 원하는 세부 조건에 맞게 타겟팅 된 유저 고유 ID 목록을 광고서버에 요청하여 데이터를 가져옵니다.
이렇게 가져온 설문 대상 유저 목록은 Redis에 저장되고 특정 유저가 설문의 대상인지 판별하는 용도로 데이터를 이용하게 됩니다.

Redis에 대상 유저를 저장하는 용도로 채택한 이유로는 아래와 같습니다.

• 대상 유저 ID 목록의 크기는 적게는 수십명에서 많게는 수십만, 수백만의 단위로 구성됩니다.
  유저 목록에 대한 데이터는 광고 서버에서 보존하고 있으므로, 대량의 크기를 가지는 정보를 다른 서비스의 DB에 다시 저장하는 작업은 피하였습니다.

• 대상 유저 ID 목록은 설문이 종료된 뒤에 다시 사용하지 않는 정보입니다. Time-to-live를 어플리케이션 레이어에서 구현하지 않고, Redis 내에서 처리할 수 있습니다.

마주한 상황

유저 ID 목록을 Redis에 저장하는 과정에서 우려되는 지점을 발견하였습니다.
개발 당시 유저 ID를 Redis에 저장하는 방식으로는 다음 그림과 같이 SET 구조를 사용하였습니다.

 설문을 생성하고 유저 5천명에게 타겟팅하였습니다. 이때 아래의 과정으로 유저 ID 5천개를 가지고 있는 SET이 추가됩니다.

이 설문에서 어떤 유저가 참여 대상인지 알기 위해 총 298,456 Byte 크기의 메모리를 소모하였습니다.

유저의 수가 상대적으로 적거나 동시 진행 중인 설문이 몇가지 되지 않는 상황에서는 천 단위의 유저 ID를 저장하는 상황은 당장 문제가 없어보입니다.
하지만 수십만명에 달하는 유저의 참여 가능 여부를 보관해야하는 상황이라면 이야기가 달라집니다.

두번째 설문에서는 유저 19만명에게 타겟팅하고, 얼만큼의 메모리가 소모되었는지 확인해보겠습니다.
동일하게 타겟팅한 유저의 양만큼 SET이 추가됩니다

이때 약 10439.65 KB (10.6902 MB)의 메모리가 소모됩니다.

19만명의 유저의 참여 정보를 저장하기 위해서 약 10MB에 달하는 메모리를 사용한다는 것은 문제가 될 것으로 우려하였습니다.
수 백만명을 대상으로 하는 설문 10개가 동시에 진행된다면 오로지 유저 목록을 담기 위해 사용하는 Redis의 메모리 크기만해도 기가바이트 단위가 될 것을 짐작할 수 있습니다.

이러한 상황을 초래하게 만들지 않고자, 메모리 크기를 줄이기 위해 Redis의 Bitmap 구조를 고려하였습니다.
Redis Bitmap은 이진 벡터와 같이 사용할 수 있는 String 자료형에서 확장된 것으로, 정수 0부터 N으로 구성된 형태의 SET을 효율적으로 표현할 수 있습니다.

Redis Bitmap 구조를 이용해 개선 시도하기

특정 유저가 설문에 참여 가능한지 정보를 알 수 있어야 하므로, 아래 명령어처럼 Bit 오프셋을 유저의 ID로 사용하였고,
Redis의 GETBIT 커맨드를 통해 오프셋 위치에 저장되는 Bit 값을 설문 참여 가능 대상 유저 여부로 사용하였습니다.

성능 면에선 SET 구조에서 사용할 수 있는 커맨드인 SISMEMBER의 시간복잡도는 O(1), Bitmap 구조의 String 값에서 가능한 커맨드인 GETBIT의 시간복잡도 또한 O(1) 으로
두 명령 모두 저장된 크기에 따른 성능 차이는 발생하지 않는 것으로 확인하였습니다.

Bitmap 구조로 변경하였을 때 메모리 크기는 어느정도 개선할 수 있었는지 보겠습니다.

가장 큰 유저 ID가 50만이면서 50만명에 대한 참여 정보를 담는다면 SET 구조에선 20,194,504 Byte, Bitmap 구조에선 114,768 Byte가 필요합니다.
만일 가장 큰 유저 ID가 75만이고, 이들 75만명에 대한 참여 정보를 담는 경우엔 SET 구조에선 36,583,112 Byte가, Bitmap 구조에선 114,768 Byte가 필요하게 됩니다.

우려되었던 메모리 크기의 문제를 SET 구조에서 Bitmap 구조로 변경하여 크게 절감할 수 있었습니다.

마무리

리멤버 리서치의 유저 타겟팅 과정에서 Redis Bitmap 구조를 이용한 것은 상수 시간의 시간 복잡도를 가지면서 차지하는 메모리는 절약하는데 이점을 얻었습니다.
그렇지만, Bitmap 구조가 모든 상황에서 좋은 것이 아니라는 점은 주의해야합니다.

상대적으로 큰 오프셋을 가지며 적은 갯수의 데이터를 보관한다면 Bitmap보다 SET에 저장할 때에 차지하는 메모리 크기가 더 작습니다.
최대 유저 ID가 1백만이면서 유저 10명의 대상 여부를 저장하는 경우가 이러한 경우입니다.
수십 혹은 수백 단위의 상대적으로 적은 수의 유저가 포함되는 경우엔 SET구조를 함께 사용하도록 고려하는 것이 좋아보입니다.

또한, Bitmap 자료 내에서 Bit가 1인 모든 유저의 ID를 구하는 것은 레디스 명령어로서 지원하지 않습니다. 따라서 이는 Redis의 Lua Scripting을 이용해 해결해야 합니다.

리멤버의 내부 어드민 페이지에서는 설문 참여 대상 유저 목록 조회를 위한 목적으로,
Bit 값이 1인 유저 ID 목록에 대해서 Integer 배열을 반환하는 Lua Script를 구현하여 사용하고 있습니다.
리멤버 리서치에선 특정 유저의 설문 대상 여부를 판별하기 위한 용도로 쓰여 Bitmap 구조가 적합하였고, 속도를 상수 시간 내에 처리하도록 보장하면서 메모리 크기에서도 많은 이점을 가질 수 있었습니다.

글의 마무리는 채용 공고로 맺겠습니다.
리멤버에선 고난도 애플리케이션 개발에서 나오는 어려운 문제의 해결을 즐기는 동료 분을 모시고 있습니다.
리멤버 서버 개발자 채용공고

감사합니다.