Hi!
(For the following, I'm only talking about HS directory.)
Here is my conundrum. I was working on plugging the new cache for proposal 224 into our OOM. I stumbled upon a fun problem.
We plan to have both current and new HS protocol in parallel. This means two caches for both version 2 (current) and 3 (prop224). So far so good.
However, here is the problem. Now, our OOM handlers is called in: cell_queues_check_size(). The heuristic is basically:
/* If we're spending over 20% of the memory limit on hidden service * descriptors, free them until we're down to 10%. */
Considering we have _two_ caches now, we somehow have to cleanup both of them "evenly" that is if we have to remove 20kb we either remove 10kb on each (if possible) or we actually clean them by entry expiry time instead regardless of which version.
I think the latter is what we want but then it complicates things a bit since both cache contains _different_ data struct. and indexed with different keys (DIGEST vs DIGEST256). One option here is to go over all entries in both cache, create temporary objects and put them in a sorted list (by expiry time). Those "temp object" would contain something like: 1) cache version, 2) expiry time and 3) index key. Once done, we go over that list and delete entries until we reach our number of bytes we need to remove.
This could work since we would do that when we are at 20% memory but still it requires allocating some small objects to _clear_ our memory... Someone has maybe something _better_ to propose? :)
(keep in mind that minimal change to the current HS code is preferable. I know that unifying both caches somehow would help but that's lots more work! and the new cache for prop224 will be able to support versionning for which our current one doesn't, it's baked for v2.)
I'm asking because this will require some refactoring for which I want to make sure we are in agreement on how to proceed and it doesn't end up not the right solution.
Basically my goal is to move the OOM handler for both v2 and v3 to one single function called hs_cache_handle_oom() and from which we'll do the gymnastic describe above. We'll stop calling rend_cache_clean_v2_descs_as_dir() explicitely after that in cell_queues_check_size().
Cheers! David
On 16 Apr 2016, at 05:47, David Goulet dgoulet@ev0ke.net wrote:
Hi!
(For the following, I'm only talking about HS directory.)
Here is my conundrum. I was working on plugging the new cache for proposal 224 into our OOM. I stumbled upon a fun problem.
We plan to have both current and new HS protocol in parallel. This means two caches for both version 2 (current) and 3 (prop224). So far so good.
However, here is the problem. Now, our OOM handlers is called in: cell_queues_check_size(). The heuristic is basically:
/* If we're spending over 20% of the memory limit on hidden service * descriptors, free them until we're down to 10%. */Considering we have _two_ caches now, we somehow have to cleanup both of them "evenly" that is if we have to remove 20kb we either remove 10kb on each (if possible) or we actually clean them by entry expiry time instead regardless of which version.
I think the latter is what we want but then it complicates things a bit since both cache contains _different_ data struct. and indexed with different keys (DIGEST vs DIGEST256). One option here is to go over all entries in both cache, create temporary objects and put them in a sorted list (by expiry time). Those "temp object" would contain something like: 1) cache version, 2) expiry time and 3) index key. Once done, we go over that list and delete entries until we reach our number of bytes we need to remove.
This could work since we would do that when we are at 20% memory but still it requires allocating some small objects to _clear_ our memory... Someone has maybe something _better_ to propose? :)
(keep in mind that minimal change to the current HS code is preferable. I know that unifying both caches somehow would help but that's lots more work! and the new cache for prop224 will be able to support versionning for which our current one doesn't, it's baked for v2.)
I'm asking because this will require some refactoring for which I want to make sure we are in agreement on how to proceed and it doesn't end up not the right solution.
Basically my goal is to move the OOM handler for both v2 and v3 to one single function called hs_cache_handle_oom() and from which we'll do the gymnastic describe above. We'll stop calling rend_cache_clean_v2_descs_as_dir() explicitely after that in cell_queues_check_size().
Having code that is only executed under rare conditions is error-prone. Allocating memory at OOM time is error-prone.
We could add cache entries to the unified list when they are created, rather than at OOM time. This also has the benefit of being faster than creating and sorting a large list at OOM time.
Alternately, we could iterate through each cache like this: Find ta, the oldest expiry time in Cache A Find tb, the oldest expiry time in Cache B Set Cache X to the cache with the oldest descriptor Set tx to the minimum expiry time from ta and tb Set ty to the maximum expiry time from ta and tb While tx <= ty and we are above the desired memory limit Deallocate the oldest descriptor from Cache X Set tx to the oldest expiry time in Cache X If we are still above the desired memory limit, repeat this entire process
We should add entries to a time-sorted list when they are created, otherwise this algorithm is O(n^2).
A third alternative is that we can iterate through each time period: Set K to the oldest expected descriptor age in hours, minus 1 hour Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours Set K to K - 1 and repeat this process
This algorithm is O(Kn), which is ok as long as K is small. This carries a slight risk of over-deallocating cache entries. Which is OK at OOM time. I like this one, because it's simple, performant, and doesn't need any extra memory allocations.
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP 968F094B ricochet:ekmygaiu4rzgsk6n
On 16 Apr (12:49:44), Tim Wilson-Brown - teor wrote:
On 16 Apr 2016, at 05:47, David Goulet dgoulet@ev0ke.net wrote:
Hi!
(For the following, I'm only talking about HS directory.)
Here is my conundrum. I was working on plugging the new cache for proposal 224 into our OOM. I stumbled upon a fun problem.
We plan to have both current and new HS protocol in parallel. This means two caches for both version 2 (current) and 3 (prop224). So far so good.
However, here is the problem. Now, our OOM handlers is called in: cell_queues_check_size(). The heuristic is basically:
/* If we're spending over 20% of the memory limit on hidden service * descriptors, free them until we're down to 10%. */Considering we have _two_ caches now, we somehow have to cleanup both of them "evenly" that is if we have to remove 20kb we either remove 10kb on each (if possible) or we actually clean them by entry expiry time instead regardless of which version.
I think the latter is what we want but then it complicates things a bit since both cache contains _different_ data struct. and indexed with different keys (DIGEST vs DIGEST256). One option here is to go over all entries in both cache, create temporary objects and put them in a sorted list (by expiry time). Those "temp object" would contain something like: 1) cache version, 2) expiry time and 3) index key. Once done, we go over that list and delete entries until we reach our number of bytes we need to remove.
This could work since we would do that when we are at 20% memory but still it requires allocating some small objects to _clear_ our memory... Someone has maybe something _better_ to propose? :)
(keep in mind that minimal change to the current HS code is preferable. I know that unifying both caches somehow would help but that's lots more work! and the new cache for prop224 will be able to support versionning for which our current one doesn't, it's baked for v2.)
I'm asking because this will require some refactoring for which I want to make sure we are in agreement on how to proceed and it doesn't end up not the right solution.
Basically my goal is to move the OOM handler for both v2 and v3 to one single function called hs_cache_handle_oom() and from which we'll do the gymnastic describe above. We'll stop calling rend_cache_clean_v2_descs_as_dir() explicitely after that in cell_queues_check_size().
Having code that is only executed under rare conditions is error-prone.
For the OOM handler, we have to rely on good testing...
Allocating memory at OOM time is error-prone.
Yup, this is the part that I don't like also!
We could add cache entries to the unified list when they are created, rather than at OOM time. This also has the benefit of being faster than creating and sorting a large list at OOM time.
Alternately, we could iterate through each cache like this: Find ta, the oldest expiry time in Cache A Find tb, the oldest expiry time in Cache B Set Cache X to the cache with the oldest descriptor Set tx to the minimum expiry time from ta and tb Set ty to the maximum expiry time from ta and tb While tx <= ty and we are above the desired memory limit Deallocate the oldest descriptor from Cache X Set tx to the oldest expiry time in Cache X If we are still above the desired memory limit, repeat this entire process
We should add entries to a time-sorted list when they are created, otherwise this algorithm is O(n^2).
A third alternative is that we can iterate through each time period: Set K to the oldest expected descriptor age in hours, minus 1 hour Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours Set K to K - 1 and repeat this process
This algorithm is O(Kn), which is ok as long as K is small. This carries a slight risk of over-deallocating cache entries. Which is OK at OOM time. I like this one, because it's simple, performant, and doesn't need any extra memory allocations.
I do also like this one. It's pretty simple and efficient.
Now there is a fourth alternative that Yawning proposed in #tor-dev yesterday which is always prioritize our v2 cache in the OOM handling that is clean the v2 before than if we have to go to the v3 cache. It would be an incentive to "v3 is much more important than v2" kind of thing.
As he describe it, it's a bit like our tap vs ntor situation under pressure, we prioritize ntor and drop tap if needed.
I'm still quite _unsure_ about this. The v3 will bring more memory pressure with this second HSDir cache. And my intuition is that most users won't switch directly to v3 but will probably have a migration path from v2 to v3 like having the v2 onion on for X months before discontinuing it.
So losing reachability because we decide to drop v2 first could not be desirable. But then also how often does a HSDir OOM is triggered... ?
Anyway, right now I'm leaning towards your approach teor of just using the time-period.
More eyes on this would be great :).
Cheers! David
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP 968F094B ricochet:ekmygaiu4rzgsk6n
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Hello,
On 4/16/2016 4:11 PM, David Goulet wrote: [snip]
A third alternative is that we can iterate through each time period: Set K to the oldest expected descriptor age in hours, minus 1 hour Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours Set K to K - 1 and repeat this process
This algorithm is O(Kn), which is ok as long as K is small. This carries a slight risk of over-deallocating cache entries. Which is OK at OOM time. I like this one, because it's simple, performant, and doesn't need any extra memory allocations.
I do also like this one. It's pretty simple and efficient.
Now there is a fourth alternative that Yawning proposed in #tor-dev yesterday which is always prioritize our v2 cache in the OOM handling that is clean the v2 before than if we have to go to the v3 cache. It would be an incentive to "v3 is much more important than v2" kind of thing.
As he describe it, it's a bit like our tap vs ntor situation under pressure, we prioritize ntor and drop tap if needed.
I'm still quite _unsure_ about this. The v3 will bring more memory pressure with this second HSDir cache. And my intuition is that most users won't switch directly to v3 but will probably have a migration path from v2 to v3 like having the v2 onion on for X months before discontinuing it.
So losing reachability because we decide to drop v2 first could not be desirable. But then also how often does a HSDir OOM is triggered... ?
Anyway, right now I'm leaning towards your approach teor of just using the time-period.
More eyes on this would be great :).
Cheers! David
I agree that teor's O(Kn) is the best approach from performance (no additional memory allocations), simplicity and efficacy point of view. O(Kn) algorithm will clear the entries only based on their expiration time, it won't care to clean the v2 / v3 caches in equal measure which is good, given that we do not know how long HS operators will take / need to upgrade their services to prop 224.
The tap vs ntor situation was a good measure, but the threat model was different (we were trying to ensure new clients using ntor get resources from relays with priority as opposite to non-updated botnet zombies using tap). In the current situation we care about v2 and v3 HS caches exactly the same, for an unknown period of time which might not be short, so we shouldn't penalize v2 in any way.
This needs to be covered regardless how often a HSDir has its OOM triggered. I don't think we should assume it's hard to flood HSDirs with descriptors until the memory is full.
Now that HSDirs will need to handle two caches, is 20% of the total memory allocated for HS descriptors a good value? What harm would increasing it to let's say 25% do?
On Sat, 16 Apr 2016 20:30:29 +0300 s7r s7r@sky-ip.org wrote:
I agree that teor's O(Kn) is the best approach from performance (no additional memory allocations), simplicity and efficacy point of view. O(Kn) algorithm will clear the entries only based on their expiration time, it won't care to clean the v2 / v3 caches in equal measure which is good, given that we do not know how long HS operators will take / need to upgrade their services to prop 224.
The tap vs ntor situation was a good measure, but the threat model was different (we were trying to ensure new clients using ntor get resources from relays with priority as opposite to non-updated botnet zombies using tap). In the current situation we care about v2 and v3 HS caches exactly the same, for an unknown period of time which might not be short, so we shouldn't penalize v2 in any way.
We do? I can think of numerous reasons as to why v3 is objectively better, and why we should incentive people to move towards 224 style HSes...
What I want is possible with Teor's 2nd algorithm (which is adequate). Make Cache A the v2 cache, and if we've freed enough ram after purging expired entries from A in a given time period, we terminate rather than touching cache B.
In effect this makes it slightly less likely for entries in the B cache to be deallocated (we probably should also halt once we have reached our target deallocation amount when attempting to compact either cache, rather than continuing to purge the rest of the time interval, it's the OOM handler, and an addition, a compare and a branch is cheap enough to be done in a loop).
This needs to be covered regardless how often a HSDir has its OOM triggered. I don't think we should assume it's hard to flood HSDirs with descriptors until the memory is full.
Now that HSDirs will need to handle two caches, is 20% of the total memory allocated for HS descriptors a good value? What harm would increasing it to let's say 25% do?
It would decrease memory available for other things, where other things is "all HSDirs are expected to first and foremost be relays, and do normal relay things like relaying traffic, before being HSDirs".
I don't remember if it's possible to opt out of being a HSDir or not (likewise, with the move to make all relays be dir caches, we already are increasing memory pressure on "things that are comically undersized that shouldn't ever be HSDirs or DirCaches in the first place")....
Regards,
Tim Wilson-Brown - teor teor2345@gmail.com writes:
[ text/plain ]
On 16 Apr 2016, at 05:47, David Goulet dgoulet@ev0ke.net wrote:
Hi!
(For the following, I'm only talking about HS directory.)
Here is my conundrum. I was working on plugging the new cache for proposal 224 into our OOM. I stumbled upon a fun problem.
<snip>
We should add entries to a time-sorted list when they are created, otherwise this algorithm is O(n^2).
A third alternative is that we can iterate through each time period: Set K to the oldest expected descriptor age in hours, minus 1 hour Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours Set K to K - 1 and repeat this process
This algorithm is O(Kn), which is ok as long as K is small. This carries a slight risk of over-deallocating cache entries. Which is OK at OOM time. I like this one, because it's simple, performant, and doesn't need any extra memory allocations.
I feel this is a reasonable approach here. It will probably have to be combined with time-sorted lists as teor suggested, otherwise each of those steps will require walking through the whole cache every time.
BTW, before it says "Set K to K - 1 and repeat this process" we should also check whether our memory issue has been addressed and if so then we can exit, right?
In that case, maybe we can add the same check between these two checks:
Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours
so that maybe sometimes we can get away with just removing stuff from the v2 cache.
Are there any other issues with the above approach?
PS: We could also in theory imagine writing those descriptors on disk, and only caching the ones that we have received requests for lately. This way we would not utilize our RAM that much...
On 18 Apr (13:18:25), George Kadianakis wrote:
Tim Wilson-Brown - teor teor2345@gmail.com writes:
[ text/plain ]
On 16 Apr 2016, at 05:47, David Goulet dgoulet@ev0ke.net wrote:
Hi!
(For the following, I'm only talking about HS directory.)
Here is my conundrum. I was working on plugging the new cache for proposal 224 into our OOM. I stumbled upon a fun problem.
<snip>
We should add entries to a time-sorted list when they are created, otherwise this algorithm is O(n^2).
A third alternative is that we can iterate through each time period: Set K to the oldest expected descriptor age in hours, minus 1 hour Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours Set K to K - 1 and repeat this process
This algorithm is O(Kn), which is ok as long as K is small. This carries a slight risk of over-deallocating cache entries. Which is OK at OOM time. I like this one, because it's simple, performant, and doesn't need any extra memory allocations.
I feel this is a reasonable approach here. It will probably have to be combined with time-sorted lists as teor suggested, otherwise each of those steps will require walking through the whole cache every time.
BTW, before it says "Set K to K - 1 and repeat this process" we should also check whether our memory issue has been addressed and if so then we can exit, right?
Yeah I would do that. Every time we cleanup a cache, we check if we've reached our bytes cutoff.
In that case, maybe we can add the same check between these two checks:
Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours
so that maybe sometimes we can get away with just removing stuff from the v2 cache.
Are there any other issues with the above approach?
While implementing this solution, I found one annoying issue :).
In order to compute K, I use the maximum lifetime of a cache entry. So basically if my maximum lifetime in hours is M=10 then K will start at 10 - 1. (Where 1 hour is basically the "assumed" HS post period.)
However, our v2 and v3 cache have different lifetimes.
v2: 48 hours is the max lifetime (REND_CACHE_MAX_AGE) plus the maximum clock skew of 24 hours (REND_CACHE_MAX_SKEW) == 72 hours.
v3: We've settled on 33 hours which is 24h time period, 6 hours of overlap period and 3 hours of maximum clock skew.
So somehow, we need to "unify" K to fit both caches. Some options (some I do not like):
1) We could iterate over both caches at first and find out the oldest descriptor which requires a first pass of O(n) + O(m). Use that value for our starting point of K. But then inherently, we'll most of the time wipe v2 descriptors since they have a long lifetime. (maybe good!?)
2) We could be crazier and set the v2 max lifetime to be the same as the v3... (FYI, we already have an open ticket about that to bring it down).
3) Go back to having a sorted list of very small objects that would contains created timestamp, version and ptr to cache entry. This adds a bit more memory for each entry (not that crazy) and require more codes in both v2 and v3. (I'm sekritly trying to _not_ add more v2 code.)
4) <insert ideas>
PS: We could also in theory imagine writing those descriptors on disk, and only caching the ones that we have received requests for lately. This way we would not utilize our RAM that much...
A new level of complexity here :). Before we go there, we should try to find out how much memory an HSDir uses periodically for its cache. Fun stat to have actually (for you out there stats lover! ;)
I expect that this could be a needed solution if HS adoption goes crazy while not having a growth in the number of relays (and even then...). Proposal? :)
Cheers! David
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
On 20 Apr 2016, at 07:22, David Goulet dgoulet@ev0ke.net wrote:
On 18 Apr (13:18:25), George Kadianakis wrote:
Tim Wilson-Brown - teor teor2345@gmail.com writes:
[ text/plain ]
On 16 Apr 2016, at 05:47, David Goulet dgoulet@ev0ke.net wrote:
Hi!
(For the following, I'm only talking about HS directory.)
Here is my conundrum. I was working on plugging the new cache for proposal 224 into our OOM. I stumbled upon a fun problem.
<snip>
We should add entries to a time-sorted list when they are created, otherwise this algorithm is O(n^2).
A third alternative is that we can iterate through each time period: Set K to the oldest expected descriptor age in hours, minus 1 hour Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours Set K to K - 1 and repeat this process
This algorithm is O(Kn), which is ok as long as K is small. This carries a slight risk of over-deallocating cache entries. Which is OK at OOM time. I like this one, because it's simple, performant, and doesn't need any extra memory allocations.
I feel this is a reasonable approach here. It will probably have to be combined with time-sorted lists as teor suggested, otherwise each of those steps will require walking through the whole cache every time.
Yes, that's why I said O(K*n), which is alright as long as K is small. If we keep sorted lists (warn: v2 code changes), then the algorithm is O(n) instead.
BTW, before it says "Set K to K - 1 and repeat this process" we should also check whether our memory issue has been addressed and if so then we can exit, right?
Yeah I would do that. Every time we cleanup a cache, we check if we've reached our bytes cutoff.
Yes, we can terminate the algorithm as soon as we reach our goal.
In that case, maybe we can add the same check between these two checks:
Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours
so that maybe sometimes we can get away with just removing stuff from the v2 cache.
Are there any other issues with the above approach?
While implementing this solution, I found one annoying issue :).
In order to compute K, I use the maximum lifetime of a cache entry. So basically if my maximum lifetime in hours is M=10 then K will start at 10 - 1. (Where 1 hour is basically the "assumed" HS post period.)
Note that we can decrement K by a multiple of the post period - for example, it can be 3 hours: 9, 6, 3, 0.
This makes the algorithm run faster (as it would iterate through the unsorted v3 list 11 times, rather than 33 times), at the cost of sometimes deallocating some more recent descriptors in that 3 hour period.
However, our v2 and v3 cache have different lifetimes.
v2: 48 hours is the max lifetime (REND_CACHE_MAX_AGE) plus the maximum clock skew of 24 hours (REND_CACHE_MAX_SKEW) == 72 hours.
v3: We've settled on 33 hours which is 24h time period, 6 hours of overlap period and 3 hours of maximum clock skew.
So somehow, we need to "unify" K to fit both caches. Some options (some I do not like):
- We could iterate over both caches at first and find out the oldest
descriptor which requires a first pass of O(n) + O(m). Use that value for our starting point of K. But then inherently, we'll most of the time wipe v2 descriptors since they have a long lifetime. (maybe good!?)
I think that clients are just as likely to re-use descriptors that are an hour old, regardless of the maximum lifetimes of v2 and v3 descriptors.
So I don't care if we take out more v2 descriptors.
- We could be crazier and set the v2 max lifetime to be the same as the v3...
(FYI, we already have an open ticket about that to bring it down).
I am ok with this, but we have no stats on it, so it's hard to tell what impact it will have (if any).
Cutting the size of the v2 cache in half would also make space for the v3 cache during the transition period. So I support this idea.
- Go back to having a sorted list of very small objects that would contains
created timestamp, version and ptr to cache entry. This adds a bit more memory for each entry (not that crazy) and require more codes in both v2 and v3. (I'm sekritly trying to _not_ add more v2 code.)
This would make deallocation O(n), but as you say, it involves v2 code changes. I wonder if we will want the sorted list in v3 going forward, regardless of what we do with v2.
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP 968F094B ricochet:ekmygaiu4rzgsk6n
Tim Wilson-Brown - teor teor2345@gmail.com writes:
[ text/plain ]
On 20 Apr 2016, at 07:22, David Goulet dgoulet@ev0ke.net wrote:
On 18 Apr (13:18:25), George Kadianakis wrote:
Tim Wilson-Brown - teor teor2345@gmail.com writes:
[ text/plain ]
On 16 Apr 2016, at 05:47, David Goulet dgoulet@ev0ke.net wrote:
Hi!
(For the following, I'm only talking about HS directory.)
Here is my conundrum. I was working on plugging the new cache for proposal 224 into our OOM. I stumbled upon a fun problem.
<snip>
We should add entries to a time-sorted list when they are created, otherwise this algorithm is O(n^2).
A third alternative is that we can iterate through each time period: Set K to the oldest expected descriptor age in hours, minus 1 hour Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours Set K to K - 1 and repeat this process
This algorithm is O(Kn), which is ok as long as K is small. This carries a slight risk of over-deallocating cache entries. Which is OK at OOM time. I like this one, because it's simple, performant, and doesn't need any extra memory allocations.
I feel this is a reasonable approach here. It will probably have to be combined with time-sorted lists as teor suggested, otherwise each of those steps will require walking through the whole cache every time.
Yes, that's why I said O(K*n), which is alright as long as K is small. If we keep sorted lists (warn: v2 code changes), then the algorithm is O(n) instead.
BTW, before it says "Set K to K - 1 and repeat this process" we should also check whether our memory issue has been addressed and if so then we can exit, right?
Yeah I would do that. Every time we cleanup a cache, we check if we've reached our bytes cutoff.
Yes, we can terminate the algorithm as soon as we reach our goal.
In that case, maybe we can add the same check between these two checks:
Deallocate all entries from Cache A that are older than K hours Deallocate all entries from Cache B that are older than K hours
so that maybe sometimes we can get away with just removing stuff from the v2 cache.
Are there any other issues with the above approach?
While implementing this solution, I found one annoying issue :).
In order to compute K, I use the maximum lifetime of a cache entry. So basically if my maximum lifetime in hours is M=10 then K will start at 10 - 1. (Where 1 hour is basically the "assumed" HS post period.)
Note that we can decrement K by a multiple of the post period - for example, it can be 3 hours: 9, 6, 3, 0.
This makes the algorithm run faster (as it would iterate through the unsorted v3 list 11 times, rather than 33 times), at the cost of sometimes deallocating some more recent descriptors in that 3 hour period.
However, our v2 and v3 cache have different lifetimes.
v2: 48 hours is the max lifetime (REND_CACHE_MAX_AGE) plus the maximum clock skew of 24 hours (REND_CACHE_MAX_SKEW) == 72 hours.
v3: We've settled on 33 hours which is 24h time period, 6 hours of overlap period and 3 hours of maximum clock skew.
So somehow, we need to "unify" K to fit both caches. Some options (some I do not like):
- We could iterate over both caches at first and find out the oldest
descriptor which requires a first pass of O(n) + O(m). Use that value for our starting point of K. But then inherently, we'll most of the time wipe v2 descriptors since they have a long lifetime. (maybe good!?)
I think that clients are just as likely to re-use descriptors that are an hour old, regardless of the maximum lifetimes of v2 and v3 descriptors.
So I don't care if we take out more v2 descriptors.
I feel this is a fine way to do this.
Since hidden services reupload their descriptor every 1 hour (both in v2 and v3), the oldest descriptors will always belong to dead hidden services, or to hidden services that have since rotated HSDirs. So I think it's OK to wipe super old v2 descriptors first.
- We could be crazier and set the v2 max lifetime to be the same as the v3...
(FYI, we already have an open ticket about that to bring it down).
I am ok with this, but we have no stats on it, so it's hard to tell what impact it will have (if any).
Cutting the size of the v2 cache in half would also make space for the v3 cache during the transition period. So I support this idea.
This also seems like a plausible approach, especially since it seems easier to implement than (1).
Before doing this we should make sure that nothing will break if we bring the 72 hours v2 lifetime down to 33 hours. Personally, I can't think of anything breaking right now.
-
David Goulet -
George Kadianakis -
s7r -
Tim Wilson-Brown - teor -
Yawning Angel