Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: rkday/ttlcache
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: master
Choose a base ref
...
head repository: biotz/ttlcache
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: master
Choose a head ref
Able to merge. These branches can be automatically merged.
  • 13 commits
  • 11 files changed
  • 1 contributor

Commits on Apr 7, 2021

  1. Copy the full SHA
    9d54fb1 View commit details
  2. Upgrade project configuration and dependencies

    - Upgrade to Clojure 1.10.0
    - Upgrade dependencies to latest versions
    - Added dependencies for coding style linting
    - Added testing configuration
    - Added Clojars deployment configuration
    - Added Travis-CI integration configuration
    iarenaza committed Apr 7, 2021
    Copy the full SHA
    5c40c15 View commit details
  3. Copy the full SHA
    bbee448 View commit details
  4. Copy the full SHA
    de40f67 View commit details
  5. Fix formatting

    To comply with Clojure community style guide.
    iarenaza committed Apr 7, 2021
    Copy the full SHA
    ca3348f View commit details
  6. Fix factor values for newer versions of clojure.core.cache

    Newer versions of clojure.core.cache for the TTL type use a different
    implementation that is way faster than it used to be. So the factors
    configured in the tests are no longer sensible and need to be
    adjusted.
    iarenaza committed Apr 7, 2021
    Copy the full SHA
    ebdf588 View commit details
  7. Fix formatting

    To comploy with Clojure community style guide
    iarenaza committed Apr 7, 2021
    Copy the full SHA
    97f1e1a View commit details
  8. Don't use transients for cache expiry

    The library didn't expect another `clojure.core.cache` cache as it's
    seed value. And it tried to do things with it that it didn't
    support. I.e., it tried to build a transient value out of it, which
    `clojure.core.cache` compatible caches don't support. This is easily
    fixed by changing the library not to convert the cache info into a
    transient value.
    
    Using transients was supposed a performance optimization, but as far
    as we've seen, it doesn't make a noticeable difference at all.
    iarenaza committed Apr 7, 2021
    Copy the full SHA
    6e24bf7 View commit details
  9. Make sure we completely evict entries from the cache

    Entries were not evicted from the composed cache when an entry was
    supposed to be evicted to make room for a newly added entry.
    
    E.g., we composed an LRU cache with a 10 entries limit, with the
    per-item TTL cache. When we already had 10 entries in the composed
    cache and we wanted to add a new one, we needed to evict one of the
    existing entries. The issue was that after adding the new entry, if
    you "dumped" the contents of the cache (e.g., by using `prn`), you
    didn't see the entry that was supposed to have been evicted. If you
    called `cache/lookup` or tried to access the entry using map notation,
    you didn't get the entry (if you used the 3-arity versions of the
    functions, you were told that there was no such entry). But if you
    called `cache/has?` with that key, you were told that the entry *was*
    in the cache! (when it was supposed to *not* be there).
    
    We were not removing the entry from the expiry-heap. Which worked
    mostly OK when we used the cache in a stand-alone configuration, but
    produced the pathological behaviour described above when used in a
    composed cache.
    iarenaza committed Apr 7, 2021
    Copy the full SHA
    424e124 View commit details
  10. Fix formatting

    To comply with Clojure community style guide.
    iarenaza committed Apr 7, 2021
    Copy the full SHA
    f8c78d9 View commit details
  11. Copy the full SHA
    bccdca5 View commit details
  12. Add CHANGELOG.md

    All notable changes to this project will be documented in this file.
    iarenaza committed Apr 7, 2021
    Copy the full SHA
    159a2db View commit details
  13. Release v0.2.0

    iarenaza committed Apr 7, 2021
    Copy the full SHA
    fafffe9 View commit details
1 change: 1 addition & 0 deletions .clj-kondo/.gitignore
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
.cache
6 changes: 6 additions & 0 deletions .clj-kondo/config.edn
Original file line number Diff line number Diff line change
@@ -0,0 +1,6 @@
{:linters
{:unsorted-required-namespaces {:level :warning}
:refer-all {:exclude #{clojure.test}}
:unused-binding {:exclude-destructured-keys-in-fn-args true}}
:lint-as
{clojure.core.cache/defcache clojure.core/defrecord}}
13 changes: 13 additions & 0 deletions .gitignore
Original file line number Diff line number Diff line change
@@ -0,0 +1,13 @@
/target
/checkouts
pom.xml
pom.xml.asc
*.jar
*.class
/.lein-*
/.nrepl-port
/.dir-locals.el
/profiles.clj
.idea/
*.iml
.eastwood
15 changes: 15 additions & 0 deletions .travis.yml
Original file line number Diff line number Diff line change
@@ -0,0 +1,15 @@
language: clojure
lein: 2.9.0
dist: xenial
jdk:
-openjdk8
script: lein do cljfmt check, eastwood, test :all
deploy:
provider: script
skip_cleanup: true
script: lein deploy
on:
tags: true
cache:
directories:
- $HOME/.m2
25 changes: 25 additions & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,25 @@
# Changelog
All notable changes to this project will be documented in this file.

The format is based on [Keep a Changelog](http://keepachangelog.com/en/1.0.0/).

## [UNRELEASED]

## [0.2.0] - 2021-05-07
### Changed
- Moved namespace coordinates from `uk.me.rkd.ttlcache` to `coop.magnet.ttlcache` (including Clojars repository)
- Updated Clojure version to 1.10.0
- Upgraded dependencies

### Added
- This CHANGELOG
- Added deploy config and build status shield
- Added clj-kondo linting

## [0.1.0] - 2021-05-07
- Original version forked from https://github.com/rkday/ttlcache

[UNRELEASED]: https://github.com/magnetcoop/buddy-auth.jwt-oidc/compare/v0.1.0..HEAD
[0.2.0]: https://github.com/magnetcoop/buddy-auth.jwt-oidc/compare/v0.1.0...v0.2.0
[0.1.0]: https://github.com/magnetcoop/buddy-auth.jwt-oidc/releases/tag/v0.1.0

119 changes: 88 additions & 31 deletions README.md
Original file line number Diff line number Diff line change
@@ -1,49 +1,105 @@
# uk.me.rkd.ttlcache
[![Build Status](https://travis-ci.com/magnetcoop/ttlcache.svg?branch=master)](https://travis-ci.com/magnetcoop/ttlcache)
[![Clojars Project](https://img.shields.io/clojars/v/coop.magnet/ttlcache.svg)](https://clojars.org/coop.magnet/ttlcache)

A Clojure library designed to improve upon core.cache's TTLCache for some use cases. Specifically, it allows cache expiry in less than O(N) time (improving performance when small numbers of entries are expiring), and it allows per-item TTLs rather than a fixed TTL for the whole cache, which is useful for applications like DNS caching or [HTTP caching](https://developers.google.com/speed/articles/caching) where protocol responses specify a TTL.
# coop.magnet.ttlcache - forked from uk.me.rkd.ttlcache

Based on [data.priority-map](https://github.com/clojure/data.priority-map) and [core.cache](https://github.com/clojure/core.cache).
A Clojure library designed to improve upon core.cache's TTLCache for
some use cases. Specifically, it allows cache expiry in less than O(N)
time (improving performance when small numbers of entries are
expiring), and it allows per-item TTLs rather than a fixed TTL for the
whole cache, which is useful for applications like DNS caching or
[HTTP caching](https://developers.google.com/speed/articles/caching)
where protocol responses specify a TTL.

## Usage
Based on [data.priority-map](https://github.com/clojure/data.priority-map)
and [core.cache](https://github.com/clojure/core.cache).

Leiningen: `[uk.me.rkd.ttlcache "0.1.0"]` ([Clojars](https://clojars.org/uk.me.rkd.ttlcache))
## Installation

:require: `[uk.me.rkd.ttlcache :refer [per-item-ttl-cache-factory ttl-cache-factory]]`
[![Clojars Project](https://clojars.org/coop.magnet/ttlcache/latest-version.svg)](https://clojars.org/coop.magnet/ttlcache)

`uk.me.rkd.ttlcache` contains two public functions, both factory functions returning an instance of [CacheProtocol](https://github.com/clojure/core.cache/wiki/Extending):
## Usage
```clojure
(require '[coop.magnet.ttlcache :refer [per-item-ttl-cache-factory ttl-cache-factory]])
```

* `ttl-cache-factory` is designed as a drop-in replacement for the core.cache one, specifying a fixed TTL for the whole cache. See [the core.cache docs](https://github.com/clojure/core.cache/wiki/TTL) for more.
* `per-item-ttl-cache-factory` creates a PerItemTTLCache instance. It takes two arguments - a map of values to seed the cache with, and a function which is applied to the key and value of any added entries, and returns the TTL in seconds (`ttl-cache-factory` is built in this factory, and just supplies `(constantly n`) as the function).
`coop.magnet.ttlcache` contains two public functions, both factory
functions returning an instance of
[CacheProtocol](https://github.com/clojure/core.cache/wiki/Extending):

* `ttl-cache-factory` is designed as a drop-in replacement for the
core.cache one, specifying a fixed TTL (in milliseconds) for the
whole cache. See [the core.cache
docs](https://github.com/clojure/core.cache/wiki/TTL) for more.
* `per-item-ttl-cache-factory` creates a PerItemTTLCache instance. It
takes two arguments:
* a map of values to seed the cache with,
* and a function which is applied to the key and value of any added
entries, and returns the TTL in milli-seconds for the
entries. `ttl-cache-factory` is built in this factory, and just
supplies `(constantly n`) as the function.

The best example is probably the tests:

```clojure
(testing "TTL cache does not return a value that has expired."
(let [C (per-item-ttl-cache-factory {} :ttl-getter (fn [key value] (:ttl value)))]
(is (nil? (-> C
(assoc :a {:val 1 :ttl 500})
(sleepy 700)
(. lookup :a))))))
user> (require '[coop.magnet.ttlcache :refer [per-item-ttl-cache-factory ttl-cache-factory]]
'[clojure.test :refer [testing is]])
nil
user> (def sleepy #(do (Thread/sleep %2) %))
#'user/sleepy
user> (testing "TTL cache does not return a value that has expired."
(let [cache-values {:a {:val 1 :ttl 900}
:b {:val 2 :ttl 500}}
ttlcache (per-item-ttl-cache-factory cache-values :ttl-getter (fn [key value] (:ttl value)))]
(is (= {:val 1 :ttl 900}
(-> ttlcache
(sleepy 700)
(. lookup :a))))
(is (nil? (-> ttlcache
(sleepy 700)
(. lookup :b))))))
true
user>
```

## Big-O complexity

The TTLCache in core.cache uses a pair of maps - one to hold the values and another to hold the TTLs. This means most operations are quite efficient, but expiring items from the cache requires iterating over the whole map, so happens in O(N) time.

This TTLCache uses [data.priority-map](https://github.com/clojure/data.priority-map) to store the TTLs in a priority queue, with O(1) find-min and O(log N) delete-min.

Lookup, insertion and manual cache eviction basically equate to get/assoc/dissoc on a Clojure priority map, so take O(log n) time (marginally worse than O(log32 n) for core.cache, but nonetheless very scalable).

TTL-based expiry (done as part of adding to the cache in both implementations), however, only takes O(M log N) time, where M is the number of items evicted and N is the number of items in the cache. This means it performs better than the core.cache implementation when small numbers of items are being expired at once - in the best case, where no items expire, it is O(1) (just a heap peek).

Expiry of large numbers of items at once is less efficient than core.cache - obviously the scalability of O(M log N) gets closer to O(N) as M gets larger, but also because large numbers of operations on the pure-Clojure priority map perform worse than operations on an ordinary Java-based `transient`-able map. I hope to be able to improve this by using a Java-based persistent heap (e.g. jc-pheap).
In versions prior to 0.6 (when this library was developed), the
TTLCache in core.cache uses a pair of maps - one to hold the values
and another to hold the TTLs. This means most operations were quite
efficient, but expiring items from the cache requires iterating over
the whole map, so happens in O(N) time.

This TTLCache uses
[data.priority-map](https://github.com/clojure/data.priority-map) to
store the TTLs in a priority queue, with O(1) find-min and O(log N)
delete-min.

Lookup, insertion and manual cache eviction basically equate to
get/assoc/dissoc on a Clojure priority map, so take O(log n) time
(marginally worse than O(log32 n) for core.cache, but nonetheless very
scalable).

TTL-based expiry (done as part of adding to the cache in both
implementations), however, only takes O(M log N) time, where M is the
number of items evicted and N is the number of items in the
cache. This means it performs better than the core.cache
implementation at the time, when small numbers of items are being
expired at once - in the best case, where no items expire, it is O(1)
(just a heap peek).

Expiry of large numbers of items at once is less efficient than
core.cache - obviously the scalability of O(M log N) gets closer to
O(N) as M gets larger, but also because large numbers of operations on
the pure-Clojure priority map perform worse than operations on an
ordinary Java-based `transient`-able map.

## Tests vs core.cache

```
$ lein test
lein test uk.me.rkd.core-cache-comparison-test
lein test coop.magnet.core-cache-comparison-test
With 0 out of 5,000 cache items being expired, adding an item to my TTLCache is 230.9435502424312 times faster than the core.cache one
With 50 out of 5,000 cache items being expired, adding an item to my TTLCache is 4.757156584034744 times faster than the core.cache one
With 250 out of 5,000 cache items being expired, adding an item to my TTLCache is 0.752112969429968 times faster than the core.cache one
@@ -65,17 +121,18 @@ My TTLCache: adding an item to a cache with 5,000 entries takes 1.2136739023112

## Running the tests

`lein test uk.me.rkd.ttlcache-test` will run a quick set of unit tests to verify the function.

`lein test uk.me.rkd.core-cache-comparison-test` will run a more exhaustive set of tests based on Criterium to verify that the caches have the expected O(log n) complexity, and to characterise its performance strengths and weaknesses against the core.cache version.

## TODO
`lein test coop.magnet.ttlcache-test` will run a quick set of unit tests
to verify the function.

* Test with [jc-pheap](https://code.google.com/p/jc-pheap/) to see if performance improves over [data.priority-map](https://github.com/clojure/data.priority-map)
`lein test coop.magnet.core-cache-comparison-test` will run a more
exhaustive set of tests based on Criterium to verify that the caches
have the expected O(log n) complexity, and to characterise its
performance strengths and weaknesses against the core.cache version.

## License

Copyright © 2014 Robert Day
Copyright © 2021 Magnet, S. Coop.

Distributed under the Eclipse Public License either version 1.0 or (at
your option) any later version.
35 changes: 27 additions & 8 deletions project.clj
Original file line number Diff line number Diff line change
@@ -1,10 +1,29 @@
(defproject uk.me.rkd.ttlcache "0.1.0"
:description "A variation of core.cache's TTLCache specialised for some different cases"
:url "https://github.com/rkday/ttlcache"
(defproject coop.magnet/ttlcache "0.2.0"
:description "A variation of core.cache's TTLCache specialised for some different cases. Forked from https://github.com/rkday/ttlcache"
:url "https://github.com/magnetcoop/ttlcache"
:license {:name "Eclipse Public License"
:url "http://www.eclipse.org/legal/epl-v10.html"}
:dependencies [[org.clojure/clojure "1.5.1"]
[org.clojure/core.cache "0.6.3"]
[criterium "0.4.3"]
[org.clojure/data.priority-map "0.0.4"]]
:jvm-opts ^:replace ["-server"] )
:dependencies [[org.clojure/clojure "1.10.0"]
[org.clojure/core.cache "1.0.207"]
[criterium "0.4.6"]
[org.clojure/data.priority-map "1.0.0"]]
:deploy-repositories [["snapshots" {:url "https://clojars.org/repo"
:username :env/clojars_username
:password :env/clojars_password
:sign-releases false}]
["releases" {:url "https://clojars.org/repo"
:username :env/clojars_username
:password :env/clojars_password
:sign-releases false}]]
:test-paths ["test"]
:test-selectors {:default (fn [m] (not (or (:integration m) (:regression m))))
:all (constantly true)
:integration :integration
:regression :regression}
:profiles
{:dev [:project/dev :profiles/dev]
:repl {:repl-options {:host "0.0.0.0"
:port 4001}}
:profiles/dev {}
:project/dev {:plugins [[jonase/eastwood "0.3.14"]
[lein-cljfmt "0.7.0"]]}})
83 changes: 83 additions & 0 deletions src/coop/magnet/ttlcache.clj
Original file line number Diff line number Diff line change
@@ -0,0 +1,83 @@
;; Copyright 2014 Rob Day
;; Copyright 2021 Magnet. S. Coop.
;; Released under the EPL
(ns coop.magnet.ttlcache
(:require [clojure.core.cache :refer [CacheProtocol defcache]]
[clojure.data.priority-map :refer [priority-map]]))

(defn- expires
[ttl]
(+ ttl (System/currentTimeMillis)))

(defn- setval
[newkey newval ttl [info ttls]]
[(assoc info newkey newval) (assoc ttls newkey (expires ttl))])

(defn- expire
([cache]
(expire cache (System/currentTimeMillis)))
([[info ttls] now]
(if (empty? ttls)
[(persistent! info) ttls]
(let [[key expires] (peek ttls)]
(if (> now expires)
(recur [(dissoc info key) (pop ttls)] now)
[info ttls])))))

(defcache PerItemTTLCache [cache expiry-heap get-ttl]
CacheProtocol
(lookup [this item]
(let [ret (. this lookup item ::nope)]
(when-not (= ret ::nope) ret)))
(lookup [this item not-found]
(if (. this has? item)
(get cache item)
not-found))
(has? [_ item]
(let [expires (get expiry-heap item 0)]
(< (System/currentTimeMillis) expires)))
(hit [this _]
this)
(miss [_ item result]
(let [updated-cache (setval item result (get-ttl item result) [cache expiry-heap])
after-expiry (expire updated-cache)]
(PerItemTTLCache. (first after-expiry)
(second after-expiry)
get-ttl)))
(seed [_ base]
(let [now (System/currentTimeMillis)]
(PerItemTTLCache. base
(into (priority-map) (for [x base]
[(key x) (+ now (get-ttl (key x) (val x)))]))
get-ttl)))
(evict [_ key]
(PerItemTTLCache. (dissoc cache key)
(dissoc expiry-heap key)
get-ttl))
Object
(toString [_]
(str cache \, \space expiry-heap)))

(defn per-item-ttl-cache-factory
"Returns a TTL cache with the cache and expiration-table initialied to `base` --
each item in `base` with its own time-to-live.
This function also takes a `:get-ttl` keyword argument that defines
a function which is applied to the key and value of any added entry,
and is expected to return the TTL -in milli-seconds- for the entry."
[base & {get-ttl :ttl-getter}]
{:pre [(map? base)
(fn? get-ttl)]}
(clojure.core.cache/seed (PerItemTTLCache. {} (priority-map) get-ttl) base))

(defn ttl-cache-factory
"Returns a TTL cache with the cache and expiration-table initialied to `base` --
each with the same time-to-live.
This function also allows an optional `:ttl` argument that defines the default
time in milliseconds that entries are allowed to reside in the cache. If not
specified, a default of 2000 milliseconds is used."
[base & {ttl :ttl :or {ttl 2000}}]
{:pre [(and (number? ttl) (<= 0 ttl))
(map? base)]}
(per-item-ttl-cache-factory base :ttl-getter (constantly ttl)))
Loading