Package com.apple.foundationdb.async

Class RangeSet

java.lang.Object
com.apple.foundationdb.async.RangeSet
@API(UNSTABLE) public class RangeSet extends Object
RangeSet supports efficient adding of ranges of keys into the database to support marking work done elsewhere as completed as well as checking if specific keys are already completed.

This is useful if one is going to be doing work that will carve out pieces from another subspace and work on those separately. The methods in here will allow for a (more-or-less) append only set that can be used to keep track of the progress that that job is making.

  • Field Details

    • UNLIMITED

      public static final int UNLIMITED
      Value indicating that there should be no limit. This should be passed to missingRanges to indicate that the read should not limit the number of results it returns.
      See Also:

  • Constructor Details

    • RangeSet

      public RangeSet(@Nonnull Subspace subspace)
      Creates a new RangeSet that will write its data to the given subspace provided. The contents of this subspace should either be empty or contain the data used by another RangeSet object.
      Parameters:
      subspace - the subspace in which to write data

  • Method Details

    • isFirstKey

      public static boolean isFirstKey(@Nonnull byte[] key)

    • isFinalKey

      public static boolean isFinalKey(@Nonnull byte[] key)

    • contains

      @Nonnull public CompletableFuture<Boolean> contains(@Nonnull TransactionContext tc, @Nonnull byte[] key)
      Determines if a single key is contained within the range set. If it is, this will return true, and if it is not, it will return false. In terms of isolation, this adds a read- conflict to the key corresponding to the key being checked but to nothing else even though it has to do a range read that might be larger. This means that updates to keys before this won't conflict unless they actually change whether this key is contained within the range set.
      Parameters:
      tc - transaction or database in which to run operation
      key - the key to check presence in set
      Returns:
      a future that contains whether some range in the set contains the key

    • insertRange

      @Nonnull public CompletableFuture<Boolean> insertRange(@Nonnull TransactionContext tc, @Nonnull Range r)
      Inserts a range into the set. This behaves the same way as the four-parameter version of RangeSet.insertRange (including conflict settings), but it gets its begin and end from the given Range object and assumes that requiresEmpty is false, i.e., it is okay for there already to be data within the given range.
      Parameters:
      tc - the transaction or database in which to operate
      r - the range to add to the set
      Returns:
      a future that is true if there were any modifications to the database and false otherwise

    • insertRange

      @Nonnull public CompletableFuture<Boolean> insertRange(@Nonnull TransactionContext tc, @Nonnull Range r, boolean requireEmpty)
      Inserts a range into the set. This behaves the same way as the four-parmater version of RangeSet.insertRange (including conflict settings), but it gets its begin and end from the given Range object.
      Parameters:
      tc - the transaction or database in which to operate
      r - the range to add to the set
      requireEmpty - whether this should only be added if this range is initally empty
      Returns:
      a future that is true if there were any modifications to the database and false otherwise

    • insertRange

      @Nonnull public CompletableFuture<Boolean> insertRange(@Nonnull TransactionContext tc, @Nullable byte[] begin, @Nullable byte[] end)
      Inserts a range into the set. This behaves the same way as the four-parameter version of RangeSet.insertRange (including conflict settings), but it assumes that requiresEmpty is false, i.e., it is okay for there already to be data within the given range.
      Parameters:
      tc - the transaction or database in which to operate
      begin - the (inclusive) beginning of the range to add
      end - the (exclusive) end of the range to add
      Returns:
      a future that is true if there were any modifications to the database and false otherwise

    • insertRange

      @Nonnull public CompletableFuture<Boolean> insertRange(@Nonnull TransactionContext tc, @Nullable byte[] begin, @Nullable byte[] end, boolean requireEmpty)
      Inserts a range into the set. The range inserted will begin at begin (inclusive) and end at end (exclusive). If the requireEmpty is set, then this will only actually change the database in the case that the range being added is not yet included in the set. If this flag is set to false, then this will "fill in the gaps" between ranges present so that the whole range is present following this transactions operation. The return value will (when ready) be equal to true if and only if there are changes (i.e., writes) to the database that need to be made, i.e., the range was not already included in the set. If the initial end point is less than the begin point, then this will throw an IllegalArgumentException indicating that one has passed an inverted range. If begin and end are equal, then this will immediately return a future that is set to false (corresponding to adding an empty range). If null is set for either endpoint, this will insert a range all the way to the end of the total range.

      In terms of isolation, this method will add both read- and write-conflict ranges. It adds a read-conflict range corresponding to the range being added, i.e., for the keys within the range from begin to end. This is so that if this range is modified concurrently by another writer, this transaction will fail (as the exact writes done depend on these keys not being modified.) It will also a write-conflict ranges corresponding to all of the individual ranges added to the database. That means that if the range is initially empty, a write-conflict range corresponding to the keys from begin to end. This is done so that if another transaction checks to see if a key in the range we are writing is within the range set and finds that it is not, this write will then cause that transaction to fail if it is committed after this one. If the range is not empty initially, write conflict ranges are added for all of the "gaps" that have to be added. (So, if the range is already full, then no write conflict ranges are added at all.)

      Parameters:
      tc - the transaction or database in which to operate
      begin - the (inclusive) beginning of the range to add
      end - the (exclusive) end of the range to add
      requireEmpty - whether this should only be added if this range is initially empty
      Returns:
      a future that is true if there were any modifications to the database and false otherwise

    • missingRanges

      @Nonnull public CompletableFuture<List<Range>> missingRanges(@Nonnull ReadTransactionContext tc)
      Returns all of the ranges that are missing within this set as list. See the three-parameter version of RangeSet.missingRanges for more details, but this will look from the beginning of the valid keys within this set to the end and find any gaps between ranges that need to be filled.
      Parameters:
      tc - transaction that will be used to access the database
      Returns:
      an iterable that will produce all of the missing ranges

    • missingRanges

      @Nonnull public AsyncIterable<Range> missingRanges(@Nonnull ReadTransaction tr)
      Returns all of the ranges that are missing within this set. See the three-parameter version of RangeSet.missingRanges for more details, but this will look from the beginning of the valid keys within this set to the end and find any gaps between ranges that need to be filled.
      Parameters:
      tr - transaction that will be used to access the database
      Returns:
      an iterable that will produce all of the missing ranges

    • missingRanges

      @Nonnull public CompletableFuture<List<Range>> missingRanges(@Nonnull ReadTransactionContext tc, @Nonnull Range superRange)
      Returns all of the ranges that are missing within a given range as a list. See the four-parameter version of RangeSet.missingRanges for more details, but this will look for ranges that aren't already within the set.
      Parameters:
      tc - transaction that will be used to access the database
      superRange - the range within to search for additional ranges
      Returns:
      an iterable that will produce all of the missing ranges

    • missingRanges

      @Nonnull public AsyncIterable<Range> missingRanges(@Nonnull ReadTransaction tr, @Nonnull Range superRange)
      Returns all of the ranges that are missing within a given range. See the four-parameter version of RangeSet.missingRanges for more details, but this will look for ranges that aren't already within the set.
      Parameters:
      tr - transaction that will be used to access the database
      superRange - the range within to search for additional ranges
      Returns:
      an iterable that will produce all of the missing ranges

    • missingRanges

      @Nonnull public CompletableFuture<List<Range>> missingRanges(@Nonnull ReadTransactionContext tc, @Nullable byte[] begin, @Nullable byte[] end)
      Returns all of the ranges that are missing within a given set of bounds as a list. See the four-parameter version of RangeSet.missingRanges for more details, but this will look for ranges that aren't already within the set.
      Parameters:
      tc - transaction that will be used to access the database
      begin - the beginning (inclusive) of the range to look for gaps
      end - the end (inclusive) of the range to look for gaps
      Returns:
      an iterable that will produce all of the missing ranges

    • missingRanges

      @Nonnull public AsyncIterable<Range> missingRanges(@Nonnull ReadTransaction tr, @Nullable byte[] begin, @Nullable byte[] end)
      Returns all of the ranges that are missing within a given set of bounds as a list. See the four-parameter version of RangeSet.missingRanges for more details, but this will look for ranges that aren't already within the set. It will not limit the number of results that it will return.
      Parameters:
      tr - transaction that will be used to access the database
      begin - the beginning (inclusive) of the range to look for gaps
      end - the end (inclusive) of the range to look for gaps
      Returns:
      an iterable that will produce all of the missing ranges

    • missingRanges

      @Nonnull public CompletableFuture<List<Range>> missingRanges(@Nonnull ReadTransactionContext tc, @Nullable byte[] begin, @Nullable byte[] end, int limit)
      Returns all of the ranges that are missing within a given set of bounds as a list. See the four-parameter version of RangeSet.missingRanges for more details, but this will look for ranges that aren't already within the set. It will not limit the number of results that it will return.
      Parameters:
      tc - transaction that will be used to access the database
      begin - the beginning (inclusive) of the range to look for gaps
      end - the end (inclusive) of the range to look for gaps
      limit - the maximum number of results to return
      Returns:
      an iterable that will produce all of the missing ranges

    • missingRanges

      @Nonnull public AsyncIterable<Range> missingRanges(@Nonnull ReadTransaction tr, @Nullable byte[] begin, @Nullable byte[] end, int limit)
      Returns all of the ranges that are missing within a given set of bounds. In particular, this will look for "gaps" in the key-value pairs between begin (inclusive) and end (exclusive) so that at the end, we know what is missing. This takes in a read transaction (which could, theoretically, be a snapshot read if we so desired). If this transaction is committed before the iterator is cancelled or completes, this can cause problems.
      Parameters:
      tr - transaction that will be used to access the database
      begin - the beginning (inclusive) of the range to look for gaps
      end - the end (inclusive) of the range to look for gaps
      limit - the maximum number of results to return
      Returns:
      an iterable that will produce all of the missing ranges

    • isEmpty

      public CompletableFuture<Boolean> isEmpty(@Nonnull ReadTransactionContext rtc)
      Determine whether this range set is empty. If given a Database, this will create a transaction and use it to read from the database. If given a ReadTransaction, it will use the provided transaction. See isEmpty(ReadTransaction) for more details on the semantics of this function.
      Parameters:
      rtc - transaction or database object that will be used to read from the database
      Returns:
      a future that will contain true if there are no ranges in this set or false otherwise
      See Also:

    • isEmpty

      public CompletableFuture<Boolean> isEmpty(@Nonnull ReadTransaction rtr)
      Determine whether this range set is empty. This will scan the given range set and return true if no ranges have been inserted into the data structure. Otherwise, it will return false.
      Parameters:
      rtr - transaction that will be used to read from the database
      Returns:
      a future that will contain true if there are no ranges in this set or false otherwise

    • clear

      public void clear(@Nonnull Transaction tr)
      Clears the subspace used by this RangeSet instance. This will remove all ranges from this set.
      Parameters:
      tr - transaction with which to run the operation

    • clear

      @Nonnull public CompletableFuture<Void> clear(@Nonnull TransactionContext tc)
      Clears the subspace used by this RangeSet instance. This will remove all ranges from this set.
      Parameters:
      tc - transaction or database in which to run operation
      Returns:
      a future that is completed when the range has been cleared

    • rep

      @Nonnull public CompletableFuture<String> rep(@Nonnull ReadTransactionContext tc)