Describe problem and encoding of sortkeys

SORTKEY - New code to store and propagate additional metadata to keep cset and delta sort order constant through transformations, like csetprune, partition, and fixing checksums.

Problem: we order the deltas in the table based on keys. If we have the same user/host/path/date then all that is left is the checksum for changesets. When we prune, the checksum can change and that can change the order we store things. The obvious place where that can cause problems is if a branch node is swapped with a trunk node. Unless we detect that at the time it happens and rework the rest of the nodes (esp all the includes and any excludes), the file is hopelessly broken.

Because this is a distributed system you pretty much can’t guarantee that you have caught all of the problems at csetprune time, two prunes could operate on the branch in one and the trunk in another and when they come together we don’t have the state we need to do the right thing.

For regular files we can get the same problem if the pathnames change the sort order.

Mysql shows this on a partition when you clone backwards and pull.

To avoid those problems, metadata is added to keep sort order the same. More details below, here is the summary: s.file ^AcK57756|62683 ^AcPanno/ChangeSet|ChangeSet patch K 57756|62683 P anno/ChangeSet|ChangeSet

Delta order is determined by cweave.c:earlier() — sort the dates, and use :KEY: (now :SORTKEY:) as the tie breaker.

Creating a bad order can lead to a pull down the road breaking, because pulls sort incoming data with existing data based on what earlier() says.

Once delta order has been shifted, then renumber could fail because of the needSwap test failing. Also a file checksum could pass but data be wrong because of a weave data blocks swapped — so a silent failure (yikes! but only caused by partition, so not in the wild).

In fastpatch mode, there’s a failure because fastpatch patch index numbers pick up the sorted order of that patch instead of the order as sent in the file (which I view as a bug/frailty, but one that is not tickled when patch is shipped in sorted order).

See t.sortkey for example of setup where keys swap order.

Data Structure

a transformation, then the overall sort order can change.

Csetprune changes cset weave data, so changes checksum. If two keys were the same except for checksum, then they could change order if new checksums sort differently. This was seen in the partitioning of the mysql repo.

These keys that different only by checksum shouldn’t happen in normal operation of bk. The unique.c code will prevent keys that differ by only the checksum. In the mysql case they were using an older version of bk that include didn’t include realhost in the csetkeys and overrode BK_HOST=mysql.com on two different machines. However we have seen these conflicts on several trees generated by imports, rcs2bk for freebsd and git2bk for linux.

In a partition, files can change path. If a file is moved between components, the partition will record the not-in-component path as BitKeeper/deleted/… which can lead to sort order being changed.

user@host and timestamp stay constant through the transformations, so at this time do not need duplication.

Random bits are only in the rootkey and currently backed up through rootlog. Random bits are only changed in the ChangeSet file and not in files. Currently, randombits are not part of the sortkey fix.

IMPLEMENTATION

Current implementation is to store the original path and checksum in the sfile and patch separated by a |: new|original

Here’s an sfile and patch entry from a component changeset file after a partition. Note that the K and P line each have 2 fields.

^As 1/0/1 ^Ad D 1.2 98/09/22 16:23:31 bk 3 2 ^Ac lots of good bugs fixed ^AcC ^AcF3 ^AcK57756|62683 ^AcPanno/ChangeSet|ChangeSet ^Ae

That means no new entries, and means that old versions of bk will read, but get path wrong. Yikes. Maybe better to store path on it’s own line? For checksum, atoi will just pick off the first number.

These are encoded in the delta struct to optimize no change in the delta struct size. The current delta struct has 16 bit sum declared among a number of pointers and 32 bit data. That leaves a 16 bit hole in the current. The new code defines sortSum in that hole.

sortpath is only used for sorting. Instead of declaring a new delta struct pointer, a trick used currently in check.c is to put 2 strings in one pointer, concatenated, and terminated by a null. The normal string interfaces see only one string; the other is hidden until needed.

This is used for storing the sortpath in the same pointer with pathname using HIDE() and HIDDEN() to write and read it.

The frailty is if pathname is ever replaced with a normal string, HIDDEN will return unknown junk.

The upside is accessing pathname works just as it does now, and no new data was added to delta structure.

TODO: feature bits and sfile/patch version to get compat working.

The desire is to have a new repo with no new meta data be read by old bks. And fail gracefully if it does. Note: log/features read after sfile has been parsed, and sfile parsing does whole table before getting to the version, so if there is new meta data, it puts out a lot of warnings before seeing it is a mismatch.

Questions:

dspec key name? :SORTKEY:, :OLDKEY:, :ORIGKEY:, … ?

sfile/patch - store K and P as two fields or give new data it’s own field, with format as a key with null fields that are the same:

bk@bk_regression.bk|ChangeSet|19980922162331|00001|f43d37729b87027e
bk@bk_regression.bk|ChangeSet|19980922162332|46770
D 1.2 98/09/22 16:23:31+00:00 bk@bk_regression.bk +1 -0
B bk@bk_regression.bk|ChangeSet|19980922162331|00001|d839d0c15b7cbc52
C
c lots of good bug fixed
F 3
I |ChangeSet||62683
K 57756
P anno/ChangeSet

In mem delta struct - d→sortpath or d→origpath instead of HIDE/HIDDEN?
If keeping HIDDEN, modify returns 0 if no hidden string and HIDE to take a 0 as the second parameter?
COMPAT All files in all nested repos are SCCS_VERSION + 1. All files in partitioned repos w/ this meta data are SCCS_VERSION + 1. No attempts at 4.x reading/writing these repos. Bump the patch version if vers > SCCS_VERSION because we don’t have feature bits in the patch and we need to support send/receive. Alternate: add a feature bits line to patch format and make send send that such that old bk’s will barf on receive.