public
Last active

Simple Cache for nodejs with nodeunit test.

  • Download Gist
cache-test.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
/**
* Unit tests for the simple-cache
* @author Kim root@aggressive-solutions.de
* @version 0.2
*/
var lfuCache = require('./lfu-cache.js');
 
exports.testSmart = function (test) {
test.expect(3);
 
// create a smart cache
var cache = new lfuCache.Cache();
var opts = {
capacity: 4,
replacement: 'smart'
};
cache.init(opts);
 
// use cache
cache.add(0, 'Null');
cache.add(1, 'One');
 
var value = cache.get(0);
test.equal(value, 'Null', 'Wrong value stored.');
 
// fill up cache
cache.add('Noise1', 123123);
cache.add('Noise2', 'useless');
 
cache.add('Two', 'Two!');
 
value = cache.get(1);
test.ok(!value, 'Value still in cache!');
 
value = cache.get('Two');
test.equal(value, 'Two!', 'Value still in cache!');
 
test.done();
 
cache.logContent();
}
 
exports.testInit = function (test) {
test.expect(1);
var cache = new lfuCache.Cache();
cache.init();
test.equal(cache.size(), 0, 'Cache is NOT empty!');
test.done();
};
 
exports.testInitOptions = function (test) {
test.expect(4);
var cache = new lfuCache.Cache();
var options = {
capacity: 2,
maxFrequency: 2,
replacement: 'lfu'
};
cache.init(options);
cache.add(0, 'Null');
cache.add(3, 'Three');
 
cache.add(1, 'One');
test.ok(cache.get(1), '1 Is NOT in cache.');
 
cache.add(2, 'Two');
test.ok(cache.get(2), '2 Is NOT in cache.');
 
//~ cache.logContent();
test.ok(!cache.get(0), '0 Is in cache.');
test.equal(cache.size(), 2, 'Capacity is NOT two.');
test.done();
};
 
exports.testAdd = function (test) {
test.expect(2);
var cache = new lfuCache.Cache();
cache.init();
cache.add('A', 'AAA');
cache.add(1, 'BBB');
 
test.equal(cache.size(), 2, 'Two entries are NOT in cache.');
cache.add('0', 'NULL!');
cache.add('1', 'TWO');
test.equal(cache.size(), 3, 'Four entries in cache expected.');
test.done();
};
 
exports.testSimpleAdd = function (test) {
test.expect(2);
var cache = new lfuCache.Cache();
cache.init();
cache.add('value is key.');
test.equal(cache.get('value is key.'), 'value is key.' );
var data = {
data: 1,
toString: function () {
return 'my custom key.';
}
};
cache.add(data);
test.equal(cache.get('my custom key.'), data );
test.done();
};
 
/*
* ----------------------------------------------------------------------------
* "THE BEER-WARE LICENSE" (Revision 42):
* <root@aggressive-solutions.de> wrote this file. As long as you retain this
* notice you can do whatever you want with this stuff. If we meet some day,
* and you think this stuff is worth it, you can buy me a beer in return. KIM
* ----------------------------------------------------------------------------
*/
cache.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324
/**
* A simple cache for key value pairs.
* Options are:
* capacity: default 512 entries
* replacement: default 'smart', 'lfu'
* maxFrequency: freqeuncy saturation for 'lfu', default 16
*
* LFU replacement:
* LFU stands for least freqeuntly used. If multiple canidates are LFU then the oldest cache entry
* is removed. The usage frequency of an entry saturates, the default maxmimum frequency is 16.
*
* SMART replacement:
* Oldest cache entry with the lowest smart value is replaced. The start smart value
* is cache capacity / 2. On a cache hit the entry's smart value is set to cache capacity.
* On a cache miss all entries' smart value is decreased by one but not less than zero.
* (If you know the proper name of this cache algorithm, please drop me an email.)
*
* Write strategy:
* You have to enforce the write strategy yourself. The cached object can write-through every change
* or you can write-back the object when it is replaced. For a write-back strategy the .add() method
* returns the replaced entry if any.
*
* See the basic usage in the unit tests. On a cache miss you have to retrieve
* the value for your data source and store it in the cache with an appropiate key.
* If a cache entry with the same key already exists, the old entry is replaced.
*
* @author Kim root@aggressive-solutions.de
* @version 0.3
*/
 
var assert = require('assert');
 
/**
* Creates a new Cache.
* @constructor
*/
exports.Cache = function() {
var buffer = {};
var hits = 0;
var miss = 0;
 
/**
* Default options
* @private
*/
var defaultOptions = {
capacity: 512,
maxFrequency: 16,
replacement:'smart'
};
var options = {};
 
/**
* Apply options.
* @private
*/
function setOptions(opts)
{
// set the options provided or keep default.
var o;
for(o in opts) {
if( opts.hasOwnProperty(o) ) {
options[o] = opts[o];
}
}
 
assert.ok(options.capacity > 0, 'Cache capacity must be greater than 0.');
assert.ok(options.maxFrequency > 0, 'Cache max freqeuncy must be greater than 0.');
}
setOptions(defaultOptions);
 
/**
* Get internal buffer size
* @private
* @returns {integer} size
*/
function getBufferSize() {
var size = 0, key;
for (key in buffer) {
if( buffer.hasOwnProperty(key) ) {
size++;
}
}
return size;
};
 
/**
* Remove the least frequently used entry and return it.
* @private
* @returns The removed entry
*/
function removeLfu() {
var size = 0,
key,
minFreq = options.maxFrequency,
candidate;
 
for (key in buffer) {
if( buffer.hasOwnProperty(key) ) {
var entry = buffer[key];
 
// TRICKY: oldest entry is the first and
// also default remove candidate.
if(entry.reads < minFreq || !candidate) {
// console.log('New LFU key: ' + key + ' reads: ' + entry.reads);
candidate = key;
minFreq = entry.reads;
}
}
}
 
var value;
if(candidate) {
value = buffer[candidate].value;
// console.log('Deleting key: ' + candidate);
delete buffer[candidate];
}
return value;
}
 
/**
* Remove the recently least useful or oldest entry and return it.
* @private
* @returns The removed value.
*/
function removeSmart() {
var key;
var candidate;
var minUseful = options.capacity;
 
for(key in buffer) {
if( buffer.hasOwnProperty(key) ) {
var entry = buffer[key];
// TRICKY: First entry is also the oldest.
// console.log('key: ' + key.toString() + ' smart: ' + entry.smart);
if(entry.smart < minUseful || !candidate) {
minUseful = entry.smart;
candidate = key;
}
}
}
 
var value;
if(candidate) {
value = buffer[candidate].value;
// console.log('SMART deleting key: ' + candidate);
delete buffer[candidate];
}
 
return value;
}
 
/**
* Get the current cache size.
* @public
* @return {integer} Size
*/
this.size = getBufferSize;
 
/**
* Initialize cache. Calling it again resets cache and its statistics.
* Missing options will set default cache options.
* @public
* @param {Object} opt Options capacity and maxFrequency (LFU limit)
*/
this.init = function (opts) {
buffer = {};
hits = 0;
miss = 0;
 
if(!opts) {
setOptions(defaultOptions);
return;
}
 
setOptions(opts);
}
 
/**
* Add key value pair to cache. Returns the relpaced entry if any. This
* is required by some write strategies.
* @public
* @param key Must be a string or have a .toString() method.
* @param value The actual value to cache.
* @returns The replaced entry if any, null otherwise.
*/
this.add = function(key, value) {
 
assert.ok(typeof key.toString === 'function', 'Key has no .toString()');
 
if(!value) {
value = key;
}
 
var entry = {
value: value,
reads: 0, // access frequency
smart: options.capacity / 2 // smart value of entry (higher is more useful)
};
 
var old;
if(getBufferSize() >= options.capacity) {
// console.log('cache is full.');
if(options.replacement === 'smart') {
old = removeSmart();
} else {
old = removeLfu();
}
}
 
// console.log('Adding key: ' + key + ' value: ' + value);
buffer[key.toString()] = entry;
 
return old;
};
 
/**
* Handle cache miss
* @private
*/
function handleMiss() {
miss += 1;
if(options.replacement === 'smart') {
var key;
for(key in buffer) {
if( buffer.hasOwnProperty(key) ) {
// decrease smart value of all entries because
// they were not useful.
var entry = buffer[key];
entry.smart -= 1;
entry.smart = Math.max(entry.smart, 0);
}
else
{
 
}
}
}
else {
// lfu
// NOTHING TODO HERE!
}
}
 
/*
* handle cache hit
* @private
*/
function handleHit(entry) {
hits += 1;
if(options.replacement === 'smart') {
// entry was useful, set highest value
entry.smart = options.capacity;
}
else {
entry.reads += 1;
entry.reads = Math.min(entry.reads, options.maxFrequency);
}
}
 
/**
* Get the value for the given key.
* @public
* @param key Must be string or have a toString() method.
* @returns The value if the key exists, null otherwise.
*/
this.get = function(key) {
 
var entry = buffer[key.toString()];
if(!entry) {
handleMiss();
// console.log('key: ' + key + ' MISS!');
return null;
}
 
handleHit(entry);
// console.log('key: ' + key + ' HIT! reads: ' + entry.reads);
return entry.value;
};
 
/**
* Get cache statatistics
* @public
*/
this.getStatistics = function() {
var stats = {
hits: hits,
miss: miss,
hit_rate: hits / (hits+miss),
hit_ratio: hits/miss,
capacity: options.capacity,
size: getBufferSize(),
maxFrequency: options.maxFrequency,
replacement: options.replacement
};
 
return stats;
};
 
this.logContent = function() {
var key,
counter = 0;
 
console.log('--- Cache ---');
for (key in buffer) {
if( buffer.hasOwnProperty(key) ) {
var entry = buffer[key.toString()];
console.log(counter + '. key: ' + key + ' value: ' +
entry.value + ' reads: ' + entry.reads + ' smart: ' +
entry.smart);
counter += 1;
}
}
};
};
 
/*
* ----------------------------------------------------------------------------
* "THE BEER-WARE LICENSE" (Revision 42):
* <root@aggressive-solutions.de> wrote this file. As long as you retain this
* notice you can do whatever you want with this stuff. If we meet some day,
* and you think this stuff is worth it, you can buy me a beer in return. KIM
* ----------------------------------------------------------------------------
*/

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.