This is an automated email from the ASF dual-hosted git repository. agoncharuk pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/ignite.git
The following commit(s) were added to refs/heads/master by this push: new 02043cc IGNITE-14111 Add javadoc for AbstractDataPageIO - Fixes #8742. 02043cc is described below commit 02043ccf0fa42ce0892649d4303d0020e7938faf Author: Alexey Goncharuk <alexey.goncha...@gmail.com> AuthorDate: Tue Feb 2 16:28:24 2021 +0300 IGNITE-14111 Add javadoc for AbstractDataPageIO - Fixes #8742. Signed-off-by: Alexey Goncharuk <alexey.goncha...@gmail.com> --- .../persistence/tree/io/AbstractDataPageIO.java | 124 +++++++++++++++++++++ 1 file changed, 124 insertions(+) diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java index 4708f423..55690b8 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java @@ -37,6 +37,130 @@ import static org.apache.ignite.internal.util.GridUnsafe.bufferAddress; /** * Data pages IO. + * + * Rows in a data page are organized into two arrays growing toward each other: items table and row data. + * <p> + * Items table contains direct or indirect items which locate a row within the page. Items table is stored at the + * beginning of a page. Each item has an item ID which serves as an external item reference + * (see {@link PageIdUtils#link(long, int)}) and can be either direct or indirect. The size of any item in the items + * table is 2 bytes. ID of a direct item is always the same as its index in items table so it is not stored in the + * item itself. ID of an indirect item may differ from its index (see example below) so it is stored it the item + * along with ID (index) of direct item. + * <p> + * Direct and indirect items are always placed in the items table in such a way that direct items are stored first, + * and indirect items are always stored after direct items. A data page explicitly stores both direct and indirect + * items count (see {@link #getDirectCount(long)} and {@link #getIndirectCount(long)}), so that the item type can be + * easily determined: items with indexes {@code [0, directCnt)} are always direct and items with indexes + * {@code [directCnt, directCnt + indirectCnt)} are always indirect. Having both direct and indirect items in a + * page allows page defragmentation without breaking external links. Total number of rows stored in a page is equal + * to the number of direct items. + * <p> + * The row data is stored at the end of the page; newer rows are stored closer to the end of the items table. + * <h3>Direct Items</h3> + * Direct items refer a stored row directly by offset in the page: + * <pre> + * +-----------------------------------------------------------------------------+ + * | Direct Items ..... (rows data) | + * | (4000), (3800), (3600) ..... row_2_cccc row_1_bbbb row_0_aaaa | + * | | | |_____________^ ^ ^ | + * | | |_________________________________| | | + * | |______________________________________________________| | + * | directCnt: 3 | + * | indirectCnt: 0 | + * +-----------------------------------------------------------------------------+ + * </pre> + * Direct item ID always matches it's index in the items table. The value of a direct item in the table is an + * offset of the row data within the page. + * <h3>Indirect Items</h3> + * An indirect item explicitly stores the indirect item ID (1 byte) and the index of the direct item it refers to + * (1 byte). The referred direct item (referrent) stores the actual offset of the row in the data page: + * <pre> + * +-----------------------------------------------------------------------------+ + * | Direct Items .. Indirect items .... (rows data) | + * | ____________________ | + * | ⌄ | | + * | (3600), (3800), (3 -> 0) .... row_2_cccc row_1_bbbb | + * | | |_____________________________^___________^ | + * | |_____________________________________| | + * | directCnt: 2 | + * | indirectCount: 1 | + * +-----------------------------------------------------------------------------+ + * </pre> + * An indirect item can only be created as a result of row deletion. Note that indirect item ID does not + * necessarily match the item index in the items table, however, indirect item IDs are always stored in sorted order + * by construction. In the picture above, the page contains two rows which are referred by two items: + * <ul> + * <li>{@code 1} is a direct item which is stored at index 1 in the items table</li> + * <li>{@code 3} is an indirect item which is stored at index 2 in the items table and refers to the direct + * item {@code 0}</li> + * </ul> + * + * <h2>Items insertion and deletion</h2> + * <p> + * When rows are added to an empty page or a page with only direct items, the items table grows naturally: + * <pre> + * +---------------------------------------------------------------+ + * | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | + * +---------------------------------------------------------------+ + * | Item | a | b | c | d | e | f | g | h | i | j | + * +---------------------------------------------------------------+ + * </pre> + * + * When an item is removed, the items table is modified in such a way, that: + * <ul> + * <li>Item of deleted row is modified to point to the row of the last direct item</li> + * <li>The last direct item is converted to an indirect item, pointing to the deleted item</li> + * </ul> + * + * <pre> + * remove(itemId=07) + * +-----------------------------------------------------------------------+ + * | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | + * +-----------------------------------------------------------------------+ + * | Item | a | b | c | d | e | f | g | j | i | (09 -> 07) | + * +-----------------------------------------------------------------------+ + * + * remove(itemId=02) + * +--------------------------------------------------------------------------------+ + * | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | + * +--------------------------------------------------------------------------------+ + * | Item | a | b | i | d | e | f | g | j | (08 -> 02) | (09 -> 07) | + * +--------------------------------------------------------------------------------+ + * </pre> + * + * If the last direct item is already referred by an indirect item, that indirect item is updated and + * all indirect items are shifted to the left by 1 effectively dropping last direct item: + * <pre> + * remove(itemId=00) + * +--------------------------------------------------------------------------------+ + * | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | + * +--------------------------------------------------------------------------------+ + * | Item | j | b | i | d | e | f | g | (08 -> 02) | (09 -> 00) | | + * +--------------------------------------------------------------------------------+ + * </pre> + * + * When adding a row to a page with indirect items, the item is added to the end of direct items in the table and + * indirect items are shifted to the right: + * <pre> + * add(k) + * +-------------------------------------------------------------------------------+ + * | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | + * +-------------------------------------------------------------------------------+ + * | Item | j | b | i | d | e | f | g | k | (08 -> 02) | (09 -> 00) | + * +-------------------------------------------------------------------------------+ + * </pre> + * + * If during an insert a newly added direct item ID matches with an existing indirect item ID, the corresponding + * indirect item is converted to a direct item, and the row being inserted is represented by a direct item + * with the referrent ID: + * <pre> + * add(l) + * +-----------------------------------------------------------------------+ + * | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | + * +-----------------------------------------------------------------------+ + * | Item | j | b | l | d | e | f | g | k | i | (09 -> 00) | + * +-----------------------------------------------------------------------+ + * </pre> */ public abstract class AbstractDataPageIO<T extends Storable> extends PageIO implements CompactablePageIO { /** */