You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@ignite.apache.org by GitBox <gi...@apache.org> on 2022/02/18 08:28:49 UTC
[GitHub] [ignite-3] ibessonov commented on a change in pull request #657: IGNITE-16275 [Native Persistence 3.0] B+Tree porting
ibessonov commented on a change in pull request #657:
URL: https://github.com/apache/ignite-3/pull/657#discussion_r809760382
##########
File path: modules/core/src/test/java/org/apache/ignite/internal/util/IgniteRandomSelfTest.java
##########
@@ -0,0 +1,53 @@
+/*
+ * 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.ignite.internal.util;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.Random;
+import java.util.concurrent.ThreadLocalRandom;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test for {@link IgniteRandom}.
+ */
+public class IgniteRandomSelfTest {
Review comment:
I wonder if benchmarks could show any difference. Can we check it? I don't really trust the information that it's "faster"
##########
File path: modules/core/src/main/java/org/apache/ignite/internal/util/IgniteRandom.java
##########
@@ -0,0 +1,60 @@
+/*
+ * 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.ignite.internal.util;
+
+import java.util.Random;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * Random to be used from a single thread. Compatible with {@link Random} but faster.
+ */
+public class IgniteRandom extends Random {
Review comment:
Is this used outside of tests?
##########
File path: modules/page-memory/src/main/java/org/apache/ignite/internal/pagememory/tree/IgniteTree.java
##########
@@ -0,0 +1,144 @@
+/*
+ * 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.ignite.internal.pagememory.tree;
+
+import org.apache.ignite.internal.util.IgniteCursor;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Interface for ignite internal tree.
+ *
+ * @param <L> Type of keys maintained by this tree.
+ * @param <T> Type of mapped values.
+ */
+public interface IgniteTree<L, T> {
Review comment:
Please add TODO here, I'm not sure that we even need this interface
##########
File path: modules/page-memory/src/main/java/org/apache/ignite/internal/pagememory/tree/BplusTree.java
##########
@@ -0,0 +1,6426 @@
+/*
+ * 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.ignite.internal.pagememory.tree;
+
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Bool.DONE;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Bool.FALSE;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Bool.READY;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Bool.TRUE;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Result.FOUND;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Result.GO_DOWN;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Result.GO_DOWN_X;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Result.NOT_FOUND;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Result.RETRY;
+import static org.apache.ignite.internal.pagememory.tree.BplusTree.Result.RETRY_ROOT;
+import static org.apache.ignite.internal.pagememory.util.PageIdUtils.effectivePageId;
+import static org.apache.ignite.internal.util.ArrayUtils.clearTail;
+import static org.apache.ignite.internal.util.ArrayUtils.set;
+import static org.apache.ignite.internal.util.IgniteUtils.hexLong;
+import static org.apache.ignite.lang.IgniteSystemProperties.getInteger;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Deque;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.concurrent.atomic.AtomicLong;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
+import org.apache.ignite.internal.pagememory.CorruptedDataStructureException;
+import org.apache.ignite.internal.pagememory.PageIdAllocator;
+import org.apache.ignite.internal.pagememory.PageMemory;
+import org.apache.ignite.internal.pagememory.datastructure.DataStructure;
+import org.apache.ignite.internal.pagememory.io.IoVersions;
+import org.apache.ignite.internal.pagememory.io.PageIo;
+import org.apache.ignite.internal.pagememory.metric.IoStatisticsHolder;
+import org.apache.ignite.internal.pagememory.metric.IoStatisticsHolderNoOp;
+import org.apache.ignite.internal.pagememory.reuse.LongListReuseBag;
+import org.apache.ignite.internal.pagememory.reuse.ReuseBag;
+import org.apache.ignite.internal.pagememory.reuse.ReuseList;
+import org.apache.ignite.internal.pagememory.tree.io.BplusInnerIo;
+import org.apache.ignite.internal.pagememory.tree.io.BplusIo;
+import org.apache.ignite.internal.pagememory.tree.io.BplusLeafIo;
+import org.apache.ignite.internal.pagememory.tree.io.BplusMetaIo;
+import org.apache.ignite.internal.pagememory.util.PageHandler;
+import org.apache.ignite.internal.pagememory.util.PageLockListener;
+import org.apache.ignite.internal.tostring.S;
+import org.apache.ignite.internal.util.FastTimestamps;
+import org.apache.ignite.internal.util.IgniteCursor;
+import org.apache.ignite.internal.util.IgniteLongList;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+import org.apache.ignite.lang.IgniteInternalException;
+import org.apache.ignite.lang.IgniteStringBuilder;
+import org.apache.ignite.lang.IgniteTuple3;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * <h3>Abstract B+Tree.</h3>
+ *
+ * <p>B+Tree is a block-based tree structure. Each block is represented with the page ({@link PageIo}) and contains a single tree node.
+ * There are two types of pages/nodes: {@link BplusInnerIo} and {@link BplusLeafIo}.
+ *
+ * <p>Every page in the tree contains a list of <i>items</i>. Item is just a fixed-size binary payload. Inner nodes and leaves may have
+ * different item sizes. There's a limit on how many items each page can hold. It is defined by a {@link BplusIo#getMaxCount(long, int)}
+ * method of the corresponding IO. There should be no empty pages in trees, so it's expected to have from {@code 1} to {@code max} items in
+ * every page.
+ *
+ * <p>Items might have different meaning depending on the type of the page. In case of leaves, every item must describe a key and a value.
+ * In case of inner nodes, items describe only keys if {@link #canGetRowFromInner} is {@code false}, or a key and a value otherwise. Items
+ * in every page are sorted according to the order dscribed by {@link #compare(BplusIo, long, int, Object)} method. Specifics of the data
+ * stored in items are defined in the implementation and generally don't matter.
+ *
+ * <p>All pages in the tree are divided into levels. Leaves are always at the level {@code 0}. Levels of inner pages are thus positive.
+ * Each
+ * level represents a singly linked list - each page has a link to the <i>forward</i> page at the same level. It can be retrieved by calling
+ * {@link BplusIo#getForward(long)}. This link must be a zero if there's no forward page. Forward links on level {@code 0} allows iterating
+ * trees keys and values effectively without traversing any inner nodes ({@code AbstractForwardCursor}). Forward links in inner nodes have
+ * different purpose, more on that later.
+ *
+ * <p>Leaves have no links other than forward links. But inner nodes also have links to their children nodes. Every inner node can be
+ * viewed
+ * like the following structure:
+ * <pre><code>
+ * item(0) item(1) ... item(N-1)
+ * link(0) link(1) link(2) ... link(N-1) link(N)
+ * </code></pre>
+ * There are {@code N} items and {@code N+1} links. Each link points to page of a lower level. For example, pages on level {@code 2} always
+ * point to pages of level {@code 1}. For an item {@code i} left subtree is defined by {@code link(i)} and right subtree is defined by
+ * {@code link(i+1)} ({@link BplusInnerIo#getLeft(long, int)} and {@link BplusInnerIo#getRight(long, int)}). All items in the left subtree
+ * are less or equal to the original item (basic property for the trees).
+ *
+ * <p>There's one more important property of these links: {@code forward(left(i)) == right(i)}. It is called a
+ * <i>triangle invariant</i>. More information on B+Tree structure can easily be found online. Following documentation
+ * concentrates more on specifics of this particular B+Tree implementation.
+ *
+ * <p><h3>General operations.</h3>
+ * This implementation allows for concurrent reads and update. Given that each page locks individually, there are general rules to avoid
+ * deadlocks.
+ * <ul>
+ * <li>
+ * Pages within a level always locked from left to right.
+ * </li>
+ * <li>
+ * If there's already a lock on the page of level X then no locks should be acquired on levels less than X.
+ * In other words, locks are aquired from the bottom to the top. The only exception to this rule is the
+ * allocation of a new page on a lower level that no one sees yet.
+ * </li>
+ * </ul>
+ * All basic operations fit into a similar pattern. First, the search is performed ({@link Get}). It goes recursively
+ * from the root to the leaf (if it's needed). On each level several outcomes are possible.
+ * <ul>
+ * <li>Exact value is found and operation can be completed.</li>
+ * <li>Insertion point is found and recursive procedure continues on the lower level.</li>
+ * <li>Insertion point is not found due to concurrent modifications, but retry in the same node is possible.</li>
+ * <li>Insertion point is not found due to concurrent modifications, but retry in the same node is impossible.</li>
+ * </ul>
+ * All these options, and more, are described in the class {@link Result}. Please refer to its usages for specifics of
+ * each operation. Once the path and the leaf for put/remove is found, the operation is then performed from the bottom
+ * to the top. Specifics are described in corresponding classes ({@link Put}, {@link Remove}).
+ */
+@SuppressWarnings({"ConstantValueVariableUse"})
+public abstract class BplusTree<L, T extends L> extends DataStructure implements IgniteTree<L, T> {
+ /** Empty array. */
+ private static final Object[] EMPTY = {};
+
+ /** Destroy msg. */
+ public static final String CONC_DESTROY_MSG = "Tree is being concurrently destroyed: ";
+
+ /** Number of repetitions to capture a lock in the B+Tree. */
+ // TODO: https://issues.apache.org/jira/browse/IGNITE-16350
+ public static final String IGNITE_BPLUS_TREE_LOCK_RETRIES = "IGNITE_BPLUS_TREE_LOCK_RETRIES";
+
+ /** Number of retries. */
+ private static final int LOCK_RETRIES = getInteger(IGNITE_BPLUS_TREE_LOCK_RETRIES, 1000);
+
+ /** Flag that the tree is destroyed. */
+ private final AtomicBoolean destroyed = new AtomicBoolean(false);
+
+ private final float minFill;
+
+ private final float maxFill;
+
+ /** Meta page id. */
+ protected final long metaPageId;
+
+ private boolean canGetRowFromInner;
+
+ // TODO: https://issues.apache.org/jira/browse/IGNITE-16350
Review comment:
I'd love to see a comment, not only a link. What's supposed to be done here?
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org