pub struct Access(/* private fields */);Expand description
How recently and how often one key has been used.
Which of the two it is depends on the Policy in force, and this type does
not know which that is. The reader picks.
Implementations§
Source§impl Access
impl Access
Sourcepub const fn from_bits(bits: u32) -> Access
pub const fn from_bits(bits: u32) -> Access
Rebuild one from bits that came out of a record.
Anything above the low twenty four is dropped rather than trusted, because those bits belong to whatever is packed alongside.
Sourcepub const fn is_unset(self) -> bool
pub const fn is_unset(self) -> bool
Whether this key has never been stamped.
All zeroes, which is what a record carries from the moment it is written until something reads it under a policy that cares. It is a sentinel and not a reading, and both readings answer for it as though the key had just been used: zero seconds idle, and the starting frequency. That is the safe direction. The other one would make every key in the database the most attractive victim available for as long as it went unread, which would evict the working set the moment a policy was switched on.
It is a sentinel rather than a flag bit because it costs nothing and because it means a record can be created without anybody deciding what to put here. The writers do not know the clock or the policy, and having them ask would have put both through every call site that makes a record.
Zero is very nearly unreachable as a real reading. An LRU stamp is zero only in the first second of 1970. An LFU stamp is zero only for a key already decayed to nothing that is touched during the one minute in every forty five days when the LFU clock wraps, and the cost of the collision is that the key looks freshly used for a moment instead of unused. That is a rounding error in a heuristic, and it is worth it to keep the write path from having to care.
Sourcepub const fn lru(now_ms: u64) -> Access
pub const fn lru(now_ms: u64) -> Access
The reading for a key touched at now_ms under an LRU policy.
Sourcepub const fn lfu(now_ms: u64) -> Access
pub const fn lfu(now_ms: u64) -> Access
The reading for a key created at now_ms under an LFU policy.
Sourcepub const fn idle_secs(self, now_ms: u64) -> u64
pub const fn idle_secs(self, now_ms: u64) -> u64
How long ago this key was read, in seconds, under an LRU policy.
This is what OBJECT IDLETIME returns. The branch is the wrap: once the
clock has gone round, a key stamped before the wrap holds a number larger
than the clock does, and subtracting the wrong way round would report a
key that was read a second ago as a hundred and ninety four days idle,
which under allkeys-lru would evict the hottest key in the database.
The wrapped arm is short by one second, because the period is MAX + 1
and Redis subtracts from MAX. That is not a mistake here, it is Redis’s
mistake reproduced on purpose, and it is worth being clear about because
it looks exactly like the kind of thing somebody would tidy up. Fixing it
would make OBJECT IDLETIME disagree with Redis by a second for the keys
that were stamped before a wrap, once every hundred and ninety four days.
It is also self consistent over there, which is the part that settles it.
RESTORE takes an idle time and turns it back into a stamp, and it adds
MAX where this subtracts MAX, so a value that goes out through
OBJECT IDLETIME and comes back in through RESTORE lands on the number
it started from. Correcting one end here would break that round trip
against a real Redis without making any single answer more true.
Sourcepub const fn freq(self, now_ms: u64, lfu: Lfu) -> u8
pub const fn freq(self, now_ms: u64, lfu: Lfu) -> u8
The frequency counter, with the decay since the last access applied.
This is what OBJECT FREQ returns and what eviction compares. The decay
is applied on read rather than on a timer, which is what makes the whole
thing free when nobody is asking: there is no sweep that walks every key
once a minute to bring counters down, and a key nobody looks at costs
nothing to not look at.
Sourcepub fn touched(self, now_ms: u64, lfu: Lfu, rng: &mut Rng) -> Access
pub fn touched(self, now_ms: u64, lfu: Lfu, rng: &mut Rng) -> Access
The field after one access under an LFU policy.
Decay first and then increment, in that order, because the other order would let a key that is read once a minute climb forever: the increment would land before the decay took it off again and the counter would ratchet up on traffic that is not actually heavy.
The increment is probabilistic and that is the whole trick. Eight bits cannot count to a million, so the counter does not count accesses, it samples them, at odds that fall as the counter rises. A key at 5 moves on the next access, a key at 100 moves on about one access in a thousand, and the result is a number that orders keys by traffic across several orders of magnitude without ever needing a ninth bit.