view tests/test-diff-upgrade.t @ 40326:fed697fa1734

sqlitestore: file storage backend using SQLite

This commit provides an extension which uses SQLite to store file
data (as opposed to revlogs).

As the inline documentation describes, there are still several
aspects to the extension that are incomplete. But it's a start.
The extension does support basic clone, checkout, and commit
workflows, which makes it suitable for simple use cases.

One notable missing feature is support for "bundlerepos." This is
probably responsible for the most test failures when the extension
is activated as part of the test suite.

All revision data is stored in SQLite. Data is stored as zstd
compressed chunks (default if zstd is available), zlib compressed
chunks (default if zstd is not available), or raw chunks (if
configured or if a compressed delta is not smaller than the raw
delta). This makes things very similar to revlogs.

Unlike revlogs, the extension doesn't yet enforce a limit on delta
chain length. This is an obvious limitation and should be addressed.
This is somewhat mitigated by the use of zstd, which is much faster
than zlib to decompress.

There is a dedicated table for storing deltas. Deltas are stored
by the SHA-1 hash of their uncompressed content. The "fileindex" table
has columns that reference the delta for each revision and the base
delta that delta should be applied against. A recursive SQL query
is used to resolve the delta chain along with the delta data.

By storing deltas by hash, we are able to de-duplicate delta storage!
With revlogs, the same deltas in different revlogs would result in
duplicate storage of that delta. In this scheme, inserting the
duplicate delta is a no-op and delta chains simply reference the
existing delta.

When initially implementing this extension, I did not have
content-indexed deltas and deltas could be duplicated across files
(just like revlogs). When I implemented content-indexed deltas, the
size of the SQLite database for a full clone of mozilla-unified
dropped:

before: 2,554,261,504 bytes
after:  2,488,754,176 bytes

Surprisingly, this is still larger than the bytes size of revlog
files:

revlog files: 2,104,861,230 bytes
du -b:        2,254,381,614

I would have expected storage to be smaller since we're not limiting
delta chain length and since we're using zstd instead of zlib. I
suspect the SQLite indexes and per-column overhead account for the
bulk of the differences. (Keep in mind that revlog uses a 64-byte
packed struct for revision index data and deltas are stored without
padding. Aside from the 12 unused bytes in the 32 byte node field,
revlogs are pretty efficient.) Another source of overhead is file
name storage. With revlogs, file names are stored in the filesystem.
But with SQLite, we need to store file names in the database. This is
roughly equivalent to the size of the fncache file, which for the
mozilla-unified repository is ~34MB.

Since the SQLite database isn't append-only and since delta chains
can reference any delta, this opens some interesting possibilities.
For example, we could store deltas in reverse, such that fulltexts
are stored for newer revisions and deltas are applied to reconstruct
older revisions. This is likely a more optimal storage strategy for
version control, as new data tends to be more frequently accessed
than old data. We would obviously need wire protocol support for
transferring revision data from newest to oldest. And we would
probably need some kind of mechanism for "re-encoding" stores. But
it should be doable.

This extension is very much experimental quality. There are a handful
of features that don't work. It probably isn't suitable for day-to-day
use. But it could be used in limited cases (e.g. read-only checkouts
like in CI). And it is also a good proving ground for alternate
storage backends. As we continue to define interfaces for all things
storage, it will be useful to have a viable alternate storage backend
to see how things shake out in practice.

test-storage.py passes on Python 2 and introduces no new test failures on
Python 3. Having the storage-level unit tests has proved to be insanely
useful when developing this extension. Those tests caught numerous bugs
during development and I'm convinced this style of testing is the way
forward for ensuring alternate storage backends work as intended. Of
course, test coverage isn't close to what it needs to be. But it is
a start. And what coverage we have gives me confidence that basic store
functionality is implemented properly.

Differential Revision: https://phab.mercurial-scm.org/D4928

#require execbit

  $ cat <<EOF >> $HGRCPATH
  > [extensions]
  > autodiff = $TESTDIR/autodiff.py
  > [diff]
  > nodates = 1
  > EOF

  $ hg init repo
  $ cd repo



make a combination of new, changed and deleted file

  $ echo regular > regular
  $ echo rmregular > rmregular
  $ "$PYTHON" -c "open('bintoregular', 'wb').write(b'\0')"
  $ touch rmempty
  $ echo exec > exec
  $ chmod +x exec
  $ echo rmexec > rmexec
  $ chmod +x rmexec
  $ echo setexec > setexec
  $ echo unsetexec > unsetexec
  $ chmod +x unsetexec
  $ echo binary > binary
  $ "$PYTHON" -c "open('rmbinary', 'wb').write(b'\0')"
  $ hg ci -Am addfiles
  adding binary
  adding bintoregular
  adding exec
  adding regular
  adding rmbinary
  adding rmempty
  adding rmexec
  adding rmregular
  adding setexec
  adding unsetexec
  $ echo regular >> regular
  $ echo newregular >> newregular
  $ rm rmempty
  $ touch newempty
  $ rm rmregular
  $ echo exec >> exec
  $ echo newexec > newexec
  $ echo bintoregular > bintoregular
  $ chmod +x newexec
  $ rm rmexec
  $ chmod +x setexec
  $ chmod -x unsetexec
  $ "$PYTHON" -c "open('binary', 'wb').write(b'\0\0')"
  $ "$PYTHON" -c "open('newbinary', 'wb').write(b'\0')"
  $ rm rmbinary
  $ hg addremove -s 0
  adding newbinary
  adding newempty
  adding newexec
  adding newregular
  removing rmbinary
  removing rmempty
  removing rmexec
  removing rmregular

git=no: regular diff for all files

  $ hg autodiff --git=no
  diff -r a66d19b9302d binary
  Binary file binary has changed
  diff -r a66d19b9302d bintoregular
  Binary file bintoregular has changed
  diff -r a66d19b9302d exec
  --- a/exec
  +++ b/exec
  @@ -1,1 +1,2 @@
   exec
  +exec
  diff -r a66d19b9302d newbinary
  Binary file newbinary has changed
  diff -r a66d19b9302d newexec
  --- /dev/null
  +++ b/newexec
  @@ -0,0 +1,1 @@
  +newexec
  diff -r a66d19b9302d newregular
  --- /dev/null
  +++ b/newregular
  @@ -0,0 +1,1 @@
  +newregular
  diff -r a66d19b9302d regular
  --- a/regular
  +++ b/regular
  @@ -1,1 +1,2 @@
   regular
  +regular
  diff -r a66d19b9302d rmbinary
  Binary file rmbinary has changed
  diff -r a66d19b9302d rmexec
  --- a/rmexec
  +++ /dev/null
  @@ -1,1 +0,0 @@
  -rmexec
  diff -r a66d19b9302d rmregular
  --- a/rmregular
  +++ /dev/null
  @@ -1,1 +0,0 @@
  -rmregular

git=yes: git diff for single regular file

  $ hg autodiff --git=yes regular
  diff --git a/regular b/regular
  --- a/regular
  +++ b/regular
  @@ -1,1 +1,2 @@
   regular
  +regular

git=auto: regular diff for regular files and non-binary removals

  $ hg autodiff --git=auto regular newregular rmregular rmexec
  diff -r a66d19b9302d newregular
  --- /dev/null
  +++ b/newregular
  @@ -0,0 +1,1 @@
  +newregular
  diff -r a66d19b9302d regular
  --- a/regular
  +++ b/regular
  @@ -1,1 +1,2 @@
   regular
  +regular
  diff -r a66d19b9302d rmexec
  --- a/rmexec
  +++ /dev/null
  @@ -1,1 +0,0 @@
  -rmexec
  diff -r a66d19b9302d rmregular
  --- a/rmregular
  +++ /dev/null
  @@ -1,1 +0,0 @@
  -rmregular

  $ for f in exec newexec setexec unsetexec binary newbinary newempty rmempty rmbinary bintoregular; do
  >     echo
  >     echo '% git=auto: git diff for' $f
  >     hg autodiff --git=auto $f
  > done
  
  % git=auto: git diff for exec
  diff -r a66d19b9302d exec
  --- a/exec
  +++ b/exec
  @@ -1,1 +1,2 @@
   exec
  +exec
  
  % git=auto: git diff for newexec
  diff --git a/newexec b/newexec
  new file mode 100755
  --- /dev/null
  +++ b/newexec
  @@ -0,0 +1,1 @@
  +newexec
  
  % git=auto: git diff for setexec
  diff --git a/setexec b/setexec
  old mode 100644
  new mode 100755
  
  % git=auto: git diff for unsetexec
  diff --git a/unsetexec b/unsetexec
  old mode 100755
  new mode 100644
  
  % git=auto: git diff for binary
  diff --git a/binary b/binary
  index a9128c283485202893f5af379dd9beccb6e79486..09f370e38f498a462e1ca0faa724559b6630c04f
  GIT binary patch
  literal 2
  Jc${Nk0000200961
  
  
  % git=auto: git diff for newbinary
  diff --git a/newbinary b/newbinary
  new file mode 100644
  index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..f76dd238ade08917e6712764a16a22005a50573d
  GIT binary patch
  literal 1
  Ic${MZ000310RR91
  
  
  % git=auto: git diff for newempty
  diff --git a/newempty b/newempty
  new file mode 100644
  
  % git=auto: git diff for rmempty
  diff --git a/rmempty b/rmempty
  deleted file mode 100644
  
  % git=auto: git diff for rmbinary
  diff --git a/rmbinary b/rmbinary
  deleted file mode 100644
  index f76dd238ade08917e6712764a16a22005a50573d..e69de29bb2d1d6434b8b29ae775ad8c2e48c5391
  GIT binary patch
  literal 0
  Hc$@<O00001
  
  
  % git=auto: git diff for bintoregular
  diff --git a/bintoregular b/bintoregular
  index f76dd238ade08917e6712764a16a22005a50573d..9c42f2b6427d8bf034b7bc23986152dc01bfd3ab
  GIT binary patch
  literal 13
  Uc$`bh%qz(+N=+}#Ni5<5043uE82|tP
  


git=warn: regular diff with data loss warnings

  $ hg autodiff --git=warn
  diff -r a66d19b9302d binary
  Binary file binary has changed
  diff -r a66d19b9302d bintoregular
  Binary file bintoregular has changed
  diff -r a66d19b9302d exec
  --- a/exec
  +++ b/exec
  @@ -1,1 +1,2 @@
   exec
  +exec
  diff -r a66d19b9302d newbinary
  Binary file newbinary has changed
  diff -r a66d19b9302d newexec
  --- /dev/null
  +++ b/newexec
  @@ -0,0 +1,1 @@
  +newexec
  diff -r a66d19b9302d newregular
  --- /dev/null
  +++ b/newregular
  @@ -0,0 +1,1 @@
  +newregular
  diff -r a66d19b9302d regular
  --- a/regular
  +++ b/regular
  @@ -1,1 +1,2 @@
   regular
  +regular
  diff -r a66d19b9302d rmbinary
  Binary file rmbinary has changed
  diff -r a66d19b9302d rmexec
  --- a/rmexec
  +++ /dev/null
  @@ -1,1 +0,0 @@
  -rmexec
  diff -r a66d19b9302d rmregular
  --- a/rmregular
  +++ /dev/null
  @@ -1,1 +0,0 @@
  -rmregular
  data lost for: binary
  data lost for: bintoregular
  data lost for: newbinary
  data lost for: newempty
  data lost for: newexec
  data lost for: rmbinary
  data lost for: rmempty
  data lost for: setexec
  data lost for: unsetexec

git=abort: fail on execute bit change

  $ hg autodiff --git=abort regular setexec
  abort: losing data for setexec
  [255]

git=abort: succeed on regular file

  $ hg autodiff --git=abort regular
  diff -r a66d19b9302d regular
  --- a/regular
  +++ b/regular
  @@ -1,1 +1,2 @@
   regular
  +regular

  $ cd ..