📕 목차
1. Introcution
2. How to Resolve?
3. Lexicographical Sorting
4. Consideration
1. Introduction
📌 As-is
빠른 저장 및 조회를 위해 Redis에 채팅 이력을 저장하여 관리하고 있는 상황.
이 때, 채팅 아이디의 시간 기반 정렬(Time based sequence), 고유성(Unique)과 높은 동시성(High Concurrency)을 보장하기 위해 TSID를 사용하기로 결정했었다.
그리고 이 값들은 처음에 Hash로 바로바로 캐싱을 했었으나, 다음과 같은 문제로 Sorted Set을 사용하기로 결정했었다.
- 채팅 조회의 경우 범위 탐색이 빈번하게 발생함.
- 해시 자체는 고유성을 보장하지만, 저장 순서가 보장되지는 않음. (id가 뒤늦게 생성된 데이터가 저장은 더 빨리 되는 경우)
그래서 이 때까지만 해도, '음, 어차피 chatId가 순서 보장하니까, score에 chatId 넣고 저장하면 되는 거 아님?'이라는 낙관적인 마인드로 설계를 구상했었다.
그러다 과거 채팅 이력을 조회하기 위한 메서드를 구현하기 위해, 위와 같은 메서드를 구현했다.
redis 명령어로 표현하면 다음과 같다.
ZREVRANGEBYSCORE chatroom:{채팅방_아이디}:message {마지막으로 조회한 메시지 아이디} 0 limit 0 {size}명령어는 zrevrangebyscore를 사용했는데, 나중에 알고 보니 redis 6.2.0 버전부터 deprecated 되었다고 한다.
하지만 현재 버전의 data redis가 해당 명령어를 지원하지 않기도 하고, redis 7.4에서도 명령어가 먹히긴 하길래 일단 그대로 사용 중이다.
이 때, max에 해당하는 값이 exclusive인지, inclusive인지 모르겠어서, lastMessageId - 1을 삽입했다.
그러면 "마지막으로 읽은 알림 이전의 채팅 이력 30개"를 무사 조회할 것이라 생각했기 때문이었다.
📌 Expected size: 0 but was: 1 in:
Domain 로직 단위 테스트를 수행할 때, 거의 모든 기능이 문제없이 동작했었다.
그래서 채팅방 이력 조회 API를 뚫을 때도 그냥 코드 몇 줄 추가하면, 기능 하나 뚝딱하고 해치울 수 있는 가벼운 태스크라고 여겼었다.
그래도 Happy Path에 대한 통합 테스트는 빠트리지 않고 작성했었다.
문제가 발생하고 멘탈이 터진 시점에 캡쳐한 거라 코드가 좀 난잡하긴 한데, 테스트 명세는 이렇다.
- given: 채팅방의 방장으로 가입한 사용자가 채팅방에 작성한 메시지 10개가 존재한다.
- when: 가장 먼저 생성된 메시지 Id를 lastMessageId로 전달한다.
- then: 이전의 데이터는 더 이상 없으므로, hasNext는 false 여야 한다.
이미 다른 Happy Path 테스트도 통과한 이후였고, 이번에도 아무런 문제 없이 통과할 것이라 여겼다.
진짜 긴장감이라고는 1도 없는 상태에서 테스트를 실행했는데,
난데없이 예상치도 못 한 결과를 마주하고, 상당히 벙쪘다.
가장 처음 생성된 채팅 데이터의 lastMessageId를 넘겼고, max는 lastMessageId - 1을 기준으로 잡고 있으니, 당연히 이전 데이터는 아무것도 존재하지 않아야 했다.
하지만 테스트 결과는 1개의 데이터를 받아왔다고 주장하는 상황.
단위 테스트도 모두 통과한 나의 로직이 실패했다고?
대체 왜?
📌 What's the problem?
테스트야 뭐,,문제가 없음을 증명하기 보단, 적어도 예상되는 경로에서 문제가 되지 않음을 보장하는 정도니까, 내가 edge case를 놓쳤을 수도 있다.
하지만 native query가 어떻게 전달되는지 확인까지 했는데 문제가 발생하는 게 이상했다.
처음엔 spring에서 쿼리를 이상하게 만든 건 아닐까 싶었는데, edge case에 대해 redis에 명령어를 똑같이 입력해도 같은 결과가 반환되었다.
그러다 뭔가 이상한 점을 하나 발견했는데
분명히 chatId를 score로 잡았는데, WITHSCORES 절을 추가하니 마지막 두 자리수가 엉뚱한 값이 들어가 있었다.
심지어 해당 데이터만 그런게 아니라, 모든 데이터가 십의 자리 수 이하부턴 엉뚱한 수가 삽입되어 있는 현상.
범인이 score라는 건 명확했다.
그래서 일단 Redis 공식 문서에서 Sorted Set의 score에 대한 정보를 좀 더 찾아보기로 했다.
엉뚱하게 Sorted Set 설명에는 없고, ZADD 명령어 설명에서 score는 double 타입을 사용한다고 적혀있었다.
그리고 score가 완벽하게 표현할 수 있는 값의 범위는 9,007,199,254,740,992.
long 타입을 커버하기엔 턱없이 부족하다.
혹시나 싶어, RedisTemplate의 zadd 명령어를 보니, 여기도 score를 double 타입으로 받고 있었다.
그렇다.
이건 메서드 명만 보고 얼추 끼워맞추던 내게 주어진 업보 청산 같은 거였다.
(다시 봐도 어이가 없다...난 대체 무슨 생각으로 코드를 작성했던 걸까?)
📌 Long, Double
가장 문제는 long, double 타입에 대한 정의를 너무 당연하다는 듯이 망각하고 있었던 것.
대충 형변환해서 값이 손실된 건 알겠는데, double을 하도 쓸 일이 없다보니 값의 표현 범위조차 가물가물했다.
그냥 long이랑 똑같은 8byte를 차지하는데, 실수형 자료다...정도?
s | eeeeeeeeeee | fffffffffffffffffffffffffffffffffffffffffffffffffffff
^ | ^ | ^
| | | | |
| | | 52비트 fraction(가수)
| | 11비트 exponent(지수)
1비트 sign(부호)문제가 발생한 원인은 실수 표현에 있다.
- Java의 double 타입은 IEEE 754 표준의 배정밀도(double-precision) 부동 소수점 형식을 따른다.
- double은 부호비트(1bit) + 지수비트(11bit; 편향값 1,023 사용) + 가수비트(52bit)를 사용한다.
- long과 마찬가지로 64bit 데이터 타입이지만 표현 가능한 실수 데이터 범위가 다르다.
예를 들어, 640,436,544,564,866,084라는 값을 갖는 long 타입 변수가 있다고 하자.
이는 6^63 - 1 범위 내에서 표현 가능한 값이므로 당연히 사용할 수 있다.
하지만 이를 double 타입으로 변환하려는 순간 문제가 발생하다.
10진수 : 640436544564866084
2진수 : 1 00011100011010010011010010011100011111101111010110000100100
double 타입 10진수: 6.4043654456486605E17
double 타입 16진수: 0x1.1c69349c7ef58p59
다시 long 타입으로 변환: 640436544564866048
다시 long 타입으로 변환 2: 100011100011010010011010010011100011111101111010110000000000long -> double 비트 치환 방법이 생각이 안 나서, 그냥 자바로 실행하고 로그를 뿌렸다.
1 000111000 1101001001 1010010011 1000111111 0111101011 0000100100- IEEE 754에서 1.xxx * 2^n 형태로 정규화하는 방법
- 가장 왼쪽의 1 제외 (암묵적 1bit; 어차피 가장 앞은 1이므로 생략해도 됨.)
- 실제 지수(유효 bit 개수): 59개
- 최종 지수 = 실제 지수(59) + 편향값(1,023) = 1,082
지수를 결정했으니 가수 영역을 결정해야 하는데, 이 부분에서 데이터 손실이 발생한다.
1 0001110001101001001101001001110001111110111101011000 0100100앞의 1을 버리고, 52-bit를 체크하면 뒤의 "0100100"(=36)은 버려지게 되므로 최종 bit는 다음과 같이 나오는 것이다.
0 10000111010 1110001101001001101001001110001111110111101011000
^ | ^ | ^
| | | | |
| | | 52비트 가수
| | 편향값이 더해진 지수 1082(10000111010)
부호비트문제는 이 값을 다시 long으로 복구하기 위해, 지수만큼 값을 표현하려다보니 가수의 부족한 bit를 모두 0으로 채우게 된 것이다.
10진수 : 640436544564866084
double 타입 10진수: 6.4043654456486605E17
다시 long 타입으로 변환: 640436544564866048그러면 정확하게 score에서 발생한 현상과 동일한 값을 얻을 수 있음을 알 수 있다..^^
복구된 값은 기존 값보다 36만큼 차이가 발생하는데, 이는 버려진 비트의 값과 동일하다.
여튼 이 때문에 lastMessageId - 1을 max로 설정하면 아무 값도 조회가 되지 않았어야 했는데,
score가 데이터 손실로 인해 id보다 작은 값을 가지게 되면서 스캔 대상이 되었던 것이다.
2. How to Resolve?
📌 오차값만큼 버리기?
long 데이터 타입의 최대값은 2^63 - 1 = 9,223,372,036,854,755,807.
길이로 따지면 최대 19자리 수를 가질 수 있다.
반면, double 타입이 표현할 수 있는 유효 숫자는 2^53 - 1 = 9,007,199,254,740,991 (암묵적 1을 포함하기 때문에 53bit).
즉, 유효 숫자는 16자리 수에 불과하다.
최악의 경우 100의 자리까지 데이터가 손실될 수 있는데, 그렇다면 lastMessageId - 1이 아니라
손실 예측 값까지의 비트를 버리는 방법은 어떤가?
lastMessageId는 TSID고, node 비트를 최소한으로 줄였기 때문에 다음과 같은 스펙을 갖고 있다.
- 42 bit: timestamp bit
- 8 bit: node bit
- 14 bit: counter (0~16,383 사이에서 같은 timestamp 내 오름차순을 보장하는 난수)
여기서 충돌이 발생할 수 있는 64 - 53 = 11bit 영역을 버림으로써, score를 계산해볼 수도 있다.
lastMessageId - 1이 아니라, lastMessageId의 낮은 자리수의 11bit를 버리고 다시 long을 사용하는 것.
11bit에 해당하는 범위는 모두 counter이므로, 16,384(14bit) / 2,048(11bit) = 8개.
따라서 같은 ms 내에 8개마다 하나씩 같은 값으로 취급될 수 있으므로, 충돌 확률은 12.5%나 된다.
12.5%...이건 너무 높다.
다른 방법을 강구해보자.
📌 score를 0으로 잡으면 어떻게 정렬될까?
score가 double 타입으로 강제된 이상, 더 이상 뭘 어떻게 해결해볼 방법이 없었다.
그래서 자료구조를 바꿔야 하나 고민도 했지만, 아예 다른 NoSQL을 사용할 게 아니라면 Sorted Set보다 이상적인 대안책도 없는 상황.
그렇다고 해시로 저장하고, 매번 O(N)만큼 읽을 게 아니라면 뭔가 방법을 찾아내야만 했다. (그것도 하루만에)
그러다 갑자기 한 가지 의문이 생겼다.
만약 동일한 score를 가진 데이터가 생성된다면, 어떻게 정렬이 되는가?
값을 덮어쓸 것인가? 아니면 또 다른 규칙에 의해 정렬이 될 것인가?
공식 문서를 한참을 들여다보다 알게된 사실.
- 모든 요소가 고유함을 보장해야 하므로 동일한 요소를 반복할 수는 없다.
- 하지만 동일한 점수를 가진 여러 다른 요소의 경우, 사전순(lexicographically)으로 정렬된다.
드디어 뭔가 해결책이 보이기 시작했다.
3. Lexicographical Sorting
📌 All Score 0, lexicographical value
이 해결책은 매우..매우매우 단순하기 그지 없는 전략을 사용한다.
기존에는 key를 "chatroom:{chatroom_id}:message", value에 메시지 데이터, 그리고 score에 chatId를 할당해주었다.
그러나 이렇게 하지 않고, score를 모두 0으로 통일해버린다면?
그리고 순서를 보장하는 chatId를 "사전순"으로 정렬되도록 만들면 된다.
즉 value는 다음과 같은 꼴이된다.
chatId{message json}
이를 코드로 구현하면 다음과 같다.
private static final String SEPARATOR = "|";
@Override
public ChatMessage save(ChatMessage message) {
try {
String messageJson = objectMapper.writeValueAsString(message);
String chatRoomKey = getChatRoomKey(message.getChatRoomId());
redisTemplate.opsForZSet().add(chatRoomKey, message.getChatId() + SEPARATOR + messageJson, 0);
} catch (JsonProcessingException e) {
log.error("Failed to save chat message: {}", message, e);
throw new RuntimeException("Failed to save chat message", e);
}
return message;
}여기서 chatId와 message json 사이에 구분자 '|'를 넣은 건, 큰 의미가 없는 행위다.
하지만 이를 굳이 삽입한 이유가 있다.
- 디버깅, 혹은 역직렬화 시 용이하다.
- Sorted Set은 문자열을 byte 배열로 비교하여 사전순 정렬을 수행하는데, `|`는 ASCII 코드 174라는 매우 큰 값을 갖는다. 따라서 prefix에 해당하는 chatId에 대해서 우선 정렬을 수행하는 것을 명시적으로 표현할 수 있다. (없어도 정렬이 되기 때문에 의미가 없다는 것)
그러면 실제로 정렬이 수행되는 것을 볼 수 있다.
(chatId 사이에 `:`를 넣은 건 내 실수다. 당시엔 저게 의미가 있을 것이라 생각했으나, 매우 무의미한 행위였다.)
📌 Score is timestamp
double 타입 정렬에 비해, 사전 순 정렬에 기대하게 되면 아무래도 느려질 것이다.
정확히 얼마나 느려질 지는 몰라도, 문자열 비교가 정수 비교보다 느리다는 것은 자명한 사실이기 때문이다.
그렇다면, SortedSet을 보다 효율적으로 활용하는 방법은 무엇일까?
score sorting과 lexicographically sorting를 모두 사용하는 방법이 있다.
adjustable
<---------->
|------------------------------------------|----------|------------|
time (msecs since 2020-01-01) node counter
42 bits 10 bits 12 bits
- time: 2^42 = ~69 years or ~139 years (with adjustable epoch)
- node: 2^10 = 1,024 (with adjustable bits)
- counter: 2^12 = 4,096 (initially random)
Notes:
The node is adjustable from 0 to 20 bits.
The node bits affect the counter bits.
The time component can be used for ~69 years if stored in a SIGNED 64 bits integer field.
The time component can be used for ~139 years if stored in a UNSIGNED 64 bits integer field.TSID 스펙에 따르면, 동일한 timestamp 내에서 node + counter는 bit가 허용하는 값 이내에서 고유성과 시간 기반 고유성을 보장한다.
node bit와 counter bit의 크기는 사용자 설정에 따라 달라질 수는 있지만, (node + counter) bit는 여전히 동일하다.
그렇다면 이렇게 생각해볼 수 있다는 의미다.
- TSID 64 bit에서 42 bits는 timestamp, 22 bits는 random
- score에는 42 bits의 timestamp를 저장 (가수 영역이 충분히 표현 가능한 범위 내)
- value의 접두사는 12 bits의 random을 접두사로 저장.
사실 이건 블로그를 작성하다가 떠오른 방법이라...코드를 구현하진 않았지만, bit 분리는 아래와 같을 것이다.
@Test
@DisplayName("TSID 분리 및 Redis SortedSet 저장 테스트")
void testTsidSeparation() {
// TSID 구조 관련 상수
final int REMAINING_BITS = 22; // node(8) + counter(14)
final long REMAINING_MASK = (1L << REMAINING_BITS) - 1;
long tsid = 640436544564866084L;
// timestamp 추출 (score로 사용)
double score = tsid >> REMAINING_BITS; // 42비트만 남김
// node + counter 추출 (value 접두사로 사용)
long remainder = tsid & REMAINING_MASK;
log.info("Original TSID: {}", tsid);
log.info("Score (timestamp): {} (size: {})", score, String.valueOf(score).length());
log.info("Remainder (node+counter): {} (size: {})", remainder, String.valueOf(remainder).length());
// Redis 저장 형식 예시
String value = String.format("%d|{json data...}", remainder);
log.info("Redis command would be: ZADD chat:messages {} {}", score, value);
}Original TSID: 640436544564866084
Score (timestamp): 1.52691970959E11 (size: 16)
Remainder (node+counter): 3648548 (size: 7)
Redis command would be: ZADD chat:messages 1.52691970959E11 3648548|{json data...}이 방식은 Sorted Set을 보다 잘 활용할 수 있을 것이라 생각한다.
- Sorted Set은 기본적으로 score(timestamp)를 사용해서 데이터들을 정렬한다.
- 만약, 동일 ms내에 생성된 데이터가 있다면, value 접두사(random)를 기반으로 사전 정렬한다.
3. Consideration
📌 Failure of SoC
마지막 방법은 블로그 포스팅을 작성하다 즉석으로 떠올린 방법인데, 상당히 기발한 아이디어라고 생각한다. (자화자찬 중)
하지만 이걸 프로젝트에 반영할 것인가에 대해선 좀 회의적인데, 가장 큰 문제는 domain 영역이 너무 id 생성 방식에 대한 관심이 많다.
domain 영역의 로직은 기본적으로 기술로부터 자유로워야 한다.
그런데 redis 캐싱을 위해 id가 TSID 기반으로 생성됨을 알고 있으며, 이를 기반으로 해결책을 구했기 때문에 명백한 관심사 분리의 실패라고 생각한다.
전자는 그나마 "Long 타입 id를 value 접두사로 사용한다" 정도라서, 모듈을 분리한다고 가정했을 때 그러려니 하겠는데 후자는 그 정도가 너무 심하다.
그렇다고 파라미터로 timestamp와 prefix를 받자니, "멍청한 사용자, 똑똑한 도구" 규칙을 어기게 된다.
딜레마에 빠져버림..
📌 Conclusion
이 문제가 발생했을 땐, 최대한 빠르게 문제를 해결해야 한다는 상황 때문에 머리가 터지는 줄 알았지만
블로그를 포스팅 하면서 되새김질 하니까 진짜 재밌는 트러블 슈팅이었다고 생각한다.
그리고 long, double... bit 연산에 대해 나름 자신있었는데, 오랜만에 보니까 하나도 떠오르질 않아서 좀 어이가 없었다..
오늘도 멍청한 저는 자아 성찰을 하며, 다시 공부를 하러 갑니다..