Rust로 상호작용형 Datalog 엔진을 직접 만들어 가며, 파싱과 사실 집합 표현, 규칙 계획·평가, 조인 구현, e-그래프 기반 최적화, 열 지향 레이어드 트라이로의 전환, 정렬·머지 가속, 메모리 사용량 절감, 그리고 향후 디스크 스필·스케일아웃·스트리밍·컴파일 특화까지 아우르는 실험과 설계를 정리합니다.
추모 기념일(Memorial Day) 연휴 동안 Kris Micinski가 뉴욕주 북부의 아름다운 Minnowbrook Conference Center에서 논리 프로그래밍 워크숍을 열었다. 나는, 악명 높은 말썽꾸러기, 오래된 업보의 심판을 받으러 가는 줄 반쯤은 확신한 채 초대되었다. 그런데 막상 가 보니 아주 훌륭했다. 목표를 공유하는 친절하고 든든한 사람들이 많았다.
요구 사항이 하나 있었는데, 행사에 대한 소회를 담은 블로그 글을 쓰라는 것이었고, Kris가 모아서 세상에 공유할 거라고 했다. 여러분은 이 워크숍에 대한 사려 깊고 세심한 글을 여러 편 보게 될 텐데, 그래서 나는 좀 다른 길을 가 보기로 했다. 시간이 매우 훌륭하긴 했지만, 전형적인 학계의 문제도 있었다: 똑똑한 사람들이 어려운 문제를 파고들지만, 당면 과제와 늘 직접 연결되지는 않는 것. 프로덕트 용어로는 결과물(outputs)은 나오는데 성과(outcomes)가 없다.
며칠간 Datalog(및 다른 논리 프로그래밍 언어) 발표를 들은 끝에, 가장 기억에 남은 건 마지막 발표였다. Denis Bueno가 ctdal에 대해 이야기했다. Datalog로 하는 프로그램 분석이다! 하지만 .. 듣는 게 참 고역이었다. 많은 도구가 작동하지 않았고; Soufflé는 그나마 되었지만 제대로 다뤄야 한다. 난관이 많았고, 솔직히 말해 발전을 원한다면 나쁜 소식이 곧 최고의 소식이다.
말로만 떠들지 말고 시간을 투자해, ‘사용 가능’하면서도 “빠른” 것을 만들면 어떤지 체험해 보기로 했다. 게다가, 다 같이 그런 걸 만드는 과정을 보는 것도 유익하고, 논리 프로그래밍도 배울 수 있다!
내가 그동안 Datalog 같은 걸 몇 번 만들어 보긴 했지만, ‘단순하면서, 쓰기 쉽고, 빠른’ 이 세 가지를 동시에 목표로 해 본 적은 별로 없다. 여기서 그걸 해 보자, Datalog로! datatoad 저장소에서 따라올 수 있다.
예전에 datafrog의 많은 부분을 만들었다(도움도 받았다). datafrog는 Datalog 엔진의 핵심을 제공하고, 남은 배선은 각자 알아서 하라는 식이다. 당연히, 당신이 상상한 Datalog 르네상스는 일어나지 않았다. 우리는 datafrog에서 시작하지는 않겠지만, 그와 같은 알고리즘 아이디어를 많이 쓸 것이다. 익숙하다면 잘 따라올 수 있을 것이다. 익숙하지 않더라도 괜찮다.
처음엔 느리고 어설픈 Datalog, 즉 엉성한 버전을 먼저 만들고, 같이 고쳐 가며 배우자는 개요를 잡아 놨다. 그런데 그게 너무 구려서, 그냥 좋은 버전부터 시작하고, 중요한 설계 지점(load-bearing moments)을 자세히 짚어가며 설명하기로 했다.
이 글을 다 읽을 즈음에는, 사실들을 대량 적재하고, 중간에 규칙을 추가하고, 꽤 준수한 성능으로 따라가는 인터랙티브 Datalog을 갖게 될 것이다. 다음은 httpd 데이터플로(PL의 의미에서) 그래프에 대해 nullability 분석을 수행한 예다.
> .list
e: 9905624
n: 138331
30.708µs
> m(?b, ?a) :- n(?a, ?b) .
52.027834ms
> .list
e: 9905624
m: 138331
n: 138331
45.916µs
> m(?c, ?a) :- m(?b, ?a), e(?b, ?c) .
8.360353834s
> .list
e: 9905624
m: 9393283
n: 138331
49.042µs
>
이건 datafrog에서는 약 2초가 걸리지만, 여기서는 8.3초다. 다만 datafrog 예제는 (u32, u32) 데이터이고, 여기서는 Vec<String> 데이터에 컴파일된 쿼리 없이 돌렸으니 4배 느린 정도다. 미래에는 더 줄이고 싶다.
아직 모든 문제에서 훌륭한 성능을 낸다고 확인하진 않았다. 일반적으로 올바른지조차 확인하지 않았다. 그래도 이런 도달성(reachability) 문제에서는 datafrog 구현과 동일한 출력 튜플 수를 낸다. 그래서 당장은 성능보다는, 사용성, 설명 가능성, 확장성에 더 신경 쓰겠다.
전체 계획을 개괄하겠다. 아직 전부 구현한 건 아니지만, 높은 희망을 품고 있다! 많은 내용이 datafrog에서 왔지만, 더 천천히, 더 깊게 시작하고, 더 멀리까지 가 보자.
계획은 톱다운이다. “Datalog란 무엇인가”에서 시작해, 인터랙티브 평가기의 프레임을 만들자.
그다음, 현재 세 개의 기능 축을 순서대로 만든다.
자연스러운 다음 단계도 몇 가지 있다. 아직 하진 않았지만, 크게 어렵지 않게 할 수 있다고 확신한다. 여기 적어 둔다. 당신이 특히 기대하고 있는데 내가 어째서인지 아직 안 했다면, 이 문단을 근거로 날 독촉해도 좋다.
아울러, 데이터 병렬 계산 패턴을 실험해 보려는 의도도 있다. 우리가 하려는 대부분은 differential dataflow와 기계적으로 매우 비슷하지만, 훨씬 단순하고(그리고 덜 강력하다).
Datalog은 간단한 논리 규칙을 서술하면, 그로부터 도달 가능한 모든 결론을 유도하는 언어다. 각 규칙은 Horn 절인데, 이는 입력 사실들을 받아 출력 사실을 내는 규칙을 차가운 말로 표현한 것이다. 이러한 논리식에는 자리표시자 변수들이 있고, Datalog의 묘미는 가능한 모든 변수 치환을 자동으로 채워 준다는 점이다.
Datalog 규칙은 “머리(head)”와 “몸체(body)”로 구성된다. 머리는 유도될 수 있는 것(들), 몸체는 충분조건들의 목록이며, :-로 구분한다. 예를 들어, 삼각형(a,b,c)이 존재하려면 세 변이 모두 있어야 한다는 규칙을 다음처럼 쓸 수 있다.
tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
tri와 edge는 관계(relation) 이름이고, a, b, c는 자유 변수다. 규칙은 묵시적으로 전칭 한정돼 있어서, 변수의 어떤 치환에 대해서든, 몸체가 참이면 머리도 참이다. 우리는 머리의 원자(atom)에 등장하는 모든 변수가 몸체에도 등장하도록 제한한다.
Datalog를 쓸 때 종종 잊지만, “사실(fact)”도 있다. 사실은 빈 몸체를 갖는 규칙, 즉 무조건 참인 명제다. 예를 들어, 다음 세 변이 존재한다는 사실을 다음처럼 적을 수 있다.
edge(1, 2) :- .
edge(1, 3) :- .
edge(2, 3) :- .
아래처럼 “다중 머리” 문법으로도 쓸 수 있다.
edge(1, 2), edge(1, 3), edge(2, 3) :- .
규칙과 사실이 합쳐지면, 더 많은 사실이 유도된다. 위 사실들로부터 tri(1, 2, 3)이 참임을 유도할 수 있다. 이는 다시 사실이 되고, tri에 의존하는 다른 규칙이 있다면 추가 사실을 이끌 수도 있다.
Datalog에는 매력적인 단조성(monotonicity)이 있다. 규칙(사실 포함)을 더 추가할수록 참인 것들의 집합은 감소하지 않는다. 게다가, 어떤 순서로 규칙을 적용하든 동일한 사실 집합에 도달하는 수렴성(confluence)도 갖는다.
이쯤에서, Datalog 셸에 규칙을 한 줄 한 줄 타이핑하고, 그 결과가 쏟아져 나오는 모습을 떠올릴 수 있기를 바란다. 그리고 곧바로, 너무 빨리 쏟아져 나와서 화면으로 보기보단 파일로 읽고 쓰고 싶어지고, 각종 실전(또는 최소 그럴싸한) 응용에 쓰고 싶어진다면 더없이 좋겠다.
규칙부터 시작하자. 사실은 결국 규칙의 특수한 형태라 다르게 다룰 것이다.
규칙은 _원자(atom)_의 리스트 두 개다. :- 앞이 머리, 뒤가 몸체다. 몸체의 모든 원자가 참이면, 머리의 원자들도 참이어야 한다.
struct Rule {
head: Vec<Atom>,
body: Vec<Atom>,
}
원자는 이름이 있는 관계와, 관계의 자리수(arity)에 맞는 수의 _항(term)_으로 이뤄진다.
struct Atom {
name: String,
terms: Vec<Term>,
}
각 항은 이름이 있는 변수이거나, 단순화를 위해 문자열 리터럴이다.
enum Term {
Var(String),
Lit(String),
}
문자열 리터럴이어야만 하는 강한 이유는 없다. 어떤 타입도 가능하고, 보통 사람들은 정수나 압축 타입을 쓴다. 사실, 이건 새빨간 거짓말이고 실제로는 타입으로 Vec<u8>을 쓸 것이다. 그 바이트들이 String인지 (u32,u32)인지 다른 무엇인지는 각자 원하면 그렇게 해도 된다. 우리가 쓰는 성질은 리터럴 동등성과 임의의 순서뿐이라, Vec<u8>을 쓰면 향후 선택지를 닫지 않는다.
사실은 빈 몸체와 머리에 변수 없는 규칙이다. 사실은 데이터로 다룰 수 있고, 각 위치의 리터럴 문자열 목록을 기록하면 된다. 최종 형태는 아니지만, 일단은 이렇게 생각하자.
type Fact = Vec<String>;
또한 사실들의 리스트를 모아 이름과 연결해, 관계의 표현으로 사용할 것이다. 역시 최종 형태는 아니지만 직관에 좋다.
type Facts = BTreeMap<String, Vec<Fact>>;
마지막으로, 사실과 규칙을 묶어 Datalog 인터프리터의 상태로 만든다.
struct State {
/// 사실이 아닌 규칙.
rules: Vec<Rule>,
/// 빈 몸체와 머리에 리터럴만 있는 규칙(=사실).
facts: facts::Facts, // 아직 자세히 공개하지 않음
}
다음은, 이걸로 뭘 어떻게 하는지다.
인터랙티브 Datalog 셸의 뼈대를 간단히 작성한다. State를 만들고, 입력에서 규칙을 반복적으로 읽어서 적용해, 새로운 사실이 없을 때까지 유도를 반복한다. 규칙 대신 이름을 입력하면, 그 이름의 관계를 출력한다.
코드는 State의 아직 정의하지 않은 몇 가지 메서드를 쓴다. 이들은 다음 섹션들에서 풀어 보겠다.
fn main() {
let mut state = State::default();
use std::io::Write;
println!("");
print!("> ");
let _ = std::io::stdout().flush();
let mut text = String::new();
while let Ok(_size) = std::io::stdin().read_line(&mut text) {
if let Some(parsed) = parse::datalog(&text) {
state.extend(parsed);
state.update();
}
else {
match text.trim() {
".list" => {
for (name, facts) in state.facts.iter() {
println!("\t{}:\t{:?}", name, facts.len());
}
}
_ => {
println!("Parse failure: {:?}", text);
}
}
}
println!("");
print!("> ");
let _ = std::io::stdout().flush();
text.clear();
}
}
여기에는 아직 보지 못한 세 메서드가 있다: parse::datalog, State::extend, State::update. Datalog 파싱은 텍스트 줄에서 규칙 리스트로 가는 자급자족 부분이다. 다음 섹션에서 다룬다. 그 전에, extend 메서드를 보고, Datalog의 심장인 update에 대해 이야기하자.
impl State {
extend는 주로 사실을 찾는다. 머리에 리터럴만 있고, 몸체가 빈 규칙이 사실이다. 우리는 이를 머리 원자(관계 이름) 아래 데이터의 리스트로 명시적으로 저장한다.
/// 새 규칙들을 상태에 추가.
pub fn extend(&mut self, rules: impl IntoIterator<Item=Rule>) {
for rule in rules.into_iter() { self.push(rule); }
}
/// 새 규칙 하나를 상태에 추가.
pub fn push(&mut self, rule: Rule) {
if rule.body.is_empty() {
for atom in rule.head.iter() {
let mut lits = Vec::with_capacity(atom.terms.len());
for term in atom.terms.iter() {
if let Term::Lit(text) = term {
lits.push(text.to_string().into_bytes());
}
else { continue; }
}
let mut builder = facts::FactBuilder::default();
builder.push(lits);
self.facts
.entry(atom.name.to_owned())
.or_default()
.add_set(builder);
}
}
else {
let rule_plan = crate::join::JoinPlan::from(&rule);
join::implement_plan(&rule, &rule_plan, self.rules.len(), true, &mut self.facts);
self.rules.push(rule);
}
}
}
여기 join:: 네임스페이스가 보일 것이다. 조금만 참자. 새 규칙이 나타났을 때 유도를 시작하기 위해 필요한 단계다. 지금은 “그 새 규칙의 유도를 시작하라” 정도로 읽어도 된다.
update는 Datalog의 심장이다. 새로운 사실이 산출되는 동안 반복적으로 유도하고, 더 이상 새로운 사실이 나오지 않으면 멈춘다. 다시 시도한다고 더 나오지는 않으니, 일단 이 시점에선 끝이다.
/// 모든 규칙을 모든 사실에 적용하고, 새 사실이 있는 동안 반복
pub fn update(&mut self) {
self.advance();
while self.active() {
for (index, rule) in self.rules.iter().enumerate() {
let rule_plan = crate::join::JoinPlan::from(rule);
join::implement_plan(rule, &rule_plan, index, false, &mut self.facts);
}
self.advance();
}
}
여기엔 우리가 배운 내용을 한 단계 진전시키는 보조 메서드가 있다. 대략적으로, active는 처리할 새 사실이 남았는지 알려주고, advance는 새 사실을 옛 사실과 비교하여 새로움(novelty)을 체크하고 다음 라운드를 준비한다.
/// 어떤 관계든 새 사실이 있으면 true
fn active(&self) -> bool {
self.facts
.values()
.any(|x| x.active())
}
/// 새 사실을 옛 사실과 비교
pub fn advance(&mut self) {
for facts in self.facts.values_mut() {
facts.advance();
}
}
사실, facts.advance() 안에는 많은 비밀이 숨겨져 있다. 사실 집합을 어떻게 표현할지 더 풀어본 뒤에 다루겠다. 그 전에, Datalog 파싱으로 잠깐 새주제(sɪɡweɪ) 하자.
Datalog 파서를 작성하겠다. 학부 때 렉싱/파싱 수업을 들었는지 기억이 안 나서, 텍스트 줄에서 Datalog 규칙을 뽑아내는 가장 좋은 방법은 아닐 것이다.
이후 코드는 현재 프로젝트의 parse.rs에 있다.
여기서 실제 문법을 공개한다. Soufflé에서 가져왔다. 특히, 변수는 리터럴과 구분하기 위해 ?로 시작한다. 개인적으로는 반대로 따옴표 "로 문자열 리터럴을 표시하는 편을 선호할 수도 있겠지만, Soufflé를 따라가는 편이 다들 편할 듯했다.
대부분의 파서는 첫 단계로 “토크나이징”을 한다. 문자 시퀀스를 더 의미 있는 기호 시퀀스로 바꾸는 일이다.
Datalog에서는 중요한 토큰이 몇 개뿐이다: ., ,, (, ), :-, ?(변수와 리터럴 구분). 이 외의 모든 것은 문자열 토큰으로, 원자나 항의 이름을 가리킨다.
/// 텍스트를 토큰 시퀀스로 변환
#[derive(Debug, PartialEq)]
enum Token {
Period,
Comma,
LParen,
RParen,
Turnstile,
Question,
Text(String),
}
부정(negation)을 추가할 때 Exclamation이 필요할 것이다. 오늘은 아니다!
내가 쓴 토크나이저는 모든 공백을 제거하고, :-을 ←로 바꿔 단일 기호로 스캔하기 쉽게 했다. 더 야심찬 분들은 더 좋은 방법을 찾아볼 수 있다.
fn tokenize(text: &str) -> Option<Vec<Token>> {
let mut text = text.replace(":-", "←");
text.retain(|c| !c.is_whitespace());
let mut result = Vec::new();
let pattern = ['.', ',', '(', ')', '←', '?'];
for token in text.split_inclusive(&pattern) {
let mut split = token.split(&pattern);
let prev = split.next().unwrap();
if !prev.is_empty() {
result.push(Token::Text(prev.to_owned()));
}
let next = token.chars().rev().next().unwrap();
result.push (
match next {
'.' => Token::Period,
',' => Token::Comma,
'(' => Token::LParen,
')' => Token::RParen,
'←' => Token::Turnstile,
'?' => Token::Question,
_ => { None? }
}
);
}
Some(result)
}
보다시피, 기호의 핵심 위치를 찾고 토큰으로 쪼개는 데 소소한 무리수가 있다. Rust에게 이 위치를 보여 달라고 설득하는 과정이 어려웠다. 게다가 기호를 소비하지 않으면서 말이다. 더 나은 구현이 가능할 것이다.
토큰 시퀀스를 파싱하면서, 다음 토큰을 들춰보고, 그에 따라 규칙/원자/항을 차례로 추출한다.
fn parse(tokens: Vec<Token>) -> Option<Vec<Rule>> {
let mut tokens = tokens.into_iter().peekable();
let mut rules = Vec::new();
while tokens.len() > 0 {
rules.push(parse_rule(&mut tokens)?);
}
Some(rules)
}
규칙 파싱은 :- 전까지 원자를 추출하고, 그다음 . 전까지 원자를 추출한다.
fn parse_rule<I: Iterator<Item=Token>>(tokens: &mut Peekable<I>) -> Option<Rule> {
let mut head = Vec::new();
while &Token::Turnstile != tokens.peek()? {
if &Token::Comma == tokens.peek()? { tokens.next(); }
head.push(parse_atom(tokens)?);
}
let Token::Turnstile = tokens.next()? else { None? };
let mut body = Vec::new();
while &Token::Period != tokens.peek()? {
if &Token::Comma == tokens.peek()? { tokens.next(); }
body.push(parse_atom(tokens)?);
}
let Token::Period = tokens.next()? else { None? };
Some(Rule { head, body })
}
원자 파싱은 이름과 왼쪽 괄호 (, 쉼표가 있는 동안 항을 추출하고, 마지막에 오른쪽 괄호 )를 기대한다.
fn parse_atom<I: Iterator<Item=Token>>(tokens: &mut Peekable<I>) -> Option<Atom> {
let Token::Text(name) = tokens.next()? else { None? };
let Token::LParen = tokens.next()? else { None? };
let mut cols = Vec::new();
cols.push(parse_term(tokens)?);
while let Token::Comma = tokens.peek()? {
tokens.next();
cols.push(parse_term(tokens)?);
}
let Token::RParen = tokens.next()? else { None? };
Some(Atom { name: name.to_owned(), cols })
}
항 파싱은 선택적 물음표를 체크하고, 그다음 텍스트 이름을 기대한다.
fn parse_term<I: Iterator<Item=Token>>(tokens: &mut Peekable<I>) -> Option<Term> {
if let Token::Question = tokens.peek()? {
tokens.next()?;
let Token::Text(term) = tokens.next()? else { None? };
Some(Term::Var(term.clone()))
}
else {
let Token::Text(term) = tokens.next()? else { None? };
Some(Term::Lit(term.clone()))
}
}
잘못된 규칙은 None을 반환한다. 무엇이 잘못됐는지 친절하게 알려주려는 큰 노력은 하지 않았다. 이쯤 되면 예상했겠지만, 더 잘 만들 수도 있었다.
앞서 사실을 Vec<String>이라 했고, 사실의 집합은 Vec<Fact>라고 했다. 완전히 정확하진 않았다.
문제는 Vec<Vec<String>>이 메모리 관리의 악몽이라는 점이다. 할당 위에 할당 위에 또 할당. 메모리가 사방에 .. 퍼진다. 지금 보고 있는 곳이 아닌 곳에. 같은 정보를 담지만 다른 물리적 표현을 쓰자.
이 섹션은 프로젝트의 facts.rs에 해당한다.
프로젝트에는 지금 외부 의존이 하나 있다: columnar. Rust 타입(예: Vec<Fact>)을 소수의 선형 할당으로 평평하게(flat) 바꿔 주는 크레이트다. 대략적으로 모든 문자열을 하나의 거대한 Vec<u8>에 몰아넣고, String 경계를 잡는 오프셋들의 리스트, 그리고 다시 Fact 경계를 잡는 오프셋들을 기록한다. 그런데 이걸 마법의 주문 하나로 다 해 준다.
<Fact as Columnar>::Container
이 타입으로 사실 집합을 표현하겠다. 너무 좋아서 이름도 붙였다.
/// 정렬된 중복 없는 사실의 리스트
struct FactContainer {
ordered: <Fact as Columnar>::Container,
}
impl std::ops::Deref for FactContainer {
type Target = <Fact as Columnar>::Container;
fn deref(&self) -> &Self::Target {
&self.ordered
}
}
Rust의 “래퍼 타입” 관용을 따른다. FactContainer는 사실 리스트를 싸고 있지만, 그 시퀀스가 정렬되어 있고 중복이 제거됐음을 나타낸다. 우리가 이것을 받을 때는 이 성질이 보장된다(물론 조심해서 만들어야 한다. 구현은 곧 본다).
columnar 컨테이너의 큰 단점은 기본적으로 append-only라는 점이다. 원칙적으로는 Vec으로 리스트 중간의 사실을 바꾸거나, 그 안의 문자열 리터럴을 바꿀 수 있지만, 우리는 그런 걸 원하지 않으니 대체로 괜찮다.
원하는 한 가지는, 리스트에 사실을 추가하는 일이다. 정렬과 중복 제거를 유지해야 한다면 문제가 있다. 리스트를 바꾸는 건 append 외에는 불가능하고, append는 정렬을 망칠 수 있다. 따라서 FactContainer와는 다른 누적 기법이 필요하다.
로그 구조적 머지 트리(LSM-tree)로 사실 집합을 표현하겠다. 복잡해 보일 수 있지만, 정말로 “FactContainer들의 리스트”라는 뜻이다.
/// 길이가 2배씩 증가하는 사실 집합의 리스트
#[derive(Clone, Default)]
pub struct FactLSM {
pub layers: Vec<FactContainer>,
}
LSM의 핵심 성질은 ‘레이어’의 크기가 기하급수적으로 커진다는 점이다. 사실을 추가하려면 FactContainer를 리스트에 넣고, 리스트를 정돈한다. 즉, 길이가 서로 2배 이내인 레이어들을 머지한다. 다음은 그 하나의 방법이다.
impl FactLSM {
/// 레이어를 추가하고 불변식을 복원
fn push(&mut self, layer: FactContainer) {
self.layers.push(layer);
self.tidy();
}
/// 레이어들이 2배씩 증가하도록 보장
fn tidy(&mut self) {
self.layers.sort_by_key(|x| x.len());
self.layers.reverse();
while let Some(pos) = (1..self.layers.len()).position(|i| self.layers[i-1].len() < 2 * self.layers[i].len()) {
while self.layers.len() > pos + 1 {
let x = self.layers.pop().unwrap();
let y = self.layers.pop().unwrap();
self.layers.push(x.merge(y));
self.layers.sort_by_key(|x| x.len());
self.layers.reverse();
}
}
}
}
여기서 FactContainer::merge는 두 정렬된 중복 없는 사실 리스트를 받아, 같은 성질을 지닌 하나의 리스트로 합친다.
LSM은, 최종 형태가 당장 필요하지 않을 때 사실 집합을 유지하기에 편리하다. 결국엔 모든 레이어를 하나의 FactContainer로 합쳐야겠지만, 준비가 될 때까지 미룰 수 있다. 너무 유용한 관용이라, 빌드 작업을 도와줄 헬퍼 타입도 도입하겠다.
/// 사실 집합을 모으는 중간 단계
pub struct FactBuilder {
/// 정렬되지 않았고 중복될 수 있는 사실
active: <Fact as Columnar>::Container,
/// 정렬되고 중복 없는 사실
layers: FactLSM,
}
이 타입은 active 공간에 어지러운 사실을 모아 두다가, 수가 많아지면 FactContainer로 바꿔 layers에 넣는다.
사실의 “라이프사이클”을 반영하기 위해, 새로 왔지만 중복이 있을 수 있는 사실, 최근의(새롭고) 독특한 사실, 완전히 처리된 사실, 이렇게 세 컬렉션을 두자. .. 음 .. 셋 중 둘은 LSM이고 셋째는 아니다.
pub struct FactSet {
/// 새로 도착했지만 새로움이 확정되지 않은 사실
pub to_add: FactLSM,
/// 중복 제거된, 처리해야 할 사실
pub recent: FactContainer,
/// 중복 제거된, 완전히 처리된 사실
pub stable: FactLSM,
}
사실, FactSet::advance가 아까 처음 섹션에서 빠져 있던 기능 중 하나다. 새 사실의 중복을 제거하고 “다시 갈 준비”를 시켜 준다고 했다. 실제로 무엇을 하는지 보자.
/// recent를 stable로 옮기고, 그다음 to_add를 recent로 이동
pub fn advance(&mut self) {
// recent를 stable로 이동
if !self.recent.is_empty() {
self.stable.push(std::mem::take(&mut self.recent));
}
// LSM을 하나의 사실 리스트로 변환
if let Some(to_add) = self.to_add.flatten() {
// 곧 할 작업을 위해 stable 정리
self.stable.tidy_through(2 * to_add.len());
// to_add에서 이미 stable에 있는 사실 제거
let mut starts = vec![0; self.stable.layers.len()];
let stable = &self.stable;
self.recent = to_add.filter(move |x| {
starts.iter_mut().zip(&stable.layers).all(|(start, layer)| {
crate::join::gallop::<Fact>(layer.borrow(), start, |y| y < x);
*start >= layer.borrow().len() || layer.borrow().get(*start) != x
})
});
}
}
마지막 클로저는 엉망이고, 불평해도 된다. to_add의 각 원소가 stable LSM 어딘가에 있는지 체크한다. 읽기 힘들 뿐이다.
사실의 라이프사이클, 즉 to_add → recent → stable은, 새로운 사실만으로 새로운 사실을 유도하고, 기존 사실로 이미 한 작업은 반복하지 않도록 안내한다. 다음 섹션에서 그 방법을 본다.
마지막(드디어!) 단계로, 규칙과 사실에서 더 많은 사실로 가는 논리를 적자. 여기서 여러 임의처럼 보였던 선택이 합쳐진다. 동시에, Datalog 규칙이란 게 무엇인지 이해하려는 머리 싸움이 시작된다.
이 내용은 프로젝트의 join.rs에 있다.
tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
먼저 edge의 사실로 이 규칙을 적용해 보고 싶을 것이다. 처음엔 압도적으로 보일 수 있으나, 접근법이 몇 가지 있다.
첫째, ?a, ?b, ?c의 실제 리터럴 값 치환은 유한하다. 각 리터럴 값은 edge 사실들에서 온다. ?a는 첫 좌표에서, ?c는 두 번째 좌표에서 온다. 전부 시도해 보는 것도 가능하다. 많긴 하지만 무한하진 않다.
둘째, 가능한 모든 치환이 무한은 아니지만 너무 많으니 더 똑똑해야 한다. 한 번에 작은 덩어리를 잡자. 마지막 두 edge 제약을 만족하는 값 a, b, c를 먼저 찾자. 그걸 vee라 부르고, 규칙을 다음처럼 다시 쓰자.
vee(?a, ?b, ?c) :- edge(?b, ?c), edge(?a, ?c).
tri(?a, ?b, ?c) :- edge(?a, ?b), vee(?a, ?b, ?c).
마지막 두 개를 고른 건 완전히 임의다. 다만 머리 쪽으로 수렴하며 축약하는 코드가 더 낫다. 반대로 하고 싶다면, 규칙 파싱 직후에 body.reverse()를 호출해도 된다.
이제 몸체에 두 관계가 있는 규칙 둘이 생겼다. 이건 같은 결과를 낸다. 이제 몸체에 원자 두 개만 있는 경우를 생각하면 된다. 특히, vee의 리터럴 3-튜플을 찾자.
이건 관계형 데이터베이스에서 말하는 동등 조인(equijoin)이다. 두 관계가 있고, 특정 좌표들이 일치해야 한다. 모든 가능한 값 할당 중 그런 걸 찾자. ?c가 두 원자에 모두 등장한다는 점을 이용해, ?c에서 출발해 바깥으로 ?a와 ?b를 찾으면 된다.
두 관계에서 어떤 키 컬럼이 일치하는 사실을 찾는 방법은? 그 키 컬럼으로 정렬한 뒤, 병합(merge)하라! (우리가 사실을 정렬하는 이유다. 중복 제거에도 도움이 된다.)
계획은 오른쪽에서 왼쪽으로 몸체를 훑으면서, 마지막 두 관계를 조인으로 바꾸고, 그 결과를 리스트의 끝에 둔다. 두 관계만 남으면, 특화된 조인을 수행해 머리에 필요한 형태로 결과를 낸다. 시작부터 한 관계만 있다면, 조인을 건너뛰고 머리에 필요한 형태로 바꾼다.
필요한 구체 요소:
아래는 사용할 조인 계획의 형태다. 강조하지만 .. 매우 순진한 계획이다. 미래에는 더 멋진 계획을 하고 싶다. “우측 선형(right linear)” 조인 계획이며, 더 단순할 수 없다(왼쪽 선형도 있다). 단순하다고 해서 쉽다는 뜻은 아니다.
/// Datalog 규칙을 위한 선형 조인 계획 설명
///
/// 계획은 오른쪽에서 왼쪽으로 진행하며, 두 원자씩 조인해 2개 이하가 남을 때까지 진행한다.
/// 몸체 원자가 1개 또는 2개면, 각각:
/// 1. 단일 몸체 원자를 머리들에 매핑하거나,
/// 2. 두 몸체 원자를 조인하고 결과를 머리들에 매핑한다.
#[derive(Debug)]
pub struct JoinPlan {
/// 각 몸체 원자에 대해, 올바른 형태로 만들기 위한 선행 작업
bodys: Vec<Plan>,
/// 맨 왼쪽을 제외한 각 조인에 대해, 키 자리수와 출력에 적용할 프로젝션
///
/// 결과가 적절히 키로 정렬되고, 요구되는 바인딩을 전달해야 한다.
joins: Vec<(usize, Vec<usize>)>,
/// 각 머리 원자에 대해, 최종 조인에서 결과를 올바른 형태로 만드는 동작
///
/// `Ok(index)`는 복사할 좌표, `Err(lit)`은 복사할 리터럴을 뜻한다.
/// `joins`가 비어 있으면 최종 조인이 없고, 각 동작을 몸체 원자의 행에 적용한다.
heads: Vec<Vec<Result<usize, String>>>,
/// 최종 머리-생성 조인의 조인 키 자리수(있다면)
arity: Option<usize>,
}
어려운 단계는 1. Rule에서 이 조인 계획을 만들고, 2. 이 계획을 사용해 조인을 구현하는 것이다.
Rule에서 JoinPlan 만들기먼저, 각 변수에 대해 그 변수가 최초로 등장하는 원자, 마지막으로 등장하는 원자를 찾는다. 좌측(오른쪽→왼쪽 진행에서의 마지막) 등장 위치는, 해당 바인딩이 유지돼야 하는 마지막 순간을 뜻한다. 그 이후에는 버려도 된다. 우측(오른쪽에서의 첫) 등장 위치는 변수가 처음 등장하는 시점을 뜻하고, 이는 다른 몸체 원자가 이 변수를 언급할 때, 키 컬럼에 포함해야 하는지 판단하는 데 중요하다.
이 정보를 가지고, 각 몸체 원자는 자신의 변수들과 좌/우 등장 정보를 보며 컬럼을 다음처럼 분류한다.
비슷하게, 각 조인에서도 두 관계의 컬럼을 같은 방식으로 분류한다.
이 생각을 통해 bodys와 joins 필드를 얻고, 어색한 arity 필드(맨 왼쪽 조인의 특수 케이스)도 해결한다.
마지막 필드 heads는 머리 원자들을 훑으며 리터럴인지 변수의 위치인지 기록하면 된다. 조인이 전혀 없을 가능성도 있으니, 단일 몸체 원자를 맵핑해야 하는 경우의 혼란도 처리한다.
이 모든 일을, 아마도 틀릴 수도 있는 코드가 joins.rs에 들어있고, JoinPlan의 From<&str> 구현으로 예쁘게 포장돼 있다.
impl<'a> From<&'a Rule> for JoinPlan {
fn from(rule: &'a Rule) -> Self {
...
}
}
여기서는 더 보여 주지 않겠다!
JoinPlan 구현하기이제 본격적으로 시작이다. 지금까지는 추상적이거나, 아주 구체적이어도 텍스트/규칙 수준이었다. 이제는 성능에 민감한 부분으로 들어간다.
조인 계획 구현은 대략 이런 시그니처의 함수에서 시작한다.
/// 주어진 계획으로 규칙을 구현한다.
///
/// 추가로, 규칙 유일 식별자(pos)는 새 관계 이름을 만드는 데 쓴다.
/// `stable` 인자는 전체 평가(full)인지, 변화분만 평가(incremental)인지 나타낸다.
pub fn implement_plan(
rule: &Rule,
plan: &JoinPlan,
pos: usize,
stable: bool,
facts: &mut Facts)
{
...
}
여기 몇 가지 비밀이 드러난다. 특히 stable 인자에 대한 질문이 생길 텐데, 이제 설명해야겠다.
stable이 설정된 경우는, 관계의 stable + recent를 모두 조인한다. 둘 다 유효하고 중복 없는 사실이며, 거의 전부 필요하다. 이는 새 규칙을 도입할 때 쓰는 모드다. 사실이 안정적이더라도, 규칙이 새로 왔으니 시작하려면 모든 걸 해야 한다.
stable이 꺼진 경우는, stable 사실만으로 유도되는 결과를 제외하고, 새 사실이 섞인 조인 결과만 원한다. stable 사실만으로 다시 유도되는 건 이미 봤으니, 시간 낭비다! 그런데 이걸 어떻게 달성할까?
조인, 특히 우리가 구현하는 이항 조인은 “쌍선형(bi-linear)”, 즉 덧셈에 분배된다. 사실 집합 A, B에 각각 최근 추가분 a, b가 있다면, 조인은 아래처럼 쓸 수 있다.
(A + a) ⋈ (B + b)
=
A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
두 번째 줄의 첫 항 A ⋈ B는 바로 stable 사실만의 조인 결과다. 으엑! 원하지 않는다!
우리가 정말 원하는 건, 최근 사실이 섞인 조인 결과에서, stable-only 조인 결과를 뺀 것이다. 위를 이렇게 바꾸면,
(A + a) ⋈ (B + b) - A ⋈ B
=
A ⋈ b + a ⋈ B + a ⋈ b
좋다! 원하는 것을 얻으려면, 최근 추가분이 반드시 하나 포함된 세 조인만 하면 된다. 그 stable 플래그를 염두에 두고, 전체 vs 증분 조인을 토글할 수 있도록 조인을 구현하겠다.
조인 구현의 첫 단계는 JoinPlan::bodys의 계획을 적용하는 것이다. 각 입력을 조인을 위해 필요한 순서로 재배치하고, 필요한 경우 필터링한다.
// 편의를 위한 새 이름
let name = format!(".temp-{:?}", pos);
// 사실을 읽어올 관계 이름을 임시로 저장
let mut names = Vec::with_capacity(rule.body.len());
// 각 몸체 계획을 새 이름의 관계에 적용
for (index, (plan, atom)) in plan.bodys.iter().zip(rule.body.iter()).enumerate() {
if plan.identity() {
facts.entry(atom.name.clone()).or_default();
names.push(atom.name.clone());
}
else {
let new_name = format!("{}-{:?}-in", name, index);
let mut builder = FactBuilder::default();
let found = facts.entry(new_name.clone()).or_default();
if stable {
for layer in found.stable.layers.iter() {
plan.apply(layer, &mut builder);
}
}
plan.apply(&found.recent, &mut builder);
facts.get_mut(&new_name).unwrap().add_set(builder);
names.push(new_name);
}
}
여기 귀여운 포인트가 있다. 계획이 no-op이라면, 우리는 그렇게 만들도록 노력했는데, 그 단계를 건너뛸 수 있다. 그 경우 소스 사실 리스트를 그대로 쓴다!
그 외에는, 앞서 소개한 믿음직한 FactBuilder를 쓰고, recent, 요청 시에는 stable의 각 레이어에도 계획을 적용한다. 빌더는 FactSet에 넘기면, FactLSM을 자신의 to_add에 통합하는 법을 안다.
이제 몸체 입력들이 모두, 머지 조인을 수행하기 위한 정렬 상태로 준비됐다. 다음 단계는, 두 개 이하가 남을 때까지 머지 조인을 적용하는 것이다. 각 조인을 수행할 때 arity(키 자리수)와, 일치한 결과를 어떻게 다룰지를 지정해야 한다. 우리는 결과를 FactBuilder에 넣고, 임시 이름과 함께 저장한다.
let mut r_name = names.pop().unwrap();
if names.len() > 1 {
// 두 컬렉션만 남을 때까지 조인 진행
for (index, (arity, projection)) in plan.joins.iter().enumerate().rev() {
let l_name = names.pop().unwrap();
let mut builder = FactBuilder::default();
join_with(facts.get(&l_name).unwrap(), facts.get(&r_name).unwrap(), stable, *arity, |v1, v2| {
builder.push(projection.iter().copied().map(|i| {
if i < v1.len() { v1.get(i) } else { v2.get(i - v1.len()) }
}));
});
// 다음 단계에서 쓸 이름으로 결과 저장
r_name = format!("{}-{:?}-mid", name, index + 1);
facts.entry(r_name.clone())
.or_default()
.add_set(builder);
}
}
조인의 마법은 다른 성에 있다. 성의 이름은 join_with. 드디어 거기로 가 보자. 사실상 datafrog에서 가져온 것이니 너무 기대는 말자. 그 전에 마지막 단계 하나 더.
몸체 원자가 두 개라면 위에서와 같은 일을 하되, 사실을 배치하는 지시만 다르게 한다. 머리가 여러 개일 수 있으니 빌더도 여러 개 쓴다. 몸체 원자가 하나뿐이면 조인 없이 관계를 읽기만 하면 된다.
어떻게 해도 코드를 깔끔하게 못 썼다. 같은 일을 세 번 반복한다. 저장소에서 확인해 보기 바란다. 미안하다.
/// 첫 `arity` 컬럼으로 `body1`과 `body2`를 조인
///
/// 일치하는 쌍에 `action`을 적용한다.
/// `stable`이 설정되면, 각 입력의 stable+recent를 조인한다;
/// 꺼져 있으면 둘 다 stable인 쌍을 제외한다.
pub fn join_with(
body1: &FactSet,
body2: &FactSet,
stable: bool,
arity: usize,
mut action: impl FnMut(<Fact as Columnar>::Ref<'_>, <Fact as Columnar>::Ref<'_>),
)
{
// 첫 `arity` 컬럼만으로 원소를 비교
// 타입에 대한 컴파일 타임 정보가 있으면 좋겠지만; 컬럼 내성으로 복구할 수 있을지도.
let order = |x: <Fact as Columnar>::Ref<'_>, y: <Fact as Columnar>::Ref<'_>| { (0 .. arity).map(|i| x.get(i)).cmp((0 .. arity).map(|i| y.get(i))) };
if stable {
for layer1 in body1.stable.layers.iter() {
for layer2 in body2.stable.layers.iter() {
join::<Fact>(layer1, layer2, order, &mut action);
}
}
}
for stable2 in body2.stable.layers.iter() {
join::<Fact>(&body1.recent, stable2, order, &mut action);
}
for stable1 in body1.stable.layers.iter() {
join::<Fact>(stable1, &body2.recent, order, &mut action);
}
join::<Fact>(&body1.recent, &body2.recent, order, &mut action);
}
아, 이건 다 거짓말이고 join 함수가 또 있다?
여기서 하는 일은 stable 비트 처리뿐이다. 최근 사실이 섞인 세 조인을 수행하고, 요청 시 stable-only 조인도 수행한다. join 함수에 stable을 넘기지 않는데, 그건 진짜 조인을 하기 때문이다.
/// `input1`과 `input2`에서 키를 맞춰 일치하면 `action` 호출
fn join<'a, T: Columnar<Ref<'a> : Ord+std::fmt::Debug>> (
input1: &'a T::Container,
input2: &'a T::Container,
mut order: impl FnMut(T::Ref<'a>, T::Ref<'a>) -> std::cmp::Ordering,
mut action: impl FnMut(T::Ref<'a>, T::Ref<'a>),
) {
use std::cmp::Ordering;
let input1 = input1.borrow();
let input2 = input2.borrow();
let mut index1 = 0;
let mut index2 = 0;
// 어느 한쪽이 소진될 때까지 계속
while index1 < input1.len() && index2 < input2.len() {
// 이 위치의 키 비교
let pos1 = input1.get(index1);
let pos2 = input2.get(index2);
match order(pos1, pos2) {
Ordering::Less => {
// `pos2`보다 엄격히 작은 동안 `index1` 전진
gallop::<T>(input1, &mut index1, |x| order(x, pos2) == Ordering::Less);
},
Ordering::Equal => {
// 모든 일치 항목 찾고 인덱스 증가
let count1 = (index1..input1.len()).take_while(|i| order(input1.get(*i), pos1) == Ordering::Equal).count();
let count2 = (index2..input2.len()).take_while(|i| order(input2.get(*i), pos2) == Ordering::Equal).count();
for i1 in 0 .. count1 {
let row1 = input1.get(index1 + i1);
for i2 in 0 .. count2 {
let row2 = input2.get(index2 + i2);
action(row1, row2);
}
}
index1 += count1;
index2 += count2;
},
std::cmp::Ordering::Greater => {
// `pos1`보다 엄격히 작은 동안 `index2` 전진
gallop::<T>(input2, &mut index2, |x| order(x, pos1) == Ordering::Less);
},
}
}
}
datafrog에서 바로 가져왔다. 거기도 어디선가 가져왔을 것이다. 내가 조인을 발명한 건 아니다.
이건 머지 조인이다. 정렬된 입력을 순차적으로 훑으며 키가 일치하는 걸 찾는다. 일치하는 키를 찾으면 action을 호출하는데, 이건 그냥 FactBuilder에 사실을 넣는 일이다. 일치하지 않으면 gallop을 호출하는데, EmptyHeaded에서 훔쳐온 것으로, 일종의 이진 탐색처럼 다음 가능한 일치 지점으로 빠르게 나아간다.
gallop을 보고 싶은가?
/// `cmp`를 만족하는 마지막 원소 다음까지 `index`를 증가
///
/// `cmp`는 단조(monotonic)라고 가정한다. 한 번 false가 되면 다시 true가 되지 않는다.
/// `upper`가 주어지면, 조사할 구간의 상한으로 작용한다.
#[inline(always)]
pub(crate) fn gallop<'a, T: Columnar>(input: <T::Container as Container<T>>::Borrowed<'a>, index: &mut usize, mut cmp: impl FnMut(<T as Columnar>::Ref<'a>) -> bool) {
let upper = input.len();
// 비어 있거나 이미 상한에 도달했다면 반환
if *index < upper && cmp(input.get(*index)) {
let mut step = 1;
while *index + step < upper && cmp(input.get(*index + step)) {
*index += step;
step <<= 1;
}
step >>= 1;
while step > 0 {
if *index + step < upper && cmp(input.get(*index + step)) {
*index += step;
}
step >>= 1;
}
*index += 1;
}
}
이게 join.rs의 실제 마지막이다. 코드 투어는 여기까지다.
Graspan 프로젝트의 데이터를 조금 갖고 있다. 그 당시 받아 둔 것이 아직도 구글 드라이브에 있다. 따라 하고 싶다면 main.rs 맨 위에 이 조각을 넣자.
for arg in std::env::args().skip(1) {
// 입력 데이터를 파일에서 읽는다.
use std::fs::File;
use std::io::{BufRead, BufReader};
let mut dict: BTreeMap<String, facts::FactBuilder> = BTreeMap::default();
let filename = arg;
let file = BufReader::new(File::open(filename).unwrap());
for readline in file.lines() {
let line = readline.expect("read error");
if !line.is_empty() && !line.starts_with('#') {
let mut elts = line.split_whitespace().rev();
if let Some(name) = elts.next() {
dict.entry(name.to_string())
.or_default()
.push(elts.rev().map(|x| x.as_bytes()));
}
}
}
for (name, facts) in dict {
state.facts
.entry(name)
.or_default()
.add_set(facts);
}
}
state.update();
입력과 프로그램 분석이 몇 가지 있다. 분석은 데이터플로와 포인터 분석으로 나눠 보자.
먼저 httpd 데이터플로 입력과 셸의 .list 명령으로 무엇을 보고 있는지 확인한다.
mcsherry@gallustrate datatoad % cargo run --release -- ~/Projects/datasets/graspan-dataflow/httpd_df
Finished `release` profile [optimized] target(s) in 0.00s
Running `target/release/datatoad /Users/mcsherry/Projects/datasets/graspan-dataflow/httpd_df`
> .list
e: 9905624
n: 138331
39.458µs
>
두 관계 e와 n이 보인다. 각각 “edge”와 “node”에 해당한다. psql과 linux 입력에서도 데이터플로 분석은 같을 것이다.
이 데이터플로 분석은 무엇인가?
n(?a, ?b) 관계는 어떤 값 ?a가 위치 ?b에 쓰일(write) 수 있음을 나타낸다.e(?a, ?b) 관계는 위치 ?a의 값이 위치 ?b로 이동될 수 있음을 나타낸다(프로그램의 대입처럼).우리가 하는 건 도달성 쿼리다. 어떤 위치에 쓰인 값이 변의 경로를 따라 어디까지 닿을 수 있는지 본다. Datalog으로 쓰면:
n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
말로 하면 “?a 값이 ?b에 쓰일 수 있고, ?b가 ?c로 복사될 수 있다면, ?a 값은 ?c에 쓰일 수 있다.”
이 규칙을 셸에 입력해 보자!
내레이션: 에러가 났다. 코드는 꼭 테스트하자, 얘들아.
에러를 고쳐서 저장소에 푸시했고, 결과는 다음과 같다.
> n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
15.494418333s
> .list
.temp-0-0-in: 9393283
e: 9905624
n: 9393283
45.375µs
>
약 15초가 걸렸다. 숫자다. Graspan이 같은 문제에서 보고한 수치(684초)보다는 훨씬 빠르다. 하지만 아직 이야기는 끝나지 않았다.
.temp-0-0-in도 있는데, 딱히 관심 있는 건 아닌 것 같다. 게다가 .. n과 비슷한 개수이고, 그 숫자는 작지 않다. 무슨 일일까?
조인에서, n의 컬럼을 먼저 ?b, 다음 ?a로 정렬해 e(?b, ?c)와 조인하고 싶다. e는 이미 ?b가 앞에 있다. 그래서 중간 컬렉션을 만들어 n을 다시 정렬해야 한다. 재정렬과 재정렬을 위한 정렬, 중복 제거는 필요 없을 수 있지만 어쨌든 하게 된다. 그래서 .temp-0-0-in은 조인을 위해 n을 재구성해야 해서 생겼다.
데이터를 다르게 적재하게 하거나, n을 두 번째 좌표로 정렬하거나, 다른 복잡한 방법을 쓸 수도 있지만, 그러지 말자. 더 단순한 방법으로, 초기의 n이 작다는 점을 이용해, 한 번만 재구성하고, 재구성된 변수를 전개(develop)하자. 다음과 같다.
m(?b, ?a) :- n(?a, ?b) .
m(?c, ?a) :- m(?b, ?a), e(?b, ?c) .
꽤 쉽다. 변수 배치를 조심하면 된다. 사실, 차라리 명확하게 변수 이름을 써 보자.
m(?loc, ?val) :- n(?val, ?loc) .
m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
e, n, m에 더 나은 이름을 주고 싶지만, 지금은 데이터 전체를 복사해야 한다. 할 수는 있지만, 변수 바인딩을 더 좋게 쓰는 것처럼 성능 무관(no-op)은 아니다. 나중으로 미루자.
이제 어떻게 되는지 보자.
> m(?loc, ?val) :- n(?val, ?loc) .
58.964458ms
> m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
8.434536333s
> .list
.temp-0-0-in: 138331
e: 9905624
m: 9393283
n: 138331
23.959µs
>
확실히 빨라졌다. 하지만 .temp-0-0-in이 여전히 있다. 이건 내 실수다. 첫 번째 규칙에서 n을 m으로 재매핑한 부분이다. 거기서는 non-identity 맵이 있을 이유가 없다. 해당(상대적으로 테스트가 덜 된) 특수 케이스의 로직을 조여야 한다.
좋은 소식은 조인을 위한 .temp 관계가 없다는 점이다. e와 m은 조인이 원하는 레이아웃을 이미 갖고 있고, 데이터를 복사해서 만들거나 유지하지 않아도 된다. 그 복사 글리치만 빼면. 하지만 지금은 무시하자.
내레이션: 그는 그 글리치를 무시할 수 없었다.
글리치는 몸체에 원자가 하나뿐이어도, 컬럼을 알파벳 순으로 정렬하는 계획을 만들기 때문이다. 이름을 저장하는 컨테이너로 BTreeSet을 쓰기 때문이다. 서사 이유로 ?a, ?b에서 ?val, ?loc으로 바꾸자 컬럼 순서가 달라졌다. 이건 더 큰 글리치를 드러낸다. 조인에도 해당되는데, 몸체 원자는 키 컬럼의 _집합_을 위에서 지정받지만, 그 _순서_는 선택할 수 있고, 자연 순서가 호환되면 그걸 선호해야 한다.
이걸 고치겠다. 하지만 지금은 아니고.
여기서 배운 건, 질의 계획 및 최적화의 일부는 사용자에게 달렸다는 점이다. 데이터의 초기 모양은 계획의 효율을 좌우한다. 이는 계산을 데이터 사용 시점까지 미룰 수 없으면 고치기 어렵다. 현 Datalog 인터프리터는 적극적으로 작업을 수행하니 의도에 맞지 않는다. 하지만 지원을 고민해 볼 만하다.
이 시점에서 다른 데이터셋을 로드하고 같은 분석을 해 보자. psql 데이터셋과 여러 linux 데이터셋이 있다. linux 데이터셋은 독립적으로 분석하기 위한 것 같다. 모두 0부터 시작하는 식별자를 쓰고, 파일 간에 동일한 코드 위치를 가리키지 않는다. 가장 큰 건 lnx_kernel_df이니 그걸 쓰겠다.
결과를 모아 규칙 평가 시간만 보고한다. 데이터 로드 시간도 적지 않지만(“디스크로 스필”에서 더 다룬다), 이상적으로는 즉시여야 한다.
| dataflow | httpd | psql | lnx_kernel |
|---|---|---|---|
| graspan | 684s | 8640s | 42840s* |
| datatoad | 8.43s | 24.33s | 55.01s |
| datafrog | 1.30s | 4.06s | 8.03s |
예전엔 datafrog 수치에서 로드 시간을 빼는 걸 잊어, datatoad 수치에 비해 과하게 우쭐했었다. 시간은 어디에 쓰이는지 다음에 더 살펴보겠지만, 답은 “가변 길이 사실과 리터럴의 불확실성 처리”다. datafrog도 많은 눈길이 닿지 않았으니, 다른 분들이 쉽게 잡을 과실이 있을지도!
Graspan의 lnx_kernel 숫자에 *를 붙인 이유는, 그들은 모든 시간을 합쳐서 보고했지만, 식별자가 충돌하므로 동시에 돌린 건 아니라는 뜻이기 때문이다. lnx_kernel 입력은 다른 입력을 합친 것보다 두 배 크다. 방향성은 틀리지 않았지만, 사실로는 부정확하다.
우리는 datafrog에 비해 오버헤드가 좀 있다. 그 차이를 설명해야 한다. 그래도 Graspan에 비해서는 의미 있는 수준이다. 실무자들이 실제로 쓰는 도구는 Soufflé이고, 분명 Graspan보다는 낫다. Soufflé가 적절한 비교 대상일 것이다.
Graspan이 고려한 두 번째 분석은 Zheng와 Rügina에서 가져온 것으로, 값과 메모리 위치의 잠재적 “별칭”에 대한 분석이다. 그들의 공식화는 두 종류의 식을 다룬다: 값 e와, 메모리 위치 *e. 입력 관계는 두 개다.
대입: A(?val, ?loc) // 각 `?loc <- ?val`
역참조: D(?val, ?loc) // 각 `*?val`로서의 `?loc`.
이 입력 데이터로, 두 종류의 별칭을 판별하고자 한다(Zheng와 Rügina 인용).
헷갈리면(나도 그렇다) 데이터와 표현된 분석으로 그냥 진행해도 된다. 그들은 다음처럼 메모리/값 별칭을 기술하며, 풀어야 할 용어가 좀 있다.
메모리 별칭: M ::= D^T V D
값 별칭: V ::= F^T M^? F
값 흐름: F ::= (A M^?)^*
뭐지 이 이상한 기호는?
오른쪽은 2항 관계들의 시퀀스다. Q ::= X Y Z는 중간 변수를 도입하여 관계를 경로로 잇는다는 뜻이다. Datalog으로 쓰면 다음과 같다.
Q(?a, ?d) :- X(?a, ?b), Y(?b, ?c), Z(?c, ?d).
Datalog엔 없는 낯선 기호들이 있다:
^T는 전치(transpose)로, 관계의 방향을 바꾼다.^?는 선택(optional)을 뜻하고, 항이 있어도 되고 없어도 된다.^*는 반복(클레이니 스타)로, 항이 0번 이상 반복될 수 있음을 뜻한다.예를 들어, M 규칙을 Datalog으로 쓰면
M(?l1, ?l2) :- D(?v1, ?l1), V(?v1, ?v2), D(?v2, ?l2).
첫 D 원자의 변수 순서를 바꿔 ^T를 처리했다는 점을 보라. 대략 “값 ?v1와 ?v2가 별칭일 수 있다면, 그것을 역참조한 메모리 위치도 메모리 별칭일 수 있다”는 뜻이다. 그럴싸하다.
나머지 두 규칙을 쓰려 하면 ^?와 ^*가 튀어나오고 .. Datalog에게 성가시다. Datalog에는 “그래.. 또는 건너뛴다”가 없다.
^?는 비교적 처리하기 쉽다. 항을 넣은 버전과 뺀 버전을 각각 쓰면 된다. 메모리 별칭을 포함할 수도 있는 값 별칭의 경우, 다음 두 규칙을 쓸 수 있다.
V(?v1, ?v2) :- F(?v3, ?v1), F(?v3, ?v2).
V(?v1, ?v2) :- F(?l1, ?v1), M(?l1, ?l2), F(?l2, ?v2).
^*는 좀 더 까다롭다. 대안 중 하나는 몸체가 비어 있는 규칙이 되기 때문이다. 대략 정체함수(항등 연산자)와의 합집합을 뜻한다. 이를 명시적으로 표현해야 할 수 있다. 일단은 그렇게 하자. 또 다른 해결책도 있는데, 규칙 집합을 폭발적으로 늘리는 것이다. 이 접근이 끔찍하면 그때 얘기하자.
값 흐름은 0회 이상의 (A M^?) 연쇄다. 다음처럼 쓸 수 있다.
F(?val, ?unk) :- A(?val, ?loc), F(?loc, ?unk).
F(?val, ?unk) :- A(?val, ?loc), M(?loc, ?loc2), F(?loc2, ?unk).
오른쪽 변수에 ?unk를 둔 이유는 .. 뭔지 아직 모른다는 뜻이다. 규칙은 기존 ?unk에서 찾은 걸 그대로 가져오라고 하지만, 어디서 시작하는가?
비공식적으로, 값과 위치의 조합 위에서의 항등 관계에서 시작한다. 값이 필요한 이유는, F의 첫 인자가 A의 첫 인자(값)에서 오기 때문이다. 위치가 필요한 이유는, F의 첫 인자가 위치와 조인되기 때문이다. 덜 할 수 있는 권한이 없으니, 우리가 들은 모든 값과 위치를 F에 넣자.
F(?v, ?v), F(?l, ?l) :- A(?v, ?l).
F(?v, ?v), F(?l, ?l) :- D(?v, ?l).
이 마지막 규칙들이 F의 정의를 완성하고 반복을 시작하게 해 준다. 이제 해 보자.
이걸 돌리는 동안 Zheng와 Rügina 논문을 읽었다. 문제를 해결하는 그들의 설명이 상대적으로 추상적이었는데, 아주 중요한 디테일을 배운다.
이제 메모리 may-alias 쿼리를 위한 디맨드 기반 알고리즘을 제시한다. 두 lvalue 식 e1, e2가 주어지면, 알고리즘은 M(e1, e2)가 성립하는지 판정한다.
그들은 오로지 M만 산출하면 된다! 그리고 더 정확히는 M을 _탐색(probe)_만 하면 된다. 그게 "디맨드 기반"이란 뜻이다. 하지만 우선 M만 보자. M만 산출하면 된다면, V를 산출할 필요가 없다. 너무 좋은 소식이다. V는 엄청 크기 때문이다. 그런데 M을 만들려면 V가 필요하지 않나? 꼭 그렇진 않다.
V에는 모든 값 별칭이 들어 있지만, M이 관심 있는 것은 주소의 값 별칭뿐이다. 즉 d의 첫 컬럼에 등장하는 값들. 그런데 도대체 왜 V를 전부 계산하고 있는가? V의 정의를 M에 인라인하자(변수 이름은 새로, 나는 처음에 그러지 않았다!).
-M(?l2, ?l1) :- d(?v1, ?l1), F(?v3, ?v1), F(?v3, ?v2), d(?v2, ?l2) .
-M(?l2, ?l1) :- d(?v1, ?l1), F(?l3, ?v1), -M(?l4, ?l3), F(?l4, ?v2), d(?v2, ?l2) .
F(?val, ?unk) :- -a(?loc, ?val), F(?loc, ?unk).
F(?val, ?unk) :- -a(?loc, ?val), -M(?loc2, ?loc), F(?loc2, ?unk).
F(?v, ?v), F(?l, ?l) :- -a(?l, ?v).
F(?v, ?v), F(?l, ?l) :- -d(?l, ?v).
입력하고 나니,
> F(?v, ?v), F(?l, ?l) :- -a(?l, ?v).
234.626393458s
> F(?v, ?v), F(?l, ?l) :- -d(?l, ?v).
98.101901291s
> .list
-M: 92806768
-a: 362799
-d: 1147612
.temp-0-1-mid: 17768284
.temp-0-2-in: 2669647
.temp-0-2-mid: 1859886
.temp-1-1-mid: 172280896
.temp-1-2-mid: 73474947
.temp-1-3-in: 2669647
.temp-1-3-mid: 1859886
.temp-3-1-mid: 173310916
F: 2669647
a: 362799
d: 1147612
86.75µs
>
-M와 F의 개수는 이전과 같으니 아마도 여전히 옳은 답이다. -V는 사라졌다. 그게 핵심이었다. 프로세스는 이제 18.96GB를 차지한다. 확실한 절약이다.
새 중간 조인이 생겼다. 특히 .temp-0-2-mid와 .temp-1-3-mid의 크기가 동일하다. 둘 다 첫 두 규칙의 끝의 두 원자 F(?v3, ?v2), d(?v2, ?l2)의 조인에 해당한다.
또한, 거꾸로 보면 이건 각 규칙의 첫 두 원자와 같다. 그냥 이름을 주고 사용하자. F와 d의 순서를 떠올리게 Fd라고 하자.
Fd(?v3, ?l2) :- F(?v3, ?v2), d(?v2, ?l2).
다시 쓰면 -M 생성이 더 짧아진다.
-M(?l2, ?l1) :- Fd(?v3, ?l1), Fd(?v3, ?l2) .
-M(?l2, ?l1) :- Fd(?l3, ?l1), -M(?l4, ?l3), Fd(?l4, ?l2) .
F(?val, ?unk) :- -a(?loc, ?val), F(?loc, ?unk).
F(?val, ?unk) :- -a(?loc, ?val), -M(?loc2, ?loc), F(?loc2, ?unk).
F(?v, ?v), F(?l, ?l) :- -a(?l, ?v).
F(?v, ?v), F(?l, ?l) :- -d(?l, ?v).
다시, 마지막 두 규칙을 입력하면 일이 시작된다.
> F(?v, ?v), F(?l, ?l) :- -a(?l, ?v).
163.471007292s
> F(?v, ?v), F(?l, ?l) :- -d(?l, ?v).
61.675481125s
> .list
-M: 92806768
-a: 362799
-d: 1147612
.temp-0-0-in: 2669647
.temp-2-1-mid: 73474947
.temp-4-1-mid: 173310916
F: 2669647
Fd: 1859886
a: 362799
d: 1147612
103.333µs
>
또 한 번 훌륭한 개선이다.
마지막으로 한 가지 더. 우리가 F로 하는 유일한 일은 끝에 d를 붙이는 것이다. 게다가 Fd는 F보다 약간 작다. 우리가 만든 것 중 필요 없던 게 있는 듯하다. Fd를 바로 계산하자. d에서 출발해, 0회 이상의 (a M^?)를 앞에 붙이는 식이다. 이건 항등 관계 문제도 해결한다. Fd는 항상 d를 포함한다.
-M(?l2, ?l1) :- Fd(?v3, ?l1), Fd(?v3, ?l2) .
-M(?l2, ?l1) :- Fd(?l3, ?l1), -M(?l4, ?l3), Fd(?l4, ?l2) .
Fd(?val, ?unk) :- -a(?loc, ?val), Fd(?loc, ?unk).
Fd(?val, ?unk) :- -a(?loc, ?val), -M(?loc2, ?loc), Fd(?loc2, ?unk).
Fd(?val, ?loc) :- -d(?loc, ?val).
이제 마지막 규칙 하나만 입력하면,
> Fd(?val, ?loc) :- -d(?loc, ?val).
162.082759041s
> .list
-M: 92806768
-a: 362799
-d: 1147612
.temp-1-1-mid: 73474947
.temp-3-1-mid: 73474947
Fd: 1859886
a: 362799
d: 1147612
34.333µs
>
여전히 똑같은 걸 본다. 중간 결과 -M Fd가 두 번 계산되고, 꽤나 크다. 이를 고치자. 나에게는 근본적으로 불공평한 이유로, - 없는 MFd가 필요하다.
MFd(?l1, ?l2) :- -M(?l3, ?l1), Fd(?l3,?l2).
-M(?l2, ?l1) :- Fd(?v3, ?l1), Fd(?v3, ?l2) .
-M(?l2, ?l1) :- Fd(?l3, ?l1), MFd(?l3, ?l2).
Fd(?val, ?unk) :- -a(?loc, ?val), Fd(?loc, ?unk).
Fd(?val, ?unk) :- -a(?loc, ?val), MFd(?loc, ?unk).
Fd(?val, ?loc) :- -d(?loc, ?val).
늘 그렇듯 마지막 규칙이 일을 시작시킨다.
> Fd(?val, ?loc) :- -d(?loc, ?val).
119.34187225s
> .list
-M: 92806768
-a: 362799
-d: 1147612
Fd: 1859886
MFd: 73474947
a: 362799
d: 1147612
31.666µs
>
그리고 우리는 5.32GB에 앉아 있다. 메모리에서 처음 계획 대비 약 10배 개선이고, 실행 시간도 거의 10배 개선이다. 우리가 가치 있는 걸 계산했는지 모르겠지만, _원래 것_을 더 빠르게 계산했을 가능성은 높다. 사실, Zheng와 Rügina가 떠난 길로 다시 돌아간 것 같다. 명시적 points-to 집합을 만들어 교집합한다.
꽤 즐거운 오후였다!
도구의 스트레스 테스트를 했고, 최적화를 위해 도구를 다시 손볼 필요 없이(몇 가지 버그 수정 외엔) 질의 최적화를 탐구할 수 있었다. 대부분 기계적인 프로그램 변환을 봤고, 질의 최적화기가 대신 해 줄 법한 일들이다. 순진한 규칙 서술에서 한 자릿수 배 향상은, 질의 최적화기의 잠재력을 증명한다.
또한, Fd처럼 인덱싱된 중간 결과에 이름을 부여해 만들면, 원하는 만큼 관목형(bushy) 조인 계획을 얻을 수 있다는 점도 배웠다. 많은 “선언적” 언어는 원하는 계획을 항상 얻을 수 없다는 답답함이 있지만, 여기서는 그렇지 않아 보인다. 반대로, 필요하지 않은 것(e.g., V)에 이름을 붙이면, 여전히 만들어 준다는 단점도 봤다. 큰 비용을 치를 수도 있다.
전반적으로, 지금까지 실험이 만족스럽다. 다음으로는 Datalog 기반의 프로그램 분석 예제를 더 모아, 어떻게 돌아가는지 보겠다. 자동화하기 전에 맞춤형 최적화 공간을 더 경험해 보자.
업데이트: “디맨드 기반” 질의 얘기를 깜박했다. 이건 대략 “매직 셋(magic sets)”이다. 타깃 리터럴을 질의에 삽입하는 변환이다. 예를 들어, 모든 d에서 시작하는 대신, 관심 있는 것들만으로 Vd를 시작한다고 생각해 보라. 그건 틀리지만, “요구(demand)”되는 사실만 탐색하도록 질의를 변환하는 일반적 방법이 있다. 매직 셋이 최적은 아니고, 몇몇논문이 더 효율적인 방법을 설명한다. 가장 단순한 방법을 찾기 위해 읽을 예정이다. 하지만 나중에.
아주 단순하고, 사실 꽤 나쁜, 조인 최적화기를 써 보자!
동기 얘기를 해 두고 싶다. Datalog. 왜 이토록 많은 일을, 다소 난해한 논리 프로그래밍 언어에 바치는가? Horn 절, 최소 Herbrand 모델, 비단조 논리까지 정말 흥분되는가? 아니?
나도 아니다. 미안하지만 미안하지 않다.
내가 Datalog에 매혹되는 이유는, 데이터 병렬 계산의 핵심 문제, 데이터 랑데부(data rendezvous)의 가장 순수한 형태로 보이기 때문이다. 데이터 병렬 계산의 본질은 “적절한 데이터가 한자리에 모이면 쉽게 푸는 하위 문제들이 있다”이다.
다음 같은 규칙을 쓸 때
h(x, y, z) :- b1(x, y), b2(y, z) .
적어도 내게는 이렇게 들린다.
각
y에 대해, 그x와z를 한데 모아야 한다.
이유는 모르겠지만, 데이터 병렬 계산에서 이걸 무수히 반복한다. 고객의 주문과 계정 상태를 묶는 조인이 필요하다는 건 당연하고, 훨씬 더 많이 있다. 예를 들어 PageRank의 한 단계를 계산하려면, 페이지 y의 랭크 x와 그가 참조하는 페이지 z를 모아야 한다(그리고 여기 쓰지는 않았지만 페이지 y의 out-degree도). 여러분 y의 친구 x들 중 업무 지인 z를 아는 누가 있는지 찾으려면, 우선 친구와 동료 목록을 모아야 한다.
데이터 병렬 계산의 원시 연산은 키로 레코드를 그룹핑하고(그룹 바이라 key), 그룹핑된 리스트를 사용자 로직에 넘겨 주는 것이다(MapReduce의 reduce). 조인은 “다 좋아, 그런데 _전부_는 아니고”라고 말하는 첫 수단이다. 정보를 선택적으로 최종 목적지 h(x, y, z)로 라우팅한다. 그게 무엇이든 간에.
데이터 병렬 계산을 위한 매우 단순한 중간 표현(IR)을 써 보자. 너무 단순할 것이다. 하지만 .. 이미 많은 시스템보다 표현력이 높다. 지금은 조인에 특화되어 있지만 곧 일반화할 것이다.
IR에는 세 가지 opcode가 있다.
pub enum Op {
/// 이름으로 참조되는 데이터 컬렉션
Var(String),
/// 각 튜플에 동작 적용
/// 동작은 필터·순열·프로젝션을 할 수 있다
Map(Action),
/// 앞쪽 so-many 컬럼을 키로 브랜딩(표기)
Key(usize),
/// 동일 키 길이를 가진 여러 컬렉션을 모은다
/// 각 키마다 데카르트 곱(크로스 조인) 생성
Mul(usize),
}
세 개라 했는데 분명 네 개다. 결국 Map과 Key를 하나의 연산자로 융합할 것이다. 그게 삶을 편하게 한다. Key와 Mul의 출력은 공유·재사용할 수 있게 하는 것이 매우 강력하다. 반면 Map의 재사용은 큰 일이 아니다.
Action 타입은 여러 일을 할 수 있다. 하지만 지금은 위에서 언급했던 Plan과 유사한 정도로 하자.
/// 행 필터, 컬럼 재정렬, 접두(prefix)로 그룹핑
pub struct Action {
/// 특정 리터럴과 같아야 하는 컬럼
lit_filter: Vec<(usize, String)>,
/// 서로 같아야 하는 컬럼 인덱스 집합들
var_filter: Vec<Vec<usize>>,
/// 출력으로 제시할 입력 컬럼 순서
projection: Vec<usize>,
/// 행들이 그룹핑되는 접두 길이
key_arity: usize,
}
이 타입과 특히 key_arity 필드가 있으면, 위의 Key variant를 버려도 된다.
이 IR만으로도 지금까지 만든 우측-선형 조인 계획을 모두 표현할 수 있다. 각 이항 조인은 동등화할 컬럼들을 키로 삼게 하고, 다음 동작을 join 함수의 action 인자로 전달하면 된다.
동시에, 이 IR은 매우 똑똑한 것과 매우 덜 똑똑한 것 모두를 표현할 수 있다. 덜 똑똑한 것부터 시작해, 점점 똑똑한 것으로 가 보자.
임의의 규칙을 우리 opcode 프로그램으로 파싱하자!
덜 똑똑하다는 게 어느 정도로냐면, 몸체의 원자들을 전부 크로스 조인하고, 머리마다 그 위에 필터와 프로젝션을 얹자는 정도다. 키 자리수 0의 Map에는 문제 없고, Mul이 여러 개에 적용되는 것도 문제 없다. 성능만 빼면 문제 없다. 성능은 곧 다룬다.
/// 다중 머리 규칙을 어셈블리 명령으로 변환
pub fn rule_to_ir(rule: &Rule) -> Vec<ENode<Op>> {
let mut head = Action::default();
// 동일 이름(동등 제약)의 컬럼 모음
let mut bind = BTreeMap::<&str, Vec<usize>>::default();
let mut prog = vec![Op::Mul(rule.body.len())];
// 각 원자는 no-op action과 함께 도입된다.
// 머리 규칙은 필터와 프로젝션을 추가한다.
for atom in rule.body.iter() {
prog.extend([
Op::nop(atom.terms.len()),
Op::Var(atom.name.clone()),
]);
for term in atom.terms.iter() {
let column = head.projection.len();
head.projection.push(column);
match term {
// 변수 항은 사용된 이름을 기록
Term::Var(name) => {
bind.entry(name)
.or_default()
.push(column);
},
// 리터럴 항은 필터를 기록
Term::Lit(data) => {
head.lit_filter
.push((column, data.to_string()));
},
}
}
}
// 같아야 하는 컬럼들을 필터 제약에 추가
// 머리의 이름 해석을 위해 `bind` 유지
head.var_filter
.extend(bind.values()
.filter(|l| l.len() > 1)
.map(|l| l.clone()));
unimplemented!("머리 원자 처리 다음!")
}
이건 우리가 해야 할 일을 수행할 Op 명령 리스트를 만든다. 폴란드 표기법(프리픽스 표기법)을 사용한다. 예를 들어
vec![
Op::Mul(2),
Op::nop(3),
Op::Var("potato"),
Op::nop(1),
Op::Var("salad"),
];
이는 키 없는 3컬럼의 potato와 키 없는 1컬럼의 salad 사이의 이항(2) 조인을 수행하라는 뜻이다. Op::nop은 컬럼 수를 받아, 아무 일도 하지 않고 그 컬럼들을 투영(projection)한다(키 자리수 0).
몸체는 준비됐다. 모든 것을 보고 싶다면 리스트 맨 앞에 Op::Map(head)를 두면 된다. 대신, 머리 원자가 여러 개이니, 각 머리에 맞게 head를 맞춤화해야 한다.
// 각 머리 원자는 `act`를 개인화하여 `join`에 적용해야 한다.
// 개인화는 서로 다른 이름만 프로젝션한다.
let heads = rule.head.iter().map(|atom| {
let mut head_names = BTreeSet::<&str>::default();
let mut head = head.clone();
head.projection.clear();
for term in atom.terms.iter() {
// 머리 원자의 리터럴은 무시
if let Term::Var(name) = term {
if head_names.insert(name) {
// 처음 나타난 동등 컬럼 사용
let col = bind.get(name.as_str()).unwrap()[0];
head.projection.push(col);
}
}
}
head
}).collect::<Vec<_>>();
리스트 heads에는 각 머리 원자의 Action이 들어 있다. 이 액션을 Op::Map으로 감싸 prog에 적용하면 올바른 결과를 계산한다. 물론 전부 크로스 조인이라, 믿을 수 없이 비효율적이다. 하지만 결과는 맞을 것이다. 아주아주 느릴 뿐.
e-graph 좋아하나? 난 무척 좋아한다.
e-graph를 모른다면 egg 웹페이지를 보라. 전에 e-graph에 대한 글도 썼다. 곧 쓸 코드에 대해 설명한다. 나는 egg 프로젝트에서 대충 빌려온 e-graph 구현을 직접 썼다. 프로 수준의 e-graph가 필요하면 egg를 써라. 나는 배우고 싶었고, 그래서 직접 해 봤다. 배우게 됐다.
e-graph를 배우기 위한 첫 단계는 term graph를 아는 것이다. term graph는 식별자 Id에서, 식별자만 참조하는 연산으로 가는 맵으로 볼 수 있다.
struct ENode<T> {
op: T,
args: Vec<Id>,
}
type TermGraph<T> = BTreeMap<Id, ENode<T>>;
이는 표현식 트리를 나타내는 한 방식이다. 각 트리 노드는 자신의 Id를 갖는다. term graph는 더 나아가 공유를 표현할 수 있다. 두 ENode가 완전히 같다면(같은 연산자와 인자), 같은 식별자를 두 곳에서 쓸 수 있다. 공유는 프로그램을 더 간결하게 만들 뿐만 아니라, 어떤 데이터를 재사용할 수 있는지도 드러낸다.
현 계획에서 유용한 공유가 많지 않다고 느낄 수 있다. 그건 우리가 이제부터 무엇을 할지 모르기 때문이다. 우리는 엄청나게 많은 e-node를 만들 것이다. 그 전에, 기존의 prog(몸체)와 heads에서 표현식을 e-graph에 넣자.
// 규칙 구현 옵션을 담는 e-graph
let mut e_graph: EGraph<Op> = Default::default();
// `join`을 삽입하고 이름 포착
let body = e_graph.insert(prog.clone());
// 각 머리는 삽입하지만 반환값은 무시
for head in heads.iter() {
e_graph.ensure(ENode::new(Op::Map(head.clone()), [body]));
}
e_graph.insert는 제공된 연산자 시퀀스를 받아 내부 e-node로 다시 빌드한다. 프로그램의 루트(여기서는 Op::Mul)에 연결된 이름을 반환한다. e_graph.ensure는 비슷하지만 생짜 e-node에도 작동한다: 연산자와 인자 식별자 리스트를 직접 지정한다. prog의 복사본들을 머리 수만큼 만들고 그 위에 head 액션을 얹을 수도 있지만, 그건 불필요한 일이다.
참고용 예시를 소개하겠다. 구현 섹션 위에서의 “영리한” 관찰을 따라가는 것이다.
head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
이 규칙은 a → b를 거꾸로 걷고, 그다음 b → a를 정방향으로 걷는다. term graph 표기로는 다음과 같다.
0 -> [ Var("a") ]
1 -> [ Map(Action { proj: [0, 1], arity: 0 })[0] ]
2 -> [ Var("b") ]
3 -> [ Map(Action { proj: [0, 1], arity: 0 })[2] ]
4 -> [ Mul(4)[1, 3, 3, 1] ]
5 -> [ Map(Action { var_filter: [[0, 3], [2, 4], [5, 6]], proj: [1, 7], arity: 0 })[4] ]
우리는 a와 b를 두 번 사용하지만, 아직 아무 일도 하지 않으므로(항등 투영과 키 없음), 재사용하기 쉽다는 점을 현명하게 알아챘다. Mul(4) 크로스 조인에 의해 학살당하긴 하겠지만, 프로그램은 더 간결해졌다.
이제 e-graph를 최적화하자! 그런데 어떻게? 아직 명령 목록뿐인데.
// e-graph 최적화!
e_iterate(&mut e_graph, &[
&MulPermute,
&MulPartition,
&MapPushdown,
]);
여기서 무슨 일이 일어났을까.
요지는 MulPermute, MulPartition, MapPushdown 각각이 새로운 e-node를 도입하고, 기존 e-node와 동치로 묶는 규칙이라는 점이다. 예를 들어 MulPermute는 다음을 동치로 묶는다.
[ Map1, Mul(k), A, B, .. Z ]
=
[ Map2, Mul(k), B, Z, .. Q ]
단, Map1과 Map2는 적절한 컬럼 순열을 반영해 같아야 한다. 순열이 매우 많고 .. 따라서 동치 e-node가 매우 많다. 구문적으로 다른 e-node라서, 모두 기록하고, 동치라고 부른다.
그럼 e-graph는 어떻게 “동치”를 부르는가? Id에서 ENode<T> 하나로 가는 맵이 아니라, Vec<ENode<T>> 리스트로 맵핑한다. 리스트의 모든 e-node는 동치이며, 서로 대체 가능하다.
세 규칙은 각각 다음을 한다.
MulPermute : Mul(k)의 입력 순열을 모두 동치로 묶는다.MulPartition : Mul(k)을 나눌 수 있는 모든 방법을 동치로 묶는다.MapPushdown : Mul(2) 위의 Map을 입력으로 푸시 다운해, 입력 로컬 필터와 프로젝션을 갖는 Map과, 동등 컬럼을 키로 묶는 Mul로 동치화한다.코드는 좀 지저분하고, 솔직히 오래 쓰고 싶지 않다. Mul(k)는 순열과 분할만으로도 최소 2^k * k!개의 동치 항을 만들 수 있다는 건 대학원 학위가 필요하지 않다.
MulPermute만 돌리고, 새로운 정보가 생기지 않을 때까지 반복하면, e-node는 그리 많지 않다.
0: -> [ Var("a") ]
1: -> [ Map(Action { proj: [0, 1], arity: 0 })[0] ]
2: -> [ Var("b") ]
3: -> [ Map(Action { proj: [0, 1], arity: 0 })[2] ]
4: -> [ Mul(4)[1, 3, 3, 1] ]
6: -> [ Mul(4)[1, 3, 1, 3] ]
10: -> [ Mul(4)[1, 1, 3, 3] ]
13: -> [ Mul(4)[3, 1, 3, 1] ]
15: -> [ Mul(4)[3, 1, 1, 3] ]
17: -> [ Mul(4)[3, 3, 1, 1] ]
a 두 번, b 두 번을 쓰는 유일하게 구별되는 방법들이다. 사실, 머리에 해당하는 e-class는 숨겼다. 거기가 동치 표현이 잔뜩 있는 곳이다. 어떤가?
EClass #5: -> [
Map(Action { var_filter: [[0, 3], [2, 4], [5, 6]], proj: [1, 7], arity: 0 })[4],
Map(Action { var_filter: [[0, 3], [2, 6], [4, 7]], proj: [1, 5], arity: 0 })[6],
Map(Action { var_filter: [[0, 5], [2, 4], [3, 6]], proj: [1, 7], arity: 0 })[4],
Map(Action { var_filter: [[0, 5], [4, 6], [2, 7]], proj: [1, 3], arity: 0 })[10],
Map(Action { var_filter: [[0, 7], [2, 6], [3, 4]], proj: [1, 5], arity: 0 })[6],
Map(Action { var_filter: [[0, 7], [4, 6], [2, 5]], proj: [1, 3], arity: 0 })[10],
Map(Action { var_filter: [[1, 2], [0, 4], [5, 6]], proj: [3, 7], arity: 0 })[13],
Map(Action { var_filter: [[1, 2], [0, 6], [4, 7]], proj: [3, 5], arity: 0 })[15],
Map(Action { var_filter: [[1, 4], [0, 2], [3, 6]], proj: [5, 7], arity: 0 })[17],
Map(Action { var_filter: [[1, 4], [0, 6], [2, 7]], proj: [5, 3], arity: 0 })[15],
Map(Action { var_filter: [[1, 6], [0, 2], [3, 4]], proj: [7, 5], arity: 0 })[17],
Map(Action { var_filter: [[1, 6], [0, 4], [2, 5]], proj: [7, 3], arity: 0 })[13],
Map(Action { var_filter: [[2, 5], [0, 4], [1, 6]], proj: [3, 7], arity: 0 })[13],
Map(Action { var_filter: [[2, 5], [4, 6], [0, 7]], proj: [3, 1], arity: 0 })[10],
Map(Action { var_filter: [[2, 7], [0, 6], [1, 4]], proj: [3, 5], arity: 0 })[15],
Map(Action { var_filter: [[2, 7], [4, 6], [0, 5]], proj: [3, 1], arity: 0 })[10],
Map(Action { var_filter: [[3, 4], [0, 2], [1, 6]], proj: [5, 7], arity: 0 })[17],
Map(Action { var_filter: [[3, 4], [2, 6], [0, 7]], proj: [5, 1], arity: 0 })[6],
Map(Action { var_filter: [[3, 6], [0, 2], [1, 4]], proj: [7, 5], arity: 0 })[17],
Map(Action { var_filter: [[3, 6], [2, 4], [0, 5]], proj: [7, 1], arity: 0 })[4],
Map(Action { var_filter: [[4, 7], [0, 6], [1, 2]], proj: [5, 3], arity: 0 })[15],
Map(Action { var_filter: [[4, 7], [2, 6], [0, 3]], proj: [5, 1], arity: 0 })[6],
Map(Action { var_filter: [[5, 6], [2, 4], [0, 3]], proj: [7, 1], arity: 0 })[4],
]
하하. 좋다.
각 Mul(4)에 대해 2 x 2 Map이 있다. 두 개의 a와 두 개의 b 입력을 고르는 두 가지 방법에 대응한다. 인자 Id가 동치인 경우 중복을 피하는 더 똑똑한 MulPermute를 쓸 수도 있다. 하지만 엄밀히 따지면, 우리가 이 term들이 모두 동치라는 사실을 아직 e-graph에 가르치지 않았다. 어쩌면 var_filter의 해시가 매우 중요할지도. 우리가 확신하는 바는 아니지만.
다음 규칙 MulPartition은 서로 다른 식별자 수를 43까지 늘리고, 동치 머리 표현 수를 48까지 두 배로 늘린다. 나머지는 꽤 깔끔하다. 만들 수 있는 서로 다른 부분 항이 그리 많지 않다. 여기에 복붙하기엔 많지만, 컴퓨터가 다루기엔 적다.
마지막 규칙 MapPushdown은 Mul 위의 필터와 프로젝션을 내려보내, 입력에서 키 자리수를 0이 아니게 만들 수 있게 한다. 이제 114개의 서로 다른 식별자가 있다. 머리의 동치 e-node는 이상하게도 68개다. 그중 몇 개는 다음처럼 생겼다.
Map(Action { proj: [1, 3], arity: 0 })[239],
즉, 어떤 Mul 항 위에 단순한 프로젝션만 올려놓은 형태다. 숫자는 조밀하지 않다. 이 경우 890까지 올라가는 것 같다.
그럼 맘에 드는 계획을 어떻게 찾나? 그중 괜찮은 게 있긴 한가?
여기서 e-graph를 훑으며 각 식별자에 비용을 매긴다. 여기서 무엇이 좋고 나쁜지 의견을 표명한다. 예를 들어, 4-way 크로스 조인이 나쁘다는 점을 확인시켜야 한다.
우리는 각 관계를, 서로 상관없는 컬럼 수로 비용 매기겠다. Map은 산출 컬럼 수다. Mul은 키 컬럼 수 + 입력의 비키 컬럼 수의 합이다(추가 키 컬럼은 첫 컬럼과 동등화되며 굳이 있을 필요가 없다). Var는 그냥 0이다. 써야 하고 컬럼 수를 알 수 없기 때문이다. e-node의 비용이 더 크면, 엄청나게 나쁘다고 보고 안 쓴다.
식별자 집합의 비용은 최대값을 쓴다. 동률이 있을 것이며, 그럴 때는 Map 연산자 수, 그다음 Mul 연산자 수를 최소화하며 깨자. Map은 데이터를 기록해야 하고, Mul은 방문해 계산만 하면 된다.
여기엔 미묘함이 있다. 한 식별자의 동치 e-node를 활성화하는 데 쓸 수 있는 식별자 집합이 매우 많다. 이 입력은 충분히 작아서 전부 열거할 수 있다. 다만 더 나쁜 옵션(다른 옵션의 상위 집합)을 억제하는 데 주의했다. 더 똑똑해지려면 0 비용부터 웨이브로 진행하면서, 현재 웨이브보다 큰 비용의 e-node를 거부할 수 있다. 어떤 비용에서 _가용성_을 확립하면, 선택지를 그들로만 얇게 만들고 좀 더 비싼 것을 해도 된다.
마지막으로, 대부분 맞다고 생각되는 작업은, 수행할 연산 시퀀스를 찾는 일이다. 더 구체적으로, ENode<Op>의 시퀀스를 반환하는데, 각 e-node가 0부터 순차 식별자를 갖도록 재번호하고, 리스트 위치를 참조하도록 한다. 참조 예를 보자.
> head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
EPlan:
step 0: ENode { op: Var("a"), args: [] }
step 1: ENode { op: Var("b"), args: [] }
step 2: ENode { op: Map(Action { proj: [0, 1], arity: 1 }), args: [0] }
step 3: ENode { op: Map(Action { proj: [1, 0], arity: 1 }), args: [1] }
step 4: ENode { op: Mul(2), args: [3, 2] }
step 5: ENode { op: Map(Action { proj: [1, 3], arity: 1 }), args: [4] }
step 6: ENode { op: Mul(2), args: [5, 5] }
step 7: ENode { op: Map(Action { proj: [1, 3], arity: 0 }), args: [6] }
40.2635ms
>
2 웨이브에서, 어떤 연산에서도 최대 2개의 상관없는 컬럼으로 발견됐다. Map 네 개가 있다. 둘은 입력용이고, 하나는 출력용이다. 추가 중간 컬렉션은 하나뿐인데, b(?y, ?z), a(?z, ?b) 조각에 해당한다.
또한, 릴리즈 빌드에서도 40ms가 적지 않다는 점을 확인할 수 있다.
위에서 언급한 영리한 걸 아직 구현하지 않았다. 시간은 거의 전부 동치 포화에서 쓰인다. 거기서 자기 손으로 낳은 어리석음이 많다.
하지만 더 순진하지 않은 동치들도 많이 만들 수 있다. 예를 들어, 합친 MulPermute와 MulPartition은, 입력을 분할하더라도 각 분할이 변수 동등성으로 연결되어 있어야 가치가 있다는 점을 알아챌 수 있다. 다른 방식의 분할은 크로스 조인을 낳는다. 피하기 어렵긴 하지만, 보통은 질의가 이상하다는 신호다.
중요한 다음 단계는, 지금까지 모두 단일 규칙이었다는 점이다. 우리는 규칙이 많고, 같은 항이 여러 머리에 나타나면 입력의 _합집합_이다. 이는 분배법칙을 배울 수 있는 Op::Sum opcode를 시사한다. 또, 우리는 규칙을 인터랙티브하게 갱신할 수 있어 어색하다. 지금은 같아 보이는 항이, 나중에 타깃 규칙을 추가하면 달라질 수 있다. 정의와 항을 잘못 동치로 묶지 않도록 주의해야 한다. 매력적이긴 하다.
당장은, 최적화 결과를 실행에 연결해 써 볼 계획이다. 구리면 이유를 알아내 고치자. 실제로 써 먹는 것이 개선의 좋은 강제 장치다.
하지만 진짜로 하고 싶은 것은 이항 조인을 벗어나는 일이다. 데이터 병렬 계산의 본질이긴 하지만, 최악 경우 최적(worst-case optimal) 열차가 터널 끝에서 달려오는 게 보인다. 더 근본적으로 나은 데이터 랑데부 방법이 있다. 원자는 여전히 Map과 Mul처럼 보이겠지만, 먼저 일반화해야 한다.
동치 포화와 추출은 거의 Datalog 프로그램이다. 데이터 병렬 패러다임에 잘 들어맞고, 핵심은 적절한 데이터 랑데부다.
최적화된 계획의 실행을 구현했다. 예상보다 일이 더 들었다.
지난번에, 우리의 계획은 Vec<ENode<Op>>로 나오고, 이 연산들을 이 순서대로 적용하며, 각 e-node의 순번으로 식별한다고 했었다. 이건 괜찮지만, 사실 각 노드를 개별적으로 실행하고 싶지는 않다.
우리에겐 Var, Map, Mul이 섞여 있다. 실전 실행 의도는 다음과 같다.
Var에 대해, 그에 의존하는 각 Map을 외부 컬렉션의 한 번의 스캔에서 모두 적용한다.Mul에 대해, 그에 의존하는 각 Map을 여러 입력의 한 번의 스캔에서 조인하며 모두 적용한다.즉, Op::Map(action)은 우리가 “수행”하는 연산이라기보다, 자신이 의존하는 연산에 큐잉하는 것이다. 이를 위해 실행 계획을 더 준비해, 실행 가능한 플랜으로 만들어야 한다.
삶을 편하게 하려고, 확장된 Action 타입을 쓰기 시작했다. 이름이 처절하게도
struct TempAction {
lit_filter: Vec<(usize, String)>,
var_filter: Vec<Vec<usize>>,
projection: Vec<Result<usize, String>>,
}
여기 projection은 컬럼 참조 혹은 문자열 리터럴이 될 수 있다. 그게 유일한 차이다. 이름은 사실 잘못 붙였다. 어디서든 이걸 쓰고 싶기 때문이다. 다만 최적화 코드를 바꾸고 생길 버그를 피하려고 여기서는 기존 타입을 유지했다.
확장된 사전 계획은 e-node를 훑으며 각 Op::Map이 자신의 입력 식별자 키로 큐에 자신을 넣게 한다. 몸체와 머리는 다르게 다룬다. 후자만 리터럴을 도입할 수 있고, 최적화에서는 이를 무시해 왔다.
// 머리는 리터럴과 중복을 위해 자신이 의존하는 원자의 도움을 필요로 한다.
let (body, head) = self.plan.split_at(self.plan.len() - self.rule.head.len());
머리와 몸체를 나눴으니, 입력에 의해 맵 액션을 큐잉할 수 있다.
let mut steps = BTreeMap::<Id,Vec<(Id, TempAction)>>::default();
// 몸체의 모든 맵 액션을, 그가 의존하는 단계에 배치
for (index, node) in body.iter().enumerate() {
if let Op::Map(action) = &node.op {
steps.entry(node.args[0])
.or_insert_with(Vec::new)
.push((index, TempAction::from_action(action)));
}
}
// 머리의 모든 맵 액션을, 그가 의존하는 단계에 배치
for ((index, node), atom) in head.iter().enumerate().zip(self.rule.head.iter()) {
if let Op::Map(action) = &node.op {
steps.entry(node.args[0])
.or_insert_with(Vec::new)
.push((body.len() + index, TempAction::from_head(atom, action)));
}
else { panic!("Malformed plan; head atom is not a map!"); }
}
이제 steps 맵에는 실제로 수행할 단계가, 수행 순서대로 들어 있다. 이어지는 것은, 훨씬 옛날의 훨씬 더 끔찍했던 맞춤형 조인 계획 평가 로직을 다시 쓰는 일이다. 좀 더 깔끔하긴 하지만, 전부 읽고 싶지 않다면 이해한다.
세팅부터 시작한다. 우리는 여전히 각 물질화된 컬렉션에 이름이 필요하다. 이 이름 중 일부는 입력 이름, 일부는 출력 이름, 나머지는 순수 임시다. 하지만 이름은 Facts에 접근해 안정/최근 사실을 꺼내고, 새 사실 후보를 추가하는 방식이다.
let mut names = BTreeMap::<Id, String>::default();
for (idx, actions) in steps {
let node = &self.plan[idx];
match &node.op {
unimplemented!()
}
}
이름에 얼마나 진지한지 보여 주기 위해, 입력에서 데이터만 불러오는 경우(조인 없음)의 이름 결정을 보자.
Op::Var(name) => {
let mut todos = Vec::default();
for (id, action) in actions.iter() {
// 머리 생산은 자신의 이름으로 써야 한다.
if *id >= body.len() {
names.insert(*id, self.rule.head[id-body.len()].name.clone());
todos.push((*id, action));
}
// 항등 변환은 입력 이름을 그대로 쓸 수 있다.
else if action.is_ident(*arities.get(name).unwrap()) {
names.insert(*id, name.clone());
}
// 비항등 + 머리 아님이면, 새 이름을 만들고 그 뒤에 적재 결과를 둔다.
else {
let new_name = format!(".temp-{}-{}", pos, id);
names.insert(*id, new_name);
todos.push((*id, action));
}
}
세 경우가 있다.
이름을 정했으면, 입력 사실을 불러와 모든 액션을 적용한다. 결과는 FactBuilder 리스트 builders로 모은다.
if !todos.is_empty() {
let mut builders = vec![FactBuilder::default(); todos.len()];
if let Some(found) = facts.get(name) {
for layer in found.stable.contents().filter(|_| stable).chain(Some(&found.recent)) {
for ((_id, action), builder) in todos.iter().zip(builders.iter_mut()) {
for item in layer.borrow().into_index_iter() {
let lit_match = action.lit_filter.iter().all(|(i,l)| item.get(*i).as_slice() == l.as_bytes());
let var_match = action.var_filter.iter().all(|idxs| idxs.iter().all(|i| item.get(*i) == item.get(0)));
if lit_match && var_match {
builder.push(action.projection.iter().map(|i|
match i { Ok(col) => item.get(*col).as_slice(),
Err(lit) => lit.as_bytes() }));
}
}
}
}
}
마지막으로, 각 빌더를 해당 FactSet에 커밋한다.
for ((id, _action), builder) in todos.iter().zip(builders.into_iter()) {
let new_name = names.get(id).unwrap();
facts.entry(new_name.clone()).or_default().add_set(builder);
}
원래는 이 부분이 훨씬 길었는데, 케이스별로 쪼개 처리했기 때문이다. 지금은 좀 짧다. 단순해졌다고까진 말 못 하겠다.
조인 쪽은 조금 더 단순하다. 입력의 정보를 가져와야 한다. 키 자리수, 이름, 사실 집합 참조.
Op::Mul(2) => {
// 입력에서 의도된 조인 키 자리수를 확인
let arity = if let Op::Map(action) = &self.plan[node.args[0]].op { action.key_arity } else { panic!("malformed plan") };
// 컬렉션 존재 보장, 그다음(대여 검사기)로 가져오기
facts.entry(names.get(&node.args[0]).unwrap().clone()).or_default();
facts.entry(names.get(&node.args[1]).unwrap().clone()).or_default();
let facts0 = facts.get(names.get(&node.args[0]).unwrap()).unwrap();
let facts1 = facts.get(names.get(&node.args[1]).unwrap()).unwrap();
let mut builders = vec![FactBuilder::default(); actions.len()];
join_with(facts0, facts1, stable, arity, |v1, v2| {
for ((_id, action), builder) in actions.iter().zip(builders.iter_mut()) {
builder.push(action.projection.iter().map(|i| {
match i { Ok(col) => if *col < v1.len() { v1.get(*col).as_slice() } else { v2.get(*col - v1.len()).as_slice() },
Err(lit) => lit.as_bytes() }}));
}
});
// 결과를 각자 `FactSet`에 커밋
for ((id, _action), builder) in actions.iter().zip(builders.into_iter()) {
let name = if *id >= body.len() { self.rule.head[id-body.len()].name.clone() } else { format!(".temp-{}-{}", pos, id) };
facts.entry(name.clone()).or_default().add_set(builder);
names.insert(*id, name);
}
}
이게 전부다! 다른 명령을 보면 불평하며 패닉하는 match 케이스가 하나 더 있다. Mul(2)와 Map(_)만 실행 가능하다.
단항 규칙으로 인해 들어온 Mul(1)을 제거하는 e-분석을 새로 추가해야 했다. 다른 버그도 여럿 있었다. 그래도 복잡한 예제에서 돌아간다.
> Fd(?val, ?loc) :- -d(?loc, ?val).
114.284011209s
> .list
-M: 92806768
-a: 362799
-d: 1147612
Fd: 1859886
MFd: 73474947
a: 362799
d: 1147612
109.333µs
>
이상하게도 5초 더 빨라졌다. 왜인지 설명은 못 하겠다. 아직 더 복잡한 계획(예: 더 순진한 버전의 이 워크로드)에는 적용해 보지 않았다. 솔직히 무섭고, 최적화를 틈나는 대로 개선하는 백그라운드 작업으로 돌리고 싶다. 또한, 다중 규칙 최적화를 가르치지 못했다. 계획 접근을 재고할 필요가 있을지도.
티저: 50GB를 5GB로 줄였지만, 여전히 필요한 것보다 약 10배 많은 메모리를 쓴다. 디스크 스필을 하기 전에, 쓰레기를 스필하지 않도록 하자. 또한 1GB도 안 쓰는데 스필을 하는 건 과시처럼 보일 수 있다. 더 어려운 문제도 찾아보자.
메모리가 어디로 가는지 자세히 보면, 대부분이 낭비라는 걸 알게 된다.
워크호스 계산을 끝까지 돌리면, 다음 관계들과 사실 개수가 있다.
> .list
-M: 92806768
-a: 362799
-d: 1147612
Fd: 1859886
MFd: 73474947
a: 362799
d: 1147612
109.333µs
>
큰 건 -M이고, MFd도 꽤 크다. 둘 다 비슷한 이야기를 하니, 여기서는 -M에 집중하자.
각 컬렉션은 사실상 로그 구조적 머지-무언가(리스트)다. 즉, 길이가 직전의 두 배 이상인 리스트들의 시퀀스로 표현된다. -M의 표현을 펼쳐 레이어 길이를 출력하면 다음과 같다.
Layer size: 57289225
Layer size: 24951369
Layer size: 6406719
Layer size: 2738555
Layer size: 1040087
Layer size: 351521
Layer size: 24612
Layer size: 4550
Layer size: 130
가장 큰 것, 57,289,225 사실의 레이어에 집중하자. 다른 레이어도 비슷한 이야기를 한다.
각 레이어는 Vec<Vec<Vec<u8>>>의 컬럼형 표현이다. 사실의 리스트, 각 사실은 바이트 리스트들의 리스트. 리스트가 너무 많다. 컬럼형 레이아웃은 세 컬럼을 쓴다.
Vecs {
bounds: Vec<usize>,
values: Vecs {
bounds: Vec<usize>,
values: Vec<u8>,
}
}
바깥 bounds는 각 사실마다, 그 안에 몇 개의 항(Vec<u8>)이 있는지 나타낸다. 안쪽 bounds는 각 항마다 바이트가 몇 개인지 나타낸다. 마지막 values에는 모든 항의 모든 바이트가 들어 있다.
가장 큰 레이어는 2GB 조금 넘게 필요하다.
총합: 2,098,253,766
= 458,313,800
+ 916,627,600
+ 723,312,366
맨 끝의 실제 바이트 데이터 외에, 데이터가 아닌 정보가 많다. 이걸 어떤 경우엔 0으로 만들겠다. 우리 경우가 그중 하나다.
여러 최적화를 순차적으로 설명한다. 마지막에는 내가 시도해 보고 구현까지 한 새로운 자료구조가 나온다. 동시에, 대부분의 최적화는 기존 표현에도 적용되며, 새 표현의 이득과 쉬운 최적화의 이득을 혼동하지 않기 위해 먼저 이들부터 적용하고 싶다.
지금 고백하자면, 모든 최적화를 구현한 건 아니다. 다른 시스템에서 구현한 적 있고, 여기서도 꽤 쉽게 할 수 있을 것이다. 다만 약간의 우스꽝스러운 장난질이 필요하다. 내 눈엔 전혀 문제 없는 장난이지만, 본격적인 자료구조로 가기 전에 이런 장난을 하고 싶지는 않았다. 그런 전제하에, 시작하자.
위의 첫 큰 숫자(458,313,800)는 사실 경계를 알려 준다. 항 목록에서 어느 오프셋에서 하나의 사실이 끝나며 다음 사실이 시작하는가? 우리의 사실은 정확히 두 컬럼을 갖는다. 일반적으로, 하나의 관계에 속한 모든 사실은 동일한 컬럼 수를 갖는다.
이 컬렉션은 정확히 (0, len+1).step_by(arity)다.
경계와 길이를 기록하는 데 458,313,800 바이트가 필요하지 않다. 데이터가 등간격(strided)일 것이라고 낙관적으로 가정하는 컨테이너를 쓸 수 있다. 즉, stride와 length만 기록한다. 이 가정이 깨지면, 명시적 오프셋 기록으로 전환한다.
이 최적화는 첫 큰 숫자를 사실상 0으로 만든다.
두 번째 큰 숫자(916,627,600)는 항의 경계를 기록한다. 바이트 리스트에서 어느 오프셋에서 하나의 항이 끝나고 다음 항이 시작하는가? 우리의 항들은 .. 바이트 수가 제각각이다. 숫자의 텍스트 표현이기 때문이다. 숫자는 최대 7자리이며, 많은 항이 실제로 7자리다.
모든 항의 길이를 기록하려면 916,627,600 바이트가 필요할 수 있지만, 항이 꼭 가변 길이일 필요는 없다. 모든 항을 7바이트로 만들고, 텍스트를 0으로 패딩하면 된다. 이 시점에서 stride 최적화가 다시 동작하며, 길이와 stride 7만 기록하면 된다.
이 최적화는 두 번째 큰 숫자를 사실상 0으로 만든다.
바이트 수가 늘 수 있지만, 곧 줄일 것이다.
남아 있는 큰 숫자(723,312,366)는 모든 항의 모든 바이트를 이어 붙인 것이다. 항당 대략 7바이트, 사실당 두 항, ~57.2M 사실로 이 숫자가 된다.
항들이 7자리 이하의 숫자라는 점을 이미 봤다. 따라서 u32에 잘 들어간다. 4바이트면 된다. 항당 7바이트에서 4바이트로 내려가면,
57,289,225
* 2
* 4
---------
= 458,313,800
바이트가 된다. 이미 1.57배 감소다. 하지만 마지막 트릭이 하나 더 있다.
u32는 훌륭한 Rust 타입이지만, 우리의 숫자는 최대 7자리이므로 3 바이트에 잘 들어간다. 그리고 우리가 다루는 건 그냥 바이트 리스트다. 3은 표준 바이트 수는 아니지만 .. 신경 쓰지 말자. 캐시라인 정렬을 볼 때 신경 쓰게 될 수 있지만 .. 지금은 괜찮다.
추가로 4/3배 절감이 누적되어 2.10배가 되고, 343,735,350 바이트까지 내려간다. 총합으로 2GB에서 ~350MB까지 갔다. 대략 6.10배 감소다. 동시에, 계산은 더 쉬워졌을 가능성이 크다. 여러 경계 정보가 많았지만, 이제는 직접 계산하게 됐다.
메모리 풋프린트를 10배 줄이겠다 했고 .. 데이터를 보기 전에 썼다. 그래도 해 보자.
마지막 개선은 정렬된 사실 리스트의 첫 항(term)이 엄청나게 반복된다는 관찰에서 온다. 이해가 된다. 정렬했으니, 같은 첫 항으로 시작하는 사실 수만큼 그 첫 항의 복제가 연달아 있을 것이다. 이 첫 항을 굳이 매번 쓸 필요가 있을까?
우리가 다루는 큰 레이어에는 57,289,225개의 상이한 사실이 있지만, 첫 항(term0)은 1,147,612개만 상이하다. 사실을 (Term, Term)의 컬렉션 대신 (Term, [Term])의 컬렉션으로 쓸 수 있다. 즉, 상이한 첫 항들의 리스트와, 각 첫 항에 대응하는 두 번째 항들의 리스트. 이를 순진하게 컬럼 형태로 쓰고, usize로 bounds를 기록한다면 다음 정도의 공간이 든다.
term0.values: 1,147,612 * 3 = 3,442,836
term1.bounds: 1,147,612 * 8 = 9,180,896
term1.values: 57,289,225 * 3 = 171,867,675
-----------
총 바이트 184,491,407
가장 큰 레이어에서, 초기 2GB 대비 11.37배 감소다. 이 패턴이 전체 5GB 상태에서 유지된다면, 500MB 아래까지 내려갈 수 있다. 작은 레이어에서는 그 정도로 강하지 않을 수도 있다. 사실 밀도가 낮아 첫 항의 반복이 덜할 수 있기 때문이다. 하지만 가장 큰 레이어에서는 거의 맞고, 이 레이어들이 전체를 지배한다.
발표는 일단 여기까지 하겠다.
다음은 실제로 이걸 하는 것이다.
첫 번째 물결의 최적화가 구현되어 동작한다. 가장 큰 배치는 이제 정확히 343,735,382 바이트를 쓴다. 이론값 343,735,350과 비교하면 딱 32바이트 더다. 이는 u64 (stride, length) 쌍 두 개다. 위에서 “사실상 0”이라 했던 두 자리.
이제 계산이 더 빠르다! 시간이 95초 전후로 오르내린다. 예전 약 115초 대비 20% 단축이다. 더 할 최적화가 있다. 구현이 꽤 캐주얼하고, 프로파일러도 아직 안 돌려 봤다.
두 번째 물결의 최적화, 리스트 대신 트리로 데이터를 기록하는 것도 측정을 위해 구현됐지만, 아직 엔진을 구동하진 않는다. 가장 큰 배치의 -M 이전/이후의 분해는 다음과 같다.
이전 바이트: 343,735,382
= 16 // 각 사실은 2 항
+ 16 // 각 항은 3 바이트
+ 343,735,350 // 2 x 3 x 57289225 바이트
새 바이트: 184,491,255
= 16 // 첫 항은 하나의 리스트만
+ 16 // 각 항은 3 바이트
+ 3,442,836 // 3 x 1147612 (첫 항) 바이트
+ 9,180,696 // 8 x 1147587 (첫 항) bounds
+ 16 // 각 항은 3 바이트
+ 171,867,675 // 3 x 57289225 바이트
새 표현은 바이트 리스트의 리스트를 두 개 쓴다. 하나는 모든 상이한 첫 항의 단일 리스트(순서대로), 다른 하나는 상이한 첫 항의 개수만큼의 두 번째 항 리스트들이다. 대부분은 바이트를 기록하지만, 두 번째 컬렉션의 각 리스트 길이도 기록해야 한다. 모든 첫 항에 두 번째 항의 개수가 같은 건 아니기 때문이다. 운 좋게도 앞의 25개 리스트는 같은 길이였다. 그래서 (첫 항) 숫자가 맞지 않는다.
다음 단계는 레이어드 트라이를 본격 도입해, 조인, 병합, 중복 제거를 시도하는 것이다. 이게 들어가고, 나쁘지 않게 돌면, 옛 표현을 끄고 메모리를 더 줄일 수 있다. 레이어드 트라이는 개인적으로 흥미롭다. 이 표현으로, 이 진부한 2항 관계보다 복잡한 관계를 표현하는 법을 더 이해하고 싶기 때문이다.
대략 예고한 만큼의 공간을 쓴다. 왔다 갔다 한다. 그리고 더 빠르다! 레이어드 트라이 표현은 데이터를 더 유용한 모양(적어도 우리에게)으로 남겨 둔다. 작동 방식을 설명하고, 개선이 무엇인지 보자!
흥미를 돋우기 위해, 사과-대-사과 비교를 위해 행 지향(“toad-row”)과 열 지향(레이어드 트라이, “toad-col”)의 전후 수치를 보자.
| dataflow | httpd | psql | lnx_kernel |
|---|---|---|---|
| graspan | 684s | 8640s | 42840s* |
| toad-row | 3.88s | 11.30s | 25.67s |
| toad-col | 3.47s | 11.94s | 23.09s |
| datafrog | 1.30s | 4.06s | 8.03s |
| aliasing | httpd | psql | lnx_kernel |
|---|---|---|---|
| graspan | 8.4h | 6.0h* | 1.7h* |
| toad-row | 28.21s | 28.25s | 7.62s |
| toad-col | 19.39s | 21.96s | 9.48s |
| datafrog | UNK | UNK | UNK |
엄밀히 말해, “toad-row” 수치는 공정 비교를 위해 하나의 최적화를 묶어 뒀다. 이 최적화를 레이어드 트라이에도 도입하면, 비교표를 업데이트할 것이다.
단서를 깔았지만, 수치는 어떤 때는 낫고, 어떤 때는 못하다. 구현을 보면서 이유를 짚어 보겠지만, 행 지향이 열 지향보다 나은 경우도 늘 있다. 시간이 흐르면 둘을 하이브리드로 쓰면 좋겠지만, 지금은 레이어드 트라이, 즉 컬럼에 올인한다.
내가 처음(내레이션: 사실 마지막)이 한 일은, 행과 열 모두에 쓸 수 있는 추상화를 찾는 것이었다. 우리는 사실 컨테이너를 표현하고 싶다. FactContainer 트레이트보다 좋은 게 있을까?
/// 사실을 담고 다룰 수 있는 타입
pub trait FactContainer : Default + Sized {
/// 사실 리스트에서 컨테이너 구성
fn form(facts: &mut Facts) -> Self;
/// 컨테이너의 사실 수
fn len(&self) -> usize;
/// 사실 수가 0이면 true
fn is_empty(&self) -> bool { self.len() == 0 }
/// 담긴 각 사실에 동작 적용
fn apply<'a>(&'a self, action: impl FnMut(&[<Terms as Container>::Ref<'a>]));
/// 첫 `arity` 컬럼으로 `self`와 `other`를 조인하고, 프로젝션 결과를 `builders`에 넣는다
fn join<'a>(&'a self, other: &'a Self, arity: usize, projections: &[&[Result<usize, String>]], builders: &mut [FactBuilder<Self>]);
/// `self`에는 있지만 `others`들에는 없는 사실로 컨테이너를 만든다
fn except<'a>(self, others: impl Iterator<Item = &'a Self>) -> Self where Self: 'a;
/// `self` 또는 `other`에 있는 사실로 컨테이너를 만든다
fn merge(self, other: Self) -> Self;
}
익숙하지 않은 용어가 몇 있다. Terms 자체, Facts, FactBuilder, 그리고 일반적인 혼란. 문맥에서 메서드를 논하면 명확해질 것이다.
마지막 세 메서드는 Datalog 평가의 일꾼이다: join, except, merge. 메서드들은 대체로 사실 컨테이너 라이프사이클 순서로 적었고, 이 순서대로 보면 이야기가 잘 풀린다.
이 이름이 최선인지는 모르겠다. 아마 이미 다른 이름이 있을 수도 있다. Radix tree가 내가 들은 이름 중 가장 멋진 이름인데, 여기 버전은 레이아웃에 더 많은 의견(때로는 도움이 안 될)을 갖고 있다.
이게 무엇인지 이해하려면, 정렬된 행 지향 표현을 떠올리자. 행은 다음처럼 생겼을 수 있다.
[ a0, b0, c0 ]
[ a0, b0, c1 ]
[ a0, b1, c1 ]
[ a0, b1, c2 ]
[ a1, b0, c1 ]
[ a1, b0, c2 ]
...
첫 컬럼은 그냥 정렬되어 있다. 값이 증가하는 순서다. 위 예에서는 a0, a1 두 값만 보인다. 나머지는 다른 두 컬럼의 상세다. 두 번째 컬럼의 값은, 첫 번째 컬럼의 각 상이한 값마다 정렬되어 있다. 일반적으로, 각 컬럼의 값은, 앞선 컬럼들의 상이한 할당마다 정렬되어 있다.
중복을 억제하고, 값이 이전 행과 바뀌지 않으면 그대로라고 기록만 할 수 있다. 예컨대:
[ a0, b0, c0 ]
[ .., .., c1 ]
[ .., b1, c1 ]
[ .., .., c2 ]
[ a1, b0, c1 ]
[ .., .., c2 ]
...
각 컬럼에서, 상이한 값들과 그 값의 반복 회수를 쓸 수 있다. 그럴 수도 있지만, 우리는 유사하지만 더 다루기 쉬운 방법을 쓴다.
각 컬럼은 값 리스트들의 리스트가 된다. 각 리스트는 해당 컬럼의 상이한 값들을 정렬한 것이다. 각 리스트는 한 distinct prefix(이전 컬럼들의 설정)에 해당한다. 각 컬럼에는 일정 개수의 리스트와, 리스트 내 총 원소 수가 있다. 어떤 컬럼의 리스트 개수는, 이전 컬럼의 총 원소 수와 같다.
모니터를 시계 방향으로 90도 돌려 보면, 위 그림은 트리처럼 보인다. 각 컬럼은 트리의 한 레이어다. 고집스러워서 트리를 쓰지는 않고 컬럼만 쓰겠다. 하지만 트리 성질을 받아들이면 더 잘할 수 있다. 결과적으로 b+ 트리같은 것을 갖게 될 것이다.
이 표현은 행보다 더 압축적인 경우가 많다. 중복을 억제하기 때문이다. 또한 검색, 조인, 기타 작업이 더 효율적일 수 있다. 이전에는 [a, b, c] 행을 전체 행 리스트에서 이진 탐색했지만, 트라이는 첫 컬럼의 [a]를 상이한 값 리스트에서 찾고, 그다음 [a]에 대한 두 번째 컬럼의 상이한 값 리스트에서 b를 찾고, 그다음 [a, b]에 대한 세 번째 컬럼의 상이한 값 리스트에서 c를 찾게 한다.
이 이점은 join, except, merge에도 확장된다. 이들은 모두 여러 컬렉션을 접두(prefix)로 정렬하고 맞춰야 한다. 레이어드 트라이 형태의 두 컬렉션은 접두를 하나씩 내려가며 맞추기 쉽다. 말로 하면 두루뭉술하니, 구현을 보며 자세히 보자.
컬럼 단위로 내려가면, 매번 작은 영역만 검색하면 된다. 반대로, 처음부터 상이한 값이 많지 않다면(예: 첫 컬럼 이후는 각 컬럼마다 상이한 값이 하나뿐), 행을 통째로 보는 편이 낫다. 행이 조각조각 드러나는 비용을 감수해야 한다.
FactContainer 구현
첫 메서드는 form(&mut Facts)로, 사실 리스트에서 레이어드 트라이를 만든다. Facts 타입은 행 지향 사실 리스트이고, (지금으로서는) 사실의 시작점이다.
구현은 저장소에 있다. 약 25줄이다. 내가 말하고 싶지 않은 전문 용어가 좀 있다. 대략적으로는 행 시퀀스를 지켜보고, 각 컬럼에서 리스트를 형성한다. 각 행이 이전 행과 다른 첫 컬럼을 찾고, 그 컬럼의 리스트-작성 중인 곳에 값을 밀어넣고, 이후 컬럼들의 리스트는 밀봉한 뒤, 해당 컬럼들의 값을 새 리스트에 밀어넣는다.
꽤 직선적인 구현이다. 비용은 1. 행을 정렬하는 비용, 2. 각 행의 값을 컬럼으로 디멀티플렉싱하는 비용의 혼합이다. 행 지향 컨테이너보다 상대적으로 비싸지만, 미래를 위한 투자다.
len(&self)는 아주 쉽다. 마지막 레이어를 보고 총 값의 개수를 반환한다.
apply는 레이어드 트라이가 표현하는 각 행에 대해 action을 적용한다.
여기에는 자연스러운 재귀 방식이 있다. 트리 레이어를 하나씩 내려가며, 스택에 접두를 유지하다가 마지막 레이어에서 액션을 수행한다. 이걸 재귀를 반복으로 바꾸며 하자. 명시적 스택을 유지한다. ranges: Vec<(usize, usize)>로 각 레이어의 활성 구간을 저장하고, 리스트 끝 원소만 보며, 새 구간을 push하고 끝나면 pop한다.
/// `layer`의 `index`에서 출발해, 모든 확장에 `action` 적용
fn apply<'a>(&'a self, mut action: impl FnMut(&[<Terms as Container>::Ref<'a>])) {
if self.layers.is_empty() { return; }
// 각 레이어의 구간을 담는 콜스택
let mut ranges = Vec::with_capacity(self.layers.len() - layer);
// 각 레이어의 값. 위와 같이, push/pop한다.
let mut values = Vec::with_capacity(self.layers.len() - layer);
// 공백에서 시작해 모든 시작 값 처리
ranges.push(self.layers[0].list.bounds.bounds(0));
// `ranges`의 맨 위 작업을 반복적으로 진행
while let Some((lower, upper)) = ranges.last_mut() {
if lower < upper {
// 마지막 레이어라면, 액션을 쭉 수행
if values.len() == self.layers.len() - 1 {
let borrow = self.layers.last().unwrap().borrow();
for index in *lower .. *upper {
values.push(borrow.values.get(index));
action(&values[..]);
values.pop();
}
ranges.pop();
values.pop();
}
// 아니면, 다음 레이어의 작업을 발견하고 큐잉
else {
let depth = values.len();
let bounds = self.layers[depth+1].list.bounds.bounds(*lower);
values.push(self.layers[depth].borrow().values.get(*lower));
*lower += 1;
ranges.push(bounds);
}
}
else {
ranges.pop();
values.pop();
}
}
}
한동안 들여다볼 수 있는 코드다. 나도 그랬다. 버그가 아직 있을 수 있다. 집착하지 말고, 각 레이어에서 활발한 경계를 추적하는 스택 idiom만 가져가자.
다음 메서드는 join, except, merge다. 이들은 공통 헬퍼 메서드에 의존한다. 먼저 소개한다.
/// `self`와 `other`의 일치 접두를 `arity` 레이어까지 정렬
///
/// 각 결정적 순간에 `action`을 호출하며, 일치하지 않는 레이어의 구간도 포함한다.
/// `action`은 각 경우에 적절하게 반응할 수 있다.
fn align<'a, F>(&'a self, other: &'a Self, arity: usize, mut action: F)
where
F: FnMut(&[<C as Container>::Ref<'a>], std::cmp::Ordering, (usize, usize)),
{
unimplemented!()
}
align은 두 인스턴스(각각 최소 arity 레이어)를 받아, 길이 최대 arity의 일치 접두를 찾는다. 좀 더 구체적으로, 공집합(비어 있지 않은 입력이라면 공통)에 시작해, 각 공통 접두의 확장을 평가하며, 다음 레이어에서 일치하지 않는 범위를 발견하거나 더 깊이 들어간다. action은 입력에 공통인 접두 위에서 호출되는데, 두 번째 인자가 무엇을 발견했는지 설명한다.
Ordering::Less: 이어지는 (lower, upper)는 다음 레이어(접두 길이 바로 다음 레이어)의 값들 중, self에만 있는 값들의 구간이다.Ordering::Greater: 이어지는 (lower, upper)는 다음 레이어의 값들 중, other에만 있는 값들의 구간이다.Ordering::Equal: 길이 arity의 접두가 둘 다에 공통이며, 이어지는 정수는 arity 레이어의 최종 값들의 위치다.일치 접두를 찾으려 할 때, 첫 두 응답은 길이 끊긴 곳을 나타내고, 세 번째는 일치점을 나타낸다. 우리의 join, except, merge는 이 로직을 쓰되, 각 경우에 하는 일이 다르다.
align 구현은 apply와 매우 비슷하다. 각 레이어에서, self의 구간과 other의 구간 쌍으로 된 스택을 유지한다. 스택 맨 위의 구간 쌍을 계속 발전시키며, 두 구간이 비어 있지 않은 동안, 첫 원소들을 비교해 작은 쪽을 전진시키며 action을 호출하거나, 같으면 다음 레이어 구간을 스택에 넣거나, 마지막 레이어라면 action을 호출한다.
join은 align을 쓰며, Ordering::Equal 경우를 찾는다. 일치가 발견됐다는 뜻이고, 이때 조인 일치가 생긴다. 남은 값들을 양 입력 모두에서 펼쳐서 크로스 조인하면 된다. 현재 구현(내가 사랑하진 않는다)은 다음과 같다.
// `self`와 `other`의 `arity` 이후 확장을 담아둘 공간
let mut extensions0: Vec<<Terms as Container>::Ref<'a>> = Vec::with_capacity(self.layers.len() - arity);
let mut extensions1: Vec<<Terms as Container>::Ref<'a>> = Vec::with_capacity(other.layers.len() - arity);
self.align(other, arity, |prefix, order, (index0, index1)| {
if let std::cmp::Ordering::Equal = order {
// TODO: 어떤 프로젝션에도 참조되지 않는 컬럼은 미리 제거
self.apply_core(arity, index0, |list| Extend::extend(&mut extensions0, list.into_iter().cloned()));
other.apply_core(arity, index1, |list| Extend::extend(&mut extensions1, list.into_iter().cloned()));
extensions0.sort(); extensions0.dedup();
extensions1.sort(); extensions1.dedup();
let width0 = self.layers.len() - arity;
let width1 = other.layers.len() - arity;
assert!(extensions0.len() / width0 > 0);
assert!(extensions1.len() / width1 > 0);
// TODO: 빌더 우선, 그다음 컬럼, 마지막으로 행 순으로 로직을 피벗
for idx0 in 0 .. (extensions0.len() / width0) {
let ext0 = &extensions0[idx0 * width0 ..][.. width0];
for idx1 in 0 .. (extensions1.len() / width1) {
let ext1 = &extensions1[idx1 * width1 ..][.. width1];
for (projection, builder) in projections.iter().zip(builders.iter_mut()) {
builder.push(projection.iter().map(|i| match i {
Ok(col) => {
if *col < arity { prefix[*col].as_slice() }
else if *col < arity + ext0.len() { ext0[col - arity].as_slice() }
else { ext1[col - ext0.len() - arity - arity].as_slice() }
}
Err(lit) => lit.as_bytes()
}));
}
}
}
// 정리
extensions0.clear();
extensions1.clear();
}
});
여기서 교묘한 건 수정된 apply를 호출한다는 점이다. arity 컬럼 이후의 index에서 시작해, apply가 전체 컬렉션을 읽는 것처럼 확장을 읽어낸다. 그 외에는 행 지향 구현과 매우 유사하다. 일치마다 모든 확장을 찾고, 어떤 컬럼을 어떤 빌더에 넣을지 지시를 따른다.
안쪽 루프에 조건 로직이 많은 게 썩 마음에 들지 않는다. 성능을 더 개선할 기회일 것 같다. 지켜보자.
except는 self에는 있지만 다른 인자 리스트에는 없는 튜플들로 이뤄진 컬렉션을 만든다. 다른 컨테이너를 순회하며, 각 컨테이너에 대해 이항 except를 호출하고 그 결과로 self를 대체한다. 이항 except는 align을 사용하고, 특히 self에만 있는 튜플들을 찾는다.
/// `others`에 없는 `self`의 모든 것을 담은 forest 생성
fn except<'a>(mut self, others: impl Iterator<Item = &'a Self>) -> Self where Self: 'a {
for other in others {
let old_len = self.len();
assert_eq!(self.layers.len(), other.layers.len());
let mut builder = TrieBuilder::with_layers(self.layers.len());
self.align(other, self.layers.len(), |prefix, order, (lower, upper)| {
if let std::cmp::Ordering::Less = order {
builder.graft(prefix, lower, upper, &self.layers[prefix.len()..]);
}
});
self = builder.done();
}
self
}
여기 또 새 코드가 있다. 이번엔 graft 메서드가 있는 TrieBuilder다. 레이어드 트라이에 특화된 빌더로, 접두와 남은 레이어에서 복사해 넣을 시작 위치를 받는다. 접두와 확장은 모두 정렬되어 있다. 우리는 self를 순서대로 훑고 있으니 당연하다. 빌더는 인수를 이어 붙여 새 레이어드 트라이를 만든다.
이 버전은 다른-다른으로 돈다. 행 구현은 한 번에 다 했다. 둘의 큰 차이는 없으리라 본다. 쓰기 쉬운 이 쪽을 먼저 썼다. 문제가 된다면 더 조사해 보겠다.
마지막으로, merge도 align을 쓰며, except와 매우 비슷하지만 각 경우에 다른 결정을 내린다.
fn merge(self, other: Self) -> Self {
if self.is_empty() { return other; }
if other.is_empty() { return self; }
let mut builder = TrieBuilder::with_layers(self.layers.len());
self.align(&other, self.layers.len(), |prefix, order, (lower, upper)| {
match order {
std::cmp::Ordering::Less => {
builder.graft(prefix, lower, upper, &self.layers[prefix.len()..]);
}
std::cmp::Ordering::Equal => {
builder.graft(prefix, lower, lower+1, &self.layers[prefix.len()..]);
}
std::cmp::Ordering::Greater => {
builder.graft(prefix, lower, upper, &other.layers[prefix.len()..]);
}
}
});
builder.done()
}
아주 비슷하다. 이번에는 언제나 빌더에 내용을 밀어 넣는다. 배울 수 있는 관점은, 영역이 배타적일 때는 복사하고, 정확한 일치가 발견되면 한 번만 복사한다는 점이다. 만약 튜플의 의미가 “존재”보다 더 부하를 견디는 것(aggregates)이라면, 일치 접두에서 self와 other의 값을 합칠 수도 있다.
이게 우리가 써야 할 모든 로직이다! 이 코드가 있으면, 행 컨테이너와 컬럼 컨테이너를 간단한 토글로 바꿔 돌릴 수 있다. 모든 것이 제대로 돌아가고, 올바른 답을 생산하는 것 같다. 문제는, 내가 쓰는 워크로드가 제한적이라는 것이다. 모든 질의가 하나의 공유 속성으로 이항 조인을 한다. 더 광범위한 테스트가 필요하지만, 일단 성능과 다음을 이야기하자!
위에서 원시 수치를 봤지만, 시간은 어디에 쓰이는지, 고칠 수 있는지 말해 보자. 나도 아직 답을 모른다. 그냥 흐지부지될 수도 있다. 그럴 경우에도 이미 몇 가지 성능 이득이 있었고, 메모리를 반으로 줄였다. 훌륭하다. 트라이는 최악 경우 최적 조인의 첫걸음이기도 하다. 곧!
내가 처음 본 성능 요인은, 많은 [u8]이 실제로 [u8; 4]라는 점을 알게 됐을 때다. 고정 폭으로 바꿀 수 있는 기회가 있으면, 성능이 극적으로 개선된다. 대략적으로, 가변 길이 텍스트에서 u32로 돌아가는 것과 비슷하다.
레이어드 트라이에, 레이어 리스트를 [u8; 4] 타입으로 upgrade하는 메서드를 추가했다. 전부 정확히 그 길이를 가지면 가능하다. 반대로 downgrade 메서드도 추가했다. Vec<[u8;4]>를 Vec<u8>로 바꾸는 일이라 더 어렵다. 원론적으로는 std::mem::transmute로 쉽게 할 수 있지만, unsafe는 싫어서 flatten().collect()로 했다.
이 동작을 except와 merge에는 쉽게 적용했다. .. 그런데 join이 약간 더 어렵다. 타입이 맞다고 Rust를 설득하기가 어렵다. 내가 100% 올바른 타입을 갖고 있지 않기 때문이고, Rust는 그걸 말하기를 좋아한다. 하지만 except와 merge만으로도 성능이 개선된다!
같은 최적화를 갖춘 행 지향 버전 수치도 포함했다(전에 봉인했던 것). except는 복잡해서 최적화하지 못했다.
| dataflow | httpd | psql | lnx_kernel |
|---|---|---|---|
| graspan | 684s | 8640s | 42840s* |
| toad-row | 3.88s | 11.30s | 25.67s |
| ^-- +opt | 3.11s | 9.49s | 19.83s |
| toad-col | 3.47s | 11.94s | 23.09s |
| ^-- +opt | 2.55s | 9.13s | 15.95s |
| datafrog | 1.30s | 4.06s | 8.03s |
| aliasing | httpd | psql | lnx_kernel |
|---|---|---|---|
| graspan | 8.4h | 6.0h* | 1.7h* |
| toad-row | 28.21s | 28.25s | 7.62s |
| ^-- +opt | 23.31s | 23.08s | 6.73s |
| toad-col | 19.39s | 21.96s | 9.48s |
| ^-- +opt | 14.26s | 16.45s | 8.33s |
| datafrog | UNK | UNK | UNK |
보듯이, 최적화는 행과 열 모두에 도움이 된다. 여기에 나타나지 않은 건, 장기적으로 최적화가 컬럼에 훨씬 더 도움이 될 것이라는 점이다. 컬럼별로 최적화할 수 있기 때문이다. 각 컬럼마다 [u8; K]인지 K만 찾으면 된다. 반면 행에서는 각 행이 [[u8; K]]가 되게 하는 하나의 K를 찾아야 한다. 어떤 컬럼은 고정 폭일 것이고, 어떤 컬럼은 텍스트, JSON 등 덜 우호적일 것이다.
지금은, 시간의 약 2/3가 join에 쓰인다. 여기를 더 최적화해 2배 정도는 더 얻을 수 있다고 본다. 아이디어는 좀 있다(위에서 몇 가지 언급). 하지만 아직 보고할 만한 건 없다. 아니, 내가 대충 내부 루프 순서를 바꿔 봤더니, 측정 가능한 개선이 없었다는 보고는 가능하다. 앗.
티저: 사실을 담고 있는 우리의 columnar 스토어는 상대적으로 적은 개수의 큰 할당들 위에 있다. 생성할 때 메모리가 아니라 파일에 쓸 수 있고, 그 결과를 메모리 매핑해 사용할 수 있다.
티저: 우리의 조인, 중복 제거, 중복 여부 체크는 모두 키의 동등성에 기반한다. 키와 그 키에 붙은 데이터를 여러 워커로 분산할 수 있다. 심지어 이를 위한 올바른 라이브러리(timely_communication)도 있어, 다중 프로세스로 스케일아웃할 수 있다.
티저: 우리의 조인은 모두 이항 조인과 물질화된 출력에 기반한다. 적절한 인덱스가 이미 있다면, 조인의 다중 선형성(multilinearity)을 이용해 내부 상태를 물질화하지 않는 계획을 만들 수 있다. 최악 경우 최적 조인도 여기서 하려던 것 같다.
티저: datafrog이 컴파일 타임에 접근했던 것에 우리가 접근하지 못해 생긴 코드상의 순간들을 더 깊이 파 보자. 우리의 데이터가 같은 레이아웃을 갖는다는 점을 이용해 Rust가 어떤 구현이 여전히 괜찮다는 걸 눈치채도록 도와주면, 성능을 꽤 회수할 수 있으리라 조심스럽게 낙관한다. 아니면, 뭔가 배우게 될 것이다.
우리의 메모리 최적화, 모든 항의 같은 크기 사용이, 인상적인 계산 최적화를 이끈다.
메모리 최적화는, 모든 항의 바이트 길이가 B이고, 한 관계의 모든 사실이 같은 항의 개수 T를 갖는다면, 관계 뒤의 Vec<u8>을 Vec<[[u8; B]; T]>로 볼 수 있다는 점이다. 데이터의 모양에 대한 모든 “미스터리”가 사라지고, Rust가 경계·길이 등을 조심스럽게 검사하는 데 쓰던 시간을 되찾는다.
특히 비교가 상당히 싸진다.
datatoad에서 비교를 어디서 하나? 거의 어디서나 한다.
이는 사실 라이프사이클 순서이기도 하고, “비교 밀도” 내림차순이기도 하다. 정렬은 비교를 많이 한다. 병합은 선형 비교, 조인과 반조인은 큰 데이터셋을 훑지 않고 건너뛴다.
정렬을 빠르게 하면 무슨 멋진 일이 생길까?
두 작업과 세 데이터셋에 대해 기준선을 얻자. 이 과정에서, 항당 3바이트 가정은 뒤로 물리고 4바이트로 올라갔다. 어떤 입력에는 1,600만을 넘는 값이 있다. 하지만 책임있는 느낌이 들어서 기분은 좋다.
위에서 복붙하면, “데이터플로” 작업에 대한 유효 비교는 다음과 같다.
| dataflow | httpd | psql | lnx_kernel |
|---|---|---|---|
| graspan | 684s | 8640s | 42840s* |
| datatoad | 7.44s | 17.26s | 42.25s |
| datafrog | 1.30s | 4.06s | 8.03s |
“별칭” 작업에 대해서는, 우리가 같은 일을 하는지 덜 확실하다. 게다가 손으로 최적화도 했다. psql은 linux처럼 여러 파일이 있다. 가장 큰 것을 쓴다. 또한, 이 문제의 datafrog 프로그램은 없다. datafrog 프로그램을 쓰는 일이 고역이기 때문이다. 사실 우리가 이 모든 걸 하는 이유이기도 하다.
| aliasing | httpd | psql | lnx_kernel |
|---|---|---|---|
| graspan | 8.4h | 6.0h* | 1.7h* |
| datatoad | 101.24s | 96.36s | 20.20s |
| datafrog | UNK | UNK | UNK |
Graspan과의 속도 차이에 너무 들뜨지 말자. 왜 큰지는 모르겠다. 중요한 건 출발점이 딱딱하냐 물렁하냐가 아니라, 우리가 성능 면에서 좌초된 바깥쪽에 있지는 않다는 증거다.
사실은 Vec<Term>로 시작한다. 각 Term은 Vec<u8>이다. 일단 100만 사실을 모으면(임의의 임계값, 재고 가치가 있음), 그 리스트를 정렬하고 중복을 제거한다.
보통은 다음처럼 정렬과 중복 제거를 한다.
fn from(facts: &mut InternalContainer) -> Self {
let mut ordered = InternalContainer::default();
let borrowed = <InternalContainer as Container<Fact>>::borrow(facts);
let mut items = borrowed.into_index_iter().collect::<Vec<_>>();
items.sort();
items.dedup();
ordered.extend(items);
use columnar::Clear;
facts.clear();
Self { ordered }
}
요지는, 사실들에 대한 참조를 모아 리스트로 만들고, 그 리스트를 정렬하고 중복을 제거한다는 것이다. 좋은 정렬 알고리즘과 달리 데이터의 국소성을 높이기 위해 데이터 자체를 옮기지 않는다는 점이 성능상 어색하다. 게다가 여기서는 컬럼형 사실/항/바이트, 모두 가변 길이다. 데이터를 효율적으로 재배치하는 방법(기수 정렬?)이 명확하지 않다.
하지만, 우리가 이미 논의한 특수 케이스가 있다. 사실 공통 자리수와 항 공통 바이트 길이가 알려진 경우다. 그런 상황을 감지하면, .. 그리고 상수를 프로그램에 미리 베이킹해 두면, 좋은 일이 생긴다. 함수 맨 위에 다음 코드를 넣자.
if let (Some(2), Some(4)) = (facts.bounds.strided(), facts.values.bounds.strided()) {
let len = unsafe {
let temp: &mut Vec<[u8; 8]> = std::mem::transmute(&mut facts.values.values);
temp.set_len(temp.len() / 8);
temp.sort();
temp.dedup();
temp.set_len(temp.len() * 8);
temp.len() as u64
};
facts.bounds.bounds[1] = len / 8;
facts.values.bounds.bounds[1] = len / 4;
return Self { ordered: std::mem::take(facts) }
}
오 세상에, unsafe가 파티에 와 있다.
여기서 하는 일은 Vec<u8>을 Vec<[u8; 8]>로 재캐스팅하는 것이다. 바이트가 8바이트 블록으로 온다는 걸 “안다”. 이 변환 없이 정렬과 중복 제거를 하는 더 좋은 방법을 모르겠다. [[T]::as_chunks_mut](https://doc.rust-lang.org/std/primitive.slice.html#method.as_chunks_mut)로 안전하게 정렬할 순 있다. 하지만 여전히 중복 제거가 필요하고, 그건 Vec이 필요한 것 같다. 고작 슬라이스 덮어쓰기로 안전한 중복 제거를 하고, 마지막에 Vec<u8>를 truncate하는 식으로 쓸 수도 있겠다. 아마 시도해 보겠다. unsafe를 피하기 위해서.
하지만 지금은, 어떤 일이 생기는지 보자! 원래 datatoad 수치와 정렬 개선의 향상을 보자. 먼저 데이터플로:
| dataflow | httpd | psql | lnx_kernel |
|---|---|---|---|
| dt-orig | 7.44s | 17.26s | 42.25s |
| dt-sort | 4.99s | 13.55s | 32.15s |
| datafrog | 1.30s | 4.06s | 8.03s |
그리고 별칭:
| aliasing | httpd | psql | lnx_kernel |
|---|---|---|---|
| dt-orig | 101.24s | 96.36s | 20.20s |
| dt-sort | 52.99s | 53.19s | 11.20s |
| datafrog | UNK | UNK | UNK |
꽤 큰 개선이다. 이렇게 큰 비율로 시간을 계속 깎을 수 있다면, 금방 훌륭한 상태가 될 것이다. 효과는 더 복잡한 별칭 분석에서 더 두드러진다. 더 많은 데이터를 움직이는 듯하다.
이건 주로 정렬 리스트 수를 제한하려는 목적이다. 조인하거나 기존 레코드에 대해 필터링해야 할 때, 적은 수의 패스만 돌면 된다.
원래 병합 코드는 그리 복잡하지 않다. 여기에 복사하지는 않겠다. 대신 함수 머리에서 비슷한 최적화 감지를 해 보자. 바르게 정렬된 입력을 찾는다.
if let (Some(2), Some(4)) = (self.ordered.bounds.strided(), self.ordered.values.bounds.strided()) {
if let (Some(2), Some(4)) = (other.ordered.bounds.strided(), other.ordered.values.bounds.strided()) {
let mut ordered = InternalContainer::default();
ordered.values.values = self.ordered.values.values.iter().chain(other.ordered.values.values.iter()).copied().collect::<Vec<_>>();
let len = unsafe {
let temp: &mut Vec<[u8; 8]> = std::mem::transmute(&mut ordered.values.values);
temp.set_len(temp.len() / 8);
temp.sort();
temp.dedup();
temp.set_len(temp.len() * 8);
temp.len() as u64
};
ordered.bounds.clear();
ordered.bounds.bounds[0] = 2;
ordered.bounds.bounds[1] = len / 8;
ordered.values.bounds.clear();
ordered.values.bounds.bounds[0] = 4;
ordered.values.bounds.bounds[1] = len / 4;
return Self { ordered };
}
}
이 케이스는 좀 더 복잡하다. 출력을 만들어야 하므로 stride와 길이를 정확히 설정해야 한다. 그 외에는 병합을 “붙이고 정렬하고 중복 제거”로 구현한다. 원래 병합보다 훨씬 덜 정교하다. 하지만 동작한다.
먼저 데이터플로:
| dataflow | httpd | psql | lnx_kernel |
|---|---|---|---|
| dt-orig | 7.44s | 17.26s | 42.25s |
| dt-sort | 4.99s | 13.55s | 32.15s |
| dt-both | 3.71s | 11.23s | 23.58s |
| datafrog | 1.30s | 4.06s | 8.03s |
그리고 별칭:
| aliasing | httpd | psql | lnx_kernel |
|---|---|---|---|
| dt-orig | 101.24s | 96.36s | 20.20s |
| dt-sort | 52.99s | 53.19s | 11.20s |
| dt-both | 31.32s | 30.08s | 8.56s |
| datafrog | UNK | UNK | UNK |
그리 많은 코드도 아닌데 꽤 괜찮은 개선이다. 이들은 모든 항의 공통 길이에 크게 의존한다. 타이핑된 원시 데이터에서는 의미가 있지만, 다시 문자열을 쓰기 시작하면 통하지 않을 것이다.
비교를 쓰는 곳이 두 군데 더 있다. 조인과 반조인(옛 사실 필터링)이다.
프로파일을 보면, 이들이 시간의 30% 정도일 수 있다. 제거할 가치가 충분하다. 혹은 그럴 것이다. 다만 우리는 이제 자료구조를 트라이 기반으로 갈아엎으려 한다. 그렇게 되면, 같은 최적화 기회를 눈여겨볼 것이다. 확실히 존재한다. 다만 컬럼 단위로 적용되며, 행 단위로 “모든 항의 같은 길이”보다 성립 가능성이 높다.
datafrog의 컴파일된 성능까지는 아직 못 갔다. 아마 미래에도 이 주제로 돌아올 것이다. 우리가 방금 한 뻔뻔한 장난 정도는 허용한다면, 같은 성능을 내지 못할 이유가 없다. 프로파일링을 하면, datatoad가 datafrog에는 없는 어떤 일을 하는지 드러날 것이다. 우리의 계산 커널들은 모두 약간의 unsafe로 맞춰질 수 있을 것 같다.
개인적으로는 먼저 unsafe 없이 안전한 바이트 셔플로 바꾸고, 안전하지만 정당화되지 않은 벡터 truncate로 마무리해 볼 생각이다. Unsafe 코드는 최악이다. 모두 피하자.
티저: “추이 폐쇄(transitive closure)” 계산을 감지하고 강연결요소 분해로 특화하는 아이디어에 꽂혀 있다. 규칙에서 읽어 낼 수 있는 동치 관계에도 비슷한 일을 할 수 있고, 그때는 예컨대 유니온-파인드 자료구조를 쓰면 된다. 또한 bddbddb, 바이너리 결정 다이어그램(BDD) 중심의 데이터베이스 얘기도 하고 싶다. 이건 factorized databases로도 이어진다. 아직 그 얘기를 안 했다면.
demand transform. 아직 100% 확신을 갖고 이해하진 못했다. 하지만 이해해야 한다. Datalog으로 데이터를 인터랙티브하게 탐색하려면 이걸 쓰고 싶을 것이다.