So I spent a while on this problem of how an fs dump/load should work,
and then cmpilato and I talked about it for a very long time as well.
We've come up with two proposals for the dump format, committed into
notes/fs_dumprestore.txt.
1. The first approach explicitly writes out each revision tree's
structure: directories, directory entries, opaque node-ids, and
all.
* The program that produces the dumpfile has a simple algorithm:
it writes out information about a revision, and writes the
revision's root directory node. Then it examines the dirents.
If any dirent is "unfamiliar" (i.e. the node-id hasn't been
written to the dumpfile yet), it recurses into that entry and
writes out the new node. If the node-id has already been
written out, then no recursion happens. Thus we have a DAG.
* The implications here are that the dumper process is keeping a
hash in memory of every node-id it's ever written to the dumpfile.
But that's what hashes are for, right? :-)
2. The second approach is almost exactly like what you'd expect an
editor to dump to disk. Directory entries are *not* written,
and there are no node-ids in sight.
* The dumper process writes out information about a revision.
Then it figures out which paths changed in the revision, and
only writes out new nodes that represent the *basenames* of
those changed paths. No need for bubble-up dirs at all. No
need for directory entries or node-ids either.
In both approaches, the 'loader' process would create a new
transaction, discover the new nodes that need processing in the
dumpfile, write the new nodes out at the correct txn locations, and
then commit.
Either way, there's no need to store predecessor history in a node;
the mere act of recommitting a transaction will re-create the correct
history relationships between nodes. (Although we *are* saving
copy-history in the dump format.)
The Big Differences:
In approach #1, the format of the dumpfile is large, because it not
only contains bubbled-up directories, but every directory node has a
list of dirents. Approach #2 has a much, much smaller format. No
dirents, no bubbled-up nodes, no node-ids. It's essentially our XML
format when you commit to XML. :-)
But approach #2 makes it difficult to restore a single revision.
You'd need to rebuild *all* previous revisions to get the one you want.
Contrast that against approach #1, whereby you can just walk right
down the tree, and discover every node-id you need somewhere in the
dumpfile. Each tree's structure is explictly traceable.
Cmpilato and I are much in favor of approach #2. We don't forsee
ourselves loading small ranges of revisions into a repository. Also,
it's not totally clear that hunting for node-ids in a dumpfile is
really any faster that rebuilding a whole range of revisions.
Here's the proposal, for convenience:
-----------------------------------------------------------------
# PROPOSAL NUMBER 1
# Okay, here's my first draft of a binary format for a filesystem
# dump. As mentioned before, it contains nothing but the abstract
# structure of the filesystem -- independent of any node-id schema or
# database back-end. All of the data in this file can be acquired by
# public function calls into svn_fs.h. Similarly, one hopes that the
# parser of this file can *rebuild* the fs using only public svn_fs.h
# routines.
# As gstein suggested, we're using rfc822-style headers to label
# logical chunks of data.
# The thing that makes this format -Large- is the fact that we're
# storing bubble-up information. Every bubbled-up directory is in
# here, complete with node-ids.
# Here is what a node looks like:
# Each node has a unique ID, an opaque svn_fs_id_t. By using
# svn_fs_unparse_id, we can get a unique string_t blob to write out.
# Later on, when something parses this file, the blob is opaque and
# meaningless, but still acts as a unique identifier when rebuilding
# a filesystem.
Node-id-length: 13
[node-id follows]
# Where this node was created, and its kind.
Revision: 1422
Path: foo/bar/baz/bop
Node-kind: file | dir
# This node was deleted in this revision, OR,
# This node was added in this revision -- possibly with copy history, OR
# This node was changed in this revision.
#
# note1: if added and Path already exists, infer a replacement.
# note2: 'changed' field is *only* so we detect pure bubble-up nodes;
# bubbled-up nodes won't have it at all.
Action: deleted | added | changed
# Was this node copied from another revision and path?
Copied-from: [revision, path]
# For property lists, I'm reusing the same hashtable-on-disk format
# that we currently use to write propfiles. It's a simple way of
# mapping const char * -> svn_string_t *. It's human readable
# (assuming your values aren't binary data), and most importantly, we
# already have a parser for this format!
Node-properties:
K 12
svn:keywords
V 15
LastChangedDate
K 14
svn:executable
V 2
on
END
# If the node is a file, then we store its fulltext like so:
Text-checksum: [md5 checksum on fulltext]
Content-length: N
[N bytes of data follow]
# If the node is a directory, then we give a list of dirents. I
# realized that this is just another hashtable like our props, mapping
# (const char *) names to (svn_string_t *) node-ids. So it makes
# sense to use the same hash-on-disk format here as well.
Directory-entries:
K 6
README
V 8
[some node id]
K 10
autogen.sh
V 9
[some node id]
END
# Here's what a revision looks like, pretty simple.
Revision-number: 1422
Revision-root-node: ID
Revision-properties:
...
...
...
END
----------------------------------------------------------------
# PROPOSAL NUMBER 2
# This format is much, much smaller in terms of disk space. It
# doesn't mention node-ids at *all*, because it leaves out *all*
# bubble-up nodes. Really, it's essentially what an editor would
# output during a commit: only changed nodes. Directories don't list
# entries at all.
# The tradeoff here is that it's more work to reconstruct a particular
# revision from the middle of a dumpfile. For example, if I have a
# dumpfile for revisions 1 to 500, and somebody wants to reconstruct
# (load) revision 300 into a repository, the *only* way to do this is
# by replaying commits 1-299 into some temporary repository.
# Where this node was created, and its kind.
Revision: 1422
Path: foo/bar/baz/bop
Node-kind: file | dir
# No need for 'changed' verb: that was only for distinguishing
# between bubble-up dirs and dirs with changed props.
Action: deleted | added
# Was this node copied from another revision and path?
Copied-from: [revision, path]
# Property list.
Node-properties:
K 12
svn:keywords
V 15
LastChangedDate
K 14
svn:executable
V 2
on
END
# If the node is a file, then we store its fulltext like so:
Text-checksum: [md5 checksum on fulltext]
Content-length: N
[N bytes of data follow]
# If the node is a directory, then we add nothing. No need for dirents.
# Here's what a revision looks like. No root-node-id needed.
Revision-number: 1422
Revision-properties:
...
...
...
END
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Mon Apr 29 21:21:17 2002