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:08:39 -0500
commit729f50615328d6b9dbadb20a9cfe28f893750d4a (patch)
tree81f6536eb89adde411c9b46d7b62e58a23dfb443
parenta5f1540e6ea2865b4f9538e36c9505829e5da0d4 (diff)
formatting
-rw-r--r--Snapshots.mdwn56
1 files changed, 28 insertions, 28 deletions
diff --git a/Snapshots.mdwn b/Snapshots.mdwn
index 324b6bf..cb3f280 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
@@ -126,8 +126,8 @@ or until we see an extent that starts after the position where extent 1 ends.
* 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
@@ -137,17 +137,17 @@ at or before our search position.
* 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:
-2: |----|
-1: |--------------|
-3: |-----------------------|
+ 2: |----|
+ 1: |--------------|
+ 3: |-----------------------|
Reading from 3, at the start of extent 1: Then what?