vagababov commented 4 years ago

In what area(s)?

/area autoscale /kind proposal

Describe the feature

Currently when we compute average concurrency or average RPS over the stable window in the autoscaler we basically iterate the buckets and sum them. While the number of buckets is limited (60/2=30) by default, the stable window can be made quite large: hours, days... we don't have an upper limit right now (which might be another good issue)

While it is quite easy to improve to precompute current value and just update the stored counter.

total += t[now] - t[windowSecondsBefore]

This can be implemented with current map based solution for the buckets.

But here comes part II: we should use a fixed memory circular buffer to store the scrape/activator returned values, thus limiting GC work that has to be done and in addition keeping the whole data in array, rather than in a map permits for data locality further improving the performance.

this changes the formula above to

was = t[curIdx]
t[curIdx] = newVal
total += newVal - was

/cc @markusthoemmes

Feature track: https://docs.google.com/document/d/1lFown9jjBSOEBieSG3kGA8-1_tAgdDxQpeo-jtgXPCE/edit#heading=h.yhdv39zgzec6

From @markusthoemmes & @vagababov meeting in Düsseldorf

knative-prow-robot commented 4 years ago

@vagababov: The label(s) kind/proposal cannot be applied. These labels are supported: ``

In response to [this](https://github.com/knative/serving/issues/5981): > >## In what area(s)? > >/area autoscale >/kind proposal > >## Describe the feature > >Currently when we compute average concurrency or average RPS over the stable window in the autoscaler we basically iterate the buckets and sum them. >While the number of buckets is limited (60/2=30) by default, the stable window can be made quite large: hours, days... we don't have an upper limit right now (which might be another good issue) > >While it is quite easy to improve to precompute current value and just update the stored counter. > >`total += t[now] - t[windowSecondsBefore]` > >This can be implemented with current `map` based solution for the buckets. > >But here comes part II: we should use a fixed memory circular buffer to store the scrape/activator returned values, thus limiting GC work that has to be done and in addition keeping the whole data in array, rather than in a map permits for data locality further improving the performance. > >this changes the formula above to > >``` >was = t[curIdx] >t[curIdx] = newVal >total += newVal - was >``` > > Instructions for interacting with me using PR comments are available [here](https://git.k8s.io/community/contributors/guide/pull-requests.md). If you have questions or suggestions related to my behavior, please file an issue against the [kubernetes/test-infra](https://github.com/kubernetes/test-infra/issues/new?title=Prow%20issue:) repository.

knative-prow-robot commented 4 years ago

@vagababov: The label(s) kind/proposal cannot be applied. These labels are supported: ``

In response to [this](https://github.com/knative/serving/issues/5981): >## In what area(s)? > >/area autoscale >/kind proposal > >## Describe the feature > >Currently when we compute average concurrency or average RPS over the stable window in the autoscaler we basically iterate the buckets and sum them. >While the number of buckets is limited (60/2=30) by default, the stable window can be made quite large: hours, days... we don't have an upper limit right now (which might be another good issue) > >While it is quite easy to improve to precompute current value and just update the stored counter. > >`total += t[now] - t[windowSecondsBefore]` > >This can be implemented with current `map` based solution for the buckets. > >But here comes part II: we should use a fixed memory circular buffer to store the scrape/activator returned values, thus limiting GC work that has to be done and in addition keeping the whole data in array, rather than in a map permits for data locality further improving the performance. > >this changes the formula above to > >``` >was = t[curIdx] >t[curIdx] = newVal >total += newVal - was >``` > >/cc @markusthoemmes > >Feature track: https://docs.google.com/document/d/1lFown9jjBSOEBieSG3kGA8-1_tAgdDxQpeo-jtgXPCE/edit#heading=h.yhdv39zgzec6 > >From @markusthoemmes & @vagababov meeting in Düsseldorf > > Instructions for interacting with me using PR comments are available [here](https://git.k8s.io/community/contributors/guide/pull-requests.md). If you have questions or suggestions related to my behavior, please file an issue against the [kubernetes/test-infra](https://github.com/kubernetes/test-infra/issues/new?title=Prow%20issue:) repository.

mi-yu commented 4 years ago

Hi, I'm at student at UT Austin and am looking to contribute to container-related project as part of my virtualization course. I'm interested in picking this issue up, could I get assigned to this issue?

pyrito commented 4 years ago

Hi, I'm also apart of the same group for the project. Could I get assigned to this issue as well?

vagababov commented 4 years ago

Hi, welcome to the Knative.

Can you tell us more about how does Knative intersect with your class (Knative by itself does not deal much with virtualization, apart from running on Kubernetes)?
Why did you pick Knative rather than anything else? Do you have any personal interest in the project, or just a picked a project from the list that was provided?
Why did you pick this issue of our hundred+ we have in general?

Also part of it I have already started to work (the second part), but the first one is still for grabs.

pyrito commented 4 years ago

Hi @vagababov,

Our final project asks that we make a contribution to an open source project that is tangentially related to virtualization: e.g. serverless frameworks
KNative had a strong community that had active members that we could find thus far. My partner and I were also interested in learning more about it.
This issue seemed easier to tackle than the others. We felt that it was doable at our level.

vagababov commented 4 years ago

Can I recommend: https://github.com/knative/serving/issues/3415 instead?

vagababov commented 4 years ago

Trying to implement part II, it turned out to be more hassle than benefit, at least the way things are done now (and the values seem to be different, since we always divide by the window size buckets, rather than # of buckets we recorded data, which is pretty different for new revisions).

vagababov commented 4 years ago

/assign /milestone Serving 0.12

knative-prow-robot commented 4 years ago

@vagababov: The provided milestone is not valid for this repository. Milestones in this repository: [Ice Box, Needs Triage, Serving "v1" (ready for production), Serving 0.12.x, Serving 0.13.x]

Use /milestone clear to clear the milestone.

In response to [this](https://github.com/knative/serving/issues/5981#issuecomment-571387131): >/assign >/milestone Serving 0.12 Instructions for interacting with me using PR comments are available [here](https://git.k8s.io/community/contributors/guide/pull-requests.md). If you have questions or suggestions related to my behavior, please file an issue against the [kubernetes/test-infra](https://github.com/kubernetes/test-infra/issues/new?title=Prow%20issue:) repository.

vagababov commented 4 years ago

/milestone Serving 0.12.x

vagababov commented 4 years ago

Done in:

6172, #6203, #6425, #6132, #6931.

vagababov commented 4 years ago

Also: #6487, #6447, #6498

knative / serving

O(1) RPS/Concurrency computations #5981

In what area(s)?

Describe the feature

6172, #6203, #6425, #6132, #6931.