From 2a6738b69c763377d1f727da9876ffdd9058262f Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Thu, 21 Mar 2024 09:47:32 +0100 Subject: [PATCH] JournalIndex.truncate() should return last entry The only time we are calling truncate(), we are following up with a seek to the appropriate entry. Return the last indexed position from truncate(), so we can do better than a linear search. JIRA: CONTROLLER-2109 Change-Id: I701b0eefbf1f4d83f74ba95b93c41407289d95cb Signed-off-by: Robert Varga --- .../storage/journal/index/JournalIndex.java | 48 +++++++-------- .../storage/journal/index/Position.java | 9 +++ .../journal/index/SparseJournalIndex.java | 59 ++++++++++--------- 3 files changed, 66 insertions(+), 50 deletions(-) diff --git a/atomix-storage/src/main/java/io/atomix/storage/journal/index/JournalIndex.java b/atomix-storage/src/main/java/io/atomix/storage/journal/index/JournalIndex.java index ddaef94e37..8608e00fc6 100644 --- a/atomix-storage/src/main/java/io/atomix/storage/journal/index/JournalIndex.java +++ b/atomix-storage/src/main/java/io/atomix/storage/journal/index/JournalIndex.java @@ -1,5 +1,6 @@ /* * Copyright 2018-2022 Open Networking Foundation and others. All rights reserved. + * Copyright (c) 2024 PANTHEON.tech, s.r.o. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -15,32 +16,33 @@ */ package io.atomix.storage.journal.index; +import org.eclipse.jdt.annotation.Nullable; + /** - * Journal index. + * Index of a particular JournalSegment. */ public interface JournalIndex { + /** + * Adds an entry for the given index at the given position. + * + * @param index the index for which to add the entry + * @param position the position of the given index + */ + void index(long index, int position); - /** - * Adds an entry for the given index at the given position. - * - * @param index the index for which to add the entry - * @param position the position of the given index - */ - void index(long index, int position); - - /** - * Looks up the position of the given index. - * - * @param index the index to lookup - * @return the position of the given index or a lesser index - */ - Position lookup(long index); - - /** - * Truncates the index to the given index. - * - * @param index the index to which to truncate the index - */ - void truncate(long index); + /** + * Looks up the position of the given index. + * + * @param index the index to lookup + * @return the position of the given index or a lesser index, or {@code null} + */ + @Nullable Position lookup(long index); + /** + * Truncates the index to the given index and returns its position, if available. + * + * @param index the index to which to truncate the index, or {@code null} + * @return the position of the given index or a lesser index, or {@code null} + */ + @Nullable Position truncate(long index); } diff --git a/atomix-storage/src/main/java/io/atomix/storage/journal/index/Position.java b/atomix-storage/src/main/java/io/atomix/storage/journal/index/Position.java index c3619364b0..640a8e8f0f 100644 --- a/atomix-storage/src/main/java/io/atomix/storage/journal/index/Position.java +++ b/atomix-storage/src/main/java/io/atomix/storage/journal/index/Position.java @@ -16,9 +16,18 @@ */ package io.atomix.storage.journal.index; +import java.util.Map.Entry; +import org.eclipse.jdt.annotation.Nullable; + /** * Journal index position. */ public record Position(long index, int position) { + public Position(final Entry entry) { + this(entry.getKey(), entry.getValue()); + } + public static @Nullable Position ofNullable(final Entry entry) { + return entry == null ? null : new Position(entry); + } } diff --git a/atomix-storage/src/main/java/io/atomix/storage/journal/index/SparseJournalIndex.java b/atomix-storage/src/main/java/io/atomix/storage/journal/index/SparseJournalIndex.java index 5fe4280eb0..2b317362c5 100644 --- a/atomix-storage/src/main/java/io/atomix/storage/journal/index/SparseJournalIndex.java +++ b/atomix-storage/src/main/java/io/atomix/storage/journal/index/SparseJournalIndex.java @@ -1,5 +1,6 @@ /* * Copyright 2018-2022 Open Networking Foundation and others. All rights reserved. + * Copyright (c) 2024 PANTHEON.tech, s.r.o. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -15,36 +16,40 @@ */ package io.atomix.storage.journal.index; -import java.util.Map; import java.util.TreeMap; /** - * Sparse index. + * A {@link JournalIndex} maintaining target density. */ -public class SparseJournalIndex implements JournalIndex { - private static final int MIN_DENSITY = 1000; - private final int density; - private final TreeMap positions = new TreeMap<>(); - - public SparseJournalIndex(double density) { - this.density = (int) Math.ceil(MIN_DENSITY / (density * MIN_DENSITY)); - } - - @Override - public void index(long index, int position) { - if (index % density == 0) { - positions.put(index, position); +public final class SparseJournalIndex implements JournalIndex { + private static final int MIN_DENSITY = 1000; + + private final int density; + private final TreeMap positions = new TreeMap<>(); + + public SparseJournalIndex() { + density = MIN_DENSITY; + } + + public SparseJournalIndex(final double density) { + this.density = (int) Math.ceil(MIN_DENSITY / (density * MIN_DENSITY)); + } + + @Override + public void index(final long index, final int position) { + if (index % density == 0) { + positions.put(index, position); + } + } + + @Override + public Position lookup(final long index) { + return Position.ofNullable(positions.floorEntry(index)); + } + + @Override + public Position truncate(final long index) { + positions.tailMap(index, false).clear(); + return Position.ofNullable(positions.lastEntry()); } - } - - @Override - public Position lookup(long index) { - Map.Entry entry = positions.floorEntry(index); - return entry != null ? new Position(entry.getKey(), entry.getValue()) : null; - } - - @Override - public void truncate(long index) { - positions.tailMap(index, false).clear(); - } } -- 2.36.6