atomix-storage/src/main/java/io/atomix/storage/journal/index/SparseJournalIndex.java

   1 /*
   2  * Copyright 2018-2022 Open Networking Foundation and others.  All rights reserved.
   3  * Copyright (c) 2024 PANTHEON.tech, s.r.o.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17 package io.atomix.storage.journal.index;
  18
  19 import com.google.common.base.MoreObjects;
  20 import java.util.TreeMap;
  21 import org.eclipse.jdt.annotation.Nullable;
  22
  23 /**
  24  * A {@link JournalIndex} maintaining target density.
  25  */
  26 public final class SparseJournalIndex implements JournalIndex {
  27     private static final int MIN_DENSITY = 1000;
  28
  29     private final TreeMap<Long, Integer> positions = new TreeMap<>();
  30     private final int density;
  31
  32     // Last known position. May not be accurate immediately after a truncate() or construction
  33     private @Nullable Position last;
  34
  35     public SparseJournalIndex() {
  36         density = MIN_DENSITY;
  37     }
  38
  39     public SparseJournalIndex(final double density) {
  40         this.density = (int) Math.ceil(MIN_DENSITY / (density * MIN_DENSITY));
  41     }
  42
  43     @Override
  44     public Position index(final long index, final int position) {
  45         final var newLast = new Position(index, position);
  46         last = newLast;
  47         if (index % density == 0) {
  48             positions.put(index, position);
  49         }
  50         return newLast;
  51     }
  52
  53     @Override
  54     public Position last() {
  55         return last;
  56     }
  57
  58     @Override
  59     public Position lookup(final long index) {
  60         return Position.ofNullable(positions.floorEntry(index));
  61     }
  62
  63     @Override
  64     public Position truncate(final long index) {
  65         // Clear all indexes unto and including index, saving the first removed entry
  66         final var tailMap = positions.tailMap(index, true);
  67         final var firstRemoved = tailMap.firstEntry();
  68         tailMap.clear();
  69
  70         // Update last position to the last entry, but make sure to return a pointer to index if that is what we have
  71         // indexed.
  72         final var newLast = Position.ofNullable(positions.lastEntry());
  73         last = newLast;
  74         return firstRemoved != null && firstRemoved.getKey() == index ? new Position(firstRemoved) : newLast;
  75     }
  76
  77     @Override
  78     public String toString() {
  79         return MoreObjects.toStringHelper(this).add("positions", positions).toString();
  80     }
  81 }