apache / apache/hudi

Implement LIRE split and merge maintenance for vector indexes

Open
#19,500 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
6.2k
Forks
2.5k
Avg merge
2d 8h
Merged PRs (30d)
111

Description

Parent: #19094
Related: #18676

## Summary
Implement LIRE (Local Incremental Rebalancing) for sustained vector-cluster skew after Tier-1 vector compaction has landed and soaked.

LIRE changes local centroid geometry but does not use persisted centroid epochs. One completed MDT delta commit publishes the replacement routing and posting state atomically. The pinned data-table/MDT instant is the topology publication identity; manifest `routingVersion` remains only the routing-kernel compatibility version.

## Scope
- Evaluate `ClusterStats` split/merge triggers for clusters touched by recent maintenance.
- Fetch authoritative raw vectors using the positional reader shared with exact rerank.
- Run local balanced 2-means for oversized clusters.
- Mint replacement cluster IDs and re-encode every affected vector against its replacement centroid.
- Merge undersized clusters into an appropriate surviving centroid and re-encode their vectors.
- Evaluate neighboring leaves directly; do not route LIRE neighbor discovery through the coarse map.
- Apply bounded neighbor reassignment and publish replacement centroid chunks, posting blocks, tombstones, and statistics in one MDT delta commit.
- Rewrite the whole affected cluster when its shard geometry permits; escalate to a new generation when the bounded one-commit rewrite cannot be guaranteed.
- Key topology-dependent caches by index partition, generation, and pinned MDT instant; do not introduce a cluster routing epoch.
- Track assignment-mismatch metrics and trigger coarse-routing rebuild/escalation when thresholds are exceeded.

## Consistency requirements
- Readers observe either the pre-rebalance or post-rebalance MDT snapshot, never a mixed routing view.
- Persisted schema and keys contain no centroid epoch dimension.
- Residual codes are always regenerated when a centroid moves.
postings are tombstoned in the same commit that publishes replacements./- Old clusters/postings are tombstoned in the same commit that publishes replacements.n- Publication catches up through a locked cutoff and prevents stale-routing writers from committing after the replacement topology./postings are tombstoned in the same commit that publishes replacements.

## Acceptance criteria
- Adversarial skew fixtures deterministically trigger split and merge paths.
idempotence, cache invalidation, and generation escalation./- Tests cover split, merge, bounded neighbor reassignment, conservation of live keys, one-commit visibility, failure before commit, retry/idempotence, pinned-instant cache identity, stale-writer rejection/retry, and generation escalation./idempotence, cache invalidation, and generation escalation.
- Coarse-routing mismatch metrics and rebuild triggers are observable.

## Dependencies
- Epoch removal in #19097 / PR #19317.
- Incremental update hook and additive `ClusterStats`.
- Freshness/frontier contract.
- Tier-1 vector compaction/repacking and locator refresh.

## Scheduling
Deferred behind the correctness and bounded-growth critical path. Synthetic skew is required for certification because organic production-like churn may not trigger LIRE for weeks or months.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the listed dependencies, especially the incremental update hook, ClusterStats, freshness/frontier contract, and Tier-1 vector compaction. Trace the positional reader, MDT delta publication, cache identity, and generation-escalation entry points before defining the work. Done requires deterministic split and merge fixtures, atomic visibility, retry and stale-writer handling, conservation checks, cache invalidation, and observable mismatch-triggered rebuilds.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
data-engineering, databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.