Package io.deephaven.engine.table.impl.util

Class WritableRowRedirectionLockFree

java.lang.Object
io.deephaven.engine.table.impl.util.WritableRowRedirectionLockFree
All Implemented Interfaces:
ChunkSink<RowKeys>, ChunkSource<RowKeys>, ChunkSource.WithPrev<RowKeys>, FillContextMaker, GetContextMaker, DefaultChunkSource<RowKeys>, DefaultChunkSource.WithPrev<RowKeys>, FillUnordered<RowKeys>, RowRedirection, WritableRowRedirection
public class WritableRowRedirectionLockFree extends Object implements WritableRowRedirection
This is a lock-free implementation of a WritableRowRedirection. The rules for using this class are as follows. Users of this class fall into two roles: 1. Readers (snapshotters), of which there can be many. 2. Writers, of which there can be only one. Responsibilities of Readers: 1. Before you start, read the LogicalClock, note its value, and also note whether it is in the Idle or Update phase. 2. If you are in the "Idle" phase, then all your calls should be to get(). 3. If you are in the "Update" phase, then all your calls should be to getPrev(). 4. You must never call a mutating operation like put() or remove(). 5. When you are done reading all the data you wanted, read the LogicalClock again. If it has the same value (both generation and phase) as when you started, then you can rely on the data you have read. Otherwise, the data you have is garbage, and you need to throw it all away and try again at step 1. Responsibilities of the Writer: 1. There must be only one Writer. 2. The Writer controls the LogicalClock. Put another way, unlike the Reader, the Writer does not have to worry about a LogicalClock transition that would invalidate its work. 3. The Writer may call read operations (get() or getPrev()) at any time, i.e. regardless of phase (Idle or Update), and they will always provide valid data. 4. The Writer must only call mutating operations (like put() or remove()) during an Update phase. The Writer MUST NOT call these mutating operations during an Idle phase. 5. The Writer has no special responsibility when transitioning the LogicalClock from Idle to Update. 6. However, upon the transition from Update to Idle, the Writer does have an additional responsibility. Namely, the writer must first transition the LogicalClock (from Update generation N to Idle generation N+1), then call our method commitUpdates(). A logical place to do this might be the Terminal Listener. Rationale that this code implements correct lock-free behavior: Section I: The perspective of the Reader. There are three cases: 1. When the LogicalClock has been in the Idle phase for the entirety of "Reader Responsibilities" steps 1-5 above. 2. When it has been in the Update phase for the entirety. 3. When it started in one phase and ended in the other. We discuss these in reverse order. For #3, our only responsibility is to not crash, corrupt memory, or go into an infinite loop. The get() / getPrev() methods don't do any memory writes (so they can't corrupt memory). The argument that they can't crash or get into an infinite loop can only be made by looking at the code. I won't try to justify it here, but hopefully we can convince ourselves that this is so. For #2, the Reader is only calling getPrev(), which only accesses 'baseline'. The Writer's last write to 'baseline' happened before it set the logical clock to Update. LogicalClock being volatile means that these writes have been 'released'. Meanwhile, the Reader's first read to 'baseline' happens after it read the Update state from the LogicalClock (and therefore has 'acquire' semantics). #1 is the most complicated. For #1, the Reader is only calling get(), which accesses both 'baseline' and 'updates'. Importantly, it consults 'updates' first, and only accesses 'baseline' for keys that are not in 'updates'. The Writer's last write to 'updates' happened before it set the logical clock to Idle (thus these writes have been released). Meanwhile, the Reader's first read from 'updates' happens after it read the Idle state from the LogicalClock (and therefore has 'acquire' semantics). Calls to get(key) where key exists in the 'updates' map are thus correct. We now concern ourselves with calls to get(key) where key does not exist in 'updates'. The Writer spends the first part of the Idle cycle busily copying data from 'updates' back into 'baseline'. These updates have these properties: 1. It does not disturb entries whose keys are are not in 'updates'. 2. When it writes to the buckets in 'baseline' it changes key slots from either 'deletedSlot' or 'emptySlot' to some new key NEWKEY. We can argue that these writes do not affect the operation of the Reader, so it doesn't matter whether the Reader sees them or not: a) Importantly, the Reader is never looking for NEWKEY, because the Reader would have satisfied any search for NEWKEY from the 'updates' map, which it consulted first. b) If NEWKEY replaces a 'deletedSlot', then the Reader will skip over it as it does its probe. Because NEWKEY != key, the Reader's logic is the same whether it seems NEWKEY or deletedSlot. c) If NEWKEY replaces an 'emptySlot', then the Reader will probe further than it otherwise would have, but this search will be ultimately futile, because it will eventually reach an emptySlot. 3. When it is finally done copying values over, the Writer will write null to the keysAndValues array inside 'updates' (this is a volatile write). Writer's last write to 'baseline' happened before it wrote that null. When Reader consults 'updates' and finds a null there, it will also see all the writes made to 'baseline' (acquire semantics). 4. Writer may need to do a rehash. If it does, it will prepare the hashed array off to the side and then write it to 'baseline.keysAndValues' with a volatile write. When reader reads 'baseline.keysAndValues' (volatile read) it will either see the old array or the fully-populated new one. Section II: The perspective of the Writer: From the Writer's own perspective, the data structure is always coherent, because the Writer is the only one writing to it. The only considerations are the Writer's responsibilities to the Reader. They are outlined in the above section "Responsibilities of the Writer". The one thing that needs to be explained further is what happens in commitUpdates(). In commitUpdates() we iterate over the 'updates' hashtable and insert entries into the 'baseline' hashtable. If we need to rehash, we do so in a way that the Reader sees either the old buckets array or the new buckets array--we need to avoid the case where it sees some intermediate array which is only partially populated. To make this simple, we populate the new array off to the side and do a volatile write to store its reference. The Reader's next read of it is a volatile read, and it will pick it up then. When commitUpdates() is done, it writes a null to the 'updates.keysAndValues'. At this point all writes to the 'baseline' hashtable are finished as of the time of the write of the null. Next time the Reader reads this reference and finds it null, this will be an acquire and all the values in 'baseline' will be visible. That takes care of the transition from Update to Idle. Regarding the transition from Idle to Update, the caller does not have any special responsibility, but the first call to put() inside an Update generation causes a new 'keysAndValues' array to be generated, which the Reader will start to see next time it looks.

  • Method Details

    • get

      public final long get(long outerRowKey)
      Gets the current value. Works correctly for Readers@Idle and Writer@Update. Readers@Update should be calling getPrev(); meanwhile Writer@Idle shouldn't be calling anything. The only Reader@Update who calls this should be one where the clock transitioned from Idle to Update while they were already running. Such a Reader should, upon eventually noticing that this transition happened, throw away their work and start again.
      Specified by:
      get in interface RowRedirection
      Parameters:
      outerRowKey - The "outer" row key
      Returns:
      The corresponding "inner" row key, or RowSequence.NULL_ROW_KEY if no mapping exists

    • getPrev

      public final long getPrev(long outerRowKey)
      Gets the previous value. Works correctly for Readers@Update and Writer@Update. Readers@Idle should be calling get(); meanwhile Writer@Idle shouldn't be calling anything. The only Reader@Idle who calls this should be one who encountered a transition from Update to Idle while they were already running. Such a Reader should, upon eventually noticing that this transition happened, throw away their work and start again.
      Specified by:
      getPrev in interface RowRedirection
      Parameters:
      outerRowKey - The "outer" row key
      Returns:
      The corresponding "inner" row key, or RowSequence.NULL_ROW_KEY if no mapping exists

    • put

      public final long put(long outerRowKey, long innerRowKey)
      Puts a value. Works correctly for Writer@Update. Readers should never call this; Writers@Idle shouldn't be calling anything.
      Specified by:
      put in interface WritableRowRedirection
      Parameters:
      outerRowKey - The outer row key to map from
      innerRowKey - The inner row key to map to
      Returns:
      The inner row key previously mapped from outerRowKey, or RowSequence.NULL_ROW_KEY if there was no mapping

    • remove

      public long remove(long outerRowKey)
      Removes a key. Works correctly for Writer@Update. Readers should never call this; Writers@Idle shouldn't be calling anything.
      Specified by:
      remove in interface WritableRowRedirection
      Parameters:
      outerRowKey - The outer row key to unmap
      Returns:
      The inner row key previously mapped from outerRowKey, or RowSequence.NULL_ROW_KEY if there was no mapping

    • removeAll

      public void removeAll(RowSequence rowSequence)
      Description copied from interface: WritableRowRedirection
      Remove the specified rowSequence.
      Specified by:
      removeAll in interface WritableRowRedirection
      Parameters:
      rowSequence - The outer row keys to remove

    • removeAllUnordered

      public void removeAllUnordered(LongChunk<RowKeys> outerRowKeys)
      Description copied from interface: WritableRowRedirection
      Remove the specified outerRowKeys.
      Specified by:
      removeAllUnordered in interface WritableRowRedirection
      Parameters:
      outerRowKeys - The outer row keys to remove

    • startTrackingPrevValues

      public void startTrackingPrevValues()
      Description copied from interface: WritableRowRedirection
      Initiate previous value tracking.
      Specified by:
      startTrackingPrevValues in interface WritableRowRedirection

    • fillFromChunk

      public void fillFromChunk(@NotNull ChunkSink.FillFromContext context, @NotNull @NotNull Chunk<? extends RowKeys> innerRowKeys, @NotNull @NotNull RowSequence outerRowKeys)
      Description copied from interface: WritableRowRedirection
      Insert mappings from each element in a RowSequence to the parallel element in a LongChunk. h
      Specified by:
      fillFromChunk in interface ChunkSink<RowKeys>
      Specified by:
      fillFromChunk in interface WritableRowRedirection
      Parameters:
      context - THe FillFromContext
      innerRowKeys - The inner row keys to map to
      outerRowKeys - The outer row keys to map from

    • fillFromChunkUnordered

      public void fillFromChunkUnordered(@NotNull @NotNull ChunkSink.FillFromContext context, @NotNull @NotNull Chunk<? extends RowKeys> innerRowKeys, @NotNull @NotNull LongChunk<RowKeys> outerRowKeys)
      Description copied from interface: ChunkSink
      Fills the ChunkSink with data from the source, with data corresponding to the keys from the given key chunk.
      Specified by:
      fillFromChunkUnordered in interface ChunkSink<RowKeys>
      Specified by:
      fillFromChunkUnordered in interface WritableRowRedirection
      Parameters:
      context - A context containing all mutable/state related data used in writing the Chunk.
      innerRowKeys - The source of the data RowSequence
      outerRowKeys - A LongChunk representing the keys to be written