ethbak opened a new pull request, #16627: URL: https://github.com/apache/lucene/pull/16627
### Overview Currently, when `IncrementalHnswGraphMerger` reuses an existing graph, `InitializedHnswGraphBuilder` copies it, repairs the nodes that lost too many neighbors, and rebalances the levels. This logic runs inside `ConcurrentHnswMerger.createBuilder`. Which is called before `HnswConcurrentMergeBuilder` even exists, so the copy/repair/rebalance process runs on the single merge thread without utilizing the worker pool. This is expensive especially for repair as it does a search per flagged node. Benchmarking with a 500k cohere index at 35% deletes shows repair takes 97.7s of a 174.7s merge. This is slower than the full rebuild process which does use the paralellized worker pool, even though it reduces CPU utilization. (Full rebuild of the same index took 97.7s for ALL steps, while the repair step itself took the same amount of time) ### Changes The three phases used to be one unit where `initGraph` would copy, repair, and rebalance the graph. With this change, the copy now fires alone (keep this part serial, its difficult/not worth to parallelize) and the other work is deferred to the concurrent merge builder which finishes the process. In practice: `InitializedHnswGraphBuilder.copyGraph` executes the copy and returns the half-built graph and the list of nodes needing repair per level, then `ConcurrentHnswMerger` hands both to `HnswConcurrentMergeBuilder`, which repairs and rebalances inside `build()`, which utilizes the worker pool. Repair is now structured to be per node per level work items to allow this parallelization. On each level, the workers take batches of flagged nodes off a shared `AtomicInteger` until that level's list is drained, one task per worker, and each worker repairs its nodes through its own scorer and searcher. Levels are repaired top-down with `invokeAll` serializing the levels (workers dont move on to next level until the current one is complete). This is necessary because nodes with no surviving neighbors have no entry point to search from, so it walks from the entry node to reach the current level, which looks at above levels (that must be completed before this happens). For this pr the rebalance work stays serial on the copy builder afterwards, as its time is negligible to the overall re-use process. Repairing concurrently needed one lock that a normal insert doesn't. With copied nodes that already inherit connections, its possible one node can be adding a reciprocal link into the same array that another is selecting. During repair, I hold `hnswLock.write(level, node)` around the selection and snapshot the entry points under `hnswLock.read(level, node)` before searching. I then release the lock before the per-neighbor loop that takes `hnswLock.write(level, nbr)`. This ensures that a worker holds at most one stripe at a time. ### Notes for reviewers - The first commit is pure restructuring as I needed to moves `fixDisconnectedNodes` and `addConnections` onto `HnswGraphBuilder`, so it may be useful to look at inter-commit diff while reviewing. - I suspect this will conflict with #16620 which at the time of writing is approved but not merged, so I will rebase afterwards. ### Benchmarking / Testing In addition to the unit tests added in the PR, I ran before/after benchmarks on cohere to show the difference with/without parallelization. cohere-1024, M=32, beamWidth=200, 500k vectors indexed as 5x100k segments, 35% delete, forceMerge(1), numMergeWorkers=8, m7g.4xlarge pinned to 8 cores | Arm | copy+repair | parallel insert | total | vs rebuild | |---|---|---|---|---| | reuse: before (#16618) | 97.7s | 77.0s | 174.7s | 1.79× | | reuse: this fix | 18.1s | 79.2s | 97.4s | 1.00× | | rebuild | 3.0s | 94.7s | 97.7s | 1.00× | We see a dramatic speedup in copy+repair time from this fix compared to re-use with no parallelism. Note that in this run specifically, re-use and rebuild are nearly the same, but this is at 35% deletes (near upper limit of the amount of repair work the merge algo needs to do) This shows that we, at worst, restore the wall-time that was lost with the previous unparallel implementation and that with lower delete percents, the speedup will be more visible (at 10% deletes, I see a ~13% speedup with re-use vs rebuild). Closes #16618 -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
