RKSPD commented on code in PR #16709: URL: https://github.com/apache/lucene/pull/16709#discussion_r4637111917
########## lucene/sandbox/src/java/org/apache/lucene/sandbox/codecs/segmentivf/SegmentIVFVectorsReader.java: ########## @@ -0,0 +1,1241 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.lucene.sandbox.codecs.segmentivf; + +import static org.apache.lucene.codecs.CodecUtil.checkIndexHeader; +import static org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.DATA_CODEC_NAME; +import static org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.DATA_EXTENSION; +import static org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.DEFAULT_PROBE_MARGIN; +import static org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.DIRECT_MONOTONIC_BLOCK_SHIFT; +import static org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.META_CODEC_NAME; +import static org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.META_EXTENSION; +import static org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.VERSION_CURRENT; +import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS; +import static org.apache.lucene.util.packed.DirectMonotonicReader.loadMeta; + +import java.io.Closeable; +import java.io.IOException; +import java.io.UncheckedIOException; +import java.lang.foreign.AddressLayout; +import java.lang.foreign.Arena; +import java.lang.foreign.FunctionDescriptor; +import java.lang.foreign.Linker; +import java.lang.foreign.MemorySegment; +import java.lang.foreign.ValueLayout; +import java.lang.invoke.MethodHandle; +import java.lang.invoke.VarHandle; +import java.nio.ByteOrder; +import java.nio.charset.StandardCharsets; +import java.nio.file.Files; +import java.nio.file.Path; +import java.util.Arrays; +import java.util.HashMap; +import java.util.List; +import java.util.Locale; +import java.util.Map; +import java.util.concurrent.ExecutorService; +import java.util.concurrent.Executors; +import java.util.concurrent.atomic.AtomicBoolean; +import java.util.concurrent.atomic.AtomicLong; +import org.apache.lucene.codecs.CodecUtil; +import org.apache.lucene.codecs.KnnVectorsReader; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.CorruptIndexException; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.IndexFileNames; +import org.apache.lucene.index.MergePolicy; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.VectorSimilarityFunction; +import org.apache.lucene.sandbox.codecs.segmentivf.Centroids.CentroidCodes; +import org.apache.lucene.sandbox.codecs.segmentivf.Centroids.CentroidGraph; +import org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.FineTier; +import org.apache.lucene.sandbox.codecs.segmentivf.SegmentIVFVectorsFormat.SearchStrategy; +import org.apache.lucene.sandbox.codecs.segmentivf.Tiers.CodeRecord; +import org.apache.lucene.sandbox.codecs.segmentivf.Tiers.FineCodec; +import org.apache.lucene.sandbox.codecs.segmentivf.Tiers.HadamardRotation; +import org.apache.lucene.sandbox.codecs.segmentivf.Tiers.Nitrox2; +import org.apache.lucene.search.AcceptDocs; +import org.apache.lucene.search.DocIdSetIterator; +import org.apache.lucene.search.KnnCollector; +import org.apache.lucene.search.VectorScorer; +import org.apache.lucene.store.ChecksumIndexInput; +import org.apache.lucene.store.FSDirectory; +import org.apache.lucene.store.FilterDirectory; +import org.apache.lucene.store.IOContext; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.store.MemorySegmentAccessInput; +import org.apache.lucene.store.RandomAccessInput; +import org.apache.lucene.util.ArrayUtil; +import org.apache.lucene.util.BitSet; +import org.apache.lucene.util.BitUtil; +import org.apache.lucene.util.Bits; +import org.apache.lucene.util.IOUtils; +import org.apache.lucene.util.NumericUtils; +import org.apache.lucene.util.VectorUtil; +import org.apache.lucene.util.packed.DirectMonotonicReader; + +/** + * Searches SegmentIVF fields by probing cells, scanning coarse codes, and reranking a shortlist. + * + * <p>The coarse scan is intentionally bandwidth-oriented: compact Nitrox2 rows are processed with + * XOR and popcount, then only a bounded set of survivors reaches the more expensive fine scorer. + * Filtered search chooses between scanning selected cells and visiting accepted documents directly. + */ +final class SegmentIVFVectorsReader extends KnnVectorsReader { + /** Coarse candidates fine-reranked per requested neighbor, and never fewer than MIN_RERANK. */ + static final int RERANK_PER_K = 7, MIN_RERANK = 100; + + /** Returns how many coarse candidates to fine-rerank for a top-{@code k} search. */ + static long rerankCount(int k) { + return Math.max(MIN_RERANK, (long) RERANK_PER_K * k); + } + + private static final int ADMIT_BLOCK = 256, FILTERED_PROBE_MULTIPLIER = 8; + private static final int VERIFY_MIN = 64, VERIFY_MULTIPLIER = 2; + private static final Kernels K = Kernels.INSTANCE; + private static final ValueLayout.OfInt INT_LE = + ValueLayout.JAVA_INT_UNALIGNED.withOrder(ByteOrder.LITTLE_ENDIAN); + + /** + * A segment's deduplicated coarse shortlist: record slots and their coarse distances, plus the + * search that gathered them, whose encoded query the rerank reuses. + */ + record Candidates(int[] slots, int[] distances, Field.Search search) { + static final Candidates EMPTY = new Candidates(new int[0], new int[0], null); + } + + private final Map<String, Field> fields = new HashMap<>(); + private final IndexInput data; + private final Uring uring; + private final Arena pinned = Arena.ofShared(); + private final AtomicLong pinnedBytes = new AtomicLong(); + private long fineBytes; + private boolean closed; + private final String segment; + private final int segmentMaxDoc; + + SegmentIVFVectorsReader(SegmentReadState state) throws IOException { + String name = segment = state.segmentInfo.name, sfx = state.segmentSuffix; + segmentMaxDoc = state.segmentInfo.maxDoc(); + byte[] id = state.segmentInfo.getId(); + String metaName = IndexFileNames.segmentFileName(name, sfx, META_EXTENSION); + try (ChecksumIndexInput meta = state.directory.openChecksumInput(metaName)) { + Throwable prior = null; + try { + checkIndexHeader(meta, META_CODEC_NAME, VERSION_CURRENT, VERSION_CURRENT, id, sfx); + for (int number = meta.readInt(); number != -1; number = meta.readInt()) { + FieldInfo info = state.fieldInfos.fieldInfo(number); + if (info == null) throw new CorruptIndexException("invalid field number " + number, meta); + fields.put(info.name, new Field(meta, info)); + } + } catch (Throwable t) { + prior = t; + } finally { + CodecUtil.checkFooter(meta, prior); + } + } + String dataName = IndexFileNames.segmentFileName(name, sfx, DATA_EXTENSION); + data = state.directory.openInput(dataName, state.context); + try { + checkIndexHeader(data, DATA_CODEC_NAME, VERSION_CURRENT, VERSION_CURRENT, id, sfx); + CodecUtil.retrieveChecksum(data); + } catch (Throwable t) { + IOUtils.closeWhileSuppressingExceptions(t, data); + throw t; + } + uring = openUring(state, dataName); + for (Field field : fields.values()) fineBytes += field.sections[2] - field.sections[1]; + Uring.addFine(fineBytes); + if (state.context.context() != IOContext.Context.MERGE) { + for (Field field : fields.values()) field.maybePin(); + } + } + + /** Opens batched fine-record reads for a data file of a file-system directory, if possible. */ + private static Uring openUring(SegmentReadState state, String name) { + if (FilterDirectory.unwrap(state.directory) instanceof FSDirectory fs) { + try { + return Uring.open(fs.getDirectory().resolve(name)); + } catch (IOException _) { + // fine records are read through the mapped input instead + } + } + return null; + } + + final class Field { + final VectorSimilarityFunction similarity; + final FineTier fineTier; + final int dim, nlist, count, nprobe, spillBits, recordLen, coarseBytes, docIdOffset; + final long rotationSeed; + final long[] sections; + final DirectMonotonicReader.Meta postingOffsets; + final HadamardRotation rotation; + final FineCodec fine; + + RandomAccessInput records, slotDocs; + MemorySegment recordsSeg; // the whole mapped records section, or null + MemorySegmentAccessInput coarseAccess; + MemorySegment coarseSeg; + // Off-heap copies published by the pinning thread; searches use the mapped sections until then. + volatile MemorySegment pinnedCoarse, pinnedSlotDocs; + private final AtomicBoolean pinning = new AtomicBoolean(); + private volatile long lastPinAttempt; + int[] cellStart, ordToSlot, ordToDoc, allCells, primaryCells; + float[][] centroids; + private volatile CentroidCodes codes; + CentroidGraph graph; + + Field(ChecksumIndexInput meta, FieldInfo info) throws IOException { + similarity = info.getVectorSimilarityFunction(); + fineTier = FineTier.values()[meta.readByte()]; + dim = meta.readVInt(); + nlist = meta.readVInt(); + count = meta.readVInt(); + rotationSeed = meta.readLong(); + nprobe = meta.readVInt(); + spillBits = meta.readVInt(); + // Sections: centroids, records, coarse, graph, ordToSlot, slotDoc, posting offsets. + sections = new long[7]; + for (int s = 0; s < sections.length; s++) sections[s] = meta.readVLong(); + postingOffsets = nlist == 0 ? null : loadMeta(meta, nlist + 1, DIRECT_MONOTONIC_BLOCK_SHIFT); + if (dim != info.getVectorDimension()) throw new CorruptIndexException("dimension", meta); + rotation = HadamardRotation.create(dim, rotationSeed); + fine = new FineCodec(fineTier, dim); + recordLen = CodeRecord.length(fine.codeBytes); + coarseBytes = Nitrox2.bytesPerVector(dim); + docIdOffset = fine.codeBytes; + } + + private RandomAccessInput section(int s) throws IOException { + return data.randomAccessSlice(sections[s], sections[s + 1] - sections[s]); + } + + synchronized Field open() throws IOException { + if (records != null) return this; + if (section(2) instanceof MemorySegmentAccessInput in) { + coarseAccess = in; + coarseSeg = segmentOrNull(in, 0, in.length()); + } + cellStart = new int[nlist + 1]; + if (nlist > 0) { + long postings = sections[sections.length - 1]; + RandomAccessInput tail = data.randomAccessSlice(postings, data.length() - postings); + var offsets = DirectMonotonicReader.getInstance(postingOffsets, tail); + for (int c = 0; c <= nlist; c++) cellStart[c] = (int) (offsets.get(c) / Integer.BYTES); + } + slotDocs = section(5); + IndexInput all = data.clone(); + centroids = new float[nlist][dim]; + all.seek(sections[0]); + for (float[] centroid : centroids) all.readFloats(centroid, 0, dim); + records = section(1); + if (records instanceof MemorySegmentAccessInput in) { + recordsSeg = segmentOrNull(in, 0, in.length()); + } + return this; + } + + /** + * Queues the off-heap copy of the coarse and slot-to-document sections when the pin budget has + * room, retrying at most once per second: a merged segment is pinned once its sources close. + * Searches never wait for the copy. + */ + void maybePin() { + if (count == 0 || pinnedCoarse != null || pinning.get()) return; + long now = System.nanoTime(); + if (lastPinAttempt != 0 && now - lastPinAttempt < 1_000_000_000L) return; + if (pinning.getAndSet(true)) return; + lastPinAttempt = now == 0 ? 1 : now; + long coarseLength = sections[3] - sections[2]; + long docsLength = sections[6] - sections[5]; + if (Uring.reservePinned(coarseLength + docsLength) == false) { + pinning.set(false); + return; + } + pinnedBytes.addAndGet(coarseLength + docsLength); + Uring.PINNER.execute( + () -> { + try { + if (docsLength > 0) pinnedSlotDocs = pin(sections[5], docsLength); + pinnedCoarse = pin(sections[2], coarseLength); + } catch (IOException | RuntimeException _) { + // the reader closed mid-copy; its reservation is released on close + } + }); + } + + /** Copies a section off-heap, where the page cache cannot evict it. */ + private MemorySegment pin(long offset, long length) throws IOException { + MemorySegment copy = pinned.allocate(length, 64); // cache-line aligned for the SIMD scans + IndexInput in = data.clone(); + in.seek(offset); + byte[] chunk = new byte[1 << 20]; + for (long at = 0; at < length; at += chunk.length) { + int n = (int) Math.min(chunk.length, length - at); + in.readBytes(chunk, 0, n); + MemorySegment.copy(chunk, 0, copy, ValueLayout.JAVA_BYTE, at, n); + } + return copy; + } + + private int docAt(RandomAccessInput docs, int slot) throws IOException { + MemorySegment pinned = pinnedSlotDocs; + return pinned != null ? pinned.getAtIndex(INT_LE, slot) : docs.readInt((long) slot * 4); + } + + private synchronized void loadOrdToSlot() throws IOException { + if (ordToSlot != null) return; + int[] slots = new int[count]; + IndexInput all = data.clone(); + all.seek(sections[4]); + all.readInts(slots, 0, count); + ordToSlot = slots; + } + + private synchronized void loadOrdinalMappings() throws IOException { + if (ordToDoc != null) return; + loadOrdToSlot(); + int[] docs = new int[count]; + for (int ord = 0; ord < count; ord++) docs[ord] = docAt(slotDocs, ordToSlot[ord]); + ordToDoc = docs; + } + + /** + * Returns a mapped slice, or null when no single mapping covers it. The slice is rebased as a + * plain native segment scoped to this reader, so the SIMD kernels see one segment type whether + * or not a section is pinned: once they have seen both, every coarse scan runs ~16% slower. + */ + @SuppressWarnings("restricted") + private MemorySegment segmentOrNull(MemorySegmentAccessInput in, long offset, long length) { + if (length == 0) return null; + try { + MemorySegment mapped = in.segmentSliceOrNull(offset, length); + if (mapped == null) return null; + return MemorySegment.ofAddress(mapped.address()).reinterpret(length, pinned, null); + } catch (IOException _) { + return null; + } + } + + /** + * Returns the mapping holding one cell run: the whole coarse section when mappable, otherwise a + * slice rebased to the run, or null when neither is mapped. Offsets start at {@code runBase}. + */ + private MemorySegment coarseRun(int slotBase, int rows) { + if (coarseSeg != null || coarseAccess == null) return coarseSeg; + return segmentOrNull(coarseAccess, (long) slotBase * coarseBytes, (long) rows * coarseBytes); + } + + private long runBase(int slotBase) { + return coarseSeg == null ? 0 : (long) slotBase * coarseBytes; + } + + private synchronized void loadCodes() throws IOException { + if (codes != null) return; + allCells = new int[nlist]; + for (int c = 0; c < nlist; c++) allCells[c] = c; + long graphLength = sections[4] - sections[3]; + graph = graphLength == 0 ? null : CentroidGraph.read(section(3), dim, graphLength); + codes = new CentroidCodes(centroids, dim, fine); + } + + synchronized int cellOf(int ord) throws IOException { + loadOrdToSlot(); + if (primaryCells == null) { + primaryCells = new int[count]; + for (int o = 0; o < count; o++) { + primaryCells[o] = records.readInt((long) ordToSlot[o] * recordLen + docIdOffset + 4); + } + } + return primaryCells[ord]; + } + + /** + * Per-query state for cell selection, coarse admission, deduplication, and fine reranking. Each + * search opens its own slices, which shadow the field's: positional reads through a shared + * slice are not thread-safe on every directory implementation. + */ + final class Search { + final RandomAccessInput records = section(1), coarse = section(2); + final RandomAccessInput slotDocs = section(5); + // One snapshot per query, so a copy published mid-query cannot mix offsets. + final MemorySegment pinnedCoarse = Field.this.pinnedCoarse; + final float[] rotated; + final byte[] qCode; + final FineCodec.Query fine; + final KnnCollector collector; + final Scratch scratch = Scratch.LOCAL.get(); + final int bins = coarseBytes * 8 + 2, shortlist, pool; + final int[] histogram = scratch.histogram = ArrayUtil.growNoCopy(scratch.histogram, bins); + int size, admitted, threshold = bins - 1; + Candidates gathered; + + Search(float[] target, KnnCollector collector, int k) throws IOException { + maybePin(); + this.collector = collector; + shortlist = (int) Math.min(count, rerankCount(k)); + pool = Math.multiplyExact(shortlist, 1 + spillBits); + scratch.reserve(shortlist); + Arrays.fill(histogram, 0, bins, 0); + if (codes == null) loadCodes(); + rotated = new float[dim]; + qCode = new byte[coarseBytes]; + rotation.rotate(VectorUtil.l2normalize(ArrayUtil.copyOfSubArray(target, 0, dim)), rotated); + Nitrox2.encode(rotated, dim, qCode, 0); + fine = Field.this.fine.query(rotated, similarity); + } + + /** A rerank of {@code from}'s shortlist on this thread, reusing its encoded query. */ + private Search(Search from, KnnCollector collector) throws IOException { + this.collector = collector; + shortlist = from.shortlist; + pool = from.pool; + rotated = from.rotated; + qCode = from.qCode; + fine = from.fine; + } + + /** Fine-reranks {@code slots}, taken from this search's shortlist, into {@code collector}. */ + void rerankInto(int[] slots, KnnCollector collector) throws IOException { + new Search(this, collector).rerank(slots, slots.length); + } + + void run(AcceptDocs acceptDocs) throws IOException { + var strategy = collector.getSearchStrategy(); + if (strategy instanceof SearchStrategy s) run(s.numProbes, s.probeMargin, acceptDocs); + else run(nprobe, DEFAULT_PROBE_MARGIN, acceptDocs); + } + + private void run(int probe, float margin, AcceptDocs acceptDocs) throws IOException { + probe = Math.min(probe, nlist); + Bits accept = acceptDocs == null ? null : acceptDocs.bits(); + if (accept instanceof BitSet filter) { + int cost = acceptDocs.cost(); + double parity = + Math.sqrt((double) shortlist * cellStart[nlist] * coarseBytes / recordLen); + if (cost > (int) Math.max(shortlist, Math.min(Integer.MAX_VALUE, parity))) { + filteredScan(selectCells(probe, 1f), filter, cost, probe); + return; + } + boolean dense = count == segmentMaxDoc; + if (dense) loadOrdToSlot(); + else loadOrdinalMappings(); + int[] slots = new int[64]; + int n = 0; + DocIdSetIterator accepted = acceptDocs.iterator(); + for (int doc = accepted.nextDoc(); doc != NO_MORE_DOCS; doc = accepted.nextDoc()) { + int ord = dense ? doc : Arrays.binarySearch(ordToDoc, doc); + if (ord < 0) continue; + slots = ArrayUtil.grow(slots, n + 1); + slots[n++] = ordToSlot[ord]; + } + if (collector == null) admitAll(slots, n); + else rerank(slots, n); + } else { + // A segment no larger than the rerank pool scans every slot: its mostly empty cells would + // spend probes on cells holding nothing. + scan(cellStart[nlist] <= pool ? allCells : selectCells(probe, margin), accept); + } + } + + private int[] selectCells(int probe, float margin) { + int[] candidates = allCells; + int got = nlist; + if (graph != null) { + candidates = scratch.candidates = ArrayUtil.growNoCopy(scratch.candidates, nlist); + int[] coarse = scratch.coarse = ArrayUtil.growNoCopy(scratch.coarse, nlist); + int ef = Math.max(CentroidGraph.MIN_EF, probe * CentroidGraph.EF_MULTIPLIER); + got = graph.search(qCode, ef, candidates, coarse); + int cap = Math.max(VERIFY_MIN, probe * VERIFY_MULTIPLIER); + if (cap < got) { + int[] counts = new int[bins]; Review Comment: Noted, this was one of the main changes for the updated PR. It should be a lot nicer to read than the previous revision. -- 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]
