@UnstableApi public final class WeightedFairQueueByteDistributor extends java.lang.Object implements StreamByteDistributor
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.
Modifier and Type | Class and Description |
---|---|
private static class |
WeightedFairQueueByteDistributor.ParentChangedEvent
Allows a correlation to be made between a stream and its old parent before a parent change occurs.
|
private class |
WeightedFairQueueByteDistributor.State
The remote flow control state for a single stream.
|
private static class |
WeightedFairQueueByteDistributor.StateOnlyComparator
A comparator for
WeightedFairQueueByteDistributor.State which has no associated Http2Stream object. |
private static class |
WeightedFairQueueByteDistributor.StatePseudoTimeComparator |
StreamByteDistributor.StreamState, StreamByteDistributor.Writer
Modifier and Type | Field and Description |
---|---|
private int |
allocationQuantum
The minimum number of bytes that we will attempt to allocate to a stream.
|
private Http2Connection |
connection |
private WeightedFairQueueByteDistributor.State |
connectionState |
private static int |
DEFAULT_MAX_STATE_ONLY_SIZE
FireFox currently uses 5 streams to establish QoS classes.
|
(package private) static 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.
|
private int |
maxStateOnlySize |
private Http2Connection.PropertyKey |
stateKey |
private IntObjectMap<WeightedFairQueueByteDistributor.State> |
stateOnlyMap
If there is no Http2Stream object, but we still persist priority information then this is where the state will
reside.
|
private PriorityQueue<WeightedFairQueueByteDistributor.State> |
stateOnlyRemovalQueue
This queue will hold streams that are not active and provides the capability to retain priority for streams which
have no
Http2Stream object. |
Constructor and Description |
---|
WeightedFairQueueByteDistributor(Http2Connection connection) |
WeightedFairQueueByteDistributor(Http2Connection connection,
int maxStateOnlySize) |
Modifier and Type | Method and Description |
---|---|
void |
allocationQuantum(int allocationQuantum)
Sets the amount of bytes that will be allocated to each stream.
|
boolean |
distribute(int maxBytes,
StreamByteDistributor.Writer writer)
Distributes up to
maxBytes to those streams containing streamable bytes and
iterates across those streams to write the appropriate bytes. |
private int |
distribute(int maxBytes,
StreamByteDistributor.Writer writer,
WeightedFairQueueByteDistributor.State state) |
private int |
distributeToChildren(int maxBytes,
StreamByteDistributor.Writer writer,
WeightedFairQueueByteDistributor.State state)
It is a pre-condition that
state.poll() returns a non-null value. |
(package private) boolean |
isChild(int childId,
int parentId,
short weight)
For testing only!
|
(package private) void |
notifyParentChanged(java.util.List<WeightedFairQueueByteDistributor.ParentChangedEvent> events)
Notify all listeners of the priority tree change events (in ascending order)
|
(package private) int |
numChildren(int streamId)
For testing only!
|
private WeightedFairQueueByteDistributor.State |
state(Http2Stream stream) |
private WeightedFairQueueByteDistributor.State |
state(int streamId) |
(package private) int |
streamableBytes0(Http2Stream stream)
For testing only!
|
void |
updateDependencyTree(int childStreamId,
int parentStreamId,
short weight,
boolean exclusive)
Explicitly update the dependency tree.
|
void |
updateStreamableBytes(StreamByteDistributor.StreamState state)
Called when the streamable bytes for a stream has changed.
|
static final int INITIAL_CHILDREN_MAP_SIZE
private static final int DEFAULT_MAX_STATE_ONLY_SIZE
private final Http2Connection.PropertyKey stateKey
private final IntObjectMap<WeightedFairQueueByteDistributor.State> stateOnlyMap
private final PriorityQueue<WeightedFairQueueByteDistributor.State> stateOnlyRemovalQueue
Http2Stream
object. See WeightedFairQueueByteDistributor.StateOnlyComparator
for the priority comparator.private final Http2Connection connection
private final WeightedFairQueueByteDistributor.State connectionState
private int allocationQuantum
private final int maxStateOnlySize
public WeightedFairQueueByteDistributor(Http2Connection connection)
public WeightedFairQueueByteDistributor(Http2Connection connection, int maxStateOnlySize)
public void updateStreamableBytes(StreamByteDistributor.StreamState state)
StreamByteDistributor
updateStreamableBytes
in interface StreamByteDistributor
public void updateDependencyTree(int childStreamId, int parentStreamId, short weight, boolean exclusive)
StreamByteDistributor
updateDependencyTree
in interface StreamByteDistributor
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
.public boolean distribute(int maxBytes, StreamByteDistributor.Writer writer) throws Http2Exception
StreamByteDistributor
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)
.
distribute
in interface StreamByteDistributor
maxBytes
- the maximum number of bytes to write.true
if there are still streamable bytes that have not yet been written,
otherwise false
.Http2Exception
- If an internal exception occurs and internal connection state would otherwise be
corrupted.public void allocationQuantum(int allocationQuantum)
allocationQuantum
- the amount of bytes that will be allocated to each stream. Must be > 0.private int distribute(int maxBytes, StreamByteDistributor.Writer writer, WeightedFairQueueByteDistributor.State state) throws Http2Exception
Http2Exception
private int distributeToChildren(int maxBytes, StreamByteDistributor.Writer writer, WeightedFairQueueByteDistributor.State state) throws Http2Exception
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:
Http2Exception
private WeightedFairQueueByteDistributor.State state(Http2Stream stream)
private WeightedFairQueueByteDistributor.State state(int streamId)
int streamableBytes0(Http2Stream stream)
boolean isChild(int childId, int parentId, short weight)
int numChildren(int streamId)
void notifyParentChanged(java.util.List<WeightedFairQueueByteDistributor.ParentChangedEvent> events)
events
- The events (top down order) which have changed