use crate::{
transaction::{CommitRecord, PublishedState},
Error, Result,
};
use serde::{de::DeserializeOwned, Deserialize, Serialize};
use std::{
fs::{self, File, OpenOptions},
io::{Read, Seek, SeekFrom, Write},
path::{Path, PathBuf},
};
const FORMAT: u32 = 4;
const MAGIC: &[u8; 8] = b"GFLOG001";
const END: &[u8; 8] = b"GFCOMMIT";
const HEADER: usize = 24;
const MAX_RECORD: usize = 64 * 1024 * 1024;
#[derive(Debug)]
pub(crate) struct Disk {
pub directory: PathBuf,
pub next_commit_id: std::sync::Mutex<Option<u64>>,
}
#[derive(Debug)]
pub(crate) struct FileGuard(File);
impl Drop for FileGuard {
fn drop(&mut self) {
let _ = self.0.unlock();
}
}
#[derive(Serialize, Deserialize)]
struct Manifest {
database_id: [u8; 16],
version: u32,
generation: u64,
commit_seq: u64,
next_id: u64,
obsolete: Vec<u64>,
}
#[derive(Serialize, Deserialize)]
struct Snapshot<T> {
database_id: [u8; 16],
version: u32,
generation: u64,
commit_seq: u64,
value: T,
}
#[derive(Serialize, Deserialize)]
pub(crate) enum LogRecord {
Header {
version: u32,
database_id: [u8; 16],
generation: u64,
base_seq: u64,
},
Reserve {
next_id: u64,
},
Commit(CommitRecord),
}
impl Disk {
pub fn acquire_ownership(&self) -> Result<FileGuard> {
let file = lock_file(&self.directory.join("lifecycle.lock"))?;
match file.try_lock() {
Ok(()) => (),
Err(std::fs::TryLockError::WouldBlock) => {
return Err(Error::DatabaseInUse(self.directory.clone()));
}
Err(std::fs::TryLockError::Error(e)) => return Err(e.into()),
}
Ok(FileGuard(file))
}
pub fn commit_lock(&self) -> Result<FileGuard> {
let file = lock_file(&self.directory.join("commit.lock"))?;
file.lock()?;
Ok(FileGuard(file))
}
pub fn initialize(&self) -> Result<()> {
if self.directory.join("MANIFEST").exists() {
match fs::remove_file(self.directory.join("INIT")) {
Ok(()) => sync_directory(&self.directory)?,
Err(e) if e.kind() == std::io::ErrorKind::NotFound => (),
Err(e) => return Err(e.into()),
}
return Ok(());
}
let mut has_initial_files = false;
for entry in fs::read_dir(&self.directory)? {
let name = entry?.file_name();
let name = name.to_string_lossy();
if !(name == "commit.lock"
|| name == "lifecycle.lock"
|| name == "MANIFEST.tmp"
|| name == "catalog-0.snapshot"
|| name == "data-0.snapshot"
|| name == "wal-0.log"
|| name == "INIT")
{
return Err(Error::Corrupt(
"manifest missing from nonempty database directory".into(),
));
}
has_initial_files |= name != "commit.lock" && name != "lifecycle.lock";
}
let marker = self.directory.join("INIT");
let database_id = if marker.exists() {
read_document(&marker)?
} else {
if has_initial_files {
return Err(Error::Corrupt(
"manifest missing without initialization marker".into(),
));
}
let mut id = [0; 16];
File::open("/dev/urandom")?.read_exact(&mut id)?;
write_document(&marker, &id)?;
sync_directory(&self.directory)?;
id
};
failpoint("init_marker");
self.install_checkpoint(&PublishedState::initial(), database_id, 0, Vec::new())?;
fs::remove_file(marker)?;
sync_directory(&self.directory)
}
pub fn load(&self) -> Result<(PublishedState, u64)> {
let manifest: Manifest = read_document(&self.directory.join("MANIFEST"))?;
check_version(manifest.version)?;
if manifest.obsolete.iter().any(|g| *g >= manifest.generation) {
return Err(Error::Corrupt("invalid obsolete file generation".into()));
}
let catalog: Snapshot<_> =
read_document(&self.path("catalog", manifest.generation, "snapshot"))?;
let data: Snapshot<_> = read_document(&self.path("data", manifest.generation, "snapshot"))?;
for (identity, version, generation, seq) in [
(
catalog.database_id,
catalog.version,
catalog.generation,
catalog.commit_seq,
),
(
data.database_id,
data.version,
data.generation,
data.commit_seq,
),
] {
check_version(version)?;
if identity != manifest.database_id
|| generation != manifest.generation
|| seq != manifest.commit_seq
{
return Err(Error::Corrupt(
"checkpoint components have different watermarks".into(),
));
}
}
let mut state = PublishedState {
commit_seq: manifest.commit_seq,
next_id: manifest.next_id,
catalog: catalog.value,
storage: data.value,
};
state.validate()?;
let mut log = OpenOptions::new().read(true).write(true).open(self.path(
"wal",
manifest.generation,
"log",
))?;
let header = read_frame(&mut log, false)?
.ok_or_else(|| Error::Corrupt("missing WAL header".into()))?;
match serde_json::from_slice::<LogRecord>(&header)? {
LogRecord::Header {
version,
database_id,
generation,
base_seq,
} if database_id == manifest.database_id
&& generation == manifest.generation
&& base_seq == manifest.commit_seq =>
{
check_version(version)?
}
_ => {
return Err(Error::Corrupt(
"WAL identity or checkpoint watermark mismatch".into(),
))
}
}
let mut valid_end = log.stream_position()?;
while let Some(payload) = read_frame(&mut log, true)? {
match serde_json::from_slice::<LogRecord>(&payload)? {
LogRecord::Header { .. } => {
return Err(Error::Corrupt("unexpected WAL header".into()))
}
LogRecord::Reserve { next_id } => {
if next_id <= state.next_id {
return Err(Error::Corrupt("ID reservation regressed".into()));
}
state.next_id = next_id;
}
LogRecord::Commit(record) => {
state = state.apply(&record)?;
}
}
valid_end = log.stream_position()?;
}
if valid_end != log.metadata()?.len() {
log.set_len(valid_end)?;
}
log.sync_all()?;
inject_io_error("recovery_directory_sync")?;
sync_directory(&self.directory)?;
self.check_graph_files(&state)?;
Ok((state, manifest.generation))
}
pub fn append(&self, generation: u64, record: &LogRecord) -> Result<()> {
let graph_commit = matches!(record, LogRecord::Commit(commit) if commit.storage.iter().any(|change| matches!(change, crate::storage::StorageChange::ReplaceParquet { .. } | crate::storage::StorageChange::BufferGraph { .. })));
let payload = serde_json::to_vec(record)?;
let bytes = encode_frame(&payload)?;
serde_json::from_slice::<LogRecord>(&payload).map_err(|error| {
Error::UnsupportedFeature(format!("WAL record cannot be recovered: {error}"))
})?;
let mut file = OpenOptions::new()
.append(true)
.open(self.path("wal", generation, "log"))?;
let write = (|| -> std::io::Result<()> {
file.write_all(&bytes[..HEADER])?;
failpoint("wal_header");
if graph_commit {
failpoint("parquet_wal_header");
failpoint("memtable_wal_header");
}
file.write_all(&bytes[HEADER..bytes.len() - END.len()])?;
failpoint("wal_payload");
if graph_commit {
failpoint("parquet_wal_payload");
failpoint("memtable_wal_payload");
}
file.write_all(END)?;
failpoint("wal_commit");
if graph_commit {
failpoint("parquet_wal_commit");
failpoint("memtable_wal_commit");
}
inject_io_error("wal_sync")?;
if graph_commit {
inject_io_error("parquet_wal_sync")?;
inject_io_error("memtable_wal_sync")?;
}
file.sync_all()?;
failpoint("wal_sync");
if graph_commit {
failpoint("parquet_wal_sync");
failpoint("memtable_wal_sync");
}
Ok(())
})();
write.map_err(Error::CommitUnknown)
}
pub fn checkpoint(&self, state: &PublishedState, old_generation: u64) -> Result<u64> {
let old: Manifest = read_document(&self.directory.join("MANIFEST"))?;
if old.generation != old_generation {
return Err(Error::Corrupt(
"checkpoint generation changed under commit lock".into(),
));
}
let mut obsolete = old.obsolete;
obsolete.retain(|g| {
[
("catalog", "snapshot"),
("data", "snapshot"),
("wal", "log"),
]
.iter()
.any(|(p, s)| self.path(p, *g, s).try_exists().unwrap_or(true))
});
obsolete.push(old_generation);
let generation = old_generation
.checked_add(1)
.ok_or_else(|| Error::InvalidDefinition("checkpoint generation exhausted".into()))?;
self.install_checkpoint(state, old.database_id, generation, obsolete)?;
self.reclaim_graph_files(state)?;
Ok(generation)
}
fn install_checkpoint(
&self,
state: &PublishedState,
database_id: [u8; 16],
generation: u64,
obsolete: Vec<u64>,
) -> Result<()> {
write_document(
&self.path("catalog", generation, "snapshot"),
&Snapshot {
database_id,
version: FORMAT,
generation,
commit_seq: state.commit_seq,
value: &state.catalog,
},
)?;
failpoint("checkpoint_catalog");
write_document(
&self.path("data", generation, "snapshot"),
&Snapshot {
database_id,
version: FORMAT,
generation,
commit_seq: state.commit_seq,
value: &state.storage,
},
)?;
failpoint("checkpoint_data");
write_document(
&self.path("wal", generation, "log"),
&LogRecord::Header {
version: FORMAT,
database_id,
generation,
base_seq: state.commit_seq,
},
)?;
sync_directory(&self.directory)?;
let manifest = Manifest {
database_id,
version: FORMAT,
generation,
commit_seq: state.commit_seq,
next_id: state.next_id,
obsolete,
};
let temp = self.directory.join("MANIFEST.tmp");
write_document(&temp, &manifest)?;
fs::rename(temp, self.directory.join("MANIFEST"))?;
failpoint("manifest_rename");
sync_directory(&self.directory)?;
failpoint("manifest_sync");
self.cleanup(&manifest);
Ok(())
}
fn cleanup(&self, manifest: &Manifest) {
for generation in &manifest.obsolete {
if *generation >= manifest.generation {
continue;
}
for (prefix, suffix) in [
("catalog", "snapshot"),
("data", "snapshot"),
("wal", "log"),
] {
let _ = fs::remove_file(self.path(prefix, *generation, suffix));
failpoint("cleanup");
}
}
let _ = sync_directory(&self.directory);
}
fn path(&self, prefix: &str, generation: u64, suffix: &str) -> PathBuf {
self.directory
.join(format!("{prefix}-{generation}.{suffix}"))
}
pub(crate) fn publish_main_snapshot(&self, state: &PublishedState) -> Result<()> {
let parent = self.read_ref("main")?;
if let Some(id) = parent {
if same_snapshot(&self.read_commit(id)?.state, state) {
return Ok(());
}
}
let id = self.allocate_commit_id()?;
self.write_commit(id, None, state)?;
self.write_ref("main", id)
}
pub(crate) fn ensure_main_snapshot(&self, state: &PublishedState) -> Result<u64> {
if let Some(id) = self.read_ref("main")? {
if same_snapshot(&self.read_commit(id)?.state, state) {
return Ok(id);
}
}
self.publish_main_snapshot(state)?;
self.read_ref("main")?
.ok_or_else(|| Error::Corrupt("main branch snapshot missing".into()))
}
pub(crate) fn read_ref(&self, name: &str) -> Result<Option<u64>> {
let path = self.refs_dir().join(name);
if !path.exists() {
return Ok(None);
}
Ok(Some(read_document(&path)?))
}
pub(crate) fn list_refs(&self) -> Result<Vec<(String, u64)>> {
let dir = self.refs_dir();
if !dir.exists() {
return Ok(Vec::new());
}
let mut refs = Vec::new();
for entry in fs::read_dir(&dir)? {
let entry = entry?;
let name = entry.file_name();
let Some(name) = name.to_str() else {
continue;
};
if name.ends_with(".tmp") || name.starts_with('.') {
continue;
}
refs.push((name.to_owned(), read_document(&entry.path())?));
}
refs.sort();
Ok(refs)
}
pub(crate) fn write_ref(&self, name: &str, commit: u64) -> Result<()> {
let dir = self.refs_dir();
fs::create_dir_all(&dir)?;
let temporary = dir.join(format!("{name}.tmp"));
write_document(&temporary, &commit)?;
sync_directory(&dir)?;
fs::rename(&temporary, dir.join(name))?;
if name != "main" {
failpoint("branch_ref_rename");
inject_io_error("branch_ref_sync")?;
}
sync_directory(&dir)?;
sync_directory(&self.directory)?;
if name != "main" {
failpoint("branch_ref_sync");
}
Ok(())
}
pub(crate) fn read_commit(&self, id: u64) -> Result<StoredCommit> {
let mut next = id;
let mut seen = std::collections::BTreeSet::new();
let mut deltas = Vec::new();
let mut tip_parent = None;
let mut state = loop {
if !seen.insert(next) {
return Err(Error::Corrupt("branch commit cycle".into()));
}
match read_document::<StoredCommitRecord>(&self.commit_path(next))? {
StoredCommitRecord::Snapshot(snapshot) => {
if next == id {
tip_parent = snapshot.parent;
}
snapshot.state.validate()?;
break snapshot.state;
}
StoredCommitRecord::Delta {
parent,
next_id,
record,
} => {
if next == id {
tip_parent = Some(parent);
}
deltas.push((next_id, record));
next = parent;
}
}
};
for (next_id, record) in deltas.into_iter().rev() {
if next_id < state.next_id {
return Err(Error::Corrupt("branch IDs regressed".into()));
}
state.next_id = next_id;
state = state.apply(&record)?;
}
Ok(StoredCommit {
parent: tip_parent,
state,
})
}
pub(crate) fn write_commit(
&self,
id: u64,
parent: Option<u64>,
state: &PublishedState,
) -> Result<()> {
let dir = self.commits_dir();
fs::create_dir_all(&dir)?;
let path = self.commit_path(id);
if path.exists() {
return Err(Error::Corrupt(format!("commit {id} already exists")));
}
write_document(
&path,
&StoredCommitRecord::Snapshot(StoredCommit {
parent,
state: state.clone(),
}),
)?;
sync_directory(&dir)?;
sync_directory(&self.directory)?;
Ok(())
}
pub(crate) fn write_branch_delta(
&self,
id: u64,
parent: u64,
next_id: u64,
record: CommitRecord,
) -> Result<()> {
let dir = self.commits_dir();
fs::create_dir_all(&dir)?;
let path = self.commit_path(id);
if path.exists() {
return Err(Error::Corrupt("branch commit already exists".into()));
}
let delta = StoredCommitRecord::Delta {
parent,
next_id,
record,
};
let payload = serde_json::to_vec(&delta)?;
serde_json::from_slice::<StoredCommitRecord>(&payload)?;
write_document(&path, &delta)?;
failpoint("branch_delta_write");
sync_directory(&dir)?;
sync_directory(&self.directory)?;
failpoint("branch_delta_sync");
Ok(())
}
pub(crate) fn allocate_commit_id(&self) -> Result<u64> {
let mut cached = self.next_commit_id.lock().map_err(|_| Error::Poisoned)?;
let id = if let Some(id) = *cached {
id
} else {
let mut max = 0u64;
let dir = self.commits_dir();
if dir.exists() {
for entry in fs::read_dir(&dir)? {
let name = entry?.file_name();
if let Some(id) = name
.to_str()
.and_then(|s| s.strip_suffix(".snap"))
.and_then(|s| s.parse::<u64>().ok())
{
max = max.max(id);
}
}
}
max.checked_add(1)
.ok_or_else(|| Error::InvalidDefinition("commit ids exhausted".into()))?
};
*cached = Some(
id.checked_add(1)
.ok_or_else(|| Error::InvalidDefinition("commit ids exhausted".into()))?,
);
Ok(id)
}
pub(crate) fn branch_data_files(&self) -> Result<std::collections::BTreeSet<String>> {
let mut files = std::collections::BTreeSet::new();
for (name, mut id) in self.list_refs()? {
if name == "main" {
continue;
}
let mut seen = std::collections::BTreeSet::new();
loop {
if !seen.insert(id) {
return Err(Error::Corrupt(format!("commit cycle at {id}")));
}
match read_document::<StoredCommitRecord>(&self.commit_path(id))? {
StoredCommitRecord::Snapshot(stored) => {
for generation in stored.state.storage.generations.values() {
if let Some(manifest) = &generation.parquet {
for table in manifest.tables() {
files.insert(format!("graph-{}.parquet", table.id));
files.insert(format!("graph-{}.index", table.id));
}
}
}
match stored.parent {
Some(parent) => id = parent,
None => break,
}
}
StoredCommitRecord::Delta { parent, record, .. } => {
use crate::{memtable::TableChange, storage::StorageChange};
for change in record.storage {
match change {
StorageChange::BufferGraph { nodes, edges, .. } => {
for change in nodes.iter().chain(edges.iter().map(|e| &e.table))
{
let id = match change {
TableChange::Parquet(t) => t.id,
TableChange::Reuse(id)
| TableChange::Mask { id, .. } => *id,
TableChange::Memory { .. } => continue,
};
files.insert(format!("graph-{id}.parquet"));
files.insert(format!("graph-{id}.index"));
}
}
StorageChange::ReplaceParquet { manifest, .. } => {
for table in manifest.tables() {
files.insert(format!("graph-{}.parquet", table.id));
files.insert(format!("graph-{}.index", table.id));
}
}
_ => (),
}
}
id = parent;
}
}
}
}
Ok(files)
}
fn refs_dir(&self) -> PathBuf {
self.directory.join("refs")
}
fn commits_dir(&self) -> PathBuf {
self.directory.join("commits")
}
fn commit_path(&self, id: u64) -> PathBuf {
self.commits_dir().join(format!("{id}.snap"))
}
}
#[derive(Clone, Debug, Serialize, Deserialize)]
pub(crate) struct StoredCommit {
pub parent: Option<u64>,
pub state: PublishedState,
}
#[derive(Clone, Debug, Serialize, Deserialize)]
enum StoredCommitRecord {
Snapshot(StoredCommit),
Delta {
parent: u64,
next_id: u64,
record: CommitRecord,
},
}
fn same_snapshot(a: &PublishedState, b: &PublishedState) -> bool {
a.commit_seq == b.commit_seq
&& a.next_id == b.next_id
&& a.storage
.generations
.keys()
.eq(b.storage.generations.keys())
&& a.storage.generations.iter().all(|(id, generation)| {
let other = &b.storage.generations[id];
match (&generation.parquet, &other.parquet) {
(Some(a), Some(b)) => a
.fragments()
.map(|t| t.id())
.eq(b.fragments().map(|t| t.id())),
(None, None) => true,
_ => false,
}
})
}
fn lock_file(path: &Path) -> Result<File> {
Ok(OpenOptions::new()
.create(true)
.truncate(false)
.read(true)
.write(true)
.open(path)?)
}
pub(crate) fn sync_directory(path: &Path) -> Result<()> {
Ok(File::open(path)?.sync_all()?)
}
fn check_version(version: u32) -> Result<()> {
if version != FORMAT {
return Err(Error::UnsupportedFeature(format!(
"database format {version}"
)));
}
Ok(())
}
fn write_document<T: Serialize>(path: &Path, value: &T) -> Result<()> {
let frame = encode_frame(&serde_json::to_vec(value)?)?;
let mut file = File::create(path)?;
file.write_all(&frame)?;
file.sync_all()?;
Ok(())
}
fn read_document<T: DeserializeOwned>(path: &Path) -> Result<T> {
let mut file = File::open(path)?;
let payload = read_frame(&mut file, false)?
.ok_or_else(|| Error::Corrupt("empty checkpoint document".into()))?;
if file.stream_position()? != file.metadata()?.len() {
return Err(Error::Corrupt("trailing checkpoint bytes".into()));
}
Ok(serde_json::from_slice(&payload)?)
}
fn encode_frame(payload: &[u8]) -> Result<Vec<u8>> {
if payload.len() > MAX_RECORD {
return Err(Error::UnsupportedFeature(
"record exceeds 64 MiB format limit".into(),
));
}
let mut bytes = Vec::with_capacity(HEADER + payload.len() + END.len());
bytes.extend_from_slice(MAGIC);
bytes.extend_from_slice(&(payload.len() as u64).to_le_bytes());
bytes.extend_from_slice(&crc32(&bytes).to_le_bytes());
bytes.extend_from_slice(&crc32(payload).to_le_bytes());
bytes.extend_from_slice(payload);
bytes.extend_from_slice(END);
Ok(bytes)
}
fn read_frame(file: &mut File, allow_tail: bool) -> Result<Option<Vec<u8>>> {
let position = file.stream_position()?;
let remaining = file
.metadata()?
.len()
.checked_sub(position)
.ok_or_else(|| Error::Corrupt("invalid file position".into()))?;
if remaining == 0 {
return Ok(None);
}
if remaining < HEADER as u64 {
if allow_tail {
return Ok(None);
}
return Err(Error::Corrupt("torn document header".into()));
}
let mut header = [0; HEADER];
file.read_exact(&mut header)?;
if &header[..8] != MAGIC
|| crc32(&header[..16]) != u32::from_le_bytes(header[16..20].try_into().unwrap())
{
return Err(Error::Corrupt("invalid frame header".into()));
}
let length = u64::from_le_bytes(header[8..16].try_into().unwrap());
if length > MAX_RECORD as u64 {
return Err(Error::Corrupt("frame length exceeds limit".into()));
}
if remaining < HEADER as u64 + length + END.len() as u64 {
if allow_tail {
file.seek(SeekFrom::End(0))?;
return Ok(None);
}
return Err(Error::Corrupt("torn checkpoint document".into()));
}
let mut payload = vec![0; length as usize];
file.read_exact(&mut payload)?;
let mut end = [0; 8];
file.read_exact(&mut end)?;
if &end != END || crc32(&payload) != u32::from_le_bytes(header[20..24].try_into().unwrap()) {
return Err(Error::Corrupt("invalid frame body or commit marker".into()));
}
Ok(Some(payload))
}
pub(crate) fn crc32(bytes: &[u8]) -> u32 {
const TABLE: [u32; 256] = {
let mut table = [0; 256];
let mut i = 0;
while i < table.len() {
let mut crc = i as u32;
let mut bit = 0;
while bit < 8 {
crc = (crc >> 1) ^ (0xedb88320 & (0u32.wrapping_sub(crc & 1)));
bit += 1;
}
table[i] = crc;
i += 1;
}
table
};
!bytes.iter().fold(!0u32, |crc, byte| {
(crc >> 8) ^ TABLE[((crc ^ u32::from(*byte)) & 0xff) as usize]
})
}
#[cfg(test)]
#[test]
fn crc32_matches_ieee_test_vectors() {
assert_eq!(crc32(b""), 0);
assert_eq!(crc32(b"123456789"), 0xcbf43926);
assert_eq!(
crc32(b"The quick brown fox jumps over the lazy dog"),
0x414fa339
);
}
pub(crate) fn failpoint(_name: &str) {
#[cfg(test)]
if std::env::var("GRAPHFUSION_TEST_CRASH").as_deref() == Ok(_name) {
std::process::exit(86);
}
}
fn inject_io_error(_name: &str) -> std::io::Result<()> {
#[cfg(test)]
if std::env::var("GRAPHFUSION_TEST_IO").as_deref() == Ok(_name) {
return Err(std::io::Error::other("injected I/O failure"));
}
Ok(())
}