Class WeightedFairQueueByteDistributor

  • All Implemented Interfaces:
    StreamByteDistributor

    @UnstableApi
    public final class WeightedFairQueueByteDistributor
    extends java.lang.Object
    implements StreamByteDistributor
    A StreamByteDistributor that is sensitive to stream priority and uses Weighted Fair Queueing approach for distributing bytes.

    Inspiration for this distributor was taken from Linux's Completely Fair Scheduler to model the distribution of bytes to simulate an "ideal multi-tasking CPU", but in this case we are simulating an "ideal multi-tasking NIC".

    Each write operation will use the allocationQuantum(int) to know how many more bytes should be allocated relative to the next stream which wants to write. This is to balance fairness while also considering goodput.

    • Field Detail

      • INITIAL_CHILDREN_MAP_SIZE

        static final int INITIAL_CHILDREN_MAP_SIZE
        The initial size of the children map is chosen to be conservative on initial memory allocations under the assumption that most streams will have a small number of children. This choice may be sub-optimal if when children are present there are many children (i.e. a web page which has many dependencies to load). Visible only for testing!
      • DEFAULT_MAX_STATE_ONLY_SIZE

        private static final int DEFAULT_MAX_STATE_ONLY_SIZE
        FireFox currently uses 5 streams to establish QoS classes.
        See Also:
        Constant Field Values
      • allocationQuantum

        private int allocationQuantum
        The minimum number of bytes that we will attempt to allocate to a stream. This is to help improve goodput on a per-stream basis.
      • maxStateOnlySize

        private final int maxStateOnlySize
    • Constructor Detail

      • WeightedFairQueueByteDistributor

        public WeightedFairQueueByteDistributor​(Http2Connection connection)
      • WeightedFairQueueByteDistributor

        public WeightedFairQueueByteDistributor​(Http2Connection connection,
                                                int maxStateOnlySize)
    • Method Detail

      • updateDependencyTree

        public void updateDependencyTree​(int childStreamId,
                                         int parentStreamId,
                                         short weight,
                                         boolean exclusive)
        Description copied from interface: StreamByteDistributor
        Explicitly update the dependency tree. This method is called independently of stream state changes.
        Specified by:
        updateDependencyTree in interface StreamByteDistributor
        Parameters:
        childStreamId - The stream identifier associated with the child stream.
        parentStreamId - The stream identifier associated with the parent stream. May be 0, to make childStreamId and immediate child of the connection.
        weight - The weight which is used relative to other child streams for parentStreamId. This value must be between 1 and 256 (inclusive).
        exclusive - If childStreamId should be the exclusive dependency of parentStreamId.
      • distribute

        public boolean distribute​(int maxBytes,
                                  StreamByteDistributor.Writer writer)
                           throws Http2Exception
        Description copied from interface: StreamByteDistributor
        Distributes up to maxBytes to those streams containing streamable bytes and iterates across those streams to write the appropriate bytes. Criteria for traversing streams is undefined and it is up to the implementation to determine when to stop at a given stream.

        The streamable bytes are not automatically updated by calling this method. It is up to the caller to indicate the number of bytes streamable after the write by calling StreamByteDistributor.updateStreamableBytes(StreamState).

        Specified by:
        distribute in interface StreamByteDistributor
        Parameters:
        maxBytes - the maximum number of bytes to write.
        Returns:
        true if there are still streamable bytes that have not yet been written, otherwise false.
        Throws:
        Http2Exception - If an internal exception occurs and internal connection state would otherwise be corrupted.
      • allocationQuantum

        public void allocationQuantum​(int allocationQuantum)
        Sets the amount of bytes that will be allocated to each stream. Defaults to 1KiB.
        Parameters:
        allocationQuantum - the amount of bytes that will be allocated to each stream. Must be > 0.
      • distributeToChildren

        private int distributeToChildren​(int maxBytes,
                                         StreamByteDistributor.Writer writer,
                                         WeightedFairQueueByteDistributor.State state)
                                  throws Http2Exception
        It is a pre-condition that state.poll() returns a non-null value. This is a result of the way the allocation algorithm is structured and can be explained in the following cases:

        For the recursive case

        If a stream has no children (in the allocation tree) than that node must be active or it will not be in the allocation tree. If a node is active then it will not delegate to children and recursion ends.

        For the initial case

        We check connectionState.activeCountForTree == 0 before any allocation is done. So if the connection stream has no active children we don't get into this method.
        Throws:
        Http2Exception
      • isChild

        boolean isChild​(int childId,
                        int parentId,
                        short weight)
        For testing only!
      • numChildren

        int numChildren​(int streamId)
        For testing only!
      • notifyParentChanged

        void notifyParentChanged​(java.util.List<WeightedFairQueueByteDistributor.ParentChangedEvent> events)
        Notify all listeners of the priority tree change events (in ascending order)
        Parameters:
        events - The events (top down order) which have changed