You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@trafficserver.apache.org by "zwoop (via GitHub)" <gi...@apache.org> on 2024/04/01 22:20:03 UTC
[PR] Improve seen list for the RAM cache [trafficserver]
zwoop opened a new pull request, #10662:
URL: https://github.com/apache/trafficserver/pull/10662
This is work continued from Jeff's initial discovery and code. This
patch will do:
1. Change the seen filter to a bitset (1/16th the size)
2. Removes the smallest hash bucket sizes (this is 2023)
3. Doubles the size of the seen filter (less collisions)
4. Ignores collisions in the seen filter completely
5. Optionally enables the seen filter at a certain fill %
6. Avoids LRU hash collisions by resizing early (75% fill)
The net effect is that we avoid the issues Jeff discovered by
both reducing collision probability, and then accept some "false
positive" RAM cache promotions to make sure collisions never
happens. We accept that it's ok to add a little too much to the
RAM cache is better than not adding it at all. And, once the
cache is properly fill, all the improvements around collisions
should make this very rare.
In addition, the optional feature to only use the seen filter when
the RAM cache is at a certain fill percentage makes startup less
straneous on the disks. Essentially, it will quickly fill the RAM
cache with popular (and some unpopular) content reducing the
disk I/O at startup by up to 50% (probably less though).
The changes also reduces the size of the seen filter by 87.5%.
**Co-Author**: Jeff Elsloo
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "SolidWallOfCode (via GitHub)" <gi...@apache.org>.
SolidWallOfCode commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1406592391
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -47,7 +48,7 @@ struct RamCacheLRU : public RamCache {
void init(int64_t max_bytes, Vol *vol) override;
// private
- uint16_t *seen = nullptr;
+ std::vector<bool> *seen = nullptr;
Review Comment:
Are you sure you don't want `std::unique_ptr<std::vector<bool>> seen;`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "SolidWallOfCode (via GitHub)" <gi...@apache.org>.
SolidWallOfCode commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1406594186
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -84,13 +85,14 @@ RamCacheLRU::size() const
ClassAllocator<RamCacheLRUEntry> ramCacheLRUEntryAllocator("RamCacheLRUEntry");
-static const int bucket_sizes[] = {127, 251, 509, 1021, 2039, 4093, 8191, 16381,
- 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301,
- 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909};
+static const int bucket_sizes[] = {8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
Review Comment:
`std::array` here? You would need to fill in the size explicitly unfortunately.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "zwoop (via GitHub)" <gi...@apache.org>.
zwoop commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1507938552
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -47,7 +48,7 @@ struct RamCacheLRU : public RamCache {
void init(int64_t max_bytes, Vol *vol) override;
// private
- uint16_t *seen = nullptr;
+ std::vector<bool> *seen = nullptr;
Review Comment:
I decided not to rewrite more than was necessary.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#issuecomment-1963179859
This pull request has been automatically marked as stale because it has not had recent activity. Marking it stale to flag it for further consideration by the community.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "ywkaras (via GitHub)" <gi...@apache.org>.
ywkaras commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1546977937
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -84,13 +86,14 @@ RamCacheLRU::size() const
ClassAllocator<RamCacheLRUEntry> ramCacheLRUEntryAllocator("RamCacheLRUEntry");
-static const int bucket_sizes[] = {127, 251, 509, 1021, 2039, 4093, 8191, 16381,
- 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301,
- 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909};
+static const int bucket_sizes[] = {8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
Review Comment:
How about:
```
static constexpr int bucket_size(unsigned bucket_idx) { return (1 << (bucket_idx + 13)) - 1; }
static std::size_t NUM_BUCKETS = 18;
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "zwoop (via GitHub)" <gi...@apache.org>.
zwoop commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1506922465
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -107,11 +109,11 @@ RamCacheLRU::resize_hashtable()
}
bucket = new_bucket;
nbuckets = anbuckets;
- ats_free(seen);
+ delete seen;
int size = bucket_sizes[ibuckets] * sizeof(uint16_t);
Review Comment:
Each bucket stores a uint16_t, no? This is old code.
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -107,11 +109,11 @@ RamCacheLRU::resize_hashtable()
}
bucket = new_bucket;
nbuckets = anbuckets;
- ats_free(seen);
+ delete seen;
int size = bucket_sizes[ibuckets] * sizeof(uint16_t);
Review Comment:
Fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "zwoop (via GitHub)" <gi...@apache.org>.
zwoop commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1506922465
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -107,11 +109,11 @@ RamCacheLRU::resize_hashtable()
}
bucket = new_bucket;
nbuckets = anbuckets;
- ats_free(seen);
+ delete seen;
int size = bucket_sizes[ibuckets] * sizeof(uint16_t);
Review Comment:
Each bucket stores a uint16_t, no? This is old code.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "bneradt (via GitHub)" <gi...@apache.org>.
bneradt commented on PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#issuecomment-1812840768
[approve ci format]
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "SolidWallOfCode (via GitHub)" <gi...@apache.org>.
SolidWallOfCode commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1406604459
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -107,11 +109,11 @@ RamCacheLRU::resize_hashtable()
}
bucket = new_bucket;
nbuckets = anbuckets;
- ats_free(seen);
+ delete seen;
int size = bucket_sizes[ibuckets] * sizeof(uint16_t);
Review Comment:
Where does `sizeof(uint16_t)` do here? Shouldn't it just be the `bucket_sizes[ibuckets]`?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "ywkaras (via GitHub)" <gi...@apache.org>.
ywkaras commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1546981262
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -84,13 +86,14 @@ RamCacheLRU::size() const
ClassAllocator<RamCacheLRUEntry> ramCacheLRUEntryAllocator("RamCacheLRUEntry");
-static const int bucket_sizes[] = {127, 251, 509, 1021, 2039, 4093, 8191, 16381,
- 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301,
- 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909};
+static const int bucket_sizes[] = {8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
+ 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 1073741827};
void
RamCacheLRU::resize_hashtable()
{
+ ink_release_assert(ibuckets < static_cast<int>(std::size(bucket_sizes)));
Review Comment:
NUM_BUCKETS
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "ywkaras (via GitHub)" <gi...@apache.org>.
ywkaras commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1546977937
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -84,13 +86,14 @@ RamCacheLRU::size() const
ClassAllocator<RamCacheLRUEntry> ramCacheLRUEntryAllocator("RamCacheLRUEntry");
-static const int bucket_sizes[] = {127, 251, 509, 1021, 2039, 4093, 8191, 16381,
- 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301,
- 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909};
+static const int bucket_sizes[] = {8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
Review Comment:
How about:
```
static constexpr int bucket_size(unsigned exp) { return (1 << (exp + 13)) - 1; }
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #10662: Improve seen list for the RAM cache
URL: https://github.com/apache/trafficserver/pull/10662
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "zwoop (via GitHub)" <gi...@apache.org>.
zwoop commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1507938079
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -84,13 +85,14 @@ RamCacheLRU::size() const
ClassAllocator<RamCacheLRUEntry> ramCacheLRUEntryAllocator("RamCacheLRUEntry");
-static const int bucket_sizes[] = {127, 251, 509, 1021, 2039, 4093, 8191, 16381,
- 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301,
- 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909};
+static const int bucket_sizes[] = {8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
+ 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 1073741827};
void
RamCacheLRU::resize_hashtable()
{
+ ink_release_assert(ibuckets < static_cast<int>(sizeof(bucket_sizes)));
Review Comment:
Fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "zwoop (via GitHub)" <gi...@apache.org>.
zwoop merged PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "SolidWallOfCode (via GitHub)" <gi...@apache.org>.
SolidWallOfCode commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1406600721
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -84,13 +85,14 @@ RamCacheLRU::size() const
ClassAllocator<RamCacheLRUEntry> ramCacheLRUEntryAllocator("RamCacheLRUEntry");
-static const int bucket_sizes[] = {127, 251, 509, 1021, 2039, 4093, 8191, 16381,
- 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301,
- 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909};
+static const int bucket_sizes[] = {8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
+ 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 1073741827};
void
RamCacheLRU::resize_hashtable()
{
+ ink_release_assert(ibuckets < static_cast<int>(sizeof(bucket_sizes)));
Review Comment:
Is this correct? `sizeof(bucket_sizes)` is the number of bytes, which means it is `sizeof(int)` * number of entries, not the number of entries.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "SolidWallOfCode (via GitHub)" <gi...@apache.org>.
SolidWallOfCode commented on code in PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#discussion_r1406601047
##########
src/iocore/cache/RamCacheLRU.cc:
##########
@@ -107,11 +109,11 @@ RamCacheLRU::resize_hashtable()
}
bucket = new_bucket;
nbuckets = anbuckets;
- ats_free(seen);
+ delete seen;
Review Comment:
Not needed with `std::unique_ptr`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Improve seen list for the RAM cache [trafficserver]
Posted by "cmcfarlen (via GitHub)" <gi...@apache.org>.
cmcfarlen commented on PR #10662:
URL: https://github.com/apache/trafficserver/pull/10662#issuecomment-2040289703
Cherry-picked to v10.0.x
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org