An error occurred fetching the project authors.
  1. 21 Jan, 2022 2 commits
  2. 28 Oct, 2021 1 commit
    • Kirill Smelkov's avatar
      wcfs: zdata: ΔFtail · f980471f
      Kirill Smelkov authored
      ΔFtail builds on ΔBtail and  provides ZBigFile-level history that WCFS
      will use to compute which blocks of a ZBigFile need to be invalidated in
      OS file cache given raw ZODB changes on ZODB invalidation message.
      
      It also will be used by WCFS to implement isolation protocol, where on
      every FUSE READ request WCFS will query ΔFtail to find out revision of
      corresponding file block.
      
      Quoting ΔFtail documentation:
      
      ---- 8< ----
      
      ΔFtail provides ZBigFile-level history tail.
      
      It translates ZODB object-level changes to information about which blocks of
      which ZBigFile were modified, and provides service to query that information.
      
      ΔFtail class documentation
      ~~~~~~~~~~~~~~~~~~~~~~~~~~
      
      ΔFtail represents tail of revisional changes to files.
      
      It semantically consists of
      
          []δF			; rev ∈ (tail, head]
      
      where δF represents a change in files space
      
          δF:
          	.rev↑
          	{} file ->  {}blk | EPOCH
      
      Only files and blocks explicitly requested to be tracked are guaranteed to
      be present. In particular a block that was not explicitly requested to be
      tracked, even if it was changed in δZ, is not guaranteed to be present in δF.
      
      After file epoch (file creation, deletion, or any other change to file
      object) previous track requests for that file become forgotten and have no
      further effect.
      
      ΔFtail provides the following operations:
      
        .Track(file, blk, path, zblk)	- add file and block reached via BTree path to tracked set.
      
        .Update(δZ) -> δF				- update files δ tail given raw ZODB changes
        .ForgetPast(revCut)			- forget changes ≤ revCut
        .SliceByRev(lo, hi) -> []δF		- query for all files changes with rev ∈ (lo, hi]
        .SliceByFileRev(file, lo, hi) -> []δfile	- query for changes of a file with rev ∈ (lo, hi]
        .BlkRevAt(file, #blk, at) -> blkrev	- query for what is last revision that changed
          					  file[#blk] as of @at database state.
      
      where δfile represents a change to one file
      
          δfile:
          	.rev↑
          	{}blk | EPOCH
      
      See also zodb.ΔTail and xbtree.ΔBtail
      
      Concurrency
      
      ΔFtail is safe to use in single-writer / multiple-readers mode. That is at
      any time there should be either only sole writer, or, potentially several
      simultaneous readers. The table below classifies operations:
      
          Writers:  Update, ForgetPast
          Readers:  Track + all queries (SliceByRev, SliceByFileRev, BlkRevAt)
      
      Note that, in particular, it is correct to run multiple Track and queries
      requests simultaneously.
      
      ΔFtail organization
      ~~~~~~~~~~~~~~~~~~~
      
      ΔFtail leverages:
      
          - ΔBtail to track changes to ZBigFile.blktab BTree, and
          - ΔZtail to track changes to ZBlk objects and to ZBigFile object itself.
      
      then every query merges ΔBtail and ΔZtail data on the fly to provide
      ZBigFile-level result.
      
      Merging on the fly, contrary to computing and maintaining vδF data, is done
      to avoid complexity of recomputing vδF when tracking set changes. Most of
      ΔFtail complexity is, thus, located in ΔBtail, which implements BTree diff
      and handles complexity of recomputing vδB when set of tracked blocks
      changes after new track requests.
      
      Changes to ZBigFile object indicate epochs. Epochs could be:
      
          - file creation or deletion,
          - change of ZBigFile.blksize,
          - change of ZBigFile.blktab to point to another BTree.
      
      Epochs represent major changes to file history where file is assumed to
      change so dramatically, that practically it can be considered to be a
      "whole" change. In particular, WCFS, upon seeing a ZBigFile epoch,
      invalidates all data in corresponding OS-level cache for the file.
      
      The only historical data, that ΔFtail maintains by itself, is history of
      epochs. That history does not need to be recomputed when more blocks become
      tracked and is thus easy to maintain. It also can be maintained only in
      ΔFtail because ΔBtail and ΔZtail does not "know" anything about ZBigFile.
      
      Concurrency
      
      In order to allow multiple Track and queries requests to be served in
      parallel, ΔFtail bases its concurrency promise on ΔBtail guarantees +
      snapshot-style access for vδE and ztrackInBlk in queries:
      
      1. Track calls ΔBtail.Track and quickly updates .byFile, .byRoot and
         _RootTrack indices under a lock.
      
      2. BlkRevAt queries ΔBtail.GetAt and then combines retrieved information
         about zblk with vδE and δZ.
      
      3. SliceByFileRev queries ΔBtail.SliceByRootRev and then merges retrieved
         vδT data with vδZ, vδE and ztrackInBlk.
      
      4. In queries vδE is retrieved/built in snapshot style similarly to how vδT
         is built in ΔBtail. Note that vδE needs to be built only the first time,
         and does not need to be further rebuilt, so the logic in ΔFtail is simpler
         compared to ΔBtail.
      
      5. for ztrackInBlk - that is used by SliceByFileRev query - an atomic
         snapshot is retrieved for objects of interest. This allows to hold
         δFtail.mu lock for relatively brief time without blocking other parallel
         Track/queries requests for long.
      
      Combined this organization allows non-overlapping queries/track-requests
      to run simultaneously. (This property is essential to WCFS because otherwise
      WCFS would not be able to serve several non-overlapping READ requests to one
      file in parallel.)
      
      See also "Concurrency" in ΔBtail organization for more details.
      
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      
      Some preliminary history:
      
      kirr/wendelin.core@ef74aebc    X ΔFtail: Keep reference to ZBigFile via Oid, not via *ZBigFile
      kirr/wendelin.core@bf9a7405    X No longer rely on ZODB cache invariant for invalidations
      kirr/wendelin.core@46340069    X found by Random
      kirr/wendelin.core@e7b598c6    X start of ΔFtail.SliceByFileRev rework to function via merging δB and δZ histories on the fly
      kirr/wendelin.core@59c83009    X ΔFtail.SliceByFileRoot tests started to work draftly after "on-the-fly" rework
      kirr/wendelin.core@210e9b07    X Fix ΔBtail.SliceByRootRev (lo,hi] handling
      kirr/wendelin.core@bf3ace66    X ΔFtail: Rebuild vδE after first track
      kirr/wendelin.core@46624787    X ΔFtail: `go test -failfast -short -v -run Random -randseed=1626793016249041295` discovered problems
      kirr/wendelin.core@786dd336    X Size no longer tracks [0,∞) since we start tracking when zfile is non-empty
      kirr/wendelin.core@4f707117    X test that shows problem of SliceByRootRev where untracked blocks are not added uniformly into whole history
      kirr/wendelin.core@c0b7e4c3    X ΔFtail.SliceByFileRev: Fix untracked entries to be present uniformly in result
      kirr/wendelin.core@aac37c11    X zdata: Introduce T to start removing duplication in tests
      kirr/wendelin.core@bf411aa9    X zdata: Deduplicate zfile loading
      kirr/wendelin.core@b74dda09    X Start switching Track from Track(key) to Track(keycov)
      kirr/wendelin.core@aa0288ce    X Switch SliceByRootRev to vδTSnapForTracked
      kirr/wendelin.core@588a512a    X zdata: Switch SliceByFileRev not to clone Zinblk
      kirr/wendelin.core@8b5d8523    X Move tracking of which blocks were accessed from wcfs to ΔFtail
      kirr/wendelin.core@30f5ddc7    ΔFtail += .Epoch in δf
      kirr/wendelin.core@22f5f096    X Rework ΔFtail so that BlkRevAt works with ZBigFile checkout from any at ∈ (tail, head]
      kirr/wendelin.core@0853cc9f    X ΔFtail + tests
      kirr/wendelin.core@124688f9    X ΔFtail fixes
      kirr/wendelin.core@d85bb82c    ΔFtail concurrency
      f980471f
  3. 20 Oct, 2021 1 commit
    • Kirill Smelkov's avatar
      X Move tracking of which blocks were accessed from wcfs to ΔFtail · 8b5d8523
      Kirill Smelkov authored
      this set has to be protected by a lock. In ΔFtail it can be naturally
      trated as "set of blocks that were explicitly requested to be tracked",
      and protected by general ΔFtail locking. If it would stay in wcfs - it
      would have to be protected by a separate lock and explicitly cared to be
      synchronized with ΔFtail.
      
      Change ΔFtail.SliceByFileRev to accept option to indicate whether we are
      interested in changed covering only explicitly tracked set. Maybe in the
      future we might want to make this the default and remove this option.
      8b5d8523
  4. 18 Oct, 2021 4 commits
  5. 15 Oct, 2021 5 commits
  6. 06 Oct, 2021 1 commit
  7. 24 Sep, 2021 1 commit
  8. 21 Sep, 2021 1 commit
  9. 13 Sep, 2021 11 commits
  10. 06 Aug, 2021 3 commits
  11. 05 Aug, 2021 1 commit
    • Kirill Smelkov's avatar
      X test that shows problem of SliceByRootRev where untracked blocks are not... · 4f707117
      Kirill Smelkov authored
      X test that shows problem of SliceByRootRev where untracked blocks are not added uniformly into whole history
      
      === RUN   TestΔFtailSliceXXX
      2021/08/05 18:07:35 zodb: FIXME: open /tmp/TestΔFtailSliceXXX2265944622/001/1.fs: raw cache is not ready for invalidations -> NoCache forced
          δftail_test.go:689: slice (@at0,@at2]:
              have: [@at1·{0 1}S @at2·{1}S]
              want: [@at1·{0 1}S @at2·{0 1}S]
      4f707117
  12. 04 Aug, 2021 3 commits
  13. 03 Aug, 2021 1 commit
  14. 23 Jul, 2021 1 commit
    • Kirill Smelkov's avatar
      X ΔFtail: `go test -failfast -short -v -run Random... · 46624787
      Kirill Smelkov authored
      X ΔFtail: `go test -failfast -short -v -run Random -randseed=1626793016249041295` discovered problems
      
      === RUN   TestΔFtailRandom
          δftail_test.go:141: # n=10 seed=1626793016249041295
      2021/07/23 12:26:01 zodb: FIXME: open /tmp/TestΔFtailRandom1363232041/001/1.fs: raw cache is not ready for invalidations -> NoCache forced
          δftail_test.go:191: #   @at0 (03e19cb6064c58dd)
          δftail_test.go:203: # → @at1 (03e19cb6064ddd99)  t0:a Da:a,b:b,c:c,d:d,e:e,f:f,g:g,h:h,i:i,j:j      ; not-yet-tracked
          δftail_test.go:375: # → @at2 (03e19cb6064fc922)  δT2:i,3:c,5:d,9:c  δD{a b c d e f g h i}   ; t0:a,2:i,3:c,5:d,9:c Da:a2,b:b2,c:c2,d:d2,e:e2,f:f2,g:g2,h:h2,i:i2,j:j        δ{0 2 3 5 9}
          δftail_test.go:472: δf:
              have: &{03e19cb6064fc922 false {2 3 5 9} true}
              want: &{03e19cb6064fc922 false {0 2 3 5 9} true}
          δftail_test.go:499: .trackSetZBlk:
              ~have: map[c:{3 9} d:{5} i:{2}]
               want: map[a:{0} c:{3 9} d:{5} i:{2}]
      
          ...
      46624787
  15. 20 Jul, 2021 1 commit
  16. 19 Jul, 2021 1 commit
  17. 16 Jul, 2021 2 commits