>From Ali Alsuliman <[email protected]>: Ali Alsuliman has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21679?usp=email )
Change subject: [ASTERIXDB-3817][TEST] Add a standalone vtree test module ...................................................................... [ASTERIXDB-3817][TEST] Add a standalone vtree test module The vector index had one test module, hyracks-storage-am-lsm-vtree-test, which reaches the page-mutation and attachment code only through an LSM component. Some paths are impractical to provoke that way, and they are the ones most likely to be wrong: a directory page splitting while it is not last in its chain, and the window after a memory component is recycled. Both have carried a real defect. hyracks-storage-am-vtree-test drives that code directly against a buffer cache, with no LSM component, operation tracker, flush or merge. 13 tests in three classes: VTreePageMutatorTest exercises the collaborator extracted from VTree: first insert into an empty directory, tuples surviving data-page splits, physical delete, and the non-last directory-page split. Assertions are on reachability -- everything inserted must still be findable by walking the directory chain the way the production code walks it -- so an orphaned chain shows up as missing tuples rather than requiring the test to know the page layout. Reintroducing the successor-dropping bug in handleMetadataPageOverflow fails it with 726 tuples reachable out of 863, and fails nothing else. VTreeStaticStructureAttachmentTest covers attach, recycle and re-attach. Two trees on one buffer cache stand in for the two components, differing in file id and root page so that "fell back to its own tree" is distinguishable from "still borrowing", and the borrowed cache is a distinct delegating stand-in over the same real cache so that it discriminates too. Against the code before the attachment was made atomic, the recycle test fails on each of those three -- file id, root page and buffer cache -- and fails nothing else. StaticStructureRefTest pins the centroid-to-directory lookup that used to be four copies of the same arithmetic. The module depends on hyracks-storage-am-lsm-vtree for LSMVTreeDataTupleWriterFactory alone, so the data-page tuple layout under test is the production one. The existing LSM test module is unchanged: all 20 of its test classes drive LSMVTree or its harness, and the tree keeps one test module per production module. Ext-ref: MB-73194 Co-Authored-By: Claude Opus 5 <[email protected]> Change-Id: I2d383bfed737719740671864d6ea5aac4097a7cf --- A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/pom.xml A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/StaticStructureRefTest.java A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/VTreePageMutatorTest.java A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/VTreeStaticStructureAttachmentTest.java M hyracks-fullstack/hyracks/hyracks-tests/pom.xml 5 files changed, 777 insertions(+), 0 deletions(-) git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/79/21679/1 diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/pom.xml b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/pom.xml new file mode 100644 index 0000000..dab6bd6 --- /dev/null +++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/pom.xml @@ -0,0 +1,111 @@ +<!-- + ! 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. + !--> +<project xmlns="http://maven.apache.org/POM/4.0.0"; xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"; xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd";> + <modelVersion>4.0.0</modelVersion> + <artifactId>hyracks-storage-am-vtree-test</artifactId> + <name>hyracks-storage-am-vtree-test</name> + + <parent> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-tests</artifactId> + <version>0.3.10-SNAPSHOT</version> + </parent> + + <properties> + <root.dir>${basedir}/../../..</root.dir> + </properties> + + <build> + <plugins> + <plugin> + <groupId>org.apache.maven.plugins</groupId> + <artifactId>maven-deploy-plugin</artifactId> + <configuration> + <skip>true</skip> + </configuration> + </plugin> + </plugins> + </build> + + <dependencies> + <dependency> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-storage-am-vtree</artifactId> + <version>${project.version}</version> + <scope>test</scope> + </dependency> + <!-- + For LSMVTreeDataTupleWriterFactory only, so the data-page tuple layout under test is byte-for-byte + the production one. Nothing here instantiates an LSM component, operation tracker, or flush/merge + machinery: that is the whole point of this module. + --> + <dependency> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-storage-am-lsm-vtree</artifactId> + <version>${project.version}</version> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-test-support</artifactId> + <version>${project.version}</version> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-storage-am-common</artifactId> + <version>${project.version}</version> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-storage-common</artifactId> + <version>${project.version}</version> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-dataflow-common</artifactId> + <version>${project.version}</version> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-data-std</artifactId> + <version>${project.version}</version> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.apache.hyracks</groupId> + <artifactId>hyracks-api</artifactId> + <version>${project.version}</version> + <scope>test</scope> + </dependency> + <dependency> + <groupId>junit</groupId> + <artifactId>junit</artifactId> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.mockito</groupId> + <artifactId>mockito-core</artifactId> + <scope>test</scope> + </dependency> + </dependencies> +</project> diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/StaticStructureRefTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/StaticStructureRefTest.java new file mode 100644 index 0000000..2b1089c --- /dev/null +++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/StaticStructureRefTest.java @@ -0,0 +1,81 @@ +/* + * 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.hyracks.storage.am.vector.impls; + +import org.apache.hyracks.storage.common.buffercache.IBufferCache; +import org.apache.hyracks.util.annotations.AiProvenance; +import org.junit.Assert; +import org.junit.Test; +import org.mockito.Mockito; + +/** + * Guards the centroid→directory-page lookup that used to be four copies of the same index + * arithmetic, spread across {@code VTree}, {@code VTreeSearchCursor} and {@code VTreeFlushLoader}. + */ +@AiProvenance(agent = AiProvenance.Agent.CLAUDE_OPUS_5, tool = AiProvenance.Tool.CLAUDE_CODE_UI, contributionKind = AiProvenance.ContributionKind.TEST_GENERATED) +public class StaticStructureRefTest { + + /** Centroid ids are absolute; the mapping is indexed relative to the first leaf centroid. */ + @Test + public void directoryPageIsLookedUpRelativeToTheFirstCentroid() { + StaticStructureRef ref = ref(new int[] { 40, 41, 42 }, 10); + + Assert.assertEquals(40, ref.directoryPageFor(10)); + Assert.assertEquals(41, ref.directoryPageFor(11)); + Assert.assertEquals(42, ref.directoryPageFor(12)); + } + + /** + * A centroid outside the mapping is not an error: navigating the shared static structure can land on + * a centroid this component never allocated a directory for, and every caller then falls back to its + * own resolution. The sentinel is what tells them to. + */ + @Test + public void centroidsOutsideTheMappingReportNoDirectoryPage() { + StaticStructureRef ref = ref(new int[] { 40, 41, 42 }, 10); + + Assert.assertEquals(StaticStructureRef.NO_DIRECTORY_PAGE, ref.directoryPageFor(9)); + Assert.assertEquals(StaticStructureRef.NO_DIRECTORY_PAGE, ref.directoryPageFor(13)); + Assert.assertEquals(StaticStructureRef.NO_DIRECTORY_PAGE, ref.directoryPageFor(Integer.MIN_VALUE)); + Assert.assertEquals(StaticStructureRef.NO_DIRECTORY_PAGE, ref.directoryPageFor(Integer.MAX_VALUE)); + } + + /** An empty mapping covers nothing rather than throwing. */ + @Test + public void anEmptyMappingCoversNoCentroid() { + Assert.assertEquals(StaticStructureRef.NO_DIRECTORY_PAGE, ref(new int[0], 0).directoryPageFor(0)); + } + + /** + * A half-built attachment is the failure this type exists to prevent, so the parts it cannot do + * without are rejected at construction rather than surfacing as an NPE during navigation. + */ + @Test + public void theMandatoryPartsAreRejectedWhenMissing() { + Assert.assertThrows(NullPointerException.class, () -> new StaticStructureRef(null, 1, 2, new int[1], 0, 1)); + Assert.assertThrows(NullPointerException.class, + () -> new StaticStructureRef(Mockito.mock(IBufferCache.class), 1, 2, null, 0, 1)); + } + + private static StaticStructureRef ref(int[] dirPageMap, int firstLeafCentroidId) { + return new StaticStructureRef(Mockito.mock(IBufferCache.class), 3, 4, dirPageMap, firstLeafCentroidId, + dirPageMap.length); + } +} diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/VTreePageMutatorTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/VTreePageMutatorTest.java new file mode 100644 index 0000000..4259dc9 --- /dev/null +++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/VTreePageMutatorTest.java @@ -0,0 +1,339 @@ +/* + * 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.hyracks.storage.am.vector.impls; + +import static org.apache.hyracks.storage.common.buffercache.context.read.DefaultBufferCacheReadContextProvider.NEW; + +import java.util.HashSet; +import java.util.Set; + +import org.apache.hyracks.api.context.IHyracksTaskContext; +import org.apache.hyracks.api.dataflow.value.ITypeTraits; +import org.apache.hyracks.api.exceptions.HyracksDataException; +import org.apache.hyracks.api.io.FileReference; +import org.apache.hyracks.data.std.primitive.DoublePointable; +import org.apache.hyracks.data.std.primitive.IntegerPointable; +import org.apache.hyracks.data.std.primitive.LongPointable; +import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder; +import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleReference; +import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference; +import org.apache.hyracks.storage.am.common.api.IPageManager; +import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory; +import org.apache.hyracks.storage.am.common.api.ITreeIndexMetadataFrame; +import org.apache.hyracks.storage.am.common.freepage.LinkedMetadataPageManagerFactory; +import org.apache.hyracks.storage.am.common.impls.NoOpOperationCallback; +import org.apache.hyracks.storage.am.common.ophelpers.IndexOperation; +import org.apache.hyracks.storage.am.lsm.vector.tuples.LSMVTreeDataTupleWriterFactory; +import org.apache.hyracks.storage.am.vector.api.IVTreeDataFrame; +import org.apache.hyracks.storage.am.vector.api.IVTreeMetadataFrame; +import org.apache.hyracks.storage.am.vector.frames.VTreeDataFrameFactory; +import org.apache.hyracks.storage.am.vector.frames.VTreeInteriorFrameFactory; +import org.apache.hyracks.storage.am.vector.frames.VTreeLeafFrameFactory; +import org.apache.hyracks.storage.am.vector.frames.VTreeMetadataFrameFactory; +import org.apache.hyracks.storage.am.vector.utils.VTreeDataTupleAccessor; +import org.apache.hyracks.storage.common.buffercache.IBufferCache; +import org.apache.hyracks.storage.common.buffercache.ICachedPage; +import org.apache.hyracks.storage.common.file.BufferedFileHandle; +import org.apache.hyracks.test.support.TestStorageManagerComponentHolder; +import org.apache.hyracks.test.support.TestUtils; +import org.apache.hyracks.util.annotations.AiProvenance; +import org.junit.After; +import org.junit.Assert; +import org.junit.Before; +import org.junit.Test; + +/** + * Drives {@link VTreePageMutator} directly against a real buffer cache, with no LSM component, + * operation tracker, flush or merge in sight — which is what extracting it from {@code VTree} was for. + * <p> + * The paths that matter here are the ones an LSM-level fixture struggles to reach on purpose: a data + * page splitting, and a <em>directory</em> page splitting while it is not last in its chain. The latter + * is the shape of a defect that shipped once already (the split page's successor was dropped, orphaning + * every page after it), and it needs a specific insert order to provoke — easy to arrange here, hard to + * arrange through a dataset. + * <p> + * Assertions are made on reachability rather than on internal structure: everything inserted must still + * be findable by walking the directory chain the way {@code insertIntoDataPages} and + * {@code tryPhysicalDelete} walk it. An orphaned chain shows up as tuples that have gone missing. + */ +@AiProvenance(agent = AiProvenance.Agent.CLAUDE_OPUS_5, tool = AiProvenance.Tool.CLAUDE_CODE_UI, contributionKind = AiProvenance.ContributionKind.TEST_GENERATED) +public class VTreePageMutatorTest { + + /** Small pages so that a few hundred tuples are enough to split data and directory pages. */ + private static final int PAGE_SIZE = 512; + private static final int NUM_PAGES = 4000; + private static final int MAX_OPEN_FILES = 10; + private static final int FRAME_SIZE = 32768; + private static final int DIMENSIONS = 4; + private static final int CENTROID_ID = 7; + + private IHyracksTaskContext ctx; + private IBufferCache bufferCache; + private FileReference file; + private int fileId; + private IPageManager freePageManager; + private ITreeIndexFrameFactory metadataFrameFactory; + private ITreeIndexFrameFactory dataFrameFactory; + private VTreeOpContext opCtx; + private VTreePageMutator mutator; + private long headDirectoryPage; + private int inserted; + + @Before + public void setUp() throws HyracksDataException { + ctx = TestUtils.create(FRAME_SIZE); + TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES); + bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx.getJobletContext().getServiceContext()); + file = ctx.getIoManager().getFileReference(0, "vtree-page-mutator-test"); + + ITreeIndexFrameFactory interiorFrameFactory = new VTreeInteriorFrameFactory(DIMENSIONS, null, null); + ITreeIndexFrameFactory leafFrameFactory = new VTreeLeafFrameFactory(DIMENSIONS, false, null, null); + metadataFrameFactory = new VTreeMetadataFrameFactory(DIMENSIONS, null, null); + // Non-quantized data tuple: <distance, centroidId, pk>. The production tuple writer is used so the + // layout under test is the real one. + ITypeTraits[] dataTraits = + { DoublePointable.TYPE_TRAITS, IntegerPointable.TYPE_TRAITS, LongPointable.TYPE_TRAITS }; + dataFrameFactory = new VTreeDataFrameFactory(new LSMVTreeDataTupleWriterFactory(dataTraits, false, null, null), + DIMENSIONS); + + freePageManager = new LinkedMetadataPageManagerFactory().createPageManager(bufferCache); + fileId = bufferCache.createFile(file); + bufferCache.openFile(fileId); + freePageManager.open(fileId); + freePageManager.init(interiorFrameFactory, leafFrameFactory); + + opCtx = new VTreeOpContext(null, interiorFrameFactory, leafFrameFactory, metadataFrameFactory, dataFrameFactory, + freePageManager, null, DIMENSIONS, NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE, + new VTreeDataTupleBuilderFactory(0, false), null); + opCtx.setOperation(IndexOperation.INSERT); + mutator = new VTreePageMutator(bufferCache, () -> fileId, freePageManager, metadataFrameFactory, false); + headDirectoryPage = newDirectoryPage(); + inserted = 0; + } + + @After + public void tearDown() throws HyracksDataException { + bufferCache.closeFile(fileId); + bufferCache.close(); + file.delete(); + } + + /** + * The first insert into an empty directory takes the create-the-first-data-page path, which is the + * one that must leave the data-page chain alone because there is no predecessor to link from. + */ + @Test + public void firstInsertCreatesAndRegistersOneDataPage() throws HyracksDataException { + insert(1.0, 1L); + + Assert.assertEquals(1, directoryEntryCount()); + Assert.assertEquals(1, reachableTupleCount()); + Assert.assertEquals(1, chainLength()); + } + + /** + * Ascending distances fill and split data pages. Every tuple must stay reachable, and the directory's + * max-distance ordering — which distance-based routing depends on — must survive each split. + */ + @Test + public void tuplesSurviveDataPageSplits() throws HyracksDataException { + for (int i = 0; i < 200; i++) { + insert(100.0 + i, i); + } + + Assert.assertTrue("expected data pages to have split", directoryEntryCount() > 1); + Assert.assertEquals(inserted, reachableTupleCount()); + assertDirectoryOrdering(); + } + + /** + * The case this module exists for: a directory page that splits while it is <em>not</em> last in its + * chain. Ascending inserts grow the chain past one page; low-distance inserts then land back on the + * first directory page, split its data pages, and overflow it a second time. If the split dropped the + * page's successor, everything after it becomes unreachable and the tuple count falls short. + */ + @Test + public void aNonLastDirectoryPageKeepsItsChainWhenItSplits() throws HyracksDataException { + // Phase 1: ascending distances until the directory itself has split at least once. + for (int i = 0; chainLength() < 2; i++) { + Assert.assertTrue("directory never split; raise the insert bound or lower PAGE_SIZE", i < 4000); + insert(1000.0 + i, i); + } + int chainAfterFirstSplit = chainLength(); + + // Phase 2: distances below everything inserted so far, so routing lands on the first directory + // page and its data pages split, adding entries to a page that is no longer last. + for (int i = 0; i < 600; i++) { + insert(i / 600.0, 100000L + i); + } + + Assert.assertTrue("the first directory page never split again, so the case was not exercised", + chainLength() > chainAfterFirstSplit); + Assert.assertEquals("directory chain lost pages after a non-last split", inserted, reachableTupleCount()); + assertDirectoryOrdering(); + } + + /** A physically deleted tuple is gone; a primary key that was never inserted is reported as absent. */ + @Test + public void physicalDeleteRemovesOnlyTheMatchingTuple() throws HyracksDataException { + for (int i = 0; i < 50; i++) { + insert(10.0 + i, i); + } + int before = reachableTupleCount(); + + Assert.assertTrue(mutator.tryPhysicalDelete(headDirectoryPage, 20.0, primaryKey(10L), sourceTuple(10L), opCtx)); + Assert.assertEquals(before - 1, reachableTupleCount()); + + Assert.assertFalse( + mutator.tryPhysicalDelete(headDirectoryPage, 20.0, primaryKey(999L), sourceTuple(999L), opCtx)); + Assert.assertEquals(before - 1, reachableTupleCount()); + } + + // ---- driving the mutator ------------------------------------------------------------------ + + private void insert(double distance, long pk) throws HyracksDataException { + mutator.insertIntoDataPages(headDirectoryPage, new double[DIMENSIONS], distance, CENTROID_ID, sourceTuple(pk), + opCtx); + inserted++; + } + + /** Source tuple shape the data-tuple builder expects with no include fields: [vector, pk]. */ + private static ITupleReference sourceTuple(long pk) throws HyracksDataException { + ArrayTupleBuilder builder = new ArrayTupleBuilder(2); + try { + builder.getDataOutput().writeDouble(0.0); // stands in for the vector; the builder never reads it + builder.addFieldEndOffset(); + builder.getDataOutput().writeLong(pk); + builder.addFieldEndOffset(); + } catch (Exception e) { + throw HyracksDataException.create(e); + } + ArrayTupleReference tuple = new ArrayTupleReference(); + tuple.reset(builder.getFieldEndOffsets(), builder.getByteArray()); + return tuple; + } + + private static byte[] primaryKey(long pk) { + byte[] key = new byte[Long.BYTES]; + for (int i = 0; i < Long.BYTES; i++) { + key[i] = (byte) (pk >>> (8 * (Long.BYTES - 1 - i))); + } + return key; + } + + private long newDirectoryPage() throws HyracksDataException { + ITreeIndexMetadataFrame metaFrame = freePageManager.createMetadataFrame(); + int pageId = freePageManager.takePage(metaFrame); + ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), NEW); + try { + page.acquireWriteLatch(); + IVTreeMetadataFrame frame = (IVTreeMetadataFrame) metadataFrameFactory.createFrame(); + frame.setPage(page); + frame.initBuffer((byte) 0); + frame.setNextPage(VTreeDataTupleAccessor.NO_NEXT_PAGE); + page.releaseWriteLatch(true); + } finally { + bufferCache.unpin(page); + } + return pageId; + } + + // ---- verification by walking the chain the mutator walks --------------------------------- + + private int chainLength() throws HyracksDataException { + int[] count = { 0 }; + walkDirectory((frame, dirPageId) -> count[0]++); + return count[0]; + } + + private int directoryEntryCount() throws HyracksDataException { + int[] count = { 0 }; + walkDirectory((frame, dirPageId) -> count[0] += frame.getTupleCount()); + return count[0]; + } + + private int reachableTupleCount() throws HyracksDataException { + int[] total = { 0 }; + Set<Long> dataPages = new HashSet<>(); + walkDirectory((frame, dirPageId) -> { + for (int i = 0; i < frame.getTupleCount(); i++) { + long dataPageId = frame.getDataPagePointer(i); + Assert.assertTrue("data page " + dataPageId + " registered twice", dataPages.add(dataPageId)); + total[0] += tupleCountIn(dataPageId); + } + }); + return total[0]; + } + + /** Max distances must be non-decreasing within a page and across the chain: routing relies on it. */ + private void assertDirectoryOrdering() throws HyracksDataException { + double[] previous = { Double.NEGATIVE_INFINITY }; + walkDirectory((frame, dirPageId) -> { + for (int i = 0; i < frame.getTupleCount(); i++) { + double max = frame.getMaxDistance(i); + Assert.assertTrue("directory out of order on page " + dirPageId + " entry " + i + ": " + max + " < " + + previous[0], max >= previous[0]); + previous[0] = max; + } + }); + } + + private int tupleCountIn(long dataPageId) throws HyracksDataException { + ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, (int) dataPageId)); + try { + page.acquireReadLatch(); + try { + IVTreeDataFrame frame = (IVTreeDataFrame) dataFrameFactory.createFrame(); + frame.setPage(page); + return frame.getTupleCount(); + } finally { + page.releaseReadLatch(); + } + } finally { + bufferCache.unpin(page); + } + } + + private void walkDirectory(DirectoryVisitor visitor) throws HyracksDataException { + Set<Long> visited = new HashSet<>(); + long dirPageId = headDirectoryPage; + while (dirPageId != VTreeDataTupleAccessor.NO_NEXT_PAGE) { + Assert.assertTrue("cycle in the directory chain at page " + dirPageId, visited.add(dirPageId)); + ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, (int) dirPageId)); + try { + page.acquireReadLatch(); + try { + IVTreeMetadataFrame frame = (IVTreeMetadataFrame) metadataFrameFactory.createFrame(); + frame.setPage(page); + visitor.visit(frame, dirPageId); + dirPageId = frame.getNextPage(); + } finally { + page.releaseReadLatch(); + } + } finally { + bufferCache.unpin(page); + } + } + } + + private interface DirectoryVisitor { + void visit(IVTreeMetadataFrame frame, long dirPageId) throws HyracksDataException; + } +} diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/VTreeStaticStructureAttachmentTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/VTreeStaticStructureAttachmentTest.java new file mode 100644 index 0000000..12cca35 --- /dev/null +++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-vtree-test/src/test/java/org/apache/hyracks/storage/am/vector/impls/VTreeStaticStructureAttachmentTest.java @@ -0,0 +1,245 @@ +/* + * 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.hyracks.storage.am.vector.impls; + +import org.apache.hyracks.api.context.IHyracksTaskContext; +import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory; +import org.apache.hyracks.api.exceptions.HyracksDataException; +import org.apache.hyracks.api.io.FileReference; +import org.apache.hyracks.data.std.primitive.LongPointable; +import org.apache.hyracks.storage.am.common.api.IPageManager; +import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory; +import org.apache.hyracks.storage.am.common.api.ITreeIndexMetadataFrame; +import org.apache.hyracks.storage.am.common.freepage.LinkedMetadataPageManagerFactory; +import org.apache.hyracks.storage.am.common.impls.NoOpIndexAccessParameters; +import org.apache.hyracks.storage.am.vector.TestDoubleArrayVectorAccessor; +import org.apache.hyracks.storage.am.vector.TestVTreeDistanceFunctionFactory; +import org.apache.hyracks.storage.am.vector.frames.VTreeDataFrameFactory; +import org.apache.hyracks.storage.am.vector.frames.VTreeInteriorFrameFactory; +import org.apache.hyracks.storage.am.vector.frames.VTreeLeafFrameFactory; +import org.apache.hyracks.storage.am.vector.frames.VTreeMetadataFrameFactory; +import org.apache.hyracks.storage.am.vector.utils.CrossPollinationConfig; +import org.apache.hyracks.storage.am.vector.utils.VTreeMetadataKeys; +import org.apache.hyracks.storage.common.buffercache.IBufferCache; +import org.apache.hyracks.test.support.TestStorageManagerComponentHolder; +import org.apache.hyracks.test.support.TestUtils; +import org.apache.hyracks.util.annotations.AiProvenance; +import org.junit.After; +import org.junit.Assert; +import org.junit.Before; +import org.junit.Test; +import org.mockito.AdditionalAnswers; +import org.mockito.Mockito; + +/** + * Covers the attach / recycle / re-attach lifecycle by which a memory component borrows the static + * clustering structure of another component, and in particular the window after a recycle. + * <p> + * That window is where a defect lived: the recycle cleared the centroid→directory mapping but left + * the borrowed buffer cache, file id and root page behind, so the component read as detached to the + * checks keyed on the mapping and as still attached to the ones keyed on the buffer cache — navigating + * a structure it had already let go of. The assertions below are on the navigation accessors, because + * those are what a search actually consults, and they are the ones that used to keep pointing at the + * released structure. + * <p> + * Two trees on one buffer cache stand in for the two components. They deliberately differ in file id and + * root page: that is what makes "fell back to its own tree" distinguishable from "still borrowing". + * <p> + * The borrowed cache is a distinct object from the borrower's own — a delegating stand-in over the same + * real cache — so that {@code getNavigationBufferCache()} discriminates too. Sharing one cache between + * the two trees would leave that assertion passing whether or not the attachment had been released, + * making the file-id and root-page assertions the only ones with teeth. + */ +@AiProvenance(agent = AiProvenance.Agent.CLAUDE_OPUS_5, tool = AiProvenance.Tool.CLAUDE_CODE_UI, contributionKind = AiProvenance.ContributionKind.TEST_GENERATED) +public class VTreeStaticStructureAttachmentTest { + + private static final int PAGE_SIZE = 512; + private static final int NUM_PAGES = 200; + private static final int MAX_OPEN_FILES = 10; + private static final int FRAME_SIZE = 32768; + private static final int DIMENSIONS = 4; + + /** Distinct from whatever the borrower's own root page is, so a stale borrow is visible. */ + private static final int STATIC_ROOT_PAGE = 5; + private static final int NUM_LEAF_CENTROIDS = 3; + private static final int FIRST_LEAF_CENTROID_ID = 11; + + private IHyracksTaskContext ctx; + private IBufferCache bufferCache; + /** + * Stands in for the static component's own cache. It delegates every call to {@link #bufferCache}, so + * the two trees really share one cache underneath; what matters is that it is a different object, which + * is what lets an assertion tell a released attachment from a live one. + */ + private IBufferCache staticCache; + private FileReference staticFile; + private FileReference memFile; + private VTree staticTree; + private VTree memTree; + + @Before + public void setUp() throws HyracksDataException { + ctx = TestUtils.create(FRAME_SIZE); + TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES); + bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx.getJobletContext().getServiceContext()); + staticFile = ctx.getIoManager().getFileReference(0, "vtree-attachment-static"); + memFile = ctx.getIoManager().getFileReference(0, "vtree-attachment-mem"); + + staticCache = Mockito.mock(IBufferCache.class, AdditionalAnswers.delegatesTo(bufferCache)); + staticTree = newTree(staticFile, staticCache); + staticTree.create(); + staticTree.activate(); + staticTree.setRootPageId(STATIC_ROOT_PAGE); + publishCentroidCounts(staticTree); + + memTree = newTree(memFile, bufferCache); + memTree.create(); + memTree.activate(); + + Assert.assertNotEquals("the two trees must differ for the fallback to be observable", staticTree.getFileId(), + memTree.getFileId()); + } + + @After + public void tearDown() throws HyracksDataException { + memTree.deactivate(); + memTree.destroy(); + staticTree.deactivate(); + staticTree.destroy(); + bufferCache.close(); + } + + /** Before attaching, a component navigates its own tree. */ + @Test + public void anUnattachedComponentNavigatesItsOwnTree() throws HyracksDataException { + Assert.assertFalse(memTree.isInitialized()); + Assert.assertEquals(memTree.getFileId(), memTree.getNavigationFileId()); + Assert.assertEquals(memTree.getRootPageId(), memTree.getNavigationRootPageId()); + Assert.assertSame(bufferCache, memTree.getNavigationBufferCache()); + } + + /** After attaching, every navigation accessor reports the borrowed structure. */ + @Test + public void anAttachedComponentNavigatesTheBorrowedStructure() throws HyracksDataException { + attach(); + + Assert.assertTrue(memTree.isInitialized()); + Assert.assertEquals(staticTree.getFileId(), memTree.getNavigationFileId()); + Assert.assertEquals(STATIC_ROOT_PAGE, memTree.getNavigationRootPageId()); + Assert.assertSame(staticCache, memTree.getNavigationBufferCache()); + Assert.assertEquals(NUM_LEAF_CENTROIDS, memTree.getNumLeafCentroidMem()); + Assert.assertEquals(FIRST_LEAF_CENTROID_ID, memTree.getFirstLeafCentroidIdMem()); + } + + /** + * The regression this test exists for. A recycle must release the whole attachment, not part of it: + * after it, no navigation accessor may still point at the structure the component gave up. + */ + @Test + public void recycleReleasesEveryPartOfTheAttachment() throws HyracksDataException { + attach(); + Assert.assertEquals("precondition: the component is borrowing", staticTree.getFileId(), + memTree.getNavigationFileId()); + + memTree.resetInitialization(); + + Assert.assertFalse(memTree.isInitialized()); + Assert.assertEquals("navigation still uses the released file", memTree.getFileId(), + memTree.getNavigationFileId()); + Assert.assertEquals("navigation still uses the released root page", memTree.getRootPageId(), + memTree.getNavigationRootPageId()); + // assertNotSame rather than assertSame: the borrowed cache is a delegating stand-in that forwards + // toString(), so an assertSame failure would print identical text for both objects and read like a + // JUnit bug. This says the same thing and its failure text stays legible. + Assert.assertNotSame("navigation still uses the released buffer cache", staticCache, + memTree.getNavigationBufferCache()); + Assert.assertSame(bufferCache, memTree.getNavigationBufferCache()); + // The centroid counts belong to the released structure, so reading them is a caller bug rather + // than something to answer with a stale value. + Assert.assertThrows(HyracksDataException.class, memTree::getNumLeafCentroidMem); + Assert.assertThrows(HyracksDataException.class, memTree::getFirstLeafCentroidIdMem); + } + + /** A recycled component can be attached again — the post-flush path the LSM layer drives. */ + @Test + public void aRecycledComponentCanAttachAgain() throws HyracksDataException { + attach(); + memTree.resetInitialization(); + attach(); + + Assert.assertTrue(memTree.isInitialized()); + Assert.assertEquals(staticTree.getFileId(), memTree.getNavigationFileId()); + Assert.assertEquals(NUM_LEAF_CENTROIDS, memTree.getNumLeafCentroidMem()); + } + + /** Attaching twice without a recycle is a no-op: the LSM layer relies on that idempotence. */ + @Test + public void attachingTwiceIsIdempotent() throws HyracksDataException { + attach(); + int rootAfterFirst = memTree.getNavigationRootPageId(); + int countAfterFirst = memTree.getNumLeafCentroidMem(); + + attach(); + + Assert.assertEquals(rootAfterFirst, memTree.getNavigationRootPageId()); + Assert.assertEquals(countAfterFirst, memTree.getNumLeafCentroidMem()); + } + + // ---- fixture ----------------------------------------------------------------------------- + + private void attach() throws HyracksDataException { + VTree.VTreeAccessor accessor = + (VTree.VTreeAccessor) staticTree.createAccessor(NoOpIndexAccessParameters.INSTANCE); + try { + memTree.setStaticStructure(accessor); + } finally { + accessor.destroy(); + } + } + + /** The two counts {@code setStaticStructure} reads out of the static tree's metadata page. */ + private static void publishCentroidCounts(VTree tree) throws HyracksDataException { + IPageManager pageManager = tree.getPageManager(); + ITreeIndexMetadataFrame metaFrame = pageManager.createMetadataFrame(); + pageManager.getMaxPageId(metaFrame); + metaFrame.put(VTreeMetadataKeys.NUM_LEAF_CENTROIDS, LongPointable.FACTORY.createPointable(NUM_LEAF_CENTROIDS)); + metaFrame.put(VTreeMetadataKeys.FIRST_LEAF_CENTROID_ID, + LongPointable.FACTORY.createPointable(FIRST_LEAF_CENTROID_ID)); + } + + private VTree newTree(FileReference file, IBufferCache cache) throws HyracksDataException { + ITreeIndexFrameFactory interiorFrameFactory = new VTreeInteriorFrameFactory(DIMENSIONS, null, null); + ITreeIndexFrameFactory leafFrameFactory = new VTreeLeafFrameFactory(DIMENSIONS, false, null, null); + ITreeIndexFrameFactory metadataFrameFactory = new VTreeMetadataFrameFactory(DIMENSIONS, null, null); + ITreeIndexFrameFactory dataFrameFactory = new VTreeDataFrameFactory( + new org.apache.hyracks.storage.am.lsm.vector.tuples.LSMVTreeDataTupleWriterFactory( + new org.apache.hyracks.api.dataflow.value.ITypeTraits[] { + org.apache.hyracks.data.std.primitive.DoublePointable.TYPE_TRAITS, + org.apache.hyracks.data.std.primitive.IntegerPointable.TYPE_TRAITS, + LongPointable.TYPE_TRAITS }, + false, null, null), + DIMENSIONS); + IPageManager pageManager = new LinkedMetadataPageManagerFactory().createPageManager(cache); + return new VTree(cache, pageManager, interiorFrameFactory, leafFrameFactory, metadataFrameFactory, + dataFrameFactory, new IBinaryComparatorFactory[] { null }, DIMENSIONS, DIMENSIONS, file, + TestDoubleArrayVectorAccessor.Factory.INSTANCE, new VTreeDataTupleBuilderFactory(0, false), null, + new TestVTreeDistanceFunctionFactory("euclidean"), CrossPollinationConfig.LEGACY); + } +} diff --git a/hyracks-fullstack/hyracks/hyracks-tests/pom.xml b/hyracks-fullstack/hyracks/hyracks-tests/pom.xml index 26c2174..66d5799 100644 --- a/hyracks-fullstack/hyracks/hyracks-tests/pom.xml +++ b/hyracks-fullstack/hyracks/hyracks-tests/pom.xml @@ -46,6 +46,7 @@ <module>hyracks-storage-common-test</module> <module>hyracks-storage-am-btree-test</module> <module>hyracks-storage-am-rtree-test</module> + <module>hyracks-storage-am-vtree-test</module> <module>hyracks-storage-am-lsm-common-test</module> <module>hyracks-storage-am-lsm-btree-test</module> <module>hyracks-storage-am-lsm-vtree-test</module> -- To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21679?usp=email To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email Gerrit-MessageType: newchange Gerrit-Project: asterixdb Gerrit-Branch: master Gerrit-Change-Id: I2d383bfed737719740671864d6ea5aac4097a7cf Gerrit-Change-Number: 21679 Gerrit-PatchSet: 1 Gerrit-Owner: Ali Alsuliman <[email protected]>
