Priority: A pure-Python HTTP/2 Priority implementation¶
Priority is a pure-Python implementation of the priority logic for HTTP/2, set out in RFC 7540 Section 5.3 (Stream Priority). This logic allows for clients to express a preference for how the server allocates its (limited) resources to the many outstanding HTTP requests that may be running over a single HTTP/2 connection.
Specifically, this Python implementation uses a variant of the implementation used in the excellent H2O project. This original implementation is also the inspiration for nghttp2’s priority implementation, and generally produces a very clean and even priority stream. The only notable changes from H2O’s implementation are small modifications to allow the priority implementation to work cleanly as a separate implementation, rather than being embedded in a HTTP/2 stack directly.
Contents:
Installation¶
Priority is a pure-Python project. This means installing it is extremely simple. To get the latest release from PyPI, simply run:
$ pip install priority
Using Priority¶
Priority has a simple API. Streams are inserted into the tree: when they are
inserted, they may optionally have a weight, depend on another stream, or
become an exclusive dependent of another stream. To manipulate the tree, we
use a PriorityTree
object.
>>> p = priority.PriorityTree()
>>> p.insert_stream(stream_id=1)
>>> p.insert_stream(stream_id=3)
>>> p.insert_stream(stream_id=5, depends_on=1)
>>> p.insert_stream(stream_id=7, weight=32)
>>> p.insert_stream(stream_id=9, depends_on=7, weight=8)
>>> p.insert_stream(stream_id=11, depends_on=7, exclusive=True)
Once streams are inserted, the stream priorities can be requested. This allows the server to make decisions about how to allocate resources.
Iterating The Tree¶
The tree in this algorithm acts as a gate. Its goal is to allow one stream “through” at a time, in such a manner that all the active streams are served as evenly as possible in proportion to their weights.
This is handled in Priority by iterating over the tree. The tree itself is an iterator, and each time it is advanced it will yield a stream ID. This is the ID of the stream that should next send data.
This looks like this:
>>> for stream_id in p:
... send_data(stream_id)
If each stream only sends when it is ‘ungated’ by this mechanism, the server will automatically be emitting stream data in conformance to RFC 7540.
Updating The Tree¶
If for any reason a stream is unable to proceed (for example, it is blocked on
HTTP/2 flow control, or it is waiting for more data from another service), that
stream is blocked. The PriorityTree
should
be informed that the stream is blocked so that other dependent streams get a
chance to proceed. This can be done by calling the
block
method of the tree with the stream
ID that is currently unable to proceed. This will automatically update the
tree, and it will adjust on the fly to correctly allow any streams that were
dependent on the blocked one to progress.
For example:
>>> for stream_id in p:
... send_data(stream_id)
... if blocked(stream_id):
... p.block(stream_id)
When a stream goes from being blocked to being unblocked, call the
unblock
method to place it back into
the sequence. Both the block
and
unblock
methods are idempotent and safe
to call repeatedly.
Additionally, the priority of a stream may change. When it does, the
reprioritize
method can be used to
update the tree in the wake of that change.
reprioritize
has the same
signature as insert_stream
, but
applies only to streams already in the tree.
Removing Streams¶
A stream can be entirely removed from the tree by calling
remove_stream
. Note that this is
not idempotent. Further, calling
remove_stream
and then re-adding
it may cause a substantial change in the shape of the priority tree, and
will cause the iteration order to change.
Priority API¶
Priority Tree¶
-
class
priority.
PriorityTree
(maximum_streams: int = 1000)[source]¶ A HTTP/2 Priority Tree.
This tree stores HTTP/2 streams according to their HTTP/2 priorities.
Changed in version 1.2.0: Added
maximum_streams
keyword argument.Parameters: maximum_streams ( int
) –The maximum number of streams that may be active in the priority tree at any one time. If this number is exceeded, the priority tree will raise a
TooManyStreamsError
and will refuse to insert the stream.This parameter exists to defend against the possibility of DoS attack by attempting to overfill the priority tree. If any endpoint is attempting to manage the priority of this many streams at once it is probably trying to screw with you, so it is sensible to simply refuse to play ball at that point.
While we allow the user to configure this, we don’t really expect them too, unless they want to be even more conservative than we are by default.
-
block
(stream_id: int) → None[source]¶ Marks a given stream as blocked, with no data to send.
Parameters: stream_id – The ID of the stream to block.
-
insert_stream
(stream_id: int, depends_on: Optional[int] = None, weight: int = 16, exclusive: bool = False) → None[source]¶ Insert a stream into the tree.
Parameters: - stream_id – The stream ID of the stream being inserted.
- depends_on – (optional) The ID of the stream that the new stream depends on, if any.
- weight – (optional) The weight to give the new stream. Defaults to 16.
- exclusive – (optional) Whether this new stream should be an exclusive dependency of the parent.
-
remove_stream
(stream_id: int) → None[source]¶ Removes a stream from the priority tree.
Parameters: stream_id – The ID of the stream to remove.
-
reprioritize
(stream_id: int, depends_on: Optional[int] = None, weight: int = 16, exclusive: bool = False) → None[source]¶ Update the priority status of a stream already in the tree.
Parameters: - stream_id – The stream ID of the stream being updated.
- depends_on – (optional) The ID of the stream that the stream now
depends on. If
None
, will be moved to depend on stream 0. - weight – (optional) The new weight to give the stream. Defaults to 16.
- exclusive – (optional) Whether this stream should now be an exclusive dependency of the new parent.
-
Exceptions¶
-
class
priority.
DeadlockError
[source]¶ Raised when there are no streams that can make progress: all streams are blocked.
-
class
priority.
PriorityLoop
[source]¶ An unexpected priority loop has been detected. The tree is invalid.
-
class
priority.
DuplicateStreamError
[source]¶ An attempt was made to insert a stream that already exists.
-
class
priority.
MissingStreamError
[source]¶ An operation was attempted on a stream that is not present in the tree.
-
class
priority.
TooManyStreamsError
[source]¶ An attempt was made to insert a dangerous number of streams into the priority tree at the same time.
New in version 1.2.0.
Vulnerability Notifications¶
This section of the page contains all known vulnerabilities in the priority library. These vulnerabilities have all been reported to us via our vulnerability disclosure policy.
Known Vulnerabilities¶
# | Vulnerability | Date Announced | First Version | Last Version | CVE |
---|---|---|---|---|---|
1 | DoS via unlimited stream insertion. | 2016-08-04 | 1.0.0 | 1.1.1 | CVE-2016-6580 |
License¶
Copyright (c) 2015 Cory Benfield
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Contributors¶
Priority is written and maintained by Cory Benfield and various contributors:
Development Lead¶
- Cory Benfield <cory@lukasa.co.uk>
Contributors¶
In chronological order: