title: How to implement a counter that decays over time?
body: <h2>Requirements of special counter</h2>
  
  <p>I want to implement a special counter: all increment operations time out after a fixed period of time (say 30 days).</p>
  
  <p>An example:</p>
  
  <ul>
  <li>Day 0: counter = 0. TTL = 30 days</li>
  <li>Day 1: increment counter (+1)</li>
  <li>Day 2: increment counter (+1)</li>
  <li>Day 3: value of counter == 2</li>
  <li>Day 31: value of counter == 1</li>
  <li>Day 32: value of counter == 0</li>
  </ul>
  
  <h2>Naive solution</h2>
  
  <p>A naïve implementation is to maintain a set of timestamps, where each timestamp equals the time of an increment. The value of the counter equals the size of the set after subtracting all timestamps that have timed out.</p>
  
  <p>This naïve counter has O(n) space (size of the set), has O(n) lookup and O(1) inserts. The values are exact.</p>
  
  <h2>Better solution (for me)</h2>
  
  <p><em>Trade speed and memory for accuracy.</em></p>
  
  <p>I want a counter with O(1) lookup and insert, O(1) space. The accuracy &lt; exact. </p>
  
  <p>Alternatively, I would accept O(log n) space and lookup.</p>
  
  <p>The counter representation should be suited for storage in a database field, i.e., I should be able to update and poll the counter rapidly without too much (de)serialization overhead.</p>
  
  <p>I'm essentially looking for a counter that resembles a HyperLogLog counter, but for a different type of approximate count: decaying increments vs. number of distinct elements</p>
  
  <p>How could I implement such a counter?</p>