apache / apache/hugegraph

[Bug] Paging returns the page-boundary record twice when limit is a multiple of 500 (BinaryEntryIterator; RocksDB and HStore)

Open
#3,191 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
3.2k
Forks
636
Avg merge
3d 11h
Merged PRs (30d)
14

Description

### Bug Type (问题类型)

rest-api / gremlin (结果不合预期) — paginated results contain duplicates

### Before submit

- [x] 我已经确认现有的 Issues 与 FAQ 中没有相同 / 重复问题 (I have confirmed and searched that there are no similar problems in the historical issue and documents)

### Environment (环境信息)

- Server Version: 1.7.0 built from `master` `98477f0` (also reproduced on master + #3184 + #3182 + #2994)
- Backend: **RocksDB (single node) and HStore (PD + 3 store nodes) — identical behaviour**, so this is server-side code, not a backend
- OS: Debian 13 VMs, Temurin 11 (server) / 17 (PD, store)
- Data Size: any vertex with ≥ 500 edges, or any vertex label with ≥ 500 vertices (tested with 1 222 edges on one vertex and 3 000 vertices under one label)

### Expected & Actual behavior (期望与实际表现)

**Expected:** following the `page` token, every element is returned exactly once.

**Actual:** when `limit` is a multiple of 500 (500, 1000, …), the **last element of page *k* is returned again as the first element of page *k+1*** — one duplicate per page boundary. No error is raised. With `limit` = 100, 250, 333, 400 or 600 there are no duplicates.

Matrix for one vertex `a` with 1 222 out-edges (1 212 of them with sort key `asset=ETC`), REST `GET /graph/edges?vertex_id="a"&direction=OUT&label=flow[&properties=…]&limit=N&page=…`, all pages followed to the end (`n` = elements returned, `uniq` = distinct ids):

```
query limit pages n uniq dups last-of-page == first-of-next
no condition 400 [400,400,400,22] 1222 1222 0
no condition 500 [500,500,224] 1224 1222 2 pages 0->1, 1->2
no condition 600 [600,600,22] 1222 1222 0
no condition 1000 [1000,223] 1223 1222 1 page 0->1
asset=ETC (sort-key prefix) 500 [500,500,214] 1214 1212 2 pages 0->1, 1->2
asset=ETC & epoch>=150 500 [500,500,209] 1209 1207 2 pages 0->1, 1->2
```

Vertices by label (3 000 `person` vertices, label index): `GET /graph/vertices?label=person&limit=500&page=…` → 3 006 returned, 3 000 distinct (6 boundaries, 6 duplicates). Not affected: queries through a secondary/range index (`label=person&properties={"age":"P.gte(30)"}`, 2 332 / 2 332 at every page size) and a full scan without label (3 505 / 3 505).

Same result through Gremlin: `g.V(a).outE('flow').has('~page', page).limit(500)`.

#### Minimal reproduction

```groovy
// gremlin: one vertex with 1200 out-edges (any >= 500 works)
graph.schema().propertyKey('epoch').asLong().ifNotExist().create()
graph.schema().vertexLabel('node').useCustomizeStringId().ifNotExist().create()
graph.schema().edgeLabel('flow').sourceLabel('node').targetLabel('node').properties('epoch').multiTimes().sortKeys('epoch').ifNotExist().create()
a = graph.addVertex(T.label, 'node', T.id, 'a'); b = graph.addVertex(T.label, 'node', T.id, 'b')
(0..<1200).each { a.addEdge('flow', b, 'epoch', it) }
graph.tx().commit()
```

```bash
# REST (prefix /graphspaces/DEFAULT on 1.7 with graphspaces; responses are gzipped regardless of Accept-Encoding)
B='http://localhost:8080/graphs/hugegraph/graph/edges?vertex_id="a"&direction=OUT&label=flow&limit=500'
curl -s --compressed "$B&page=" | jq -r '.edges[-1].id, .page' # last id of page 1 + token
curl -s --compressed "$B&page=" | jq -r '.edges[0].id' # == last id of page 1 <-- duplicate
# repeat with limit=400: the ids differ, as expected
```

A stand-alone probe that runs the whole matrix against any live server (Python 3, stdlib only) is here:
https://github.com/SebastianGruza/hugegraph-oracle-suite/blob/main/suite/page_probe.py — it prints the duplicated ids and the page boundaries they sit on.

### Root cause

`BinaryEntryIterator.fetch()` (`hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/serializer/BinaryEntryIterator.java`, lines 69–96 on `98477f0`) merges store records into the current `BackendEntry` and leaves the loop in three ways:

1. the next record belongs to a new entry → it is buffered in `this.next`; `position()` points at an unread key ✔
2. the limit is reached → the loop deliberately reads `limit + 1` records and calls `removeLastRecord()` (lines 89–95, comment *"Need remove last one because fetched limit + 1 records"*) ✔
3. the current entry holds `INLINE_BATCH_SIZE` columns → `break` (lines 76–81) — **after** the record that triggered the check has been merged into the entry that is about to be emitted ✘

`INLINE_BATCH_SIZE` is `Query.COMMIT_BATCH` = 500 (`BackendEntryIterator.java:36`, `Query.java:47`; it is *not* `query.page_size`, the two just share the value). The backend iterator advances `position()` in `hasNext()` to the key of the record it is about to hand out (`RocksDBStdSessions.java:1133-1136`), so after exit 3 the position is the key of an **emitted** record. `BinaryEntryIterator.pageState()` (lines 117–123) builds `PageState(position, 0, count)` with the offset hard-coded to 0, and the next page restarts **inclusively** from that position (`BinarySerializer.prefixQuery` → `IdPrefixQuery(inclusive = true)`, `BinarySerializer.java:946-963`; sort-key range queries force `includeStart = true` at `:704-713`). Hence the duplicate.

Why only multiples of 500: with `limit = L`, exit 2 fires on record `L+1` and removes it — clean. When `L mod 500 == 0`, exit 3 fires on record `L` *before* record `L+1` is read; the consumer then stops on `reachLimit()` without calling `fetch()` again, so the position is never refreshed. `QueryList.OptimizedQuery.iterator()` (`QueryList.java:166-183`) passes the user limit straight to the store (*"Not set limit to pageSize due to PageEntryIterator.remaining"*), so `query.page_size` never splits the scan and changing it cannot fix the edge case. For the label-index path the sub-query limit **is** `query.page_size` (`IdHolder.java:124-138`, `GraphIndexTransaction.doIndexQueryOnce` `:736-761`), but a label index keeps all element ids under one index key — one huge entry, same stale position.

Not related to #3190 (query-batch boundaries in `QueryResults`/`InputOrderIterator`): the batch here is the 500-record chunk of a single backend entry inside `BinaryEntryIterator`, and the defect is the page position it leaves behind.

Related: the four `// FIXME` blocks in `BinarySerializer.java` (708-711, 824-827, 856-859, 954-957) that disable the lower-bound assertion *"due to the inconsistency in the definition of `position` of RocksDB scan iterator and Hstore"*, and the `// QUESTION: Resetting the position` comments in `HstoreSessionsImpl.ColumnIterator` (`:245-254`, `:318-328`). The existing paging tests (`EdgeCoreTest.testQuery*EdgesOfVertexInPaging`) use `limit(1)` on 18 edges and never cross a batch boundary; the REST default `limit=100` hides it in everyday use.

### Fix

Check the full batch **before** merging the record and start the next entry with it (`this.next = this.merger.apply(null, elem)`), so that `position()` never points at an emitted record — the same invariant the limit path keeps via `removeLastRecord()`. ~24 lines in `BinaryEntryIterator`, plus a core test (`EdgeCoreTest#testQueryOutEdgesOfVertexInPagingAtBatchBoundary`: 1 200 edges, page limits 400 / 500 / 600 / 1 000, asserts count and distinct count). On unpatched core the test fails with `limit 500 expected:<1200> but was:<1202>`; with the fix it passes. With the patched `hugegraph-core` deployed to both a RocksDB and an HStore server the matrix above is `dups=0` for every size, and a 174-query cross-backend regression run differs from the pre-fix run in exactly one case (1 214 → 1 212, same set of distinct ids).

I will open a PR with the fix and the test. Full analysis and before/after data: https://github.com/SebastianGruza/hugegraph-oracle-suite/blob/main/docs/findings.md#f1 (found by comparing id sets between RocksDB and HStore on the same server: both backends carried the bug, `distinct < returned` on the reference side gave it away).

### Vertex/Edge example (问题点 / 边数据举例)

```javascript
// limit=500 over 1212 edges a->b (sort keys asset, epoch); page 1 last id == page 2 first id, page 2 last id == page 3 first id
GET /graphspaces/DEFAULT/graphs/hugegraph/graph/edges?vertex_id="a"&direction=OUT&label=flow&properties={"asset":"ETC"}&limit=500&page=
// duplicated ids observed (positions 500 and 1000 of the concatenated pages):
"Sa>1>1>ETC!2NI>Sb", "Sa>1>1>ETC!2V5>Sb"
// limit=400 / 600 over the same data: 1212 ids, all distinct
```

### Schema [VertexLabel, EdgeLabel, IndexLabel] (元数据结构)

```javascript
// GET /graphspaces/DEFAULT/graphs/hugegraph/schema/edgelabels/flow
{"name":"flow","source_label":"node","target_label":"node","frequency":"MULTIPLE","sort_keys":["asset","epoch"],
"properties":["asset","epoch","amount"],"nullable_keys":[],"enable_label_index":false}
// vertexlabel node: id_strategy CUSTOMIZE_STRING; property keys asset TEXT, epoch LONG, amount DOUBLE
// the vertex-label variant used vertexlabel person (CUSTOMIZE_STRING, enable_label_index true) with 3000 vertices
```

Contributor guide

Open the contributing guide

Research direction

Start with BinaryEntryIterator.fetch() and pageState(), then inspect EdgeCoreTest#testQuery*EdgesOfVertexInPaging and the RocksDB/HStore iterator behavior named in the report. Run the paging tests with limits 400, 500, 600, and 1,000 over more than 500 edges. Done means every page boundary returns distinct records and the regression passes across both backends.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend-api-design, databases
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
58/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.