(최적화 2) 비트 패킹으로 주문 ID 최적화

이전 글: 메모리 얼라인먼트와 병목

이 글은 매매 시스템 시리즈의 최적화 파트 두 번째 글입니다.

다음 글: 저지연 로깅

주문 ID의 요구사항

OMS에서 주문 ID는 핵심 식별자입니다. 주문을 생성하고, 조회하고, 체결을 매칭할 때 모두 주문 ID를 사용합니다.

기본적인 요구사항:

• 고유성: 주문마다 유일해야 함
• 거래소 구분: 어느 거래소의 주문인지 알아야 함
• 빠른 조회: HashMap에서 O(1) 조회

---

단순한 구현: 구조체

가장 직관적인 방법은 구조체로 만드는 것입니다.

struct OrderId {
    venue: u8,      // 거래소 (1~255)
    order_id: u64,  // 주문 번호
}

이 구조체의 크기는 얼마일까요? 9바이트일 것 같지만, 실제로는 좀 다릅니다.

+-------+--------+----------+
| venue |  pad   | order_id |
| 1byte | 7bytes |  8bytes  |
+-------+--------+----------+
         Total: 16 bytes

이전 글에서 다뤘듯이, u64의 자연 정렬을 맞추기 위해 7바이트 패딩이 들어갑니다. 9바이트 데이터가 16바이트를 차지합니다.

해시 성능 문제

크기보다 더 큰 문제는 해시 연산입니다. HashMap<OrderId, Order>로 주문을 관리할 때, 키의 해시를 계산해야 합니다.

impl Hash for OrderId {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.venue.hash(state);
        self.order_id.hash(state);
    }
}

두 필드를 각각 해시해야 합니다. 단순해 보이지만, 주문 조회는 초당 수만 번 일어날 수 있습니다.

---

비트 패킹: u64 하나로

그래서 다른 방법을 생각해 봤습니다. u64는 64인데 이걸 쪼개서 쓰면 어떨까요?

• 상위 8비트: 거래소 (0~255)
• 하위 56비트: 주문 ID

+----------+---------------------------+
|  venue   |         order_id          |
|  8 bits  |         56 bits           |
+----------+---------------------------+
           Total: 8 bytes (u64)

56비트면 약 7경(2^56 ≈ 7.2×10^16)개의 주문을 표현할 수 있습니다. 하루 1억 건씩 200만 년을 쓸 수 있는 양입니다.

구현

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct OrderId(pub u64);

impl OrderId {
    const VENUE_SHIFT: u64 = 56;
    const VENUE_MASK: u64 = 0xFF << Self::VENUE_SHIFT;
    const ORDER_MASK: u64 = !Self::VENUE_MASK;

    pub const VENUE1: u64 = 1;
    pub const VENUE2: u64 = 2;
    pub const VENUE3: u64 = 4;

    pub fn new(venue: u64, order_id: u64) -> Self {
        Self((venue << Self::VENUE_SHIFT) | (order_id & Self::ORDER_MASK))
    }

    #[inline]
    pub fn venue(&self) -> u64 {
        (self.0 & Self::VENUE_MASK) >> Self::VENUE_SHIFT
    }

    #[inline]
    pub fn order_id(&self) -> u64 {
        self.0 & Self::ORDER_MASK
    }
}

비트 연산 설명

venue = 1 (VENUE1)
order_id = 12345

Step 1: venue << 56
  0x0000_0000_0000_0001 << 56
= 0x0100_0000_0000_0000

Step 2: order_id & ORDER_MASK
  0x0000_0000_0000_3039 (12345)
& 0x00FF_FFFF_FFFF_FFFF
= 0x0000_0000_0000_3039

Step 3: OR
  0x0100_0000_0000_0000
| 0x0000_0000_0000_3039
= 0x0100_0000_0000_3039

하나의 u64에 거래소와 주문 ID가 모두 들어갑니다.

---

성능 비교

메모리

방식	크기
구조체 (venue: u8, order_id: u64)	16 bytes
비트 패킹 (u64)	8 bytes

50% 감소. 100만 개 주문이면 8MB 절약입니다.

해시 연산

구조체 방식:

// 두 번의 해시 연산
self.venue.hash(state);
self.order_id.hash(state);

비트 패킹 방식:

// 한 번의 해시 연산
self.0.hash(state);

u64 하나의 해시는 대부분의 해시 함수에서 단일 연산입니다.

캐시 효율

이전 글에서 캐시 라인이 64바이트라고 했습니다.

방식	크기	캐시 라인당 개수
구조체	16 bytes	4개
비트 패킹	8 bytes	8개

같은 캐시 라인에 두 배 많은 주문 ID를 담을 수 있습니다.

---

결론

비트 패킹은 단순한 기법인데 효과가 꽤 좋습니다:

1. 메모리 50% 절약 (16 → 8 bytes)
2. 해시 연산 단순화 (2회 → 1회)
3. 캐시 효율 2배 (라인당 4개 → 8개)

이전 글에서 “병목은 메모리 이동에서 발생한다”고 했습니다. 데이터를 작게 만들면 더 많은 데이터가 캐시에 들어가고, 메모리 접근 횟수가 줄어듭니다.

---