Skip to content

impl w3d1 & w3d2 #2

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
Zhou-jw merged 6 commits into from
Jan 22, 2025
Merged

impl w3d1 & w3d2 #2

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
d132205
w3d2 task: w1d1_test task3 capacity
Zhou-jw Jan 18, 2025
37e0668
fix dead loop when insert same key with different timestamp to skipli…
Zhou-jw Jan 19, 2025
4448401
w3d2 : refactor get() in lsm_storage
Zhou-jw Jan 19, 2025
ad5f331
fix timestamped_key for_testing_ts()
Zhou-jw Jan 21, 2025
8d0201c
fix SstableBuilder.add(), correctly set from slice after call of fini…
Zhou-jw Jan 22, 2025
7663822
fix find_block_idx()
Zhou-jw Jan 22, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
115 changes: 114 additions & 1 deletion .vscode/launch.json
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -40,12 +40,125 @@
"RUSTC_TOOLCHAIN=/home/zjw/.rustup/toolchains/stable-x86_64-unknown-linux-gnu"
],
"preRunCommands": [
"command script import ${workspaceFolder}/util/rust_prettifier_for_lldb.py",
"command script import ${workspaceFolder}/util/rust_prettifier_for_lldb.py"
],
"args": [
"tests::week2_day5",
"--show-output"
]
},
{
"type": "lldb-dap",
"request": "launch",
"name": "test tests::week1_day2::test_task4_integration",
"cwd": "${workspaceFolder}/mini-lsm-starter",
"program": "${workspaceFolder}/target/debug/deps/mini_lsm_starter-430c4aaead80470b",
"env": [
"RUST_BACKTRACE=short",
"RUSTC_TOOLCHAIN=/home/zjw/.rustup/toolchains/stable-x86_64-unknown-linux-gnu"
],
"preRunCommands": [
"command script import ${workspaceFolder}/util/rust_prettifier_for_lldb.py"
],
"args": [
"tests::week1_day2::test_task4_integration",
"--exact",
"--show-output"
]
},
{
"type": "lldb-dap",
"request": "launch",
"name": "test tests::week1_day1::test_task3_freeze_on_capacity",
"cwd": "${workspaceFolder}/mini-lsm-starter",
"program": "${workspaceFolder}/target/debug/deps/mini_lsm_starter-430c4aaead80470b",
"env": [
"RUST_BACKTRACE=short",
"RUSTC_TOOLCHAIN=/home/zjw/.rustup/toolchains/stable-x86_64-unknown-linux-gnu"
],
"preRunCommands": [
"command script import ${workspaceFolder}/util/rust_prettifier_for_lldb.py"
],
"args": [
"tests::week1_day1::test_task3_freeze_on_capacity",
"--exact",
"--show-output"
]
},
{
"type": "lldb-dap",
"request": "launch",
"name": "test-mod tests::week1_day6",
"cwd": "${workspaceFolder}/mini-lsm-starter",
"program": "${workspaceFolder}/target/debug/deps/mini_lsm_starter-430c4aaead80470b",
"env": [
"RUST_BACKTRACE=short",
"RUSTC_TOOLCHAIN=/home/zjw/.rustup/toolchains/stable-x86_64-unknown-linux-gnu"
],
"preRunCommands": [
"command script import ${workspaceFolder}/util/rust_prettifier_for_lldb.py"
],
"args": [
"tests::week1_day6",
"--show-output"
]
},
{
"type": "lldb-dap",
"request": "launch",
"name": "test tests::week2_day1::test_task3_integration",
"cwd": "${workspaceFolder}/mini-lsm-starter",
"program": "${workspaceFolder}/target/debug/deps/mini_lsm_starter-430c4aaead80470b",
"env": [
"RUST_BACKTRACE=short",
"RUSTC_TOOLCHAIN=/home/zjw/.rustup/toolchains/stable-x86_64-unknown-linux-gnu"
],
"preRunCommands": [
"command script import ${workspaceFolder}/util/rust_prettifier_for_lldb.py"
],
"args": [
"tests::week2_day1::test_task3_integration",
"--exact",
"--show-output"
]
},
{
"type": "lldb-dap",
"request": "launch",
"name": "test tests::week2_day2::test_integration",
"cwd": "${workspaceFolder}/mini-lsm-starter",
"program": "${workspaceFolder}/target/debug/deps/mini_lsm_starter-430c4aaead80470b",
"env": [
"RUST_BACKTRACE=short",
"RUSTC_TOOLCHAIN=/home/zjw/.rustup/toolchains/stable-x86_64-unknown-linux-gnu"
],
"preRunCommands": [
"command script import ${workspaceFolder}/util/rust_prettifier_for_lldb.py"
],
"args": [
"tests::week2_day2::test_integration",
"--exact",
"--show-output"
]
},
{
"type": "lldb-dap",
"request": "launch",
"name": "test tests::week3_day1::test_sst_build_multi_version_hard",
"cwd": "${workspaceFolder}/mini-lsm-starter",
"program": "${workspaceFolder}/target/debug/deps/mini_lsm_starter-430c4aaead80470b",
"env": [
"RUST_BACKTRACE=short",
"RUSTC_TOOLCHAIN=/home/zjw/.rustup/toolchains/stable-x86_64-unknown-linux-gnu"
],
"preRunCommands": [
"command script import ${workspaceFolder}/util/rust_prettifier_for_lldb.py"
],
"args": [
"tests::week3_day1::test_sst_build_multi_version_hard",
"--exact",
"--show-output"
]
}
]
}
3 changes: 3 additions & 0 deletions mini-lsm-starter/src/block/iterator.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -105,6 +105,7 @@ impl BlockIterator {
.append(&self.first_key.key_ref()[..key_overlap_len]);
self.key.append(key);
let ts = entry.get_u64();
self.key.set_ts(ts);
let value_len = entry.get_u16() as usize;
let value_offset_begin = offset + SIZEOF_U16 * 2 + res_len + SIZEOF_U64 + SIZEOF_U16;
let value_offset_end = value_offset_begin + value_len;
Expand All @@ -128,6 +129,7 @@ impl BlockIterator {
/// Note: You should assume the key-value pairs in the block are sorted when being added by
/// callers.
pub fn seek_to_key(&mut self, key: KeySlice) {
// if key doesn't exist, it will seek to empty key
let mut low = 0;
let mut high = self.block.offsets.len();
while low < high {
Expand All @@ -143,6 +145,7 @@ impl BlockIterator {
self.seek_to(low);

// if key doesn't exist, it will seek to the last_key in this block
// O(n)
// let mut offset: usize;
// for i in 0..self.block.offsets.len() {
// offset = self.block.offsets[i] as usize;
Expand Down
10 changes: 8 additions & 2 deletions mini-lsm-starter/src/compact.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -134,7 +134,7 @@ impl LsmStorageInner {
let builder_inner = sst_builder.as_mut().unwrap();
builder_inner.add(iter.key(), iter.value());

if builder_inner.estimated_size() >= target_sst_size && !is_same_as_prevkey{
if builder_inner.estimated_size() >= target_sst_size && !is_same_as_prevkey {
let next_sst_id = self.next_sst_id();
let block_cache = self.block_cache.clone();
let builder = sst_builder.take().unwrap();
Expand All @@ -148,7 +148,7 @@ impl LsmStorageInner {

iter.next()?;

if !is_same_as_prevkey {
if !is_same_as_prevkey && iter.is_valid() {
prev_key.clear();
prev_key.extend(iter.key().key_ref());
}
Expand Down Expand Up @@ -357,6 +357,12 @@ impl LsmStorageInner {
}
snapshot.levels[0] = (1, level_1);

println!("===== After compaction =====");
println!("L0 : {:?}", snapshot.l0_sstables);
for (tier, sstables) in snapshot.levels.iter() {
println!("L{:?} : {:?}", tier, sstables);
}
println!();
// lock and update LsmStorageState
{
let _state_lock = self.state_lock.lock();
Expand Down
23 changes: 17 additions & 6 deletions mini-lsm-starter/src/iterators/merge_iterator.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -94,11 +94,17 @@ impl<I: 'static + for<'a> StorageIterator<KeyType<'a> = KeySlice<'a>>> StorageIt
while let Some(mut inner_iter) = self.iters.peek_mut() {
//cur.1.key is the latest data, when next.1.key==cur.1.key , inner_iter should call inner_iter.next()
// eprintln!(
// "cur.1.key is {:?}, cur.1.value is {:?}",
// "cur.1.key is {:?}, ts is {:?}, cur.1.value is {:?}",
// cur.1.key(),
// cur.1.key().ts(),
// cur.1.value()
// );
// eprintln!("inner_iter.1.key is {:?}", inner_iter.1.key());
// eprintln!(
// "inner_iter.1.key is {:?}, ts is {:?}, inner_iter.1.value is {:?}",
// inner_iter.1.key(),
// inner_iter.1.key().ts(),
// inner_iter.1.value()
// );
// io::stdout().flush().unwrap();
if cur.1.key() == inner_iter.1.key() {
/*
Expand Down Expand Up @@ -160,9 +166,14 @@ impl<I: 'static + for<'a> StorageIterator<KeyType<'a> = KeySlice<'a>>> StorageIt
}

fn num_active_iterators(&self) -> usize {
match self.current {
Some(_) => self.iters.len() + 1,
None => self.iters.len(),
}
self.iters
.iter()
.map(|x| x.1.num_active_iterators())
.sum::<usize>()
+ self
.current
.as_ref()
.map(|x| x.1.num_active_iterators())
.unwrap_or(0)
}
}
18 changes: 9 additions & 9 deletions mini-lsm-starter/src/iterators/two_merge_iterator.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -81,16 +81,16 @@ impl<
}

fn num_active_iterators(&self) -> usize {
if !self.aflag {
if !self.b.is_valid() {
return 0;
}
return self.b.num_active_iterators();
}
// if !self.aflag {
// if !self.b.is_valid() {
// return 0;
// }
// return self.b.num_active_iterators();
// }

if !self.b.is_valid() {
return self.a.num_active_iterators();
}
// if !self.b.is_valid() {
// return self.a.num_active_iterators();
// }

self.a.num_active_iterators() + self.b.num_active_iterators()
}
Expand Down
2 changes: 2 additions & 0 deletions mini-lsm-starter/src/key.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5,6 +5,8 @@ use timestamped_key as key;

pub const TS_ENABLED: bool = key::TS_ENABLED;
pub const TS_DEFAULT: u64 = key::TS_DEFAULT;
pub const TS_RANGE_BEGIN: u64 = key::TS_RANGE_BEGIN;
pub const TS_RANGE_END: u64 = key::TS_RANGE_END;
pub const TS_MAX: u64 = key::TS_MAX;
pub const TS_MIN: u64 = key::TS_MIN;

Expand Down
13 changes: 10 additions & 3 deletions mini-lsm-starter/src/key/timestamped_key.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,6 +12,8 @@ pub(super) type KeyVec = Key<Vec<u8>>;
pub(super) type KeyBytes = Key<Bytes>;

pub const TS_DEFAULT: u64 = 0;
pub const TS_RANGE_BEGIN: u64 = std::u64::MAX;
pub const TS_RANGE_END: u64 = std::u64::MIN;
pub const TS_MAX: u64 = std::u64::MAX;
pub const TS_MIN: u64 = std::u64::MIN;

Expand All @@ -33,7 +35,7 @@ impl<T: AsRef<[u8]>> Key<T> {
}

pub fn for_testing_ts(self) -> u64 {
0
self.1
}
}

Expand All @@ -58,6 +60,11 @@ impl Key<Vec<u8>> {
self.0.extend(data)
}

/// set ts
pub fn set_ts(&mut self, ts: u64) {
self.1 = ts;
}

/// Set the key from a slice without re-allocating. The signature will change in week 3.
pub fn set_from_slice(&mut self, key_slice: KeySlice) {
self.0.clear();
Expand Down Expand Up @@ -87,7 +94,7 @@ impl Key<Vec<u8>> {
}

pub fn for_testing_from_vec_no_ts(key: Vec<u8>) -> Self {
Self(key, u64::default())
Self(key, TS_DEFAULT)
}
}

Expand Down Expand Up @@ -168,7 +175,7 @@ impl<T: AsRef<[u8]> + Default> Default for Key<T> {

impl<T: AsRef<[u8]> + PartialEq> PartialEq for Key<T> {
fn eq(&self, other: &Self) -> bool {
self.0.eq(&other.0)
(self.0.as_ref(), self.1).eq(&(other.0.as_ref(), other.1))
}
}

Expand Down
12 changes: 8 additions & 4 deletions mini-lsm-starter/src/lsm_iterator.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -34,7 +34,7 @@ impl LsmIterator {
end_bound,
prev_key: Vec::new(),
};
valid_iter.move_to_next_key()?;
valid_iter.move_to_key()?;
Ok(valid_iter)
}

Expand All @@ -49,7 +49,7 @@ impl LsmIterator {
// Ok(())
// }

fn move_to_next_key(&mut self) -> Result<()> {
fn move_to_key(&mut self) -> Result<()> {
// while self.inner.is_valid() && self.inner.value().is_empty() {
// self.inner.next()?;
// }
Expand All @@ -66,6 +66,10 @@ impl LsmIterator {

self.prev_key.clear();
self.prev_key.extend(self.inner.key().key_ref());

if !self.inner.value().is_empty() {
break;
}
}
Ok(())
}
Expand All @@ -76,7 +80,7 @@ impl LsmIterator {
self.is_valid = false;
return Ok(());
}

match self.end_bound.as_ref() {
Bound::Included(x) => {
self.is_valid =
Expand Down Expand Up @@ -110,7 +114,7 @@ impl StorageIterator for LsmIterator {
fn next(&mut self) -> Result<()> {
// self.inner.next()?;
self.inner_next()?;
self.move_to_next_key()?;
self.move_to_key()?;
Ok(())
}

Expand Down
Loading
Loading