siimon
Proposal for faster insertions during metrics aggregation.
On the back of #687, there is clearly a need for the aggregation code to do something similar.
The main problem is: I am using a constraint that doesn't hold for cluster mode, and likely would not hold for workers #401 either.
Things working against us:
- The primary has to accept all of the stats of all of its children, before it can process them
- Most of the metadata is thrown away
- what is true of one worker may not be true of another, therefore the missing metadata is inaccurate or would have to be cooked anyway
- dealing with labels is comparatively expensive
Things working in our favor:
1 ) the sent data is much simpler than the source data 2) data collection is mostly additive 3) labels get more complex over time, but 4) labels are monetarily expensive, so the growth should be asymptotic 5) we have global knowledge that we can retain if it results in amortized costs 6) Metric aggregation is now sorted by metric name, which should improve data locality, help with data gathering 7) Util is not part of the public API. We may break it in any fashion we see fit, and only negatively affect the contributors. 8) Label,value combinatorics have a high OPEX with cloud providers, and people are motivated not to go too crazy with them. So we can survive with quadratic time, if necessary.
We could make a data structure that works like LabelMap but allows for new labelNames to be added over time. However then you have to either recreate the underlying data structure when you add a new label name, or figure out some way to look up by truncated keys, which could fail without escaping the values, which is expensive to do here..
The amortized resizing option is still open to us.
Build the initial table with too many columns, and fill in the columns in chronological order of first encountering them.
| label1 | label2 | label3 | ? | ? | ? | ? | ? |
| ------------- | ------------- | ------------- | --- | --- | --- | --- | --- |
| - | 200 | 'get' | - | - | - | - | - |
| orange | - | - | - | - | - | - | - |
| blue | 403 | - | - | - | - | - | - |
With keys like
|200|get|||||
Then when a new tag is encountered:
| label1 | label2 | label3 | label4 | ? | ? | ? | ? |
...
| blue | 403 | - | - | - | - | - | - |
| green | 200 | - | new year's | - | - | - | - |
Until we reach label9, and now the table width is full. Then we need to create a new table, expand the label width by ??%, copy all of the values from the old map, adding additional pipe letters to the end of every key from the old table and re-insert them into the new. At a growth factor of two, the amortized number of times you have to insert every key into the table is 2 (Taylor series, 1 + 1/2 + 1/4 + 1/8 + ...)
That has a high likelihood of making tables about 2x as big as they should be, and there are also documented GC problems that occur if the factor is greater than the golden ratio (1.61) because the memory fragmentation. Most frameworks now use 1.5 for this unless they're doing bitwise math for powers of two.
But I think we could probably do fine with an initial size of 5-10 and a growth factor of 20% to 1/3
Instead of the labels being sorted alphabetically, they would be sorted chronologically by where they appear in the responses from the workers. And if we steal an idea from #611, we could reset the entries on every collection rather than dropping them and starting afresh. I believe this would potentially do away with the need for the WeakMap, and thus avoid #684
What we might do though is instead of keeping every metric name we have ever seen, is make a new top level map and recycle entries from the old one. Make the new table, scavenging the old table, drop the old table to allow reset to work better.
