98 lines
2.4 KiB
Markdown
98 lines
2.4 KiB
Markdown
# Age Caching Simulation
|
|
|
|
Client -> TTL Cache -> Database
|
|
Capacity C (C = n (example: 100))
|
|
|
|
TTL increases on cache hit
|
|
Age of information / Age of the entry in the cache
|
|
Database has latest object, cache entry may be old (we don't know)
|
|
|
|
Age of entry should have low age of information
|
|
|
|
Update function from cache to refresh based on mu (refresh rate)
|
|
|
|
Loss function based on TTL and age in cache called beta(i)
|
|
|
|
Event based simulation
|
|
|
|
lambda(i) is zipf distribution describing the rate the client requests the object "i"
|
|
|
|
Inter arrival time of each object => exponential
|
|
|
|
Hit rate and the average age of the object based on TTL
|
|
|
|
## Notes 11/13/2024
|
|
|
|
### Limitations of time
|
|
|
|
Run the simulation not time based but based on when the least ranked object is requested
|
|
at least times for example.
|
|
Least ranked object -> least zipf value
|
|
|
|
2-3h
|
|
|
|
### mu
|
|
|
|
Simulate lambda and mu to see what increases the cost function
|
|
|
|
### Bandwidth
|
|
|
|
Finite bandwidth between cache and server
|
|
miss requests and cache updates should not go over the bandwidth
|
|
|
|
### Two versions
|
|
|
|
- [x] Default
|
|
|
|
- Do Refresh
|
|
- Do Request
|
|
|
|
- [x] No Refresh
|
|
|
|
- Just Request
|
|
- No Refresh
|
|
|
|
- [x] Infinite TTL
|
|
|
|
- LRU
|
|
- Infinite TTL
|
|
- No Refresh
|
|
|
|
- [x] Random Eviction
|
|
|
|
- Random eviction
|
|
- Regular TTL
|
|
- With Refresh
|
|
|
|
- [x] Random Eviction w/o Refresh
|
|
- Random eviction
|
|
- Regular TTL
|
|
- No Refresh
|
|
|
|
| Name | Cache Capacity | MAX_REFRESH_RATE | cache_type | CACHE_TTL |
|
|
| -------------------- | -------------------- | ---------------- | ------------------------- | --------- |
|
|
| Default | DATABASE_OBJECTS | 1< | CacheType.LRU | 5 |
|
|
| No Refresh | DATABASE_OBJECTS | 0 | CacheType.LRU | 5 |
|
|
| Infinite TTL | DATABASE_OBJECTS / 2 | 0 | CacheType.LRU | 0 |
|
|
| Random Eviction (RE) | DATABASE_OBJECTS / 2 | 1< | CacheType.RANDOM_EVICTION | 5 |
|
|
| RE without Refresh | DATABASE_OBJECTS / 2 | 0 | CacheType.RANDOM_EVICTION | 5 |
|
|
|
|
### Runtime
|
|
|
|
CPU times: user 3min 46s, sys: 43 s, total: 4min 29s
|
|
Wall time: 4min 29s
|
|
for ACCESS_COUNT_LIMIT = 10_000 # Total time to run the simulation
|
|
|
|
## Notes 11/29/2024
|
|
|
|
C_m = cost for cache miss
|
|
C_delta = cost for refresh
|
|
C = Cm + C_delta over all objects summarized
|
|
|
|
We wanna minimize cost function
|
|
|
|
N = number of objects
|
|
B is cache size
|
|
|
|
C_f roughly equals C_m
|