Package com.bytedesk.core.uid.buffer

Class RingBuffer

java.lang.Object
com.bytedesk.core.uid.buffer.RingBuffer
public class RingBuffer extends Object
Represents a ring buffer based on array.
Using array could improve read element performance due to the CUP cache line. To prevent the side effect of False Sharing, PaddedAtomicLong is using on 'tail' and 'cursor'

A ring buffer is consisted of:

  • slots: each element of the array is a slot, which is be set with a UID
  • flags: flag array corresponding the same index with the slots, indicates whether can take or put slot
  • tail: a sequence of the max slot position to produce
  • cursor: a sequence of the min slot position to consume
    • Author:
    yutianbao

    • Field Details

      • LOGGER

        private static final org.slf4j.Logger LOGGER

      • START_POINT

        private static final int START_POINT
        Constants
        See Also:

      • CAN_PUT_FLAG

        private static final long CAN_PUT_FLAG
        See Also:

      • CAN_TAKE_FLAG

        private static final long CAN_TAKE_FLAG
        See Also:

      • DEFAULT_PADDING_PERCENT

        public static final int DEFAULT_PADDING_PERCENT
        See Also:

      • bufferSize

        private final int bufferSize
        The size of RingBuffer's slots, each slot hold a UID

      • indexMask

        private final long indexMask

      • slots

        private final long[] slots

      • flags

        private final PaddedAtomicLong[] flags

      • tail

        private final AtomicLong tail
        Tail: last position sequence to produce

      • cursor

        private final AtomicLong cursor
        Cursor: current position sequence to consume

      • paddingThreshold

        private final int paddingThreshold
        Threshold for trigger padding buffer

      • rejectedPutHandler

        private RejectedPutBufferHandler rejectedPutHandler
        Reject put/take buffer handle policy

      • rejectedTakeHandler

        private RejectedTakeBufferHandler rejectedTakeHandler

      • bufferPaddingExecutor

        private BufferPaddingExecutor bufferPaddingExecutor
        Executor of padding buffer

    • Constructor Details

      • RingBuffer

        public RingBuffer(int bufferSize)
        Constructor with buffer size, paddingFactor default as 50
        Parameters:
        bufferSize - must be positive & a power of 2

      • RingBuffer

        public RingBuffer(int bufferSize, int paddingFactor)
        Constructor with buffer size and padding factor
        Parameters:
        bufferSize - must be positive and a power of 2
        paddingFactor - percent in (0, 100), padding buffer when tail-cursor < threshold

    • Method Details

      • put

        public boolean put(long uid)
        Put an UID in the ring and tail moved
        We use 'synchronized' to guarantee the UID fill in slot and publish new tail sequence as atomic operations
        Note that: It is recommended to put UID in a serialize way, cause we once batch generate a series UIDs and put the one by one into the buffer, so it is unnecessary put in multi-threads
        Parameters:
        uid -
        Returns:
        false means that the buffer is full, apply RejectedPutBufferHandler

      • take

        public long take()
        Take an UID of the ring at the next cursor, this is a lock free operation by using atomic cursor

        Before getting the UID, we also check whether reach the padding threshold, the padding buffer operation will be triggered in another thread
        If there is no more available UID to be taken, the specified RejectedTakeBufferHandler will be applied

        Returns:
        UID
        Throws:
        IllegalStateException - if the cursor moved back

      • calSlotIndex

        protected int calSlotIndex(long sequence)
        Calculate slot index with the slot sequence (sequence % bufferSize)

      • discardPutBuffer

        protected void discardPutBuffer(RingBuffer ringBuffer, long uid)
        Discard policy for RejectedPutBufferHandler, we just do logging

      • exceptionRejectedTakeBuffer

        protected void exceptionRejectedTakeBuffer(RingBuffer ringBuffer)
        Policy for RejectedTakeBufferHandler, throws RuntimeException after logging

      • initFlags

        private PaddedAtomicLong[] initFlags(int bufferSize)
        Initialize flags as CAN_PUT_FLAG

      • getTail

        public long getTail()
        Getters

      • getCursor

        public long getCursor()

      • getBufferSize

        public int getBufferSize()

      • setBufferPaddingExecutor

        public void setBufferPaddingExecutor(BufferPaddingExecutor bufferPaddingExecutor)
        Setters

      • setRejectedPutHandler

        public void setRejectedPutHandler(RejectedPutBufferHandler rejectedPutHandler)

      • setRejectedTakeHandler

        public void setRejectedTakeHandler(RejectedTakeBufferHandler rejectedTakeHandler)

      • toString

        public String toString()
        Overrides:
        toString in class Object