Rust struct는 단순하고 빠르지만, 수백 개의 NULL 가능 SQL 컬럼을 rkyv로 직렬화할 때는 Option 오버헤드가 병목이 될 수 있다. 비트맵과 (필요 시) 희소 레이아웃으로 직렬화 형식을 바꿔 행 크기와 디스크 I/O를 크게 줄인 사례를 다룬다.
몇몇 변수가 함께 묶여야 할 때 우리는 그것들을 struct에 넣습니다. 프로그래머는 대개 별 생각 없이 자동으로 그렇게 하죠.
그리고 대부분의 경우 그 선택이 옳습니다.
Struct는 단순하고, 빠르고, 예측 가능합니다. 하지만 가끔은 그 전제가 무너집니다. 이것은 그런 사례 중 하나에 대한 이야기입니다.
우리 고객 중 한 곳에서 이상한 성능 문제를 보고했습니다. 새로운 유스케이스는 기존 파이프라인과 비슷한 양의 데이터를 처리했는데, 훨씬 더 느리게 실행되었습니다.
그건 흔치 않은 일이었습니다. 우리 엔진은 보통 고객이 보내는 데이터를 충분히 따라잡습니다. 그래서 더 자세히 들여다볼 필요가 있다고 느꼈습니다.
Feldera에서는 사용자가 입력 데이터를 SQL 테이블로, 출력 데이터를 SQL 뷰로 정의합니다. 우리는 그 사이의 SQL을 컴파일해서 쿼리를 증분(incremental) 평가하는 Rust 프로그램으로 만듭니다.
테이블의 각 행은 Rust struct가 됩니다.
다음은 성능 저하를 유발한 워크로드에서 발췌한 (익명화된) 예시입니다:
create table user (
anon0 boolean NULL,
anon1 boolean NULL,
anon2 boolean NULL,
anon3 boolean NULL,
anon4 VARCHAR NULL,
anon5 VARCHAR NULL,
anon6 VARCHAR NULL,
anon7 INT NULL,
anon8 SHOPPING_CART NULL,
anon9 BOOLEAN NULL,
anon10 BOOLEAN NULL,
anon11 BOOLEAN NULL,
anon12 VARCHAR NULL,
anon13 VARCHAR NULL,
anon14 VARCHAR NULL,
anon15 VARCHAR NULL,
anon16 VARCHAR NULL,
anon17 VARCHAR NULL,
anon18 VARCHAR NULL,
anon10 VARCHAR NULL,
anon11 VARCHAR NULL,
# ...
# the list goes on and on...
# ...
anon715 VARCHAR NULL,
우리 SQL 컴파일러는 이를 Rust struct로 변환합니다:
#[derive(Clone, Debug, Eq, PartialEq, Default, PartialOrd, Ord)]
pub struct struct_832943b1fac84177 {
field0: Option<bool>,
field1: Option<bool>,
field2: Option<bool>,
field3: Option<bool>,
field4: Option<SqlString>,
field5: Option<SqlString>,
field6: Option<SqlString>,
field7: Option<i32>,
field8: Option<struct_1b1bf3264e30bced>,
field9: Option<bool>,
field10: Option<bool>,
field11: Option<bool>,
field12: Option<SqlString>,
// ...
// the list goes on and on...
// ...
field715: Option<SqlString>,
이 struct는 수백 개의 필드를 가지며, 그 대부분이 optional입니다.
이는 SQL에서 바로 온 것입니다. NULL 가능 컬럼은 Rust에서 Option<T>가 됩니다.
즉 이 워크로드는 수백 개의 optional 필드를 가진 행을 만들어 냈습니다.
(처음 8개 필드만 있는) 더 작은 버전의 struct 메모리 레이아웃을 살펴봅시다.
저는 memoffset 크레이트를 사용해 레이아웃을 덤프했습니다:
(size=40B, align=8)
Offset
0x00 ┌──────────────────────────────────────────────┐
│ field7: Option<i32> │
│ size 8, align 4 │
│ bytes: [discriminant + i32 (+ padding)] │
0x08 ├──────────────────────────────────────────────┤
│ field4: Option<SqlString> (8B) │
│ SqlString is 8B (ArcStr pointer) │
0x10 ├──────────────────────────────────────────────┤
│ field5: Option<SqlString> (8B) │
0x18 ├──────────────────────────────────────────────┤
│ field6: Option<SqlString> (8B) │
0x20 ├──────────────────────────────────────────────┤
│ field0: Option<bool> (1B) │
0x21 ├──────────────────────────────────────────────┤
│ field1: Option<bool> (1B) │
0x22 ├──────────────────────────────────────────────┤
│ field2: Option<bool> (1B) │
0x23 ├──────────────────────────────────────────────┤
│ field3: Option<bool> (1B) │
0x24 ├──────────────────────────────────────────────┤
│ padding (4B) rounds total size to mult. of 8 │
0x28 └──────────────────────────────────────────────┘
몇 가지가 눈에 띕니다:
Option<bool>과 Option<SqlString>은 사실상 공짜입니다. Rust는 니치(niche) 최적화를 사용해 추가 공간 없이 None을 인코딩합니다. 예를 들어 SqlString은 ArcStr 포인터인데, Rust는(NonNull을 통해) 이것이 절대 null이 아님을 보장합니다.Option<i32>, 패킹되지 않은 Option<bool> 값들, 그리고 끝의 패딩에서만 옵니다.전반적으로 이 레이아웃은 이미 꽤 효율적입니다. Option이 여러 개 있어도 struct는 40바이트밖에 되지 않습니다.
따라서 메모리 내 표현은 문제가 아닙니다.
Feldera는 거의 항상 메모리에 다 들어가지 않는 데이터셋에 사용됩니다.
그래서 이 struct들은 결국 디스크에 기록됩니다.
즉, 이를 직렬화해야 합니다.
우리는 Rust의 제로-카피 직렬화 프레임워크인 rkyv를 사용합니다. rkyv에서는 보통 몇 개의 derive 매크로만으로 직렬화를 끝낼 수 있습니다:
#[derive(Debug, rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)]
pub struct struct_832943b1fac84177 {
field0: Option<bool>,
field1: Option<bool>,
field2: Option<bool>,
field3: Option<bool>,
field4: Option<SqlString>,
field5: Option<SqlString>,
field6: Option<SqlString>,
field7: Option<i32>
}
내부적으로 rkyv는 struct의 아카이브(archived) 표현을 생성합니다.
확장된 코드(cargo expand)를 살펴보면 대략 다음과 같은 것을 찾게 됩니다:
/// An archived [`struct_832943b1fac84177`]
pub struct Archivedstruct_832943b1fac84177 {
/// The archived counterpart of [`struct_832943b1fac84177::field0`]
field0: rkyv::option::Option<bool>,
/// The archived counterpart of [`struct_832943b1fac84177::field1`]
field1: rkyv::option::Option<bool>,
/// The archived counterpart of [`struct_832943b1fac84177::field2`]
field2: rkyv::option::Option<bool>,
/// The archived counterpart of [`struct_832943b1fac84177::field3`]
field3: rkyv::option::Option<bool>,
/// The archived counterpart of [`struct_832943b1fac84177::field4`]
field4: rkyv::option::Option<rkyv::string::ArchivedString>,
/// The archived counterpart of [`struct_832943b1fac84177::field5`]
field5: rkyv::option::Option<rkyv::string::ArchivedString>,
/// The archived counterpart of [`struct_832943b1fac84177::field6`]
field6: rkyv::option::Option<rkyv::string::ArchivedString>,
/// The archived counterpart of [`struct_832943b1fac84177::field7`]
field7: rkyv::option::Option<i32>
}
여기서는 몇 가지 일이 벌어집니다:
Archived 대응 타입을 갖습니다.지금까지는 모두 합리적으로 보이지만, 여기서부터 일이 꼬이기 시작합니다.
ArchivedString이 어떻게 구현되어 있는지 보면 대략 이런 형태입니다:
static const INLINE_CAPACITY: usize = 15;
#[derive(Clone, Copy)]
#[repr(C)]
struct InlineRepr {
bytes: [u8; INLINE_CAPACITY],
len: u8,
}
/// An archived string representation that can inline short strings.
pub union ArchivedStringRepr {
out_of_line: OutOfLineRepr,
inline: InlineRepr,
}
이 레이아웃은 영리합니다. 짧은 문자열을 인라인으로 저장해 할당을 피합니다.
하지만 중요한 Rust 최적화를 깨뜨립니다.
앞서 Option<T>는 때때로 니치 값(예: null 포인터)을 사용해 추가 공간 없이 None을 저장할 수 있다고 했습니다. 그런데 ArchivedString에는 더 이상 그런 니치가 없습니다. 인라인 표현이 전체 버퍼를 사용하기 때문에 이제 모든 바이트 패턴이 유효해집니다.
즉 Option<ArchivedString>은 명시적인 판별자(discriminant)를 저장해야 합니다.
그래서 Option이 더 이상 공짜가 아닙니다.
앞에서 본 struct에는 700개가 넘는 optional 필드가 있었습니다.
Rust에서는 이런 struct를 설계하지 않을 것입니다. Option이 700개에 이르기 훨씬 전에 다른 레이아웃을 선택했을 겁니다.
하지만 SQL 스키마는 종종 이런 모습입니다. 컬럼은 기본적으로 NULL 가능이고, 폭이 넓은 테이블도 흔합니다.
문제는 이를 직렬화할 때 드러납니다. 다음은 앞서 보았던 8개 필드짜리 작은 struct의 아카이브 레이아웃입니다:
• struct_...::Archived (rkyv size_64)
(size=88B, align=8)
Offset
0x00 ┌──────────────────────────────────────────────┐
│ field4: Archived<Option<SqlString>> │
│ size: 24B │
| (16 bytes SqlString, 8 bytes Option) │
0x18 ├──────────────────────────────────────────────┤
│ field5: Archived<Option<SqlString>> │
│ size: 24B │
0x30 ├──────────────────────────────────────────────┤
│ field6: Archived<Option<SqlString>> │
│ size: 24B │
0x48 ├──────────────────────────────────────────────┤
│ field7: Archived<Option<i32>> │
│ size: 8B │
0x50 ├──────────────────────────────────────────────┤
│ field0: Archived<Option<bool>> │
│ size: 2B │
0x52 ├──────────────────────────────────────────────┤
│ field1: Archived<Option<bool>> │
│ size: 2B │
0x54 ├──────────────────────────────────────────────┤
│ field2: Archived<Option<bool>> │
│ size: 2B │
0x56 ├──────────────────────────────────────────────┤
│ field3: Archived<Option<bool>> │
│ size: 2B │
0x58 └──────────────────────────────────────────────┘
문자열을 보세요. 아카이브 문자열은 16바이트, Option 판별자는 8바이트입니다. 문자열이 비어 있든 값이 None이든 상관없이 말이죠.
그래서 아카이브된 struct는 88바이트가 됩니다. 메모리 내 버전은 40바이트였습니다. 2배 이상 커진 것입니다.
해결책은 간단합니다. Option<T>를 저장하는 대신, 어떤 필드가 None인지 기록하는 비트맵을 저장합니다.
직렬화 중 레이아웃은 다음과 같습니다:
| bitmap | values... |
비트맵의 각 비트는 하나의 필드에 대응합니다:
0 → 필드가 None
1 → 필드가 존재
행을 역직렬화할 때는 먼저 비트맵을 확인합니다.
0이면, 필드는 None입니다.1이면, 값을 읽고 Some(...)으로 감쌉니다.비트맵 트릭을 쓰려면 직렬화 중에 한 가지 질문에 답해야 합니다:
이 필드가 None인가?
쉽게 들리지만, 직렬화기는 어떤 타입 T에 대해 제네릭입니다.
Rust에는 리플렉션이 없어서, T가 Option인지 간단히 물어볼 수 없습니다.
다행히 우리는 이 struct에 등장하는 타입들을 통제할 수 있습니다.
그래서 작은 헬퍼 트레이트를 도입합니다:
pub trait NoneUtils {
type Inner;
fn is_none(&self) -> bool;
fn unwrap_or_self(&self) -> &Self::Inner;
fn from_inner(inner: Self::Inner) -> Self;
}
아이디어는 간단합니다: Option<T>와 T를 동일하게 취급합니다.
Option<T>는 None인지 여부를 노출하고, 내부 값에 접근할 수 있습니다:
impl<T> IsNone for Option<T> {
type Inner = T;
fn is_none(&self) -> bool {
self.is_none()
}
fn unwrap_or_self(&self) -> &Self::Inner {
self.as_ref()
.expect("IsNone::unwrap_or_self called on None")
}
fn from_inner(inner: Self::Inner) -> Self {
Some(inner)
}
}
그 외의 모든 타입은 항상 존재하는 것처럼 동작합니다:
impl<T> IsNone for T {
type Inner = T;
fn is_none(&self) -> bool {
false
}
fn unwrap_or_self(&self) -> &Self::Inner {
self
}
fn from_inner(inner: Self::Inner) -> Self {
inner
}
}
이 트레이트로 직렬화기는 모든 필드를 같은 방식으로 다룰 수 있습니다.
is_none()를 호출해 비트맵을 업데이트하고, 값이 존재한다면 unwrap_or_self()로 직렬화합니다.
이제 필요한 구성 요소 NoneUtils가 생겼습니다.
이것은 직렬화기가 어떤 필드에 대해서든 두 가지 질문을 하도록 해줍니다:
None인가?이는 struct의 직렬화 레이아웃을 바꾸기에 충분합니다.
직렬화를 위한 새로운 두 단계는 다음과 같습니다:
None인지 기록하는 비트맵을 쓴다.Option 래퍼 없이 직렬화한다.개념적으로 레이아웃은 이렇게 보입니다:
| bitmap | field0 | field1 | field2 | field3 | ... |
비트맵은 필드당 1비트를 저장합니다:
bit = 1 → value present
bit = 0 → value was None
필드 자체는 Option 없이 저장됩니다:
Option<T> → T
T → T
직렬화 중에는 value.unwrap_or_self()를 호출합니다.
이렇게 하면 아카이브 레이아웃에서 Option 오버헤드를 제거할 수 있습니다.
역직렬화는 이 과정을 반대로 수행합니다.
비트맵을 참조해 각 필드를 재구성합니다:
if bitmap[i] == 0
return None
else
read value
return Some(value)
다시 말해, NoneUtils가 T::from_inner(inner)를 통해 세부사항을 감춥니다.
이 모든 로직을 생성하는 코드는 매크로로 자동 생성됩니다.
Option을 제거한 레이아웃은 컴팩트하고, 단순하며, 캐시 친화적입니다.
하지만 여기에는 또 다른 기회가 있습니다. 모든 행이 항상 같은 모양을 갖지는 않습니다. 많은 필드가 NULL이라면, 모든 필드를 순차적으로 위한 공간을 예약하는 것은 낭비입니다. 이런 상황에서는 실제로 존재하는 값만 저장할 수 있습니다.
필드 타입은 크기가 서로 다를 수 있고 가변 길이도 있기 때문에, 오프셋을 미리 계산할 수는 없습니다.
그래서 희소(sparse) 레이아웃은 저장된 값들에 대한 상대 포인터 인덱스를 유지합니다:
| bitmap | ptrs | values... |
비트맵은 여전히 어떤 필드가 존재하는지 기록합니다. ptrs 벡터는 존재하는 각 필드에 대해 값 영역 안을 가리키는 상대 포인터를 담습니다. 필드를 읽을 때는 먼저 비트맵을 확인합니다. 비트가 설정되어 있으면 포인터를 사용해 아카이브된 값으로 직접 점프합니다.
이렇게 하면 NULL 필드를 완전히 건너뛰면서도 빠른 접근을 지원할 수 있습니다. optional 컬럼이 많은 폭 넓은 SQL 테이블에서는 행 크기를 극적으로 줄일 수 있습니다.
수백 개의 NULL 가능 컬럼이 있는 테이블에서는 이득이 누적됩니다. 이전에는 None이거나 빈 문자열인 경우에도 항상 24바이트를 소비했지만, 이제는 최선의 경우 단 1비트만 소비합니다.
이번 조사를 시작하게 만든 워크로드에서는 직렬화된 행 크기를 대략 2배 줄였습니다. 디스크 I/O도 그에 맞춰 감소했습니다. 처리량은 고객이 기대하던 수준으로 돌아왔습니다.
Rust struct는 훌륭합니다.
하지만 중요한 가정을 하나 합니다:
대부분의 필드는 존재한다.
SQL 테이블은 일반적으로 정반대의 가정을 합니다:
대부분의 필드는 존재하지 않을 수도 있다.
다음 세 가지를 결합하면:
평범한 struct 레이아웃의 오버헤드는 병목이 되기 시작합니다.
해결은 놀랄 만큼 단순했습니다. rkyv가 직렬화 프레임워크로서 여기에서 많은 유연성을 제공했기 때문에, 메모리 내 struct 인터페이스는 그대로 유지하면서 직렬화 형식만 바꿀 수 있었습니다. 이제는 행 단위로 최적의 표현(밀집 vs. 희소)을 선택합니다.
때로 최고의 최적화는 영리한 알고리즘이 아닙니다. 때로는 데이터의 형태를 바꾸는 것뿐입니다.