Implement garbage collector for dict backend

[youknowone]

Because dict backend doesn't have any gc machansm, it can be infinitely inflated.
For now, this is warned in documentation but GC will make everyone happy even who doesn't read document.

Decision background: The most important feature of dict backend is transparency. So that user always can access to the bare key/value data of the backend. Due to this limitation, encoding or adding metadata is not a preferred way for dict backend.

Policy:

• Do not gc unless its size hits maxsize
• Default value of maxsize is 128. Let's follow @ring.lru interface for maxsize.
• Once it hits the maxsize, the gc removes at least 25% of maxsize.
• GC runs 2 strategies one by one.
  • 1st strategy
    • (psuedo) Randomly pick an element and check it is expired.
    • If expired, remove it and run 1st strategy again; otherwise increase missing counter.
    • Once the missing counter hits 4, exit from the strategy.
  • Condition checking: If gc succeeed to remove more than 25% of garbages, stop here.
  • 2nd strategy
    • Randomly pick an element and remove until the size goes less than 75% of maxsize

[amsukdu]

Hello sir,
I think I can work on this. Will you let me?

[youknowone]

Hello! Thanks to participate in this project.

Any kind of participation is welcomed and appreciated.
Of course you can take this over. Please don't hesitate to share any question, problem or suggestion you encounter during this work.

[amsukdu]

Quite a few questions but I think you'll answer these with delight 😄

1. if the user didn't define expire, we go straight to strategy 2, right?
2. Does missing counter have to be parameterized?
3. You noted

Condition checking: If gc succeeed to remove more than 25% of garbages, stop here.

but I think it could be maxsize not garbages. If it really is garbages, I assume we have to count all of the garbages based on the expire.

4. storage_class seems like a wrapper of the actual backend cache storage, such as obj. If the storage_class can be injected by the user, how can we track all the getters and setters?

[youknowone]

1. Yes
2. For now, I don't think so. A constant variable seems enough.
3. Yes. 25% of maxsize is correct.
4. It is up to users. If someone replaced the storage (implementation), it means they needs their own behaviors. So we only need to implement this feature into the default storage class.