Skip to content

[YTDB-1200, YTDB-1201, YTDB-1202] Fix link collection identity and persistence - #1313

Open
Andrii Lomakin (andrii0lomakin) wants to merge 1 commit into
developfrom
YTDB-1200-1201-1202-link-collection-fixes
Open

[YTDB-1200, YTDB-1201, YTDB-1202] Fix link collection identity and persistence#1313
Andrii Lomakin (andrii0lomakin) wants to merge 1 commit into
developfrom
YTDB-1200-1201-1202-link-collection-fixes

Conversation

@andrii0lomakin

@andrii0lomakin Andrii Lomakin (andrii0lomakin) commented Sep 17, 2026 •
edited
Loading

Copy link
Copy Markdown
Collaborator

PR Title:

[YTDB-1200, YTDB-1201, YTDB-1202] Fix link collection identity and persistence

Motivation:

This pull request fixes three related reliability problems. A link collection stores record references. A link bag allows duplicate references. A link set rejects duplicates.

A pointer identifies stored link collection data. Serialization converts database values into stored bytes. The main record serializer converts complete records to and from stored bytes. A delta serializer converts changed record fields to and from stored bytes. ChangeableRecordId stores a record identity that can change. LinkBagPointer identifies a link collection location.

Record identity updates can compare against the wrong field. Empty live link collections can lose allocation evidence after restart. Allocator-produced pointers can be rejected as invalid. These defects can skip notifications, reuse identifiers, and bypass pointer serialization. The design keeps the existing identifier model and protects stored references.

Planned changes:

Intention

Make record identity changes and stored link collection identifiers reliable, including after restart.

Goals
  1. Apply valid collection identifier changes and send required notifications.
  2. Prevent identifier sharing within one link collection storage file.
  3. Preserve that protection for empty collections and after restart.
  4. Accept allocator-produced pointers and reject invalid pointers.
  5. Verify pointer serialization for link bags and link sets.
  6. Reject invalid pointers when the main record serializer reads link bags and link sets.
Components and data flow
Record creation -> ChangeableRecordId -> notifications

Link bags and link sets -> allocator -> link collection storage
                                      ^
                                      | recovery log writes counter state
                                      |
                                restart restores counter

Link bags and link sets -> pointer validation
                         -> delta serializer
                         -> main record serializer

Tests verify both serializers and both collection types.

A recovery log records storage changes for failure recovery. It writes counter state with pointer creation, so restart can restore the counter from storage.

Current state

ChangeableRecordId can compare a requested collection identifier with a record position. Empty live link collections can lose allocation evidence after restart. LinkBagPointer rejects negative identifiers produced by the allocator. The main record serializer does not reject every invalid stored pointer.

What changes

Identity changes compare the requested identifier with the current identifier. Real changes send before and after notifications. No-op assignments send no notifications.

The allocator keeps negative identifiers and the existing database-wide counter. Counter information persists with link collection storage through the existing recovery mechanism. Counter and pointer updates commit together. Restart allocation continues beyond every committed identifier, including identifiers for empty collections.

Pointer validation accepts a nonnegative file identifier with a negative link collection identifier. Pointer validation rejects invalid file identifiers and invalid zero or positive link collection identifiers. Both serializers apply this validation while reading link bags and link sets.

Approach

Use the existing recovery mechanism for counter updates. Validate pointers across both serializer paths. Test valid negative identifiers, invalid file identifiers, and invalid zero or positive link collection identifiers. Test round trips for both link bags and link sets.

Key decisions
  • Retain the negative allocation scheme and global counter.
  • Increase the storage format version. Require export and import for older databases.
  • Persist allocation state instead of reconstructing it only from stored entries.
  • Exclude automatic migration by scanning stored records to keep this change bounded.
  • Keep all three fixes in one track and one pull request.
Out of scope
  • Repairing already mixed collections.
  • Automatic migration by scanning records.
  • Changing the negative allocation scheme.
  • Redesigning the serialization format.
  • Separate YTDB-1178 concurrency failures.
  • Main record serializer changes beyond pointer validation and related tests.
Risks & accepted trade-offs
  • Older databases require export and import after the format increase.
  • Link entries alone cannot reconstruct allocation state for empty live link collections.
  • Automatic migration by scanning stored records is excluded to keep the change bounded.
  • Counter and pointer updates must share atomic recovery boundaries.
  • Invalid stored pointers will fail during reading instead of later operations.
  • Independent review closed all implementation findings.
  • Final post-adversarial design approval and pre-implementation approval were user-approved on 2026-09-17.
  • The user approved the complete track diff on 2026-09-17.
Suggestions:

None.

Verification approach

Verify identity changes and notifications. Verify pointer validity and round trips for bags and sets. Verify empty-collection restart allocation, rollback, and crash recovery. Run relevant unit and integration tests. Measure changed-line coverage under the project gate.

The compile gate passed. The core suite passed with 1,930 tests, zero failures, zero errors, and 20 skips. Selected integration tests passed with seven tests and no failures. Coverage passed with 90.3 percent line coverage and 76.9 percent branch coverage across 21 changed Java files.

@andrii0lomakin
Fix link collection identity and durable allocation
313e250 
Implemented the approved YTDB-1200, YTDB-1201, and YTDB-1202 fixes.

What had to be implemented:
- Correct collection identity comparison and notification behavior.
- Durable negative link-collection allocation across empty bags and restart.
- Domain-aware pointer validation for allocated and invalid identifiers.
- Invalid-pointer rejection in both main record serializer reader variants.
- Pointer round trips for link bags and link sets.
- Storage format 25 with export and import required for older databases.

The result preserves the existing global counter and negative allocation scheme. No high-level design changes were made.

Approved high-level design:

Intention: Make record identity changes and stored link collection identifiers reliable after restart.

Goals:
1. Apply valid collection identifier changes and send required notifications.
2. Prevent identifier sharing within one link collection storage file.
3. Preserve that protection for empty collections and after restart.
4. Accept allocated pointers and reject invalid pointers.
5. Verify pointer serialization for link bags and link sets.
6. Reject invalid pointers when the main record serializer reads link bags and link sets.

A link collection stores record references. A link bag allows duplicates. A link set rejects duplicates. A pointer identifies stored link collection data.

Components:
Record identity -> ChangeableRecordId -> notifications
Link bags and sets -> allocator -> link storage -> recovery log -> restart counter
Link bags and sets -> pointer validation -> delta and main serializers

Approach:
- Compare requested identity with the current collection identifier.
- Notify listeners only for real identity changes.
- Persist the allocation counter with pointer creation through the existing recovery mechanism.
- Restore the global counter from stored link-collection state.
- Accept nonnegative file identifiers with negative link-collection identifiers.
- Reject invalid pointers while reading stored link bags and link sets.
- Keep existing serialization formats.

Non-goals:
- Repairing mixed collections.
- Automatic migration by scanning records.
- Changing identifier signs or ownership.
- Redesigning serialization formats.
- Fixing YTDB-1178 concurrency behavior.
- Unrelated serializer hardening.

The implementation adds focused regression tests and release notes. Verification evidence remains separate from this commit message.
@andrii0lomakin
Andrii Lomakin (andrii0lomakin) force-pushed the YTDB-1200-1201-1202-link-collection-fixes branch from ca2c53c to 313e250 Compare September 17, 2026 14:35
@andrii0lomakin
Andrii Lomakin (andrii0lomakin) marked this pull request as ready for review September 17, 2026 14:37
@github-actions

github-actions Bot commented Sep 17, 2026

Copy link
Copy Markdown

Test Count Gate Results

Tolerance: 5% drop allowed per module

Overall: ✅ 35759 tests (baseline: 35740, +19)

Module Baseline Current Change Status
core 25101 25120 +19 ✅
docker-tests 1893 1893 +0 ✅
embedded 1932 1932 +0 ✅
examples 6 6 +0 ✅
gremlin-annotations 30 30 +0 ✅
jmh-ldbc 73 73 +0 ✅
server 5538 5538 +0 ✅
tests 1167 1167 +0 ✅

@github-actions

github-actions Bot commented Sep 17, 2026

Copy link
Copy Markdown

Coverage Gate Results

Thresholds: 85% line, 70% branch

Line Coverage: ✅ 90.3% (65/72 lines)

File Coverage Uncovered Lines
core/src/main/java/com/jetbrains/youtrackdb/internal/core/id/ChangeableRecordId.java ✅ 100.0% (2/2) -
core/src/main/java/com/jetbrains/youtrackdb/internal/core/serialization/serializer/record/binary/RecordSerializerBinaryV1.java ❌ 83.3% (5/6) 900
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/impl/local/paginated/wal/PageOperationRegistry.java ✅ 100.0% (1/1) -
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/LinkBagPointer.java ✅ 100.0% (1/1) -
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/LinkCollectionsBTreeManagerShared.java ❌ 77.8% (14/18) 78-79, 151, 183
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/ridbagbtree/EntryPoint.java ✅ 100.0% (9/9) -
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/ridbagbtree/RidbagEntryPointSetRidBagIdCounterOp.java ✅ 91.3% (21/23) 63, 66
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/ridbagbtree/SharedLinkBagBTree.java ✅ 100.0% (12/12) -

Branch Coverage: ✅ 76.9% (20/26 branches)

File Coverage Lines with Uncovered Branches
core/src/main/java/com/jetbrains/youtrackdb/internal/core/id/ChangeableRecordId.java ✅ 100.0% (2/2) -
core/src/main/java/com/jetbrains/youtrackdb/internal/core/serialization/serializer/record/binary/RecordSerializerBinaryV1.java ✅ 100.0% (2/2) -
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/LinkBagPointer.java ✅ 100.0% (4/4) -
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/LinkCollectionsBTreeManagerShared.java ❌ 66.7% (4/6) 77, 179
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/ridbagbtree/EntryPoint.java ✅ 100.0% (2/2) -
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/ridbagbtree/RidbagEntryPointSetRidBagIdCounterOp.java ❌ 62.5% (5/8) 62, 65, 68
core/src/main/java/com/jetbrains/youtrackdb/internal/core/storage/ridbag/ridbagbtree/SharedLinkBagBTree.java ❌ 50.0% (1/2) 136

@github-actions

github-actions Bot commented Sep 18, 2026

Copy link
Copy Markdown

JMH LDBC Benchmark Comparison

Base: b0a5cb1f8a (fork-point with develop) | Head: 313e25037b
Throughput: 🔴 2 regression(s) (>±5% threshold, non-overlapping error bars, <10% relative error)

Database Load Time

Time Δ
Base 28m 22.0s
Head 28m 15.0s -0.4% (-7.0s)

Single-Thread Results

Benchmark Base ops/s Base err Head ops/s Head err Δ%
ic10_friendRecommendation 10.3 ±1.2% 10.3 ±1.2% -0.5%
ic11_jobReferral 35.1 ±2.1% 35.2 ±1.3% +0.1%
ic12_expertSearch 37.0 ±2.4% 36.4 ±3.9% -1.6%
ic13_shortestPath 3,277 ±6.8% 3,155 ±6.3% -3.7%
ic1_transitiveFriends 87.9 ±3.8% 65.8 ±6.3% -25.2% 🔴
ic2_recentFriendMessages 203.5 ±2.2% 192.1 ±8.3% -5.6%
ic3_friendsInCountries 11.1 ±4.0% 11.0 ±3.5% -1.3%
ic4_newTopics 3.5 ±5.3% 3.6 ±7.8% +3.4%
ic5_newGroups 0.935 ±2.2% 0.921 ±2.2% -1.4%
ic6_tagCoOccurrence 3.3 ±4.5% 3.2 ±4.3% -3.1%
ic7_recentLikers 584.3 ±3.3% 574.0 ±3.3% -1.8%
ic8_recentReplies 744.9 ±1.4% 748.4 ±1.2% +0.5%
ic9_recentFofMessages 4.4 ±34.8% 4.4 ±32.7% +1.2%
is1_personProfile 38,458 ±3.0% 36,687 ±4.4% -4.6%
is2_personPosts 1,056 ±0.9% 1,044 ±1.3% -1.1%
is3_personFriends 10,735 ±6.6% 10,536 ±5.8% -1.8%
is4_messageContent 49,156 ±4.6% 48,767 ±3.3% -0.8%
is5_messageCreator 46,115 ±4.6% 46,239 ±4.0% +0.3%
is6_messageForum 32,626 ±2.2% 32,001 ±2.2% -1.9%
is7_messageReplies 5,977 ±1.2% 5,880 ±1.8% -1.6%

Multi-Thread Results

Benchmark Base ops/s Base err Head ops/s Head err Δ%
ic10_friendRecommendation 186.3 ±2.7% 189.1 ±1.9% +1.5%
ic11_jobReferral 584.9 ±1.5% 594.2 ±0.9% +1.6%
ic12_expertSearch 705.1 ±1.8% 712.2 ±3.1% +1.0%
ic13_shortestPath 68,209 ±3.7% 65,950 ±4.6% -3.3%
ic1_transitiveFriends 1,701 ±1.0% 1,381 ±1.1% -18.8% 🔴
ic2_recentFriendMessages 3,637 ±1.4% 3,638 ±2.3% +0.0%
ic3_friendsInCountries 178.3 ±5.1% 182.9 ±1.6% +2.6%
ic4_newTopics 46.0 ±4.0% 47.9 ±3.4% +4.3%
ic5_newGroups 6.6 ±1.4% 6.6 ±0.9% -0.5%
ic6_tagCoOccurrence 55.6 ±1.4% 53.9 ±1.5% -3.0%
ic7_recentLikers 10,689 ±2.0% 10,561 ±1.7% -1.2%
ic8_recentReplies 14,961 ±1.3% 14,823 ±1.5% -0.9%
ic9_recentFofMessages 71.9 ±3.3% 74.2 ±4.6% +3.1%
is1_personProfile 529,586 ±1.0% 527,870 ±1.6% -0.3%
is2_personPosts 22,348 ±1.8% 22,315 ±1.3% -0.1%
is3_personFriends 194,892 ±1.5% 196,342 ±1.8% +0.7%
is4_messageContent 638,876 ±1.2% 645,707 ±0.6% +1.1%
is5_messageCreator 609,137 ±2.6% 603,999 ±1.5% -0.8%
is6_messageForum 444,400 ±1.9% 449,215 ±0.9% +1.1%
is7_messageReplies 108,511 ±1.9% 108,260 ±1.8% -0.2%

Gremlin Translator Results

Translator-on arm from LdbcGremlinTranslatorBenchmark (production default). Pass --gremlin-arms both for the off arm too.

Benchmark Base ops/s Base err Head ops/s Head err Δ%
gremlin_friendsNotLocatedInPlace 12,273 ±1.8% 12,295 ±1.3% +0.2%
gremlin_ic11_friendsCompaniesInCountry 6,513 ±4.9% 6,685 ±1.1% +2.6%
gremlin_ic1_repeatKnowsToThreeHopsDeclines 6.6 ±0.7% 6.5 ±1.5% -2.1%
gremlin_ic2_friendsMessagesOrdered 44.9 ±9.1% 45.1 ±8.5% +0.4%
gremlin_ic7_likers 1,159 ±1.0% 1,153 ±2.1% -0.5%
gremlin_ic8_recentRepliesOrdered 955.4 ±2.8% 969.8 ±0.7% +1.5%
gremlin_is1_fullProfile 36,287 ±1.7% 37,286 ±1.7% +2.8%
gremlin_is1_personCityProfile 44,578 ±3.5% 45,727 ±2.7% +2.6%
gremlin_is2_personMessages 854.5 ±0.8% 855.0 ±1.6% +0.1%
gremlin_is3_friendsWithDatesDeclines 8,318 ±3.2% 8,306 ±2.8% -0.1%
gremlin_is3_friendsWithNames 12,883 ±2.6% 13,029 ±1.7% +1.1%
gremlin_is4_coalesceMessageContentDeclines 36,145 ±2.1% 35,940 ±2.5% -0.6%
gremlin_is5_messageCreator 43,234 ±1.6% 42,645 ±4.0% -1.4%
gremlin_is6_forumOfPost 26,013 ±1.9% 27,111 ±1.4% +4.2%
gremlin_is7_optionalFriendOfCreatorDeclines 12,482 ±2.5% 12,328 ±1.4% -1.2%
gremlin_is7_repliesWithAuthors 46,601 ±3.4% 46,553 ±1.8% -0.1%
gremlin_knowsFilteredByFriendFirstName 26,711 ±1.6% 26,459 ±2.4% -0.9%
gremlin_knowsFirstNameCount 26,632 ±2.1% 26,162 ±2.2% -1.8%
gremlin_knowsFirstNames 24,277 ±2.1% 24,236 ±0.9% -0.2%
gremlin_knowsFirstNamesFolded 24,020 ±1.7% 24,051 ±0.8% +0.1%
gremlin_knowsGroupCountByLastName 19,620 ±1.9% 19,794 ±1.1% +0.9%
gremlin_knowsOrderedPageDeclines 16,930 ±2.4% 16,866 ±2.2% -0.4%
gremlin_mutualFriendTriangle 155.8 ±4.4% 157.4 ±2.9% +1.0%
gremlin_threeHopKnowsExcludingIntermediate 1.7 ±3.6% 1.6 ±4.6% -2.7%
gremlin_twoHopKnows 91.8 ±1.3% 91.5 ±6.8% -0.3%
gremlin_vertexByRidDeclines 144,770 ±2.0% 144,715 ±0.9% -0.0%

Scalability (MT/ST ratio)

Benchmark Base ratio Base err Head ratio Head err Δ%
ic10_friendRecommendation 18.07x ±3.0% 18.45x ±2.2% +2.1%
ic11_jobReferral 16.66x ±2.6% 16.90x ±1.6% +1.5%
ic12_expertSearch 19.07x ±3.0% 19.58x ±5.0% +2.7%
ic13_shortestPath 20.82x ±7.7% 20.90x ±7.8% +0.4%
ic1_transitiveFriends 19.34x ±3.9% 20.99x ±6.4% +8.5%
ic2_recentFriendMessages 17.87x ±2.6% 18.94x ±8.6% +6.0%
ic3_friendsInCountries 16.05x ±6.5% 16.67x ±3.8% +3.9%
ic4_newTopics 13.07x ±6.7% 13.18x ±8.5% +0.9%
ic5_newGroups 7.06x ±2.6% 7.13x ±2.3% +0.9%
ic6_tagCoOccurrence 16.93x ±4.7% 16.95x ±4.6% +0.1%
ic7_recentLikers 18.29x ±3.8% 18.40x ±3.7% +0.6%
ic8_recentReplies 20.09x ±1.9% 19.81x ±1.9% -1.4%
ic9_recentFofMessages 16.49x ±34.9% 16.80x ±33.0% +1.9%
is1_personProfile 13.77x ±3.2% 14.39x ±4.6% +4.5%
is2_personPosts 21.16x ±2.0% 21.37x ±1.8% +1.0%
is3_personFriends 18.16x ±6.8% 18.63x ±6.1% +2.6%
is4_messageContent 13.00x ±4.8% 13.24x ±3.4% +1.9%
is5_messageCreator 13.21x ±5.3% 13.06x ±4.2% -1.1%
is6_messageForum 13.62x ±2.9% 14.04x ±2.4% +3.1%
is7_messageReplies 18.15x ±2.3% 18.41x ±2.6% +1.4%

@github-actions

github-actions Bot commented Sep 18, 2026

Copy link
Copy Markdown

JMH LDBC Benchmark Comparison

Base: b0a5cb1f8a (fork-point with develop) | Head: 313e25037b
Throughput: 🔴 2 regression(s) (>±5% threshold, non-overlapping error bars, <10% relative error)

Database Load Time

Time Δ
Base 27m 49.0s
Head 27m 56.0s +0.4% (+7.0s)

Single-Thread Results

Benchmark Base ops/s Base err Head ops/s Head err Δ%
ic1_transitiveFriends 92.3 ±7.9% 80.7 ±5.0% -12.5% 🔴

Multi-Thread Results

Benchmark Base ops/s Base err Head ops/s Head err Δ%
ic1_transitiveFriends 1,748 ±1.4% 1,517 ±2.0% -13.2% 🔴

Gremlin Translator Results

Translator-on arm from LdbcGremlinTranslatorBenchmark (production default). Pass --gremlin-arms both for the off arm too.

Benchmark Base ops/s Base err Head ops/s Head err Δ%
gremlin_ic1_repeatKnowsToThreeHopsDeclines 6.5 ±0.7% 6.5 ±1.0% -0.0%

Scalability (MT/ST ratio)

Benchmark Base ratio Base err Head ratio Head err Δ%
ic1_transitiveFriends 18.95x ±8.0% 18.79x ±5.3% -0.8%

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

See More

Successfully merging this pull request may close these issues.

1 participant

@andrii0lomakin