You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Stefan Sperling <st...@elego.de> on 2011/09/01 00:06:40 UTC
Re: FSFS successor ID design draft
On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
> I'll try to tweak my proposal such that successor ID updates become
> transactional and happen as part of every commit.
Here's a first shot at this. Comments welcome.
To support transactional semantics, any new data written to the FSFS
filesystem must be tied to the newly created revision.
This way, updating 'current' as the final step in each commit makes the
new data appear. Failing to update 'current' will cause any data added
by failing commits to be overwritten by the next successfull commit.
The following design tries to keep this principle valid for sucessor-ids.
There is one compromise though which hopefully won't hurt too much.
Thanks again to danielsh for providing some initial feedback via IRC.
Implementation proposal
=======================
- On-disk File Format -
All files related to the map are stored in the repos/db/successors
directory ("successors directory").
The successor map contains 3 kinds of files:
1) Node-revision map files.
These files map node-revision IDs to lists of revisions.
This map answers the question:
"In which revisions were successors of a node-revision created?"
2) Created-revision map file.
These files map revision numbers of file offsets in successor data files.
This map answers the question:
"Where in the successor data are those successors which were created
in revision N?"
3) Successor data files.
These files store raw successor data.
The different kinds of files refer to each other as shown below:
node_rev_id map revision map successor data
+-------+ +--------+ +-----------+
| ... | | ... | | ... |
+------>rN---------+ | offset | +----->successor |
| | ... | | | offset | | | successor |
| | ... | +----->offset----+ | END |
node_rev_id --+ | rQ | | ... | | successor |
| | ... | | offset | | ... |
+------>rX---------+ | ... | | ... |
| ... | | | ... | | END |
| ... | +----->offset---------->successor |
| rZ | | ... | | END |
+-------+ +--------+ +-----------+
Each type of file is described below in detail.
-- Node-revision-ID map files --
The purpose of node-revision-id map files is to facilitate lookup
of successors of a given node-revision.
The files are named after the number of the revision the node-revision
was created in, modulo some fixed to-be-determined value (i.e. there
won't be one file per node revision, but one file for every 10, 100,
or so, node-revisions).
The files are stored within the "node-revs" sub-directory:
db/successors/node-revs/1
db/successors/node-revs/2
db/successors/node-revs/3
...
db/successors/node-revs/N
db/successors/node-revs/M
...
Each node-revision map file stores a mapping of the form
node_rev_id => [revnum, revnum, ...]
The revision numbers identify those revisions in which one or more
successors of a given node-revision were added.
In the first iteration of this design, the mapping is stored as lines
of ASCII text. Each line contains an unparsed node_revision_id, a space
separator (ASCII 0x20), and a revision number in ASCII decimal representation.
(The design may be refined later to use a more efficient storage model.)
-- Revision map files --
The purpose of the revision map file is to facilitate lookup
of successor data created in a given revision.
The files are named after the numbers of revisions they are responsible for,
modulo some fixed to-be-determined value (i.e. there won't be one file
per revision, but one file for every 10, 100, or so, revisions; each file
is responsible for some range of revisions).
The files are stored within the "revs" sub-directory:
db/successors/revs/1
db/successors/revs/2
db/successors/revs/3
...
db/successors/revs/N
db/successors/revs/M
...
Each file consists of an array of 64bit big-endian integers.
The N'th integer (starting from N=1) in the file specifies the offset
of successor data (in the corresponding successor data file) which was
added in the N'th revision within the revision range the map file is
responsible for.
-- Successor-data files --
These files use the same naming scheme as the revision map files (i.e.
each successor data file is responsible for successors created within
a specific range of revisions).
The files are stored within the "successor-ids" sub-directory:
db/successors/successor-ids/1
db/successors/successor-ids/2
db/successors/successor-ids/3
...
db/successors/successor-ids/N
db/successors/successor-ids/M
...
Each file consists of lines each containing two unparsed node_rev_id
ASCII strings, separated by ASCII 0x20. The first node-revision ID is a
predecessor, and the second one is one of its successors.
The special string "END" on a single line signifies that the following
successor data belongs to the next revision.
(The design may be refined later to use a more efficient storage model.)
- Procedure for Readers -
A reader first reads the 'current' file and remembers the revision number.
It locates the node-revision map file corresponding to the given node_rev_id,
based on the node_rev_id's revision modulo a known fixed value.
It opens this file and reads it to obtain a list of revisions which created
successors of the given node_rev_id. It ignores lines listing node_rev_ids
not matching the given node_rev_id. It also ignores revisions greater than
'current'.
Next, the reader opens the corresponding revision map files,
based on revision numbers in the list, each modulo a known fixed value.
For each revision N in the revision list, it seeks to the revision's byte
offset within a revision map file and reads 4 bytes to obtain the offset
corresponding to revision N within a successor data file.
The reader then opens the corresponding successor data files,
based on revision numbers in the list, each modulo a known fixed value.
For each revision offset, it seeks to this offset and reads lines until it
finds the line "END". It loops through all lines and appends those
successor IDs to the set of successors which list a predecessor matching
the given node_rev_id.
In exceptional cases (see below) it is possible that a given revision
does not actually contain any successors of the given node_rev_id.
- Procedure for Writers -
Assume that the writer has access to a mapping from predecessor
node-revision ID to one or more successor node-revision IDs.
(The exact mechanism managing this mapping still needs to be determined.
But it can be assumed to be available as all predecessors and successors
are known within the context of a commit.)
When committing a finished transaction (in fs_fs.c:commit_body()),
the writer obtains a write-lock on all files within the successors
directory it needs to modify.
Let rN be the new revision the writer is committing.
The writer creates an empty temporary file.
If rN falls within the revision range of an existing successor data
file, the writer looks up the offset of revision N-1 in the corresponding
revision map file. It copies content from the corresponding successor data
file to a temporary file up to this offset, and copies any data that follows
until a line containing "END" has been copied. (Note that this step discards
data left behind by any previous attempt at committing rN).
The writer appends any new successor data to the temporary file (note
that there may be no successor data in case the revision is empty).
It then adds a terminating "END".
The writer creates another empty temporary file.
If rN falls within the revision range of an existing revision map file,
it copies ((N-2)*4) bytes of content from the revision map file into the
temporary file. (Note that this step discards data left behind by any
previous attempt at committing rN).
The writer appends, to the temporary file, the offset of the new data
it wrote into the successor data file.
Likewise, the writer creates empty temporary files for each node-revision
map files is needs to modify. It copies all content from any such
node-revision map files which already exist, and appends a line to each
file containing the node_revision ID and the new revision number.
After moving the proto-revprop file into place, and before updating
'current', the writer moves temporary files into place in the successors
directory, in the following order:
1) the new successor data file
2) the new revision map file
3) each new node_rev_id map file
If the writer fails to update all files in the successors directory,
it will also fail to update 'current'. In this case, readers will ignore
the new successor data until another commit succeeds in creating rN.
Once a commit of rN has succeeded, readers following node-rev-id map
entries updated by the failing commit might end up with an empty
successors list for rN. Such erroneous entries will not be cleaned
up automatically, but can be eliminated by re-creating the repository
(e.g. via a dump/load cycle). However, the actual successor data stored
for committed revisions is always correct, and the likelihood of incorrect
node-revision ID map entries to occur is small.
Re: 'svnadmin upgrade' Re: FSFS successor ID design draft
Posted by Daniel Shahaf <da...@elego.de>.
That's the tool I had in mind, but to "lazily populate the cache" is
the tricky bit.
Mark Phippard wrote on Tue, Sep 06, 2011 at 11:50:40 -0400:
> If it makes any sense, you could look at what we did in 1.5 for merge tracking.
>
> Merge tracking required a new bit of information -- the node origin
> index. Dump/Load automatically populated this index. svnadmin
> upgrade bumped the format but did not populate the index. Instead the
> index was lazily built as needed and you suffered the performance
> penalty of doing it this way. To offset this, we provided a separate
> tool svn-populate-node-origins-index which a user can run of they want
> to avoid the dump/load but still have predictable performance. The
> tool runs a lot faster than a dump/load and basically lets you
> manually pre-populate the index so that users do not get the
> inconsistent performance they would get if it was being built on the
> fly at unpredictable moments.
>
> Mark
>
>
>
> On Tue, Sep 6, 2011 at 11:42 AM, Daniel Shahaf <da...@elego.de> wrote:
> > r1165700 mentions that we need to decide what to do with 'svnadmin
> > upgrade'.
> >
> > 1. We could punt and require a dump/load. All format >=6 FSFS instances
> > always have a full successors store.
> >
> > 2. We could store the progeny shard size and the successors data shard
> > size in the 'format' file. If those values are absent (or zero),
> > then the successor lookup operation returns SVN_ERR_UNSUPPORTED_FEATURE.
> >
> > We can also reconstruct the successors cache without a dump/load, via
> > a tools/ binary that operates as follows:
> >
> > for (i = 0; i < CONSTANT; i++)
> > check 'current' and build the successors data up to that revision
> > with write lock:
> > check 'current' and build the successors data up to that revision
> > updates 'format' with the shard sizes
> > (release write lock)
> >
> > Requiring a dump/load is a barrier for _any_ upgrade from pre-1.8 to
> > post-1.8, so I prefer (2) to (1). 'svnadmin upgrade' might want to warn
> > about this.
> >
> > Stefan Sperling wrote on Thu, Sep 01, 2011 at 00:06:40 +0200:
> >> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
> >> > I'll try to tweak my proposal such that successor ID updates become
> >> > transactional and happen as part of every commit.
> >>
> >> Here's a first shot at this. Comments welcome.
> >>
> >> To support transactional semantics, any new data written to the FSFS
> >> filesystem must be tied to the newly created revision.
> >> This way, updating 'current' as the final step in each commit makes the
> >> new data appear. Failing to update 'current' will cause any data added
> >> by failing commits to be overwritten by the next successfull commit.
> >>
> >> The following design tries to keep this principle valid for sucessor-ids.
> >> There is one compromise though which hopefully won't hurt too much.
> >>
> >> Thanks again to danielsh for providing some initial feedback via IRC.
> >>
> >>
> >> Implementation proposal
> >> =======================
> >>
> >>
> >> - On-disk File Format -
> >>
> >> All files related to the map are stored in the repos/db/successors
> >> directory ("successors directory").
> >>
> >> The successor map contains 3 kinds of files:
> >>
> >> 1) Node-revision map files.
> >> These files map node-revision IDs to lists of revisions.
> >> This map answers the question:
> >> "In which revisions were successors of a node-revision created?"
> >>
> >> 2) Created-revision map file.
> >> These files map revision numbers of file offsets in successor data files.
> >> This map answers the question:
> >> "Where in the successor data are those successors which were created
> >> in revision N?"
> >>
> >> 3) Successor data files.
> >> These files store raw successor data.
> >>
> >> The different kinds of files refer to each other as shown below:
> >>
> >> node_rev_id map revision map successor data
> >> +-------+ +--------+ +-----------+
> >> | ... | | ... | | ... |
> >> +------>rN---------+ | offset | +----->successor |
> >> | | ... | | | offset | | | successor |
> >> | | ... | +----->offset----+ | END |
> >> node_rev_id --+ | rQ | | ... | | successor |
> >> | | ... | | offset | | ... |
> >> +------>rX---------+ | ... | | ... |
> >> | ... | | | ... | | END |
> >> | ... | +----->offset---------->successor |
> >> | rZ | | ... | | END |
> >> +-------+ +--------+ +-----------+
> >>
> >> Each type of file is described below in detail.
> >>
> >>
> >> -- Node-revision-ID map files --
> >>
> >> The purpose of node-revision-id map files is to facilitate lookup
> >> of successors of a given node-revision.
> >>
> >> The files are named after the number of the revision the node-revision
> >> was created in, modulo some fixed to-be-determined value (i.e. there
> >> won't be one file per node revision, but one file for every 10, 100,
> >> or so, node-revisions).
> >>
> >> The files are stored within the "node-revs" sub-directory:
> >>
> >> db/successors/node-revs/1
> >> db/successors/node-revs/2
> >> db/successors/node-revs/3
> >> ...
> >> db/successors/node-revs/N
> >> db/successors/node-revs/M
> >> ...
> >>
> >> Each node-revision map file stores a mapping of the form
> >> node_rev_id => [revnum, revnum, ...]
> >> The revision numbers identify those revisions in which one or more
> >> successors of a given node-revision were added.
> >>
> >> In the first iteration of this design, the mapping is stored as lines
> >> of ASCII text. Each line contains an unparsed node_revision_id, a space
> >> separator (ASCII 0x20), and a revision number in ASCII decimal representation.
> >> (The design may be refined later to use a more efficient storage model.)
> >>
> >>
> >> -- Revision map files --
> >>
> >> The purpose of the revision map file is to facilitate lookup
> >> of successor data created in a given revision.
> >>
> >> The files are named after the numbers of revisions they are responsible for,
> >> modulo some fixed to-be-determined value (i.e. there won't be one file
> >> per revision, but one file for every 10, 100, or so, revisions; each file
> >> is responsible for some range of revisions).
> >>
> >> The files are stored within the "revs" sub-directory:
> >>
> >> db/successors/revs/1
> >> db/successors/revs/2
> >> db/successors/revs/3
> >> ...
> >> db/successors/revs/N
> >> db/successors/revs/M
> >> ...
> >>
> >>
> >> Each file consists of an array of 64bit big-endian integers.
> >> The N'th integer (starting from N=1) in the file specifies the offset
> >> of successor data (in the corresponding successor data file) which was
> >> added in the N'th revision within the revision range the map file is
> >> responsible for.
> >>
> >>
> >> -- Successor-data files --
> >>
> >> These files use the same naming scheme as the revision map files (i.e.
> >> each successor data file is responsible for successors created within
> >> a specific range of revisions).
> >>
> >> The files are stored within the "successor-ids" sub-directory:
> >>
> >> db/successors/successor-ids/1
> >> db/successors/successor-ids/2
> >> db/successors/successor-ids/3
> >> ...
> >> db/successors/successor-ids/N
> >> db/successors/successor-ids/M
> >> ...
> >>
> >>
> >> Each file consists of lines each containing two unparsed node_rev_id
> >> ASCII strings, separated by ASCII 0x20. The first node-revision ID is a
> >> predecessor, and the second one is one of its successors.
> >> The special string "END" on a single line signifies that the following
> >> successor data belongs to the next revision.
> >> (The design may be refined later to use a more efficient storage model.)
> >>
> >>
> >> - Procedure for Readers -
> >>
> >> A reader first reads the 'current' file and remembers the revision number.
> >>
> >> It locates the node-revision map file corresponding to the given node_rev_id,
> >> based on the node_rev_id's revision modulo a known fixed value.
> >>
> >> It opens this file and reads it to obtain a list of revisions which created
> >> successors of the given node_rev_id. It ignores lines listing node_rev_ids
> >> not matching the given node_rev_id. It also ignores revisions greater than
> >> 'current'.
> >>
> >> Next, the reader opens the corresponding revision map files,
> >> based on revision numbers in the list, each modulo a known fixed value.
> >> For each revision N in the revision list, it seeks to the revision's byte
> >> offset within a revision map file and reads 4 bytes to obtain the offset
> >> corresponding to revision N within a successor data file.
> >>
> >> The reader then opens the corresponding successor data files,
> >> based on revision numbers in the list, each modulo a known fixed value.
> >> For each revision offset, it seeks to this offset and reads lines until it
> >> finds the line "END". It loops through all lines and appends those
> >> successor IDs to the set of successors which list a predecessor matching
> >> the given node_rev_id.
> >>
> >> In exceptional cases (see below) it is possible that a given revision
> >> does not actually contain any successors of the given node_rev_id.
> >>
> >>
> >> - Procedure for Writers -
> >>
> >> Assume that the writer has access to a mapping from predecessor
> >> node-revision ID to one or more successor node-revision IDs.
> >> (The exact mechanism managing this mapping still needs to be determined.
> >> But it can be assumed to be available as all predecessors and successors
> >> are known within the context of a commit.)
> >>
> >> When committing a finished transaction (in fs_fs.c:commit_body()),
> >> the writer obtains a write-lock on all files within the successors
> >> directory it needs to modify.
> >>
> >> Let rN be the new revision the writer is committing.
> >>
> >> The writer creates an empty temporary file.
> >>
> >> If rN falls within the revision range of an existing successor data
> >> file, the writer looks up the offset of revision N-1 in the corresponding
> >> revision map file. It copies content from the corresponding successor data
> >> file to a temporary file up to this offset, and copies any data that follows
> >> until a line containing "END" has been copied. (Note that this step discards
> >> data left behind by any previous attempt at committing rN).
> >>
> >> The writer appends any new successor data to the temporary file (note
> >> that there may be no successor data in case the revision is empty).
> >> It then adds a terminating "END".
> >>
> >> The writer creates another empty temporary file.
> >>
> >> If rN falls within the revision range of an existing revision map file,
> >> it copies ((N-2)*4) bytes of content from the revision map file into the
> >> temporary file. (Note that this step discards data left behind by any
> >> previous attempt at committing rN).
> >>
> >> The writer appends, to the temporary file, the offset of the new data
> >> it wrote into the successor data file.
> >>
> >> Likewise, the writer creates empty temporary files for each node-revision
> >> map files is needs to modify. It copies all content from any such
> >> node-revision map files which already exist, and appends a line to each
> >> file containing the node_revision ID and the new revision number.
> >>
> >> After moving the proto-revprop file into place, and before updating
> >> 'current', the writer moves temporary files into place in the successors
> >> directory, in the following order:
> >>
> >> 1) the new successor data file
> >> 2) the new revision map file
> >> 3) each new node_rev_id map file
> >>
> >> If the writer fails to update all files in the successors directory,
> >> it will also fail to update 'current'. In this case, readers will ignore
> >> the new successor data until another commit succeeds in creating rN.
> >> Once a commit of rN has succeeded, readers following node-rev-id map
> >> entries updated by the failing commit might end up with an empty
> >> successors list for rN. Such erroneous entries will not be cleaned
> >> up automatically, but can be eliminated by re-creating the repository
> >> (e.g. via a dump/load cycle). However, the actual successor data stored
> >> for committed revisions is always correct, and the likelihood of incorrect
> >> node-revision ID map entries to occur is small.
> >
>
>
>
> --
> Thanks
>
> Mark Phippard
> http://markphip.blogspot.com/
Re: 'svnadmin upgrade' Re: FSFS successor ID design draft
Posted by Mark Phippard <ma...@gmail.com>.
If it makes any sense, you could look at what we did in 1.5 for merge tracking.
Merge tracking required a new bit of information -- the node origin
index. Dump/Load automatically populated this index. svnadmin
upgrade bumped the format but did not populate the index. Instead the
index was lazily built as needed and you suffered the performance
penalty of doing it this way. To offset this, we provided a separate
tool svn-populate-node-origins-index which a user can run of they want
to avoid the dump/load but still have predictable performance. The
tool runs a lot faster than a dump/load and basically lets you
manually pre-populate the index so that users do not get the
inconsistent performance they would get if it was being built on the
fly at unpredictable moments.
Mark
On Tue, Sep 6, 2011 at 11:42 AM, Daniel Shahaf <da...@elego.de> wrote:
> r1165700 mentions that we need to decide what to do with 'svnadmin
> upgrade'.
>
> 1. We could punt and require a dump/load. All format >=6 FSFS instances
> always have a full successors store.
>
> 2. We could store the progeny shard size and the successors data shard
> size in the 'format' file. If those values are absent (or zero),
> then the successor lookup operation returns SVN_ERR_UNSUPPORTED_FEATURE.
>
> We can also reconstruct the successors cache without a dump/load, via
> a tools/ binary that operates as follows:
>
> for (i = 0; i < CONSTANT; i++)
> check 'current' and build the successors data up to that revision
> with write lock:
> check 'current' and build the successors data up to that revision
> updates 'format' with the shard sizes
> (release write lock)
>
> Requiring a dump/load is a barrier for _any_ upgrade from pre-1.8 to
> post-1.8, so I prefer (2) to (1). 'svnadmin upgrade' might want to warn
> about this.
>
> Stefan Sperling wrote on Thu, Sep 01, 2011 at 00:06:40 +0200:
>> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
>> > I'll try to tweak my proposal such that successor ID updates become
>> > transactional and happen as part of every commit.
>>
>> Here's a first shot at this. Comments welcome.
>>
>> To support transactional semantics, any new data written to the FSFS
>> filesystem must be tied to the newly created revision.
>> This way, updating 'current' as the final step in each commit makes the
>> new data appear. Failing to update 'current' will cause any data added
>> by failing commits to be overwritten by the next successfull commit.
>>
>> The following design tries to keep this principle valid for sucessor-ids.
>> There is one compromise though which hopefully won't hurt too much.
>>
>> Thanks again to danielsh for providing some initial feedback via IRC.
>>
>>
>> Implementation proposal
>> =======================
>>
>>
>> - On-disk File Format -
>>
>> All files related to the map are stored in the repos/db/successors
>> directory ("successors directory").
>>
>> The successor map contains 3 kinds of files:
>>
>> 1) Node-revision map files.
>> These files map node-revision IDs to lists of revisions.
>> This map answers the question:
>> "In which revisions were successors of a node-revision created?"
>>
>> 2) Created-revision map file.
>> These files map revision numbers of file offsets in successor data files.
>> This map answers the question:
>> "Where in the successor data are those successors which were created
>> in revision N?"
>>
>> 3) Successor data files.
>> These files store raw successor data.
>>
>> The different kinds of files refer to each other as shown below:
>>
>> node_rev_id map revision map successor data
>> +-------+ +--------+ +-----------+
>> | ... | | ... | | ... |
>> +------>rN---------+ | offset | +----->successor |
>> | | ... | | | offset | | | successor |
>> | | ... | +----->offset----+ | END |
>> node_rev_id --+ | rQ | | ... | | successor |
>> | | ... | | offset | | ... |
>> +------>rX---------+ | ... | | ... |
>> | ... | | | ... | | END |
>> | ... | +----->offset---------->successor |
>> | rZ | | ... | | END |
>> +-------+ +--------+ +-----------+
>>
>> Each type of file is described below in detail.
>>
>>
>> -- Node-revision-ID map files --
>>
>> The purpose of node-revision-id map files is to facilitate lookup
>> of successors of a given node-revision.
>>
>> The files are named after the number of the revision the node-revision
>> was created in, modulo some fixed to-be-determined value (i.e. there
>> won't be one file per node revision, but one file for every 10, 100,
>> or so, node-revisions).
>>
>> The files are stored within the "node-revs" sub-directory:
>>
>> db/successors/node-revs/1
>> db/successors/node-revs/2
>> db/successors/node-revs/3
>> ...
>> db/successors/node-revs/N
>> db/successors/node-revs/M
>> ...
>>
>> Each node-revision map file stores a mapping of the form
>> node_rev_id => [revnum, revnum, ...]
>> The revision numbers identify those revisions in which one or more
>> successors of a given node-revision were added.
>>
>> In the first iteration of this design, the mapping is stored as lines
>> of ASCII text. Each line contains an unparsed node_revision_id, a space
>> separator (ASCII 0x20), and a revision number in ASCII decimal representation.
>> (The design may be refined later to use a more efficient storage model.)
>>
>>
>> -- Revision map files --
>>
>> The purpose of the revision map file is to facilitate lookup
>> of successor data created in a given revision.
>>
>> The files are named after the numbers of revisions they are responsible for,
>> modulo some fixed to-be-determined value (i.e. there won't be one file
>> per revision, but one file for every 10, 100, or so, revisions; each file
>> is responsible for some range of revisions).
>>
>> The files are stored within the "revs" sub-directory:
>>
>> db/successors/revs/1
>> db/successors/revs/2
>> db/successors/revs/3
>> ...
>> db/successors/revs/N
>> db/successors/revs/M
>> ...
>>
>>
>> Each file consists of an array of 64bit big-endian integers.
>> The N'th integer (starting from N=1) in the file specifies the offset
>> of successor data (in the corresponding successor data file) which was
>> added in the N'th revision within the revision range the map file is
>> responsible for.
>>
>>
>> -- Successor-data files --
>>
>> These files use the same naming scheme as the revision map files (i.e.
>> each successor data file is responsible for successors created within
>> a specific range of revisions).
>>
>> The files are stored within the "successor-ids" sub-directory:
>>
>> db/successors/successor-ids/1
>> db/successors/successor-ids/2
>> db/successors/successor-ids/3
>> ...
>> db/successors/successor-ids/N
>> db/successors/successor-ids/M
>> ...
>>
>>
>> Each file consists of lines each containing two unparsed node_rev_id
>> ASCII strings, separated by ASCII 0x20. The first node-revision ID is a
>> predecessor, and the second one is one of its successors.
>> The special string "END" on a single line signifies that the following
>> successor data belongs to the next revision.
>> (The design may be refined later to use a more efficient storage model.)
>>
>>
>> - Procedure for Readers -
>>
>> A reader first reads the 'current' file and remembers the revision number.
>>
>> It locates the node-revision map file corresponding to the given node_rev_id,
>> based on the node_rev_id's revision modulo a known fixed value.
>>
>> It opens this file and reads it to obtain a list of revisions which created
>> successors of the given node_rev_id. It ignores lines listing node_rev_ids
>> not matching the given node_rev_id. It also ignores revisions greater than
>> 'current'.
>>
>> Next, the reader opens the corresponding revision map files,
>> based on revision numbers in the list, each modulo a known fixed value.
>> For each revision N in the revision list, it seeks to the revision's byte
>> offset within a revision map file and reads 4 bytes to obtain the offset
>> corresponding to revision N within a successor data file.
>>
>> The reader then opens the corresponding successor data files,
>> based on revision numbers in the list, each modulo a known fixed value.
>> For each revision offset, it seeks to this offset and reads lines until it
>> finds the line "END". It loops through all lines and appends those
>> successor IDs to the set of successors which list a predecessor matching
>> the given node_rev_id.
>>
>> In exceptional cases (see below) it is possible that a given revision
>> does not actually contain any successors of the given node_rev_id.
>>
>>
>> - Procedure for Writers -
>>
>> Assume that the writer has access to a mapping from predecessor
>> node-revision ID to one or more successor node-revision IDs.
>> (The exact mechanism managing this mapping still needs to be determined.
>> But it can be assumed to be available as all predecessors and successors
>> are known within the context of a commit.)
>>
>> When committing a finished transaction (in fs_fs.c:commit_body()),
>> the writer obtains a write-lock on all files within the successors
>> directory it needs to modify.
>>
>> Let rN be the new revision the writer is committing.
>>
>> The writer creates an empty temporary file.
>>
>> If rN falls within the revision range of an existing successor data
>> file, the writer looks up the offset of revision N-1 in the corresponding
>> revision map file. It copies content from the corresponding successor data
>> file to a temporary file up to this offset, and copies any data that follows
>> until a line containing "END" has been copied. (Note that this step discards
>> data left behind by any previous attempt at committing rN).
>>
>> The writer appends any new successor data to the temporary file (note
>> that there may be no successor data in case the revision is empty).
>> It then adds a terminating "END".
>>
>> The writer creates another empty temporary file.
>>
>> If rN falls within the revision range of an existing revision map file,
>> it copies ((N-2)*4) bytes of content from the revision map file into the
>> temporary file. (Note that this step discards data left behind by any
>> previous attempt at committing rN).
>>
>> The writer appends, to the temporary file, the offset of the new data
>> it wrote into the successor data file.
>>
>> Likewise, the writer creates empty temporary files for each node-revision
>> map files is needs to modify. It copies all content from any such
>> node-revision map files which already exist, and appends a line to each
>> file containing the node_revision ID and the new revision number.
>>
>> After moving the proto-revprop file into place, and before updating
>> 'current', the writer moves temporary files into place in the successors
>> directory, in the following order:
>>
>> 1) the new successor data file
>> 2) the new revision map file
>> 3) each new node_rev_id map file
>>
>> If the writer fails to update all files in the successors directory,
>> it will also fail to update 'current'. In this case, readers will ignore
>> the new successor data until another commit succeeds in creating rN.
>> Once a commit of rN has succeeded, readers following node-rev-id map
>> entries updated by the failing commit might end up with an empty
>> successors list for rN. Such erroneous entries will not be cleaned
>> up automatically, but can be eliminated by re-creating the repository
>> (e.g. via a dump/load cycle). However, the actual successor data stored
>> for committed revisions is always correct, and the likelihood of incorrect
>> node-revision ID map entries to occur is small.
>
--
Thanks
Mark Phippard
http://markphip.blogspot.com/
Re: 'svnadmin upgrade' Re: FSFS successor ID design draft
Posted by Stefan Sperling <st...@elego.de>.
On Tue, Sep 06, 2011 at 06:42:44PM +0300, Daniel Shahaf wrote:
> r1165700 mentions that we need to decide what to do with 'svnadmin
> upgrade'.
>
> 1. We could punt and require a dump/load. All format >=6 FSFS instances
> always have a full successors store.
>
> 2. We could store the progeny shard size and the successors data shard
> size in the 'format' file. If those values are absent (or zero),
> then the successor lookup operation returns SVN_ERR_UNSUPPORTED_FEATURE.
>
> We can also reconstruct the successors cache without a dump/load, via
> a tools/ binary that operates as follows:
>
> for (i = 0; i < CONSTANT; i++)
> check 'current' and build the successors data up to that revision
> with write lock:
> check 'current' and build the successors data up to that revision
> updates 'format' with the shard sizes
> (release write lock)
>
3. Have 'svnadmin upgrade' populate successor data by harvesting
existing revision files.
This will take a while. I don't know how long exactly.
As I mentioned in the commit message, if we do for this route we should
at least provide progress information (e.g. in form of outputting the
numbers of revisions which have been processed).
Upgrade code will also need to be written for the BDB backend.
'svnadmin upgrade' Re: FSFS successor ID design draft
Posted by Daniel Shahaf <da...@elego.de>.
r1165700 mentions that we need to decide what to do with 'svnadmin
upgrade'.
1. We could punt and require a dump/load. All format >=6 FSFS instances
always have a full successors store.
2. We could store the progeny shard size and the successors data shard
size in the 'format' file. If those values are absent (or zero),
then the successor lookup operation returns SVN_ERR_UNSUPPORTED_FEATURE.
We can also reconstruct the successors cache without a dump/load, via
a tools/ binary that operates as follows:
for (i = 0; i < CONSTANT; i++)
check 'current' and build the successors data up to that revision
with write lock:
check 'current' and build the successors data up to that revision
updates 'format' with the shard sizes
(release write lock)
Requiring a dump/load is a barrier for _any_ upgrade from pre-1.8 to
post-1.8, so I prefer (2) to (1). 'svnadmin upgrade' might want to warn
about this.
Stefan Sperling wrote on Thu, Sep 01, 2011 at 00:06:40 +0200:
> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
> > I'll try to tweak my proposal such that successor ID updates become
> > transactional and happen as part of every commit.
>
> Here's a first shot at this. Comments welcome.
>
> To support transactional semantics, any new data written to the FSFS
> filesystem must be tied to the newly created revision.
> This way, updating 'current' as the final step in each commit makes the
> new data appear. Failing to update 'current' will cause any data added
> by failing commits to be overwritten by the next successfull commit.
>
> The following design tries to keep this principle valid for sucessor-ids.
> There is one compromise though which hopefully won't hurt too much.
>
> Thanks again to danielsh for providing some initial feedback via IRC.
>
>
> Implementation proposal
> =======================
>
>
> - On-disk File Format -
>
> All files related to the map are stored in the repos/db/successors
> directory ("successors directory").
>
> The successor map contains 3 kinds of files:
>
> 1) Node-revision map files.
> These files map node-revision IDs to lists of revisions.
> This map answers the question:
> "In which revisions were successors of a node-revision created?"
>
> 2) Created-revision map file.
> These files map revision numbers of file offsets in successor data files.
> This map answers the question:
> "Where in the successor data are those successors which were created
> in revision N?"
>
> 3) Successor data files.
> These files store raw successor data.
>
> The different kinds of files refer to each other as shown below:
>
> node_rev_id map revision map successor data
> +-------+ +--------+ +-----------+
> | ... | | ... | | ... |
> +------>rN---------+ | offset | +----->successor |
> | | ... | | | offset | | | successor |
> | | ... | +----->offset----+ | END |
> node_rev_id --+ | rQ | | ... | | successor |
> | | ... | | offset | | ... |
> +------>rX---------+ | ... | | ... |
> | ... | | | ... | | END |
> | ... | +----->offset---------->successor |
> | rZ | | ... | | END |
> +-------+ +--------+ +-----------+
>
> Each type of file is described below in detail.
>
>
> -- Node-revision-ID map files --
>
> The purpose of node-revision-id map files is to facilitate lookup
> of successors of a given node-revision.
>
> The files are named after the number of the revision the node-revision
> was created in, modulo some fixed to-be-determined value (i.e. there
> won't be one file per node revision, but one file for every 10, 100,
> or so, node-revisions).
>
> The files are stored within the "node-revs" sub-directory:
>
> db/successors/node-revs/1
> db/successors/node-revs/2
> db/successors/node-revs/3
> ...
> db/successors/node-revs/N
> db/successors/node-revs/M
> ...
>
> Each node-revision map file stores a mapping of the form
> node_rev_id => [revnum, revnum, ...]
> The revision numbers identify those revisions in which one or more
> successors of a given node-revision were added.
>
> In the first iteration of this design, the mapping is stored as lines
> of ASCII text. Each line contains an unparsed node_revision_id, a space
> separator (ASCII 0x20), and a revision number in ASCII decimal representation.
> (The design may be refined later to use a more efficient storage model.)
>
>
> -- Revision map files --
>
> The purpose of the revision map file is to facilitate lookup
> of successor data created in a given revision.
>
> The files are named after the numbers of revisions they are responsible for,
> modulo some fixed to-be-determined value (i.e. there won't be one file
> per revision, but one file for every 10, 100, or so, revisions; each file
> is responsible for some range of revisions).
>
> The files are stored within the "revs" sub-directory:
>
> db/successors/revs/1
> db/successors/revs/2
> db/successors/revs/3
> ...
> db/successors/revs/N
> db/successors/revs/M
> ...
>
>
> Each file consists of an array of 64bit big-endian integers.
> The N'th integer (starting from N=1) in the file specifies the offset
> of successor data (in the corresponding successor data file) which was
> added in the N'th revision within the revision range the map file is
> responsible for.
>
>
> -- Successor-data files --
>
> These files use the same naming scheme as the revision map files (i.e.
> each successor data file is responsible for successors created within
> a specific range of revisions).
>
> The files are stored within the "successor-ids" sub-directory:
>
> db/successors/successor-ids/1
> db/successors/successor-ids/2
> db/successors/successor-ids/3
> ...
> db/successors/successor-ids/N
> db/successors/successor-ids/M
> ...
>
>
> Each file consists of lines each containing two unparsed node_rev_id
> ASCII strings, separated by ASCII 0x20. The first node-revision ID is a
> predecessor, and the second one is one of its successors.
> The special string "END" on a single line signifies that the following
> successor data belongs to the next revision.
> (The design may be refined later to use a more efficient storage model.)
>
>
> - Procedure for Readers -
>
> A reader first reads the 'current' file and remembers the revision number.
>
> It locates the node-revision map file corresponding to the given node_rev_id,
> based on the node_rev_id's revision modulo a known fixed value.
>
> It opens this file and reads it to obtain a list of revisions which created
> successors of the given node_rev_id. It ignores lines listing node_rev_ids
> not matching the given node_rev_id. It also ignores revisions greater than
> 'current'.
>
> Next, the reader opens the corresponding revision map files,
> based on revision numbers in the list, each modulo a known fixed value.
> For each revision N in the revision list, it seeks to the revision's byte
> offset within a revision map file and reads 4 bytes to obtain the offset
> corresponding to revision N within a successor data file.
>
> The reader then opens the corresponding successor data files,
> based on revision numbers in the list, each modulo a known fixed value.
> For each revision offset, it seeks to this offset and reads lines until it
> finds the line "END". It loops through all lines and appends those
> successor IDs to the set of successors which list a predecessor matching
> the given node_rev_id.
>
> In exceptional cases (see below) it is possible that a given revision
> does not actually contain any successors of the given node_rev_id.
>
>
> - Procedure for Writers -
>
> Assume that the writer has access to a mapping from predecessor
> node-revision ID to one or more successor node-revision IDs.
> (The exact mechanism managing this mapping still needs to be determined.
> But it can be assumed to be available as all predecessors and successors
> are known within the context of a commit.)
>
> When committing a finished transaction (in fs_fs.c:commit_body()),
> the writer obtains a write-lock on all files within the successors
> directory it needs to modify.
>
> Let rN be the new revision the writer is committing.
>
> The writer creates an empty temporary file.
>
> If rN falls within the revision range of an existing successor data
> file, the writer looks up the offset of revision N-1 in the corresponding
> revision map file. It copies content from the corresponding successor data
> file to a temporary file up to this offset, and copies any data that follows
> until a line containing "END" has been copied. (Note that this step discards
> data left behind by any previous attempt at committing rN).
>
> The writer appends any new successor data to the temporary file (note
> that there may be no successor data in case the revision is empty).
> It then adds a terminating "END".
>
> The writer creates another empty temporary file.
>
> If rN falls within the revision range of an existing revision map file,
> it copies ((N-2)*4) bytes of content from the revision map file into the
> temporary file. (Note that this step discards data left behind by any
> previous attempt at committing rN).
>
> The writer appends, to the temporary file, the offset of the new data
> it wrote into the successor data file.
>
> Likewise, the writer creates empty temporary files for each node-revision
> map files is needs to modify. It copies all content from any such
> node-revision map files which already exist, and appends a line to each
> file containing the node_revision ID and the new revision number.
>
> After moving the proto-revprop file into place, and before updating
> 'current', the writer moves temporary files into place in the successors
> directory, in the following order:
>
> 1) the new successor data file
> 2) the new revision map file
> 3) each new node_rev_id map file
>
> If the writer fails to update all files in the successors directory,
> it will also fail to update 'current'. In this case, readers will ignore
> the new successor data until another commit succeeds in creating rN.
> Once a commit of rN has succeeded, readers following node-rev-id map
> entries updated by the failing commit might end up with an empty
> successors list for rN. Such erroneous entries will not be cleaned
> up automatically, but can be eliminated by re-creating the repository
> (e.g. via a dump/load cycle). However, the actual successor data stored
> for committed revisions is always correct, and the likelihood of incorrect
> node-revision ID map entries to occur is small.
Re: FSFS successor ID design draft
Posted by Daniel Shahaf <da...@elego.de>.
Daniel Shahaf wrote on Sun, Sep 04, 2011 at 02:23:28 +0300:
> some noderevs --- for example, the noderev for ^/subversion/trunk/BUGS
> --- are copied much more than others,
Bad example.
Re: FSFS successor ID design draft
Posted by Daniel Shahaf <da...@elego.de>.
Stefan Sperling wrote on Mon, Sep 05, 2011 at 12:52:10 +0200:
> On Mon, Sep 05, 2011 at 01:23:14PM +0300, Daniel Shahaf wrote:
> > Stefan Sperling wrote on Mon, Sep 05, 2011 at 11:38:11 +0200:
> > > So you're saying that we should run the plaintext proposed above
> > > through svndiff? Can you explain in more detail how this would work?
> > > What is the base of a delta?
> > >
> >
> > The file contains one or more DELTA\n..ENDREP\n streams:
> >
> > DELTA
> > <svndiff stream>
> > ENDREP
> > DELTA
> > <svndiff stream>
> > ENDREP
> >
> > (In second thought, we should be storing the length of the stream
> > somewhere; on the DELTA header seems a fine place:
> >
> > DELTA 512
> > <512 bytes of svndiff stream>
> > ENDREP
> > DELTA 37
> > <37 bytes of svndiff stream>
> > ENDREP
> >
> > .) When the file is read, readers decode all the deltas and concatenate
> > the resulting plaintexts. When the file is rewritten, writers
> > optionally combine the first N deltas into a single delta that produces
> > the combined plaintext.
> >
> > The deltas can be self-compressed (like a DELTA\n rep in the revision
> > files), ie, having no base.
>
> OK, I see. You're trying to save disk space, trading it for CPU time
> during read/write operations. Does that make sense? Is the amount of
> data really going to be big enough to be worth it?
>
When you phrase it that way: I doubt it.
You suggested a 'more efficient storage model', so I remarked about one
idea that crossed my mind. Obviously there are others, such as grouping
the storage by LHS of the mapping, rather than scattering map entries
with the same LHS all over the file.
> > > What is 'lhs'?
> > lhs = left-hand side
> > rhs = right-hand side
>
> > How about calling them after ths RHS'es of the mappings rather than
> > after the fact that they are mappings?
> >
> >
> > Currently:
> >
> > - noderev map file, revision map file, successors data file
> >
> > Perhaps:
> >
> > - noderev posterity file, successor offsets file, successors data file
>
> These names are fine with me.
>
> What would you call them on disk?
>
/successors/progeny/M
/successors/offsets/N
/successors/data/N
where M and N are the oldest revision number of their respective shards.
(So, for example, M = 0, 1000, 2000, 3000... )
Can probably improve on those names a bit...
Re: FSFS successor ID design draft
Posted by Stefan Sperling <st...@elego.de>.
On Mon, Sep 05, 2011 at 01:23:14PM +0300, Daniel Shahaf wrote:
> Stefan Sperling wrote on Mon, Sep 05, 2011 at 11:38:11 +0200:
> > So you're saying that we should run the plaintext proposed above
> > through svndiff? Can you explain in more detail how this would work?
> > What is the base of a delta?
> >
>
> The file contains one or more DELTA\n..ENDREP\n streams:
>
> DELTA
> <svndiff stream>
> ENDREP
> DELTA
> <svndiff stream>
> ENDREP
>
> (In second thought, we should be storing the length of the stream
> somewhere; on the DELTA header seems a fine place:
>
> DELTA 512
> <512 bytes of svndiff stream>
> ENDREP
> DELTA 37
> <37 bytes of svndiff stream>
> ENDREP
>
> .) When the file is read, readers decode all the deltas and concatenate
> the resulting plaintexts. When the file is rewritten, writers
> optionally combine the first N deltas into a single delta that produces
> the combined plaintext.
>
> The deltas can be self-compressed (like a DELTA\n rep in the revision
> files), ie, having no base.
OK, I see. You're trying to save disk space, trading it for CPU time
during read/write operations. Does that make sense? Is the amount of
data really going to be big enough to be worth it?
> > What is 'lhs'?
> lhs = left-hand side
> rhs = right-hand side
> How about calling them after ths RHS'es of the mappings rather than
> after the fact that they are mappings?
>
>
> Currently:
>
> - noderev map file, revision map file, successors data file
>
> Perhaps:
>
> - noderev posterity file, successor offsets file, successors data file
These names are fine with me.
What would you call them on disk?
> (Is 'progeny' the more appropriate word here?
I like 'progeny' because it means 'immediate offspring'.
'Posterity' includes all ancestors in all generations, and that's not
what the file is storing.
> > I am happy to just leave this debris in the files for now.
> >
> > I would guess that nobody will ever even notice this problem in practice.
> > The number of commits failing within the time window where succesor data
> > is updated will statistically be very low to begin with.
> > Each time it happens we lose a very small fraction of disk space. We also
> > suffer a teeny tiny bit of read performance loss for readers of successors
> > of the affected node-revision. So what...
> >
> > If it ever becomes a real problem, people can dump/load.
> >
>
> It'll work, but it's a kill a fly with a fleet approach :). Dump/load
> the entire history (many MB of svndiffs) only to fix some derived
> noderev->offset map data?
Sure, it's not optimal. I doubt anyone will be bothered enough to
perform a dump/load just for this.
Re: FSFS successor ID design draft
Posted by Daniel Shahaf <da...@elego.de>.
Stefan Sperling wrote on Mon, Sep 05, 2011 at 11:38:11 +0200:
> On Sun, Sep 04, 2011 at 02:23:28AM +0300, Daniel Shahaf wrote:
> > > Each node-revision map file stores a mapping of the form
> > > node_rev_id => [revnum, revnum, ...]
> > > The revision numbers identify those revisions in which one or more
> > > successors of a given node-revision were added.
> > >
> > > In the first iteration of this design, the mapping is stored as lines
> > > of ASCII text. Each line contains an unparsed node_revision_id, a space
> > > separator (ASCII 0x20), and a revision number in ASCII decimal representation.
> > > (The design may be refined later to use a more efficient storage model.)
> > >
> >
> > Some wild ideas here:
> >
> > - Multiple, concatenated DELTA\n..ENDREP\n svndiff streams. That's
> > appendable and compressible (a deltify process can combin adjacent
> > streams, which will trigger zlib compression).
> >
> > (That won't work for the successors data since offsets into it are
> > stored elsewhere.)
>
> So you're saying that we should run the plaintext proposed above
> through svndiff? Can you explain in more detail how this would work?
> What is the base of a delta?
>
The file contains one or more DELTA\n..ENDREP\n streams:
DELTA
<svndiff stream>
ENDREP
DELTA
<svndiff stream>
ENDREP
(In second thought, we should be storing the length of the stream
somewhere; on the DELTA header seems a fine place:
DELTA 512
<512 bytes of svndiff stream>
ENDREP
DELTA 37
<37 bytes of svndiff stream>
ENDREP
.) When the file is read, readers decode all the deltas and concatenate
the resulting plaintexts. When the file is rewritten, writers
optionally combine the first N deltas into a single delta that produces
the combined plaintext.
The deltas can be self-compressed (like a DELTA\n rep in the revision
files), ie, having no base.
> > - Some packing support that also implements grouping of all the map
> > entries with the same lhs? Is that needed, or should the API at this
>
> What is 'lhs'?
>
lhs = left-hand side
rhs = right-hand side
> > level only implement 'slurp the entire map into a hash mapping ints to
> > arrays of revnums'?
>
> I would say so, with the possible retriction that only a certain range
> of revisions is slurped into memory. This way, the API can optimise for
> callers which are only interested in a certain revision range (e.g.
> graphing tools can reconstruct the history of a file in several steps).
>
> > (OT: those terms for the three kinds of files you have haven't sat well
> > with me; from the term alone I couldn't instantly recall what the
> > contents of the file were.)
>
> What would you call them? I'm open to suggestions.
>
How about calling them after ths RHS'es of the mappings rather than
after the fact that they are mappings?
Currently:
- noderev map file, revision map file, successors data file
Perhaps:
- noderev posterity file, successor offsets file, successors data file
(Is 'progeny' the more appropriate word here? I'm not sufficiently
familiar with its use, and there are no mentions of it as a simple noun
in the dev@ archives...)
> > > In exceptional cases (see below) it is possible that a given revision
> > > does not actually contain any successors of the given node_rev_id.
> > >
> >
> > Implementation question: would it make sense to have a mode for
> > inquiring about several noderev's successors at the same time, in order
> > to amortize the lookup operation (three open()s, several read()s of the
> > successor data file)'s cost across them?
>
> Yes, sure.
>
> The API could take a list of node-revision IDs and return a hash table
> keyed on node-revision ID, with the values being arrays of revision offsets.
>
+1
> > > When committing a finished transaction (in fs_fs.c:commit_body()),
> > > the writer obtains a write-lock on all files within the successors
> > > directory it needs to modify.
> > >
> >
> > Clarification: do you propose that a single write lock be obtained to
> > cover the entire successors/** hierarchy?
> >
> > Also: is the FSFS write lock (which is held by commit_body() whilst it
> > runs) sufficient for this?
>
> I would say the global write lock is sufficient.
>
> I wasn't sure how exactly locking in FSFS works. You can read this
> statement as "the writer has some kind of write lock on everything it
> needs to change, possibly implied by a global write lock".
>
Okay.
> > > If rN falls within the revision range of an existing revision map file,
> > > it copies ((N-2)*4) bytes of content from the revision map file into the
> > > temporary file. (Note that this step discards data left behind by any
> > > previous attempt at committing rN).
> > >
> >
> > ((N-2)*4) is bogus for N=1, and it's also missing a modulo operation
> > somewhere.
>
> Math is hard!
>
> > But the gist is clear: copy the four bytes of every
> > preceding revision in the shard.
>
> Yup.
>
:-)
> > > If the writer fails to update all files in the successors directory,
> > > it will also fail to update 'current'. In this case, readers will ignore
> > > the new successor data until another commit succeeds in creating rN.
> > > Once a commit of rN has succeeded, readers following node-rev-id map
> > > entries updated by the failing commit might end up with an empty
> > > successors list for rN. Such erroneous entries will not be cleaned
> > > up automatically, but can be eliminated by re-creating the repository
> > > (e.g. via a dump/load cycle).
> >
> > Near the start you referred to a 'compromise'. Is that the compromise?
>
> This is what I meant, yes.
>
Okay.
> > That said, one issue. Debris in the successor data file or revision map
> > file will be overwritten as soon as an attempt to commit rN succeeds;
> > however, noderev map entries remain until a dump/load. How feasible
> > would it be to also have a cleanup procedure for them?
>
> I am happy to just leave this debris in the files for now.
>
> I would guess that nobody will ever even notice this problem in practice.
> The number of commits failing within the time window where succesor data
> is updated will statistically be very low to begin with.
> Each time it happens we lose a very small fraction of disk space. We also
> suffer a teeny tiny bit of read performance loss for readers of successors
> of the affected node-revision. So what...
>
> If it ever becomes a real problem, people can dump/load.
>
It'll work, but it's a kill a fly with a fleet approach :). Dump/load
the entire history (many MB of svndiffs) only to fix some derived
noderev->offset map data?
> One thing that is a little annoying is that file checksums for successor
> maps in production and backup repositories might not match up. Folks
> might then infer that there is some kind of repository corruption.
> So we should make 'svnadmin verify' print a warning if we find debris
> entries in the map. The warning would also explain that this is harmless
> and does not constitute corruption.
>
Sounds fine. (And another job for the svn_fs__verify() API!)
> > Such a cleanup procedure could grab the commits (and successors, if it's
> > separate) write locks, attempt to read the successors data for all
> > noderevs in a noderev map file, and delete the bogus entries from the
> > noderev map file. (It could delete them either by atomically replacing
> > the file with a new version, or by replacing the first byte of the
> > revnum by some agreed non-[0-9\n] byte representing "This line of the
> > noderev map file shall be ignored".
> >
> > (it must be a single byte because some revnums are represented in ASCII
> > by a single byte)
>
> If you really want to we can always bolt something like this on later.
Agreed.
(Did I just propose another instance of "Let's bolt <another> thing on FSFS!"?)
Re: FSFS successor ID design draft
Posted by Stefan Sperling <st...@elego.de>.
On Sun, Sep 04, 2011 at 02:23:28AM +0300, Daniel Shahaf wrote:
> > Each node-revision map file stores a mapping of the form
> > node_rev_id => [revnum, revnum, ...]
> > The revision numbers identify those revisions in which one or more
> > successors of a given node-revision were added.
> >
> > In the first iteration of this design, the mapping is stored as lines
> > of ASCII text. Each line contains an unparsed node_revision_id, a space
> > separator (ASCII 0x20), and a revision number in ASCII decimal representation.
> > (The design may be refined later to use a more efficient storage model.)
> >
>
> Some wild ideas here:
>
> - Multiple, concatenated DELTA\n..ENDREP\n svndiff streams. That's
> appendable and compressible (a deltify process can combin adjacent
> streams, which will trigger zlib compression).
>
> (That won't work for the successors data since offsets into it are
> stored elsewhere.)
So you're saying that we should run the plaintext proposed above
through svndiff? Can you explain in more detail how this would work?
What is the base of a delta?
> - Some packing support that also implements grouping of all the map
> entries with the same lhs? Is that needed, or should the API at this
What is 'lhs'?
> level only implement 'slurp the entire map into a hash mapping ints to
> arrays of revnums'?
I would say so, with the possible retriction that only a certain range
of revisions is slurped into memory. This way, the API can optimise for
callers which are only interested in a certain revision range (e.g.
graphing tools can reconstruct the history of a file in several steps).
> (OT: those terms for the three kinds of files you have haven't sat well
> with me; from the term alone I couldn't instantly recall what the
> contents of the file were.)
What would you call them? I'm open to suggestions.
> > In exceptional cases (see below) it is possible that a given revision
> > does not actually contain any successors of the given node_rev_id.
> >
>
> Implementation question: would it make sense to have a mode for
> inquiring about several noderev's successors at the same time, in order
> to amortize the lookup operation (three open()s, several read()s of the
> successor data file)'s cost across them?
Yes, sure.
The API could take a list of node-revision IDs and return a hash table
keyed on node-revision ID, with the values being arrays of revision offsets.
> > When committing a finished transaction (in fs_fs.c:commit_body()),
> > the writer obtains a write-lock on all files within the successors
> > directory it needs to modify.
> >
>
> Clarification: do you propose that a single write lock be obtained to
> cover the entire successors/** hierarchy?
>
> Also: is the FSFS write lock (which is held by commit_body() whilst it
> runs) sufficient for this?
I would say the global write lock is sufficient.
I wasn't sure how exactly locking in FSFS works. You can read this
statement as "the writer has some kind of write lock on everything it
needs to change, possibly implied by a global write lock".
> > If rN falls within the revision range of an existing revision map file,
> > it copies ((N-2)*4) bytes of content from the revision map file into the
> > temporary file. (Note that this step discards data left behind by any
> > previous attempt at committing rN).
> >
>
> ((N-2)*4) is bogus for N=1, and it's also missing a modulo operation
> somewhere.
Math is hard!
> But the gist is clear: copy the four bytes of every
> preceding revision in the shard.
Yup.
> > If the writer fails to update all files in the successors directory,
> > it will also fail to update 'current'. In this case, readers will ignore
> > the new successor data until another commit succeeds in creating rN.
> > Once a commit of rN has succeeded, readers following node-rev-id map
> > entries updated by the failing commit might end up with an empty
> > successors list for rN. Such erroneous entries will not be cleaned
> > up automatically, but can be eliminated by re-creating the repository
> > (e.g. via a dump/load cycle).
>
> Near the start you referred to a 'compromise'. Is that the compromise?
This is what I meant, yes.
> That said, one issue. Debris in the successor data file or revision map
> file will be overwritten as soon as an attempt to commit rN succeeds;
> however, noderev map entries remain until a dump/load. How feasible
> would it be to also have a cleanup procedure for them?
I am happy to just leave this debris in the files for now.
I would guess that nobody will ever even notice this problem in practice.
The number of commits failing within the time window where succesor data
is updated will statistically be very low to begin with.
Each time it happens we lose a very small fraction of disk space. We also
suffer a teeny tiny bit of read performance loss for readers of successors
of the affected node-revision. So what...
If it ever becomes a real problem, people can dump/load.
One thing that is a little annoying is that file checksums for successor
maps in production and backup repositories might not match up. Folks
might then infer that there is some kind of repository corruption.
So we should make 'svnadmin verify' print a warning if we find debris
entries in the map. The warning would also explain that this is harmless
and does not constitute corruption.
> Such a cleanup procedure could grab the commits (and successors, if it's
> separate) write locks, attempt to read the successors data for all
> noderevs in a noderev map file, and delete the bogus entries from the
> noderev map file. (It could delete them either by atomically replacing
> the file with a new version, or by replacing the first byte of the
> revnum by some agreed non-[0-9\n] byte representing "This line of the
> noderev map file shall be ignored".
>
> (it must be a single byte because some revnums are represented in ASCII
> by a single byte)
If you really want to we can always bolt something like this on later.
Re: FSFS successor ID design draft
Posted by Daniel Shahaf <da...@elego.de>.
Stefan Sperling wrote on Thu, Sep 01, 2011 at 00:06:40 +0200:
> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
> > I'll try to tweak my proposal such that successor ID updates become
> > transactional and happen as part of every commit.
>
> Here's a first shot at this. Comments welcome.
>
> To support transactional semantics, any new data written to the FSFS
> filesystem must be tied to the newly created revision.
> This way, updating 'current' as the final step in each commit makes the
> new data appear. Failing to update 'current' will cause any data added
> by failing commits to be overwritten by the next successfull commit.
>
> The following design tries to keep this principle valid for sucessor-ids.
This indeed induces nice properties on the design.
Aside from the auto-overwrite properties you mention, it also lends
itself to 'old files are read-only' (to the degree that property is
possible to do for the successor-ids feature) and to making storage
requirements uniform: some noderevs --- for example, the noderev for
^/subversion/trunk/BUGS --- are copied much more than others, and this
design has the storage propertional to the revisions of the copy targets
rather than the copy sources.
> There is one compromise though which hopefully won't hurt too much.
>
> Thanks again to danielsh for providing some initial feedback via IRC.
>
>
> Implementation proposal
> =======================
>
>
> - On-disk File Format -
>
> All files related to the map are stored in the repos/db/successors
> directory ("successors directory").
>
> The successor map contains 3 kinds of files:
>
> 1) Node-revision map files.
> These files map node-revision IDs to lists of revisions.
> This map answers the question:
> "In which revisions were successors of a node-revision created?"
>
> 2) Created-revision map file.
> These files map revision numbers of file offsets in successor data files.
> This map answers the question:
> "Where in the successor data are those successors which were created
> in revision N?"
>
> 3) Successor data files.
> These files store raw successor data.
>
> The different kinds of files refer to each other as shown below:
>
> node_rev_id map revision map successor data
> +-------+ +--------+ +-----------+
> | ... | | ... | | ... |
> +------>rN---------+ | offset | +----->successor |
> | | ... | | | offset | | | successor |
> | | ... | +----->offset----+ | END |
> node_rev_id --+ | rQ | | ... | | successor |
> | | ... | | offset | | ... |
> +------>rX---------+ | ... | | ... |
> | ... | | | ... | | END |
> | ... | +----->offset---------->successor |
> | rZ | | ... | | END |
> +-------+ +--------+ +-----------+
>
> Each type of file is described below in detail.
>
>
> -- Node-revision-ID map files --
>
> The purpose of node-revision-id map files is to facilitate lookup
> of successors of a given node-revision.
>
> The files are named after the number of the revision the node-revision
> was created in, modulo some fixed to-be-determined value (i.e. there
> won't be one file per node revision, but one file for every 10, 100,
> or so, node-revisions).
>
> The files are stored within the "node-revs" sub-directory:
>
> db/successors/node-revs/1
> db/successors/node-revs/2
> db/successors/node-revs/3
> ...
> db/successors/node-revs/N
> db/successors/node-revs/M
> ...
>
> Each node-revision map file stores a mapping of the form
> node_rev_id => [revnum, revnum, ...]
> The revision numbers identify those revisions in which one or more
> successors of a given node-revision were added.
>
> In the first iteration of this design, the mapping is stored as lines
> of ASCII text. Each line contains an unparsed node_revision_id, a space
> separator (ASCII 0x20), and a revision number in ASCII decimal representation.
> (The design may be refined later to use a more efficient storage model.)
>
Some wild ideas here:
- Multiple, concatenated DELTA\n..ENDREP\n svndiff streams. That's
appendable and compressible (a deltify process can combin adjacent
streams, which will trigger zlib compression).
(That won't work for the successors data since offsets into it are
stored elsewhere.)
- Some packing support that also implements grouping of all the map
entries with the same lhs? Is that needed, or should the API at this
level only implement 'slurp the entire map into a hash mapping ints to
arrays of revnums'?
>
(OT: those terms for the three kinds of files you have haven't sat well
with me; from the term alone I couldn't instantly recall what the
contents of the file were.)
> -- Revision map files --
>
> The purpose of the revision map file is to facilitate lookup
> of successor data created in a given revision.
>
> The files are named after the numbers of revisions they are responsible for,
> modulo some fixed to-be-determined value (i.e. there won't be one file
> per revision, but one file for every 10, 100, or so, revisions; each file
> is responsible for some range of revisions).
>
> The files are stored within the "revs" sub-directory:
>
> db/successors/revs/1
> db/successors/revs/2
> db/successors/revs/3
> ...
> db/successors/revs/N
> db/successors/revs/M
> ...
>
>
> Each file consists of an array of 64bit big-endian integers.
> The N'th integer (starting from N=1) in the file specifies the offset
> of successor data (in the corresponding successor data file) which was
> added in the N'th revision within the revision range the map file is
> responsible for.
>
>
> -- Successor-data files --
>
> These files use the same naming scheme as the revision map files (i.e.
> each successor data file is responsible for successors created within
> a specific range of revisions).
>
> The files are stored within the "successor-ids" sub-directory:
>
> db/successors/successor-ids/1
> db/successors/successor-ids/2
> db/successors/successor-ids/3
> ...
> db/successors/successor-ids/N
> db/successors/successor-ids/M
> ...
>
>
> Each file consists of lines each containing two unparsed node_rev_id
> ASCII strings, separated by ASCII 0x20. The first node-revision ID is a
> predecessor, and the second one is one of its successors.
> The special string "END" on a single line signifies that the following
> successor data belongs to the next revision.
> (The design may be refined later to use a more efficient storage model.)
>
>
> - Procedure for Readers -
>
> A reader first reads the 'current' file and remembers the revision number.
>
> It locates the node-revision map file corresponding to the given node_rev_id,
> based on the node_rev_id's revision modulo a known fixed value.
>
> It opens this file and reads it to obtain a list of revisions which created
> successors of the given node_rev_id. It ignores lines listing node_rev_ids
> not matching the given node_rev_id. It also ignores revisions greater than
> 'current'.
>
> Next, the reader opens the corresponding revision map files,
> based on revision numbers in the list, each modulo a known fixed value.
> For each revision N in the revision list, it seeks to the revision's byte
> offset within a revision map file and reads 4 bytes to obtain the offset
> corresponding to revision N within a successor data file.
>
> The reader then opens the corresponding successor data files,
<Implementation note>
When multiple successors are available, there is a performance trade-off
here: what order to iterate the revision map files and successor data
files, when multiple revisions in multiple shards contain successors.
</Implementation note>
/me fondly recalls an exercise from BSc: "Compare the 3! possible
orderings of the elementary algorithm for N×N matrix multiplication"
(for a fixed C representation of matrices).
</Implementation note>
> based on revision numbers in the list, each modulo a known fixed value.
> For each revision offset, it seeks to this offset and reads lines until it
> finds the line "END". It loops through all lines and appends those
> successor IDs to the set of successors which list a predecessor matching
> the given node_rev_id.
(would be easier to parse if the words "to the set of successors" were relocated)
>
> In exceptional cases (see below) it is possible that a given revision
> does not actually contain any successors of the given node_rev_id.
>
Implementation question: would it make sense to have a mode for
inquiring about several noderev's successors at the same time, in order
to amortize the lookup operation (three open()s, several read()s of the
successor data file)'s cost across them?
>
> - Procedure for Writers -
>
> Assume that the writer has access to a mapping from predecessor
> node-revision ID to one or more successor node-revision IDs.
> (The exact mechanism managing this mapping still needs to be determined.
> But it can be assumed to be available as all predecessors and successors
> are known within the context of a commit.)
>
> When committing a finished transaction (in fs_fs.c:commit_body()),
> the writer obtains a write-lock on all files within the successors
> directory it needs to modify.
>
Clarification: do you propose that a single write lock be obtained to
cover the entire successors/** hierarchy?
Also: is the FSFS write lock (which is held by commit_body() whilst it
runs) sufficient for this?
> Let rN be the new revision the writer is committing.
>
> The writer creates an empty temporary file.
>
> If rN falls within the revision range of an existing successor data
> file, the writer looks up the offset of revision N-1 in the corresponding
> revision map file. It copies content from the corresponding successor data
> file to a temporary file up to this offset, and copies any data that follows
> until a line containing "END" has been copied. (Note that this step discards
> data left behind by any previous attempt at committing rN).
>
> The writer appends any new successor data to the temporary file (note
> that there may be no successor data in case the revision is empty).
> It then adds a terminating "END".
>
> The writer creates another empty temporary file.
>
> If rN falls within the revision range of an existing revision map file,
> it copies ((N-2)*4) bytes of content from the revision map file into the
> temporary file. (Note that this step discards data left behind by any
> previous attempt at committing rN).
>
((N-2)*4) is bogus for N=1, and it's also missing a modulo operation
somewhere. But the gist is clear: copy the four bytes of every
preceding revision in the shard.
(Which reminds me that r0's single noderev has successors too.)
> The writer appends, to the temporary file, the offset of the new data
> it wrote into the successor data file.
>
> Likewise, the writer creates empty temporary files for each node-revision
> map files is needs to modify. It copies all content from any such
> node-revision map files which already exist, and appends a line to each
> file containing the node_revision ID and the new revision number.
>
It may append multiple lines in case multiple noderevs are covered by
a single noderev map file.
> After moving the proto-revprop file into place, and before updating
> 'current', the writer moves temporary files into place in the successors
> directory, in the following order:
>
> 1) the new successor data file
> 2) the new revision map file
> 3) each new node_rev_id map file
>
> If the writer fails to update all files in the successors directory,
> it will also fail to update 'current'. In this case, readers will ignore
> the new successor data until another commit succeeds in creating rN.
> Once a commit of rN has succeeded, readers following node-rev-id map
> entries updated by the failing commit might end up with an empty
> successors list for rN. Such erroneous entries will not be cleaned
> up automatically, but can be eliminated by re-creating the repository
> (e.g. via a dump/load cycle).
Near the start you referred to a 'compromise'. Is that the compromise?
Does 'compromise' refer to something else?
> However, the actual successor data stored
> for committed revisions is always correct, and the likelihood of incorrect
> node-revision ID map entries to occur is small.
Suppose committing rN failed. That might have left debris in one of the
following forms:
- Appends to the noderev map files.
- Appends to the revision map file.
- Appends to the successor data file.
Revision map data is ignored until 'current' is >=N; therefore, if
a reader opens the map file at rN's offset, then an attempt to commit rN
has succeeded, which means readers will never see the successor data of
failed commit attempts.
/me satisfied.
>
That said, one issue. Debris in the successor data file or revision map
file will be overwritten as soon as an attempt to commit rN succeeds;
however, noderev map entries remain until a dump/load. How feasible
would it be to also have a cleanup procedure for them?
Such a cleanup procedure could grab the commits (and successors, if it's
separate) write locks, attempt to read the successors data for all
noderevs in a noderev map file, and delete the bogus entries from the
noderev map file. (It could delete them either by atomically replacing
the file with a new version, or by replacing the first byte of the
revnum by some agreed non-[0-9\n] byte representing "This line of the
noderev map file shall be ignored".
(it must be a single byte because some revnums are represented in ASCII
by a single byte)
>
+1
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Ivan Zhakov <iv...@visualsvn.com>.
On Mon, Sep 5, 2011 at 21:55, Stefan Sperling <st...@elego.de> wrote:
> On Mon, Sep 05, 2011 at 07:38:51PM +0200, Bert Huijben wrote:
>> > Also slightly OT (no FSFS-guruness here), but I think another
>> > important use-case is being able to quickly answer the question "in
>> > which revision was $URL@$REV deleted?" Or "give me the log of
>> > $URL@$REV up and until it was deleted."
>>
>> svn_ra_get_deleted_rev(), which answers this question was introduced in 1.6.
>> (But I don't know where it is used.)
>
> The guts of this are in svn_repos_deleted_rev().
> It runs a binary search across a specific revision range to find the
> delete event. During this search it repeatedly scans history backwards
> to find a related node and has to employ a complicated set of rules to
> deal with copies and replacements.
>
> This could be simplified with successor support. Just scan successors
> upwards from the start revision until either the end revision is reached
> or the node disappears. The only complication are multiple copies of the
> node. If more than one copy event is found they will all need to be
> scanned upwards but only one will match the node we're looking for.
>
It looks like just performance optimization. We can do it later, after
fixing tree-conflicts on moves.
--
Ivan Zhakov
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Stefan Sperling <st...@elego.de>.
On Mon, Sep 05, 2011 at 07:38:51PM +0200, Bert Huijben wrote:
> > Also slightly OT (no FSFS-guruness here), but I think another
> > important use-case is being able to quickly answer the question "in
> > which revision was $URL@$REV deleted?" Or "give me the log of
> > $URL@$REV up and until it was deleted."
>
> svn_ra_get_deleted_rev(), which answers this question was introduced in 1.6.
> (But I don't know where it is used.)
The guts of this are in svn_repos_deleted_rev().
It runs a binary search across a specific revision range to find the
delete event. During this search it repeatedly scans history backwards
to find a related node and has to employ a complicated set of rules to
deal with copies and replacements.
This could be simplified with successor support. Just scan successors
upwards from the start revision until either the end revision is reached
or the node disappears. The only complication are multiple copies of the
node. If more than one copy event is found they will all need to be
scanned upwards but only one will match the node we're looking for.
RE: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Bert Huijben <be...@qqmail.nl>.
> -----Original Message-----
> From: Johan Corveleyn [mailto:jcorvel@gmail.com]
> Sent: maandag 5 september 2011 13:15
> To: Ivan Zhakov; dev@subversion.apache.org
> Subject: Re: question for FSFS gurus (was: Re: FSFS successor ID design
draft)
>
> On Mon, Sep 05, 2011 at 01:46:09PM +0400, Ivan Zhakov wrote:
> [...]
> > I'm not FSFS guru, but I still feel that FSFS successor ID doesn't
> > worth to be implemented because there is no strong reasons/usage for
> > it. For me it looks like bottom-up design approach.
>
> Also slightly OT (no FSFS-guruness here), but I think another
> important use-case is being able to quickly answer the question "in
> which revision was $URL@$REV deleted?" Or "give me the log of
> $URL@$REV up and until it was deleted."
svn_ra_get_deleted_rev(), which answers this question was introduced in 1.6.
(But I don't know where it is used.)
> This question comes up in practice once in a while (has been asked a
> couple of times on the users-list, and to me personally by some of my
> dev-colleagues). The workaround is usually to script around it for
> example by doing a "log -v" of an ancestor and looking for the first
> deletion after $REV (or something similar).
>
> When it is suggested that this kind of search could also be
> implemented as a feature inside svn (even if it's slow, at least it
> would be part of the core), that request is always refused by saying
> that it wouldn't be performant enough (and consequently eat too much
> resources of an SVN server). I hope an FSFS successor ID storage could
> help in this regard.
Bert
>
> --
> Johan
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Johan Corveleyn <jc...@gmail.com>.
On Mon, Sep 05, 2011 at 01:46:09PM +0400, Ivan Zhakov wrote:
[...]
> I'm not FSFS guru, but I still feel that FSFS successor ID doesn't
> worth to be implemented because there is no strong reasons/usage for
> it. For me it looks like bottom-up design approach.
Also slightly OT (no FSFS-guruness here), but I think another
important use-case is being able to quickly answer the question "in
which revision was $URL@$REV deleted?" Or "give me the log of
$URL@$REV up and until it was deleted."
This question comes up in practice once in a while (has been asked a
couple of times on the users-list, and to me personally by some of my
dev-colleagues). The workaround is usually to script around it for
example by doing a "log -v" of an ancestor and looking for the first
deletion after $REV (or something similar).
When it is suggested that this kind of search could also be
implemented as a feature inside svn (even if it's slow, at least it
would be part of the core), that request is always refused by saying
that it wouldn't be performant enough (and consequently eat too much
resources of an SVN server). I hope an FSFS successor ID storage could
help in this regard.
--
Johan
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Stefan Sperling <st...@elego.de>.
On Mon, Sep 05, 2011 at 12:12:31PM +0200, Stefan Sperling wrote:
> > Anyway we can implement top-level part of handling moves and then
> > optimize it using FSFS successor ID storage or something else.
>
> We need the bottom parts first.
> It won't perform well enough without successor-IDs.
I should have been clearer:
"It" in my quote above is not the algorithm I posted pseudo-code for.
"It" is a different algorithm that finds nodes which were deleted in
the history of the target branch of a merge (again,
see http://svn.haxx.se/dev/archive-2011-08/0624.shtml).
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Stefan Sperling <st...@elego.de>.
On Mon, Sep 05, 2011 at 01:57:51PM +0400, Ivan Zhakov wrote:
> No, I think that auto-resolving tree-conflicts involving moves is most
> important task for Subversion 1.8. But I feel it could be implemented
> without implementing FSFS successor ID storage. It seems that
> algorithm that you posted could be reversed.
I have caused some confusion here, sorry.
Contrary to how I initially presented it, That algorithm has *nothing*
to do with successor IDs.
Please see this post where I corrected my mistake:
http://svn.haxx.se/dev/archive-2011-08/0624.shtml
> Anyway we can implement top-level part of handling moves and then
> optimize it using FSFS successor ID storage or something else.
We need the bottom parts first.
It won't perform well enough without successor-IDs.
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Ivan Zhakov <iv...@visualsvn.com>.
On Mon, Sep 5, 2011 at 14:43, Daniel Shahaf <da...@elego.de> wrote:
> Ivan Zhakov wrote on Mon, Sep 05, 2011 at 13:57:51 +0400:
>> On Mon, Sep 5, 2011 at 13:52, Stefan Sperling <st...@elego.de> wrote:
>> > On Mon, Sep 05, 2011 at 01:46:09PM +0400, Ivan Zhakov wrote:
>> >> On Mon, Sep 5, 2011 at 13:41, Stefan Sperling <st...@elego.de> wrote:
>> >> > On Thu, Sep 01, 2011 at 12:06:40AM +0200, Stefan Sperling wrote:
>> >> >> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
>> >> >> > I'll try to tweak my proposal such that successor ID updates become
>> >> >> > transactional and happen as part of every commit.
>> >> >>
>> >> >> Here's a first shot at this. Comments welcome.
>> >> >
>> >> > FSFS gurus:
>> >> >
>> >> > Are any of you looking at this?
>> >> > Do you think this is worth writing a prototype implementation for?
>> >> >
>> >> > I have so far only received feedback from danielsh. This makes me very
>> >> > happy but if anyone with a couple more years of FSFS experience under
>> >> > their belt could comment I would be even happier.
>> >> >
>> >> I'm not FSFS guru, but I still feel that FSFS successor ID doesn't
>> >> worth to be implemented because there is no strong reasons/usage for
>> >> it. For me it looks like bottom-up design approach.
>> >
>> > Hmmm... you don't think that auto-resolving tree-conflicts involving
>> > moves during merges is worth implementing?
>> >
>> No, I think that auto-resolving tree-conflicts involving moves is most
>> important task for Subversion 1.8. But I feel it could be implemented
>> without implementing FSFS successor ID storage. It seems that
>> algorithm that you posted could be reversed.
>>
>
> What do you mean by 'reversed'?
>
I mean to iterate over added_nodes (instead of deleted_nodes).
--
Ivan Zhakov
Re: question for FSFS gurus (was: Re: FSFS successor ID design
draft)
Posted by Daniel Shahaf <da...@elego.de>.
Ivan Zhakov wrote on Mon, Sep 05, 2011 at 13:57:51 +0400:
> On Mon, Sep 5, 2011 at 13:52, Stefan Sperling <st...@elego.de> wrote:
> > On Mon, Sep 05, 2011 at 01:46:09PM +0400, Ivan Zhakov wrote:
> >> On Mon, Sep 5, 2011 at 13:41, Stefan Sperling <st...@elego.de> wrote:
> >> > On Thu, Sep 01, 2011 at 12:06:40AM +0200, Stefan Sperling wrote:
> >> >> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
> >> >> > I'll try to tweak my proposal such that successor ID updates become
> >> >> > transactional and happen as part of every commit.
> >> >>
> >> >> Here's a first shot at this. Comments welcome.
> >> >
> >> > FSFS gurus:
> >> >
> >> > Are any of you looking at this?
> >> > Do you think this is worth writing a prototype implementation for?
> >> >
> >> > I have so far only received feedback from danielsh. This makes me very
> >> > happy but if anyone with a couple more years of FSFS experience under
> >> > their belt could comment I would be even happier.
> >> >
> >> I'm not FSFS guru, but I still feel that FSFS successor ID doesn't
> >> worth to be implemented because there is no strong reasons/usage for
> >> it. For me it looks like bottom-up design approach.
> >
> > Hmmm... you don't think that auto-resolving tree-conflicts involving
> > moves during merges is worth implementing?
> >
> No, I think that auto-resolving tree-conflicts involving moves is most
> important task for Subversion 1.8. But I feel it could be implemented
> without implementing FSFS successor ID storage. It seems that
> algorithm that you posted could be reversed.
>
What do you mean by 'reversed'?
> Anyway we can implement top-level part of handling moves and then
> optimize it using FSFS successor ID storage or something else.
>
>
> --
> Ivan Zhakov
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Ivan Zhakov <iv...@visualsvn.com>.
On Mon, Sep 5, 2011 at 13:52, Stefan Sperling <st...@elego.de> wrote:
> On Mon, Sep 05, 2011 at 01:46:09PM +0400, Ivan Zhakov wrote:
>> On Mon, Sep 5, 2011 at 13:41, Stefan Sperling <st...@elego.de> wrote:
>> > On Thu, Sep 01, 2011 at 12:06:40AM +0200, Stefan Sperling wrote:
>> >> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
>> >> > I'll try to tweak my proposal such that successor ID updates become
>> >> > transactional and happen as part of every commit.
>> >>
>> >> Here's a first shot at this. Comments welcome.
>> >
>> > FSFS gurus:
>> >
>> > Are any of you looking at this?
>> > Do you think this is worth writing a prototype implementation for?
>> >
>> > I have so far only received feedback from danielsh. This makes me very
>> > happy but if anyone with a couple more years of FSFS experience under
>> > their belt could comment I would be even happier.
>> >
>> I'm not FSFS guru, but I still feel that FSFS successor ID doesn't
>> worth to be implemented because there is no strong reasons/usage for
>> it. For me it looks like bottom-up design approach.
>
> Hmmm... you don't think that auto-resolving tree-conflicts involving
> moves during merges is worth implementing?
>
No, I think that auto-resolving tree-conflicts involving moves is most
important task for Subversion 1.8. But I feel it could be implemented
without implementing FSFS successor ID storage. It seems that
algorithm that you posted could be reversed.
Anyway we can implement top-level part of handling moves and then
optimize it using FSFS successor ID storage or something else.
--
Ivan Zhakov
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Stefan Sperling <st...@elego.de>.
On Mon, Sep 05, 2011 at 01:46:09PM +0400, Ivan Zhakov wrote:
> On Mon, Sep 5, 2011 at 13:41, Stefan Sperling <st...@elego.de> wrote:
> > On Thu, Sep 01, 2011 at 12:06:40AM +0200, Stefan Sperling wrote:
> >> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
> >> > I'll try to tweak my proposal such that successor ID updates become
> >> > transactional and happen as part of every commit.
> >>
> >> Here's a first shot at this. Comments welcome.
> >
> > FSFS gurus:
> >
> > Are any of you looking at this?
> > Do you think this is worth writing a prototype implementation for?
> >
> > I have so far only received feedback from danielsh. This makes me very
> > happy but if anyone with a couple more years of FSFS experience under
> > their belt could comment I would be even happier.
> >
> I'm not FSFS guru, but I still feel that FSFS successor ID doesn't
> worth to be implemented because there is no strong reasons/usage for
> it. For me it looks like bottom-up design approach.
Hmmm... you don't think that auto-resolving tree-conflicts involving
moves during merges is worth implementing?
Re: question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Ivan Zhakov <iv...@visualsvn.com>.
On Mon, Sep 5, 2011 at 13:41, Stefan Sperling <st...@elego.de> wrote:
> On Thu, Sep 01, 2011 at 12:06:40AM +0200, Stefan Sperling wrote:
>> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
>> > I'll try to tweak my proposal such that successor ID updates become
>> > transactional and happen as part of every commit.
>>
>> Here's a first shot at this. Comments welcome.
>
> FSFS gurus:
>
> Are any of you looking at this?
> Do you think this is worth writing a prototype implementation for?
>
> I have so far only received feedback from danielsh. This makes me very
> happy but if anyone with a couple more years of FSFS experience under
> their belt could comment I would be even happier.
>
I'm not FSFS guru, but I still feel that FSFS successor ID doesn't
worth to be implemented because there is no strong reasons/usage for
it. For me it looks like bottom-up design approach.
--
Ivan Zhakov
question for FSFS gurus (was: Re: FSFS successor ID design draft)
Posted by Stefan Sperling <st...@elego.de>.
On Thu, Sep 01, 2011 at 12:06:40AM +0200, Stefan Sperling wrote:
> On Tue, Aug 30, 2011 at 12:43:29PM +0200, Stefan Sperling wrote:
> > I'll try to tweak my proposal such that successor ID updates become
> > transactional and happen as part of every commit.
>
> Here's a first shot at this. Comments welcome.
FSFS gurus:
Are any of you looking at this?
Do you think this is worth writing a prototype implementation for?
I have so far only received feedback from danielsh. This makes me very
happy but if anyone with a couple more years of FSFS experience under
their belt could comment I would be even happier.
Thanks.