summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKent Overstreet <kent.overstreet@gmail.com>2019-11-19 16:08:39 -0500
committerKent Overstreet <kent.overstreet@gmail.com>2019-11-19 16:10:30 -0500
commit8b95f9672373b80fe4b799b9def4f2969be8a082 (patch)
treed845d99dd4a124e5653c2b9c387ab1ed1442bec1
parenta5f1540e6ea2865b4f9538e36c9505829e5da0d4 (diff)
formatting
-rw-r--r--Snapshots.mdwn62
1 files changed, 31 insertions, 31 deletions
diff --git a/Snapshots.mdwn b/Snapshots.mdwn
index 324b6bf..185e4c3 100644
--- a/Snapshots.mdwn
+++ b/Snapshots.mdwn
@@ -58,8 +58,8 @@ extents are listed in their sort order in the btree.
Suppose we have these two extents:
-1: |--------|
-2: |---------|
+ 1: |--------|
+ 2: |---------|
This is a problem: on lookup (for snapshot 2), we find the extent in 1 first, as
we should - we do require data from it. But we cannot use all of that extent; 2
@@ -71,25 +71,25 @@ snapshots in between.
Suppose we add the restriction: a child extent cannot cross the boundary at the
end of the ancestor extent, instead we split the child extent:
-2: |----|
-1: |--------|
-2: |----|
+ 2: |----|
+ 1: |--------|
+ 2: |----|
This is still a problem for lookups, for example:
- |------|
- |-------|
- |--------|
- |---------|
-|----------|
+ |------|
+ |-------|
+ |--------|
+ |---------|
+ |----------|
We must also add the restriction: start of child cannot land in middle of
ancestor. Then we have these extents.
-1: |---|
-2: |----|
-1: |----|
-2: |----|
+ 1: |---|
+ 2: |----|
+ 1: |----|
+ 2: |----|
This appears workable - however, given that we can have an arbitrary number of
extents in different snapshots at the same position, this means we'll have to
@@ -97,11 +97,11 @@ either split an unbounded number of existing extents - or we could only split
the extent that's visible in the child snapshot, but this seems to result in
invariants that would be difficult or impossible to check:
-5: |----|
-4: |---||----|
-3: |---------|
-2: |---------|
-1: |---------|
+ 5: |----|
+ 4: |---||----|
+ 3: |---------|
+ 2: |---------|
+ 1: |---------|
A different approach:
---------------------
@@ -114,8 +114,8 @@ position.
Back to the first example:
-1: |--------|
-2: |---------|
+ 1: |--------|
+ 2: |---------|
Suppose we're reading from snapshot 2 at the position where extent 1 starts.
Lookup returns extent 1, as it should - but we need to determine when to stop
@@ -124,10 +124,10 @@ start position, we can scan forwards until we find an extent that overwrites 1
(is in a newer snapshot than 1 and a descendant of the snapshot we're reading),
or until we see an extent that starts after the position where extent 1 ends.
-* Example 2:
+Example 2:
-2: |----|
-1: |--------------|
+ 2: |----|
+ 1: |--------------|
Suppose we're reading at the position where extent 1 starts. Lookup will return
extent 2, but we actually want extent 1: What we can do is notice that the
@@ -135,19 +135,19 @@ extent lookup return starts after the lookup position - so then iterate
backwards, ordered by extent start position, until we find an extent that starts
at or before our search position.
-* Example 3:
+Example 3:
-1: |----|
-2: |--------------|
+ 1: |----|
+ 2: |--------------|
Reading from snapshot 2, at the position where extent 1 starts. Lookup returns
extent 1, but we actually want extent 2.
-* Example 4:
+Example 4:
-2: |----|
-1: |--------------|
-3: |-----------------------|
+ 2: |----|
+ 1: |--------------|
+ 3: |-----------------------|
Reading from 3, at the start of extent 1: Then what?