Repository: youknowone/ring

Issue:
Expirable LRU cache
For now, `@ring.lru` ignores `expire` parameter.

In this case, expiration maybe not very correct.

A suggestion.
- Put timestamp into 5th paramter of `link`.
- For hot items, it will be expired by checking timestamp at next `get`.
- For cold items, it will be smoothly expired by LRU logic.

LruCache source: https://github.com/youknowone/ring/blob/master/ring/func/lru_cache.py

- Will it need a separated class like PersistantDict and ExpirableDict?
  - Probably not.

Discussion:
JimJeon: This PR fixes #107 
JimJeon: Python 2.7 Build fails, I'll fix it.
youknowone: Thanks! It seems everything goes well. Installing this module for py2 will work: https://pypi.org/project/mock/
JimJeon: It was already in the setup.py package list. I just added some compatibility codes.
codecov[bot]: # [Codecov](https://codecov.io/gh/youknowone/ring/pull/121?src=pr&el=h1) Report
> Merging [#121](https://codecov.io/gh/youknowone/ring/pull/121?src=pr&el=desc) into [master](https://codecov.io/gh/youknowone/ring/commit/14a2ed761c5ce773eea9d9ca076f48203c561fb2?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `97.14%`.


```diff
@@            Coverage Diff             @@
##           master     #121      +/-   ##
==========================================
- Coverage   98.02%   98.02%   -<.01%     
==========================================
  Files          14       14              
  Lines        1415     1463      +48     
==========================================
+ Hits         1387     1434      +47     
- Misses         28       29       +1
```





Patch:
diff --git a/ring/func/lru_cache.py b/ring/func/lru_cache.py
index 47e3649..7333811 100644
--- a/ring/func/lru_cache.py
+++ b/ring/func/lru_cache.py
@@ -2,6 +2,7 @@
 # This file follows PYTHON SOFTWARE FOUNDATION LICENSE VERSION 2 as CPython
 # does.
 
+import time
 from threading import RLock
 
 try:
@@ -12,13 +13,15 @@ except ImportError:
         "CacheInfo", ["hits", "misses", "maxsize", "currsize"])
 
 SENTINEL = object()  # unique object used to signal cache misses
-PREV, NEXT, KEY, RESULT = 0, 1, 2, 3  # names for the link fields
+PREV, NEXT, KEY, RESULT, EXPIRE = 0, 1, 2, 3, 4  # names for the link fields
 FULL, HITS, MISSES = 0, 1, 2  # names for stat
 
 
 class LruCache(object):
     """Created by breaking down functools.lru_cache from CPython 3.7.0."""
 
+    now = time.time
+
     def __init__(self, maxsize):
         cache = {}
         cache_get = cache.get  # bound method to lookup a key or return None
@@ -26,16 +29,23 @@ class LruCache(object):
         lock = RLock()     # because linkedlist updates aren't threadsafe
         self.root = []   # root of the circular doubly linked list
         # initialize by pointing to self
-        self.root[:] = [self.root, self.root, None, None]
+        self.root[:] = [self.root, self.root, None, None, None]
         stat = [False, 0, 0]
 
+        def expiration_time(expire):
+            if expire is None:
+                return expire
+            return self.now() + expire
+
         def get(key):
+            _now = self.now()
             with lock:
                 link = cache_get(key)
-                if link is not None:
+                if link is not None and \
+                        (link[EXPIRE] is None or _now < link[EXPIRE]):
                     root = self.root
                     # Move the link to the front of the circular queue
-                    link_prev, link_next, _key, result = link
+                    link_prev, link_next, _key, result, _ = link
                     link_prev[NEXT] = link_next
                     link_next[PREV] = link_prev
                     last = root[PREV]
@@ -46,25 +56,40 @@ class LruCache(object):
                     return result
                 else:
                     stat[MISSES] += 1
+                    if link is not None:
+                        _delete(key)
             return SENTINEL
 
+        def _delete(key):
+            oldresult = self.root[RESULT]  # noqa
+            # delete from the linked list
+            link = cache[key]
+            link_prev, link_next, _, _, _ = link
+            link_prev[NEXT] = link_next
+            link_next[PREV] = link_prev
+
+            # delete from the cache
+            del cache[key]
+            stat[FULL] = False
+
         def delete(key):
             with lock:
-                oldresult = self.root[RESULT]  # noqa
-                del cache[key]
-                stat[FULL] = False
+                _delete(key)
 
-        def set(key, result):
+        def set(key, result, expire=None):
+            expired_time = expiration_time(expire)
             with lock:
                 link = cache_get(key)
                 if link is not None:
                     # Update link to store the new result
-                    link[-1] = result
+                    link[RESULT] = result
+                    link[EXPIRE] = expired_time
                 elif stat[FULL]:
                     # Use the old root to store the new key and result.
                     oldroot = self.root
                     oldroot[KEY] = key
                     oldroot[RESULT] = result
+                    oldroot[EXPIRE] = expired_time
                     # Empty the oldest link and make it the new root.
                     # Keep a reference to the old key and old result to
                     # prevent their ref counts from going to zero during the
@@ -85,7 +110,7 @@ class LruCache(object):
                     root = self.root
                     # Put result in a new link at the front of the queue.
                     last = root[PREV]
-                    link = [last, root, key, result]
+                    link = [last, root, key, result, expired_time]
                     last[NEXT] = root[PREV] = cache[key] = link
                     # Use the cache_len bound method instead of the len() function
                     # which could potentially be wrapped in an lru_cache itself.
@@ -116,14 +141,17 @@ class LruCache(object):
             with lock:
                 return key in cache
 
-        def touch(key):
+        def touch(key, expire=None):
+            expired_time = expiration_time(expire)
             with lock:
                 root = self.root
                 link = cache_get(key)
                 if link is None:
                     raise KeyError
                 # Move the link to the front of the circular queue
-                link_prev, link_next, _key, result = link
+                link_prev, link_next, _key, result, _ = link
+                # Also, update expiration time
+                link[EXPIRE] = expired_time
                 link_prev[NEXT] = link_next
                 link_next[PREV] = link_prev
                 last = root[PREV]
diff --git a/ring/func/sync.py b/ring/func/sync.py
index 496e4b2..07e042b 100644
--- a/ring/func/sync.py
+++ b/ring/func/sync.py
@@ -191,7 +191,7 @@ class LruStorage(fbase.CommonMixinStorage, fbase.StorageMixin):
         return self.backend.has(key)
 
     def set_value(self, key, value, expire):
-        self.backend.set(key, value)
+        self.backend.set(key, value, expire)
 
     def delete_value(self, key):
         try:
@@ -398,7 +398,7 @@ class DiskCacheStorage(fbase.CommonMixinStorage, fbase.StorageMixin):
 
 
 def lru(
-        lru=None, key_prefix=None, coder=None,
+        lru=None, key_prefix=None, expire=None, coder=None,
         user_interface=CacheUserInterface, storage_class=LruStorage,
         maxsize=128, **kwargs):
     """LRU(Least-Recently-Used) cache interface.
@@ -427,7 +427,6 @@ def lru(
     :see: :func:`functools.lru_cache` for LRU cache basics.
     :see: :func:`ring.func.sync.CacheUserInterface` for sub-functions.
     """
-    expire = None
     if lru is None:
         lru = lru_mod.LruCache(maxsize)
         if key_prefix is None:


Test patch:
diff --git a/tests/test_lru_cache.py b/tests/test_lru_cache.py
index 54ba45a..d4658eb 100644
--- a/tests/test_lru_cache.py
+++ b/tests/test_lru_cache.py
@@ -7,6 +7,11 @@ except ImportError:
     def _make_key(args, kwds, typed):
         return args, tuple(sorted(kwds.items()))
 
+try:
+    from unittest.mock import MagicMock
+except ImportError:
+    from mock import MagicMock
+
 
 def test_lru_cache_porting():
     def lru_cache(maxsize=128, typed=False):
@@ -67,3 +72,27 @@ def test_lru_object():
         assert SENTINEL is lru.get(c)
 
     lru.cache_info()
+
+
+def test_expire_object():
+    lru = LruCache(3)
+
+    now_mock = MagicMock()
+    now_mock.return_value = 0
+    lru.now = now_mock
+
+    lru.set('a', 10, expire=1)
+    lru.set('b', 20, expire=2)
+    lru.set('c', 30, expire=3)  # a - b - c
+    # Check if cache works well
+    assert lru.get('a') == 10  # b - c - a
+    # Check if 'a' key expired
+    now_mock.return_value = 1
+    assert lru.get('a') == SENTINEL  # b - c
+    # Check if lru logic works well
+    lru.set('d', 40, expire=4)  # b - c - d
+    assert lru.get('b') == 20  # c - d - b
+    # Check if 'c' key not expired
+    assert lru.get('c') == 30  # d - b - c
+    lru.set('e', 50)  # b - c - e
+    assert lru.get('d') == SENTINEL