apache / apache/couchdb

_changes?since=X results are incorrectly ordered after two rounds of shard splitting

Open
#4,640 4 comments 0 reactions 0 assignees View on GitHub
bug needs-triage
Dominant language
Erlang
Stars
7k
Forks
1.1k
Avg merge
1d 16h
Merged PRs (30d)
9

Description

## Description

We have observed that if we capture a `seq` value from a `_changes` response, and then perform two rounds of shard splitting on a database, requesting `_changes?since=X` with `X` set to the captured `seq` value returns results out of order; events from the same shard are not presented in ascending order. This might affect the behaviour of replicators/indexers relying on `seq` values for checkpointing.

## Steps to Reproduce

The following script reproduces the behaviour on my machine:

```bash
#!/bin/bash

CDB_AUTH='admin:admin'
CDB_HOST='127.0.0.1'
CDB_PORT=5984

cdb () {
curl -gs -H 'Content-Type: application/json' "$(cdb-host)$1" "${@:2}"
}

cdb-host () {
echo "http://${CDB_AUTH}@${CDB_HOST}:${CDB_PORT}"
}

stop-jobs () {
cdb '/_reshard/jobs' | jq -r '.jobs[] | .id' | while read -r id ; do
cdb "/_reshard/jobs/$id" -X DELETE
done
}

split-shards () {
local db="$1"

cdb "/$db/_shards" | jq -r '.shards | keys[]' | while read -r range ; do
cdb '/_reshard/jobs' -X POST \
-d '{ "type": "split", "db": "'$db'", "range": "'$range'" }'
done
}

wait-for-q () {
local db="$1"
local q="$2"

while [[ $(cdb "/$db" | jq -r '.cluster.q') != $q ]] ; do
sleep 1
done
}

db='test-db'

cdb "/$db" -X DELETE
cdb "/$db?q=2" -X PUT

for n in {1..10} ; do
cdb "/$db/doc-$n" -X PUT -d '{ "n": '$n' }'
done

last_seq_q2="$(cdb "/$db/_changes" | jq -r '.last_seq')"

stop-jobs
split-shards "$db"
wait-for-q "$db" 4

last_seq_q4="$(cdb "/$db/_changes" | jq -r '.last_seq')"

cdb "/$db/_changes?since=$last_seq_q2" | jq

stop-jobs
split-shards "$db"
wait-for-q "$db" 8

last_seq_q8="$(cdb "/$db/_changes" | jq -r '.last_seq')"

cdb "/$db/_changes?since=$last_seq_q4" | jq
cdb "/$db/_changes?since=$last_seq_q2" | jq
```

The first two `_changes` requests return an empty `results` array as expected, showing that a `seq` value continues to work after one round of splitting. The final one, where a `seq` captured while `q=2` is used when `q=8` returns the entire history, with events out of order.

For example, on one run of this script the `_changes` response contained:

```json
{
"seq": "30-g1AAAAKVeJzLYWBg4MhgTmEQTM4vTc5ISXLIyU9OzMnILy7JAUoxJTIkyf___z8rgzmRJRcowJ6alGySlmqJTQMeY5IUgGSSPcykDKYUBtbigpzMErCZpslJZmbmBqSa6QAyMx5qJgPYJAPLRAsjcwtSTUoAmVRPVdflsQBJhgYgBTR2PshcNjRzzUxTTSzMU8gydwHE3P0InxsZJ5obmpuSZdoBiGn3qe3KBxBz_5NobhYAREXOrQ",
"id": "doc-7",
"changes": [
{
"rev": "1-f996a2834eb8c362514d171f99324abd"
}
]
},
{
"seq": "23-g1AAAAKBeJzLYWBg4MhgTmEQTM4vTc5ISXLIyU9OzMnILy7JAUoxJTIkyf___z8rgzmRJRcowJ6alGySlmqJTQMeY5IUgGSSPdQkBohJQGMMTA1INckBZFI8ikkGlokWRuYWpJqUADKpHmoSI9ikREtTU_OkJBJNymMBkgwNQApo2HyQaWwZTCkMrMUFOZklYHPNTFNNLMxTyDJ3AcTc_Qj_Ghknmhuam5Jl2gGIafep7coHEHP_k2huFgBjZMkL",
"id": "doc-2",
"changes": [
{
"rev": "1-43a36d04d31d38efc5b9245c53e00627"
}
]
}
```

The descending value of the numeric part of the `seq` value looked curious to me so I ran these values through a parser tool and obtained:

```
original: '30-g1AAAAKVeJzLYWBg4MhgTmEQTM4vTc5ISXLIyU9OzMnILy7JAUoxJTIkyf___z8rgzmRJRcowJ6alGySlmqJTQMeY5IUgGSSPcykDKYUBtbigpzMErCZpslJZmbmBqSa6QAyMx5qJgPYJAPLRAsjcwtSTUoAmVRPVdflsQBJhgYgBTR2PshcNjRzzUxTTSzMU8gydwHE3P0InxsZJ5obmpuSZdoBiGn3qe3KBxBz_5NobhYAREXOrQ',
parsed: [
[ 'couchdb@localhost-00000000-1fffffff', 4 ],
[ 'couchdb@localhost-20000000-3fffffff', 4 ],
[ 'couchdb@localhost-40000000-5fffffff', 0 ],
[ 'couchdb@localhost-60000000-7fffffff', 4 ],
[ 'couchdb@localhost-80000000-9fffffff', 6 ],
[ 'couchdb@localhost-a0000000-bfffffff', 0 ],
[ 'couchdb@localhost-c0000000-dfffffff', 6 ],
[ 'couchdb@localhost-e0000000-ffffffff', 6 ]
]

original: '23-g1AAAAKBeJzLYWBg4MhgTmEQTM4vTc5ISXLIyU9OzMnILy7JAUoxJTIkyf___z8rgzmRJRcowJ6alGySlmqJTQMeY5IUgGSSPdQkBohJQGMMTA1INckBZFI8ikkGlokWRuYWpJqUADKpHmoSI9ikREtTU_OkJBJNymMBkgwNQApo2HyQaWwZTCkMrMUFOZklYHPNTFNNLMxTyDJ3AcTc_Qj_Ghknmhuam5Jl2gGIafep7coHEHP_k2huFgBjZMkL',
parsed: [
[ 'couchdb@localhost-00000000-1fffffff', 4 ],
[ 'couchdb@localhost-20000000-3fffffff', 0 ],
[ 'couchdb@localhost-40000000-5fffffff', 0 ],
[ 'couchdb@localhost-60000000-7fffffff', 1 ],
[ 'couchdb@localhost-80000000-9fffffff', 6 ],
[ 'couchdb@localhost-a0000000-bfffffff', 0 ],
[ 'couchdb@localhost-c0000000-dfffffff', 6 ],
[ 'couchdb@localhost-e0000000-ffffffff', 6 ]
]
```

The second event has a lower sequence number for shards `20-3f` and `60-7f`, showing events from some shards are being returned out of order.

Using the `seq` values in this response also returned events out of order, for example requesting `/test-db/_changes?since=30-g1AAAAKVeJzLYWBg4MhgTmEQTM4vTc5ISXLIyU9OzMnILy7JAUoxJTIkyf___z8rgzmRJRcowJ6alGySlmqJTQMeY5IUgGSSPcykDKYUBtbigpzMErCZpslJZmbmBqSa6QAyMx5qJgPYJAPLRAsjcwtSTUoAmVRPVdflsQBJhgYgBTR2PshcNjRzzUxTTSzMU8gydwHE3P0InxsZJ5obmpuSZdoBiGn3qe3KBxBz_5NobhYAREXOrQ` returns some out of order events:

```json
{
"seq": "27-g1AAAAKBeJyd0UsOgjAQANAG8LP1BHoEQNrCSm6inYKppIoJuNab6E30JnqTWiiGxBiTsplJpunLfCRCaCrcDM14eeIig1SWnElRVrXUTw5DMFdKFcJl3l4XJjnwaJsnvz78YWChI6w-knAyNKqOcle3JuZACPVtzbQx152JWslPWBzS2FbaNNK5k9xWYgnGFMBSOng6ootOGrv2WyMEAp_Z9mW0m9Hu_ZThktGA4kHaw2jPRht_3YHgPIppNsh9GVdZusUb18nIzw",
"id": "doc-8",
"changes": [
{
"rev": "1-817027c9296c2d2d688c568237e89624"
}
]
},
{
"seq": "27-g1AAAAJ3eJyd0VEOgjAMANAFEP31BHoEQLbBl9xE1w0zyRQT8FtvojfRm-hNcAwMiSEm8NMma_rSdgohNJO2QHOen7kUkKicMyXzolS6ZDEEi6qqMmkz56AfpinwcJfGfQ1_GFjqCOuvJC2BJsVJ7UtjYg6EUG-omdTmpjWRkbyYRQGNhkrbWrq0km0kFmNMAQZKR0dHdNVJY7fuaoSA77GhczXavdEe3ZbBilGf4lHas9FeteYajfs7xkkwSns3mrmb-_OrBKdhREWfkH0AQvjGHw",
"id": "doc-10",
"changes": [
{
"rev": "1-6829757f6498d33021e0a764f0a492af"
}
]
},
{
"seq": "22-g1AAAAJteJyd0F0OgjAMAOAJ-PPqCfQIMGSDJ7mJrgMyyRQT8FlvojfRm-hNcAwML8RkvLRJm35pKxFCC2EnaMmLCxcJxLLgTIqirKRqWQzBqq7rXNjMOarCPAW-ydJoaOAPA2sVYfuThJWgaXmWh0qbAQdCqGtqxo2560ykJTdiIaahqbRvpGsn2VpiURBQAEPp5KiIbiop7N5_jRDwXGa6V6s9Wu3ZX4l9Rj0ajNJerfZutJnWuJcxTvAo7dNq-m8TrYU-9lI8eGn-BZDCwuE",
"id": "doc-1",
"changes": [
{
"rev": "1-731bef401491606a3b246ed178e697c1"
}
]
},
```

## Expected Behaviour

Results in the `_changes` response should be ordered such that events from the same shard are presented in ascending order. Ideally, the `since` value would continue to limit the results returned, instead of returning the entire history.

## Your Environment

* CouchDB version used: 3.3.2
* Browser name and version: n/a
* Operating system and version: macOS Ventura 13.3.1

CouchDB info:

```json
{
"couchdb": "Welcome",
"version": "3.3.2",
"git_sha": "11a234070",
"uuid": "0b5ad401f2d593405eaeb94cc1210f9b",
"features": [
"access-ready",
"partitioned",
"pluggable-storage-engines",
"reshard",
"scheduler"
],
"vendor": {
"name": "The Apache Software Foundation"
}
}
```

Contributor guide

Open the contributing guide

Research direction

Start with the _changes endpoint and the _reshard split jobs, using the provided shell reproduction to compare results after q=2, q=4, and q=8. Trace how since values are interpreted across shard splits. Done means events from each shard remain in ascending order and a captured since value does not incorrectly return the entire history.

Written by the indexing model from the issue text.

Assessment

Tech stack
erlang
Domain
api, databases, distributed-systems
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.