Everyone, my name is Alexander Krzanovski, and I'll be speaking on my colleague, Evgeny
Michanik, who made the most part of the work, which I will talk about.
Also, today, Robin Marks, say about cloning on server side, so I'm exactly from a web server,
development site in Particle HPP-Poxia, so I'll be also talking about how cloning happens
from HPP-Poxia site, and Particle In HP streams.
To talk about HP streams, I would love to use for the website in page test resources,
and I already made the prepaid report for the website, this LCP, I will talk more about
HPP in terms of HP streams, and this, if we click on, well, yeah, let me check the connection.
Thank you very much.
Okay, so we finally have internet.
Let's try again.
Yeah, yeah, here we go.
So, this LCP is good, and we, on this graph, we have a LCP-edged green line, about three seconds.
The thing is that if we check the protocol for ZEM with HP2, and with this protocol, we have single
CP connection, single CP, TOS connection inside, and we have a bunch of HP streams, each delivering
a separate VB source, and this depends on C-B between the streams, and priority.
So, to check the dependency, let's click on dependency graph, and have a go.
So, in this called dependency stream, and in Particle, this is not zero, which is a point note,
and there are lists of HP streams.
So, those three streams are dependent on each other.
Other streams like 11 and 15, siblings in dependency 3, and that means that they share bandwidth.
Let's back to the start, and we also have priority, it's a weight for the stream.
If we have a look on this values, this one, 47 weight, and another 220.
So, fast to good.
We had HP streams scheduling for a while, and in late 23, we started to optimize our stream schedule
to get more performance for web clients.
And at the time, the topic was well started, the good papers from Robin Marks about HP streams,
operations scheduling, and concerns, so this is a very well started topic.
And the more important thing is that the two FC1 is 75, 40, which is considered outdated,
and represented by 9218.
However, by late 23, it was more than one year, like in Particle 1, year, and half since 1992, 18 was published.
So, it appeared for us that nobody used the new standard for HP2.
Instead, everyone used it 75, 40, all standard for HP2, and the newer FC is used only for HP3.
We had a lot of discussions internally, whether we need to see on-premise those standard,
while the new one, which replaced the old one, but also in-premise stations used those standard.
So, we said, okay, a punty nobody cares about HP2, quite a few HP2, so we had to implement 75, 40.
We'll back to this topic later, but for now, let's consider what's the difference between the standard.
The first and main difference in our, in the stock, it's a dependent CDM.
So, 75, 40 is about dependents 3. We saw it on web page, test 4 for DMs, there's another example for much deeper dependency 3.
And there are also some differences between weights and audency. For example, in 75, 40 we have weights, 3 in 90 to 18, we have audency, we can use bit difference, but for now we can ignore the differences.
As this representation, we'll have a look on it on the next slide, there are two slides, we also added them.
Later, but this interesting point about the out of priority, this one, things which could be named as a cloning.
In particular, if we back to our example, here we see that a bunch of PNG resources can schedule more or less in parallel.
But, intermediate reproxy, for example, your CDN can receive requests simultaneously.
And storage can schedule the request to different upstream service, depends on installation.
And different upstream service can require different times.
So, technically, you can receive response for less prioritized requests earlier.
And at this point, intermediate reproxy must consider what to do, whether to be a WFC component and passport, sending a full priority resource until higher priority resource is received.
Or just send everything as it receives.
Surely most of the implementation sent a slightly as possible to not introduce artificial delays.
It's like, not the WFC component, but this proves performance.
Next about repatriation, it's happens on both the standards, in both the standards, it's about way changes or audency changes like priorities.
And the next one is about dependency reconstruction.
On this figure, we see that stream A becomes dependent on its grandson G.
So, we need to rebuild dependent C3 and place G on top of A.
And we have two cases.
The first one is that stream A is non-exclusive.
It means that it can share bandwidth with other streams as we solve for PNG resources.
In this case, we just replace CA chart with P basically construction.
However, if A stream is exclusive, it means that it cannot share bandwidth.
It doesn't allow any siblings in dependent C3.
And in this case, the sibling F was a SA chart.
So, as we see, in this simple example, we see that the three operations is quite complex.
So, if you try to program this, you have non-drivaled three operations, right?
Let's have a look at how five folks generates the HP streams.
The first interesting thing is that, for you folks, like you see, the groups of paired ones on the side.
And the first line is creating either stream without no weight.
Without dependency without nothing, it's just either stream.
And next claim is sent to point out the exact properties for the stream in particular weight.
Dependency and x-visual.
In this slide, this trace we received on TMPW site.
And when five folks is used to browse some resources.
And with this case, we see what five folks really sends to WebExivator.
However, if we back to web page test, for example, considering resources, it's marked as exclusive.
But regardless of which resources we're going to observe, it will be have exclusive folks set.
I have no idea which folks version of the page test used, which engine bought, this is what we have.
The next thing is that both the streams, 15 and 11, which actually share bandwidths.
Now, mark it as exclusive. So let's find the streams, this is 11, it's exclusive.
And each 15 is also exclusive.
So apparently, Web page test builds depending on the cigar in non-of-shek and point weight.
I believe it doesn't use any, I mean, the five folks sent it, so everything should be good.
But, unfortunately, depends on C3, it has some internal bugs.
So by all the streams, it cannot share bandwidths.
They actually depend on each other.
Next thing is that if we build the same dependency for home browser, we clearly see that in home, we see just a clear dependency.
There's no bandwidth sharing between each stream, so to all.
The same for other browsers, why cage and so on.
And even for five folks, it's not clear what actually five folks doesn't expect, but actually we have a clear dependency.
So technically, it means that even for 75, 40, we don't have any bandwidth sharing, or at least we should not have.
And there are actually not so many cases when we do need bandwidth sharing.
One of the case could be progressive gpx.
Another case is five folks' case.
It's unclear what five folks does, what to expect.
And the next one is NGHDP2 library, and in particular two lot benchmark, which remains hp2 benchmark.
And it does use bandwidth sharing in created stream.
So technically, it's a rich, free space for the web API, which might benefit from bandwidth sharing.
Probably everyone can imagine situation, you can benefit from bandwidth sharing.
So we decided still to implement bandwidth sharing in a proper way.
A couple of words about progressive gpx, we made the research.
If anyone has feedback about this, I would love to know about web performance,
Devroom, but from our research, it seems that nobody uses progressive gpx nowadays.
And even resources, which are expected to use a lot of images, which must be shown very quickly, do not use progressive gpx.
And the set would typically VP, or some optimization techniques are used to get good performance for web pages.
That's back to bandwidth sharing for free folks again.
So as we saw that free folks actually don't use excessive.
At least now, it raises which we explore several versions of Firefox.
There were no excessive fog set by Firefox.
And from web page test, we actually see that, well, in this web page test, we see that most of the transfers,
like the PNG connections were initiated simultaneously, but transfers happen more less in different times.
Maybe, except, exceptions only, there was a bias, for example, for stream 5 and stream 5.
So we see that there are some like this, and that seems that parallel bandwidth transfers.
But this also received four Firefox days, and here we see that there are clear bandwidth sharing four Firefox.
And basically, this very bad technique to achieve bad performance.
So the first image, like technologistslogger.png, this green line, by 91 milliseconds, this apparently image crucial for LCP.
And the image sharing bandwidth with other images, and we should not have been sharing bandwidth to improve our VCP.
So more beneficial to firstly deliver first crucial image, and don't have to that in shape as the transfers.
Not only that, but actually for the second image.
It also not wise to share bandwidth with other different images, because we see it's png.
Images not progress with GPEX, so user don't see any progress until images start to finish downloading.
For a long time, user will see just a blank page without anything.
And basically, this, but the sharing is not good for, like, with comparison symbol on the web.
Another interesting thing about Firefox, and unique thing, is that Firefox builds a lot of idle streams, which are just placeholders in.
So in this picture, streams 13, 35, 7, all the top-level streams are just placeholders.
They never transfer any data, and the user just placeholders in dependency 3.
Now, as a browser has this feature, and this unique for Firefox, and this just a plantation feature.
And for sure, for folks sense a lot of representation frames.
Let's summarize difference between the two standards.
So, 7540 is outdated, replaced by 9218.
For a while, it appears that nobody uses it for HP2.
9218 is quite more attractive for developers, because it's simple.
There's no sophisticated three operations for dependency 3.
It's much simpler, and it's newer.
So, technically, we should have June 1918.
So, there were a lot of available open-source implementations.
So, we started to investigate several of them with all compatible items.
And first was an engineer.
So, there's some technical techniques, and due to this technical and better CPU utilization.
They create memory usage, so every stream, create a stream.
Has we had more than one keyword by two data, just to schedule streams and find was the next stream we'll be scheduled.
Another thing is that they use only 64 different groups.
While we have 256 actual stream spirities, so there's some inaccuracies in the algorithm.
We made a simple Python script, which compares the algorithm with ideal.
Weighted for a queueing can be found that sometimes it's not a theoretical react.
Again, it's a theoretical react, not necessary on real work work.
So, we also move it to another implementations.
And just to be true, users are weighted for a queue, which is true for a queueing.
And basically, the performance in terms of quality of the scheduling is the best, because it's a natural weighted for a queueing, a queueerative program.
But we didn't like the implementation.
And it causes more data copies.
It keeps the scheduling covariance spirit of stream.
That's actually, so you have a stream.
So you have a helping data selection.
And CPU must access different memory reality.
It's not good for optimal CPU cache.
Since we do care about performance, we also need more efficient implementation.
So we wanted something class fast as H2A, but as good quality as NGHTP2.
We noticed that typically on the same dependency 3 level, we never have more than 100 streams.
So depends on 3 can be very large.
But on the same level, we never have a lot of streams.
Typically, we have only one stream, right?
Second, we noticed that the resource was frequent.
So when we make one of the stream, we need to reinforce the stream to depend on the C3, to recall it's weight.
So the first question was, which data structure we should use to keep streams and make weight-of-a-fail queue algorithm work.
We considered several data structures.
It's elastic binary trees, binary and fibonacci hips in such and such a way, like in H2A.
And we ended up with the elastic binary tree.
Let me talk more about this tree because it's very unique data structure.
It's not described at all.
Wikipedia.
The data structure is used by HAPOX, also for scheduling purposes.
It's invading by Willi Tareo, the original author of HAPOX.
And the unique feature of the tree is that it's essentially binary logic stream.
It means that if you have a large number, like 10 bits.
And each tree represents a zero or one.
And it means that in binary tree, on each level, you decide whether to go to the left branch,
like for zero bit or to the right for one bit one.
And this, so you can have a likelihood of 10.
But in case of elastic binary tree, you can pack the bits and not so many levels introduced.
The good thing about the binary tree is that it keeps all the nodes keeping data.
So it doesn't access different memory locality locations for CPUs.
So when you use the data structure to pick up next stream, the CPU accesses the memory location on the ones.
And, naturally, it's not balance it binary tree.
So it works very well for small data sets, not good for large data sets.
But since we have not so many streams on the same level, it works the best for us.
We made the Mikubinchmark for 100 elements.
Maybe three was, some were slow as an extra insertions.
But much faster than a heap implementation, like Fibonacci and binary heap.
So we choose an elastic binary tree.
So we finish it with data structure.
Let's move with algorithm for weighted firecure.
And Kazuhoko 10 years ago presented schedule algorithm for it to end one of them.
Weighted firecure is well-studied topic, and it's a pair of many applications,
even in the latest Linux kernel schedule, EVDF, also used weighted firecure.
There are different papers, different research articles, but most of them are about the same ideas,
why we have a deficit or a penalty, like a log in case of the Linux kernel schedule.
And the fire algorithms is very intuitive.
So on this case, we create a penalty.
So with penalty, we take a percent.
It's how much data was actually sent last time.
We multiplied from any constant.
In this case, it's 256.
You can choose any other constant, and this is some pending, graduated value.
And the next one, when we compute the cycle, this exactly was the next stream to be sent next.
As more cycle is, the latest stream will be sent.
So as a larger penalty, we have the weight that we are going to be sent.
As more weight the stream has, it's already going to be sent.
It's very intuitive.
And next, we use updated pending value.
It's just a residual of penalties.
So for cycle, we use penalty by division, and for a graduated value,
the pending query have a residual value.
This example of only two streams, A and B, with Pyreaches 10 and 5.
Pay attention that A and B sends data with different chunks.
First sends 100, third sent, 150, and the last transmission is 150.
So being sent with different chunks, we end up with transmission of the same amount.
And the algorithm starts to transmit A and B one after another.
So this is true for a queueing.
So both the streams start to be transmitted from the first transmission.
The key difference between this algorithms, also used in GSTP2.
And H2 is that H2 ignores data sent.
So it only uses sends frames, and as much data as you have,
can be sent by a stream according to the schedule.
So it's just about ordering.
So you can imagine that in this case, we have a streams A and B.
B is double less Pyreaches than A.
But suppose that B sends one iteration 10 times more data than A.
So in this algorithm, B will be consuming five times more bandwidth than A.
B is still less Pyreaches.
So it's also about a queueing of algorithm.
So in our case in GSTP2, we know how much data we sent.
We can just adjust the content.
Very little is this and this is about Pyreaches.
So it was like middle 24.
We implemented the new schedule, the very first schedule, very first schedule.
And Firefox and Home are also that they did move to 92.
18.
And with this standard, we found that we're not alone,
who didn't implement 92.
18.
So in GSTP2 supports this feature.
H2 doesn't support at all.
And the next supports it, but not in terms of 92.
18.
So a seven implementation, while browser started to use the feature.
Firefox 128 was the first version who started to use the feature by default.
126 and 127 were able to use 92.
18 if several are also the support.
But by default, they don't announce the feature.
So in terms of Firefox, Firefox behave just the same as previously.
But it adds settings, not if she is 75, 40,
means as streams in connection going to use the new conduct.
And also to the previous scheme, we as wait without either schemes.
It adds urgency and appreciation of luck.
So with this standard, we, if seven implementation is 75, 40,
compare and only, it can use wait and exit the fog.
If it's under sent 92, 18, that it can use urgency and increase the fog.
We, at the same time, we have failed logarithmic schedule.
We did a lot of optimizations on memory locations to improve CPU cage usage streams
player locations.
So if your webpage creates 10 streams, then the first 10 streams are nearly for free.
But others will involve more memory resources.
Also, if there are no any bandwidth sharing,
or any layer, we don't want any time on resource sharing, whatever.
And also by default, it's 92, 18, compared by in terms of wait.
And if you use progressive impacts or like web API,
which can benefit from bandwidth sharing, you can use a configuration option.
The next thing about impasse is that it's built into the links to your paper stack.
And essentially, HP layer is called by HP callback.
So on each iteration HP schedules, no precisely how much data HP is able to send.
It can reach the HP congestion window and then also the receive site window.
And form a TOS record and HP frame of optimal size for the current state on HP level.
The extensions for HP proxy for HP drawer and divine for engineers,
but they use poker first values, so it's asynchronous stuff.
And if you form TOS records non-optimal size,
it could be very crucial for latency.
With TOS records, we have a trailer, so each TOS records finishes with a trailer.
And trailer contains authentication data required to start the encryption of the record.
So for example, if your application server forms like 10 TOS records,
but HP is able to deliver only 1 KW,
then the head of TOS records is delivered to the client,
but the TOS records stays in the center buffer.
And receiver cannot start TOS decryption,
because it doesn't have TOS trailer.
And only when HP delivers the trailer,
the decryption process can start.
So with good knowledge about CP state, we can avoid such situation.
So that's the thing which I wanted to cover is security,
that's why a couple of security issues involving HP stream mechanisms.
The one is pretty old, like 10 years ago, about dependents C3,
so if your website implementation isn't a real component,
then a attacker can send built dependents C3
like when root node depends on the lift.
So we have a cycle in three,
and the schedule goes through the infinite loop trying to get the next stream.
The next one is about priority frame and the related vulnerability
like last year about control frames,
fluids that basically with priority frames,
we saw that priority frames involves the delivery construction,
relatively heavyweight operation,
so it's a good vector for DOS attack,
and sending a lot of priority frames,
and also other control frames could lead to DOS vulnerability.
Typically, this can be mitigated with limits like limiting
the maximum number of open HP streams.
I think all the implementation does this,
so you limit the size of dependents C3,
and essentially you get the most cheaper triaporation.
And also typically,
implementations limit number of control frames,
and that's so from our site,
we have a week here.
I discovered more about research in HP stream schedule
with a pattern code implementing H2O.
Algorithm, and that's the hypothesis and open source.
And finally, if you enjoy hacking Linux kernel code,
doing some sophisticated algorithm programming,
and so on, we definitely want to have from you,
so we're hiding.
So that's all.
I think we have some time for questions.
Yep.
Thank you for listening.
Questions?
So beyond what you presented the day for the algorithms,
is there anything else that, for example, for the H cases,
or for the frustrations where we have packet loss,
and data needs to be sent again on a stream.
Or is it outside of the scope, what you've got?
Yeah, I think it's outside of the scope,
because we do not emit CPU logic at all,
so we just work on CPU co-bets,
and we let CPU do its work.
So it's under the, yeah, yeah.
We do not emit CPU logic at all,
so we just work on CPU co-bets,
and we let CPU do its work,
so it's under the, yeah, yeah.
Yeah, it's a complete separate layer,
it's for any application service,
but we just call it by CPU co-bets,
so that's the difference.
Yeah, thank you for question.
No?
Okay, thank you.
Thank you.
Thank you so much.
Thank you.