Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMike Gerwitz <gerwitzm@lovullo.com>2016-12-30 15:31:31 -0500
committerMike Gerwitz <gerwitzm@lovullo.com>2017-01-04 16:17:37 -0500
commit7d9756902703c9f2c2cccb6285477b4f27a800e6 (patch)
tree9dce02b13c83372f7e4ea8c8ad4b3e0bbbb4bf6b
parent0be39adfdb2ebe7afbb963a2180294b1f62bd57d (diff)
downloadliza-7d9756902703c9f2c2cccb6285477b4f27a800e6.tar.gz
liza-7d9756902703c9f2c2cccb6285477b4f27a800e6.tar.bz2
liza-7d9756902703c9f2c2cccb6285477b4f27a800e6.zip
Add MissLookup trait
* src/store/MissLookup.js: Add trait. * test/store/MissLookupTest.js: Add test case.
-rw-r--r--src/store/MissLookup.js163
-rw-r--r--test/store/MissLookupTest.js163
2 files changed, 326 insertions, 0 deletions
diff --git a/src/store/MissLookup.js b/src/store/MissLookup.js
new file mode 100644
index 0000000..b3f3aea
--- /dev/null
+++ b/src/store/MissLookup.js
@@ -0,0 +1,163 @@
+/**
+ * Auto-lookup for store misses
+ *
+ * Copyright (C) 2016 LoVullo Associates, Inc.
+ *
+ * This file is part of the Liza Data Collection Framework
+ *
+ * Liza is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+var Trait = require( 'easejs' ).Trait,
+ Class = require( 'easejs' ).Class,
+ Store = require( './Store' );
+
+
+/**
+ * Automatically try to look up values on store miss
+ *
+ * A common use case for key/value stores is caching. Unless the
+ * cache is being warmed by another system, it's likely that the
+ * caller will process whatever item is missing and then immediately
+ * add it to the cache. This simplifies that situation by
+ * automatically calling a function on miss and holding the request
+ * until the datum becomes available.
+ *
+ * To guard against stampeding, and to relieve callers from handling
+ * other concurrency issues, all requests for the same key will return
+ * the same promise until that promise is resolved or rejected (see
+ * `#get`).
+ *
+ * @example
+ * function lookup( key )
+ * {
+ * return Promise.resolve( key + ' foobar' );
+ * }
+ *
+ * let store = Store.use( MissLookup( lookup ) );
+ *
+ * store.get( 'unknown' )
+ * .then( function( value )
+ * {
+ * // value 'unknown foobar'
+ * } );
+ *
+ * This trait can also be used purely to prevent stampeding by
+ * providing a miss function that is effectively a noop for a given
+ * situation.
+ */
+module.exports = Trait( 'MissLookup' )
+ .implement( Store )
+ .extend(
+{
+ /**
+ * Store miss key lookup function
+ *
+ * @type {function(string)}
+ */
+ 'private _lookup': null,
+
+ /**
+ * Unresolved promises for misses, by key
+ *
+ * @type {Object}
+ */
+ 'private _misses': {},
+
+
+ /**
+ * Initialize key miss lookup
+ *
+ * The unary miss lookup function `lookup` will be provided with
+ * the key of the store item that missed and should return the
+ * intended value of that item. The resulting item will be stored
+ * and returned. If no item is found, `lookup` should return
+ * `undefined`.
+ *
+ * @param {function(string): Promise} lookup store miss key lookup
+ */
+ __mixin: function( lookup )
+ {
+ if ( typeof lookup !== 'function' )
+ {
+ throw TypeError( 'Lookup function must be a function' );
+ }
+
+ this._lookup = lookup;
+ },
+
+
+ /**
+ * Retrieve item from the store under `key`, attempting lookup on
+ * store miss
+ *
+ * In the event of a miss, the looked up value is added to the
+ * store. This method waits for the add operation to complete
+ * before fulfilling the promise by re-requesting the key from the
+ * supertype (allowing it to do its own thing).
+ *
+ * On the first miss for a given key `K`, a promise `P` is stored.
+ * To prevent stampeding and other awkward concurrency issues,
+ * all further requests for `K` will receive the same promise
+ * `P` until it is resolved.
+ *
+ * A word of caution: if the lookup function does not return a
+ * value, it will continue to be called for each request
+ * thereafter. This might not be a good thing if the lookup
+ * operating is intensive, so the lookup should take into
+ * consideration this possibility.
+ *
+ * @param {string} key store key
+ *
+ * @return {Promise} promise for the key value
+ */
+ 'virtual abstract override public get': function( key )
+ {
+ var _self = this,
+ __super = this.__super.bind( this );
+
+ // to prevent stampeding, return any existing unresolved
+ // promise for this key
+ if ( this._misses[ key ] )
+ {
+ return this._misses[ key ];
+ }
+
+ // note that we have to store the reference immediately so we
+ // don't have two concurrent failures, so this will store a
+ // promise even if the key already exists (which is okay)
+ return this._misses[ key ] = this.__super( key )
+ .then( function( value )
+ {
+ // already exists
+ delete _self._misses[ key ];
+
+ return value;
+ } )
+ .catch( function()
+ {
+ delete _self._misses[ key ];
+
+ return _self._lookup( key )
+ .then( function( value )
+ {
+ return _self.add( key, value );
+ } )
+ .then( function()
+ {
+ return __super( key );
+ } );
+ } );
+ },
+} );
diff --git a/test/store/MissLookupTest.js b/test/store/MissLookupTest.js
new file mode 100644
index 0000000..2c7e7d3
--- /dev/null
+++ b/test/store/MissLookupTest.js
@@ -0,0 +1,163 @@
+/**
+ * Test case for Cascading store
+ *
+ * Copyright (C) 2016 LoVullo Associates, Inc.
+ *
+ * This file is part of the Liza Data Collection Framework
+ *
+ * Liza is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+"use strict";
+
+var Class = require( 'easejs' ).Class,
+ store = require( '../../' ).store,
+ chai = require( 'chai' ),
+ expect = chai.expect,
+ Store = store.MemoryStore,
+ Sut = store.MissLookup;
+
+chai.use( require( 'chai-as-promised' ) );
+
+const StubStore = Class.extend( Store,
+{
+ 'virtual override get': function( key )
+ {
+ return this.__super( key )
+ .then( val => val + ' get' );
+ },
+} );
+
+
+describe( 'store.MissLookup', () =>
+{
+ it( 'requires function for cache miss', () =>
+ {
+ expect( () => StubStore.use( Sut( {} ) )() )
+ .to.throw( TypeError );
+ } );
+
+ it( 'invokes lookup on cache miss', () =>
+ {
+ const expected = 'quux';
+ const miss = ( key ) => Promise.resolve( key + expected );
+ const sut = StubStore.use( Sut( miss ) )();
+
+ // key + expected + StubStore#get
+ return Promise.all( [
+ expect( sut.get( 'foo' ) )
+ .to.eventually.equal( 'foo' + expected + ' get' ),
+
+ expect( sut.get( 'bar' ) )
+ .to.eventually.equal( 'bar' + expected + ' get' ),
+ ] );
+ } );
+
+
+ it( 'caches miss lookup', () =>
+ {
+ let calln = 0;
+
+ const expected = {};
+
+ function miss()
+ {
+ // should not be called more than once
+ expect( ++calln ).to.equal( 1 );
+ return Promise.resolve( expected );
+ }
+
+ const sut = Store.use( Sut( miss ) )();
+
+ // should miss
+ return expect( sut.get( 'foo' ) ).to.eventually.equal( expected )
+ .then( () =>
+ {
+ // should not miss
+ expect( sut.get( 'foo' ) ).to.eventually.equal( expected );
+ } );
+ } );
+
+
+ it( 'does not miss on existing cache item', () =>
+ {
+ const fail = () => { throw Error( 'Should not have missed' ) };
+ const sut = Store.use( Sut( fail ) )();
+
+ return expect(
+ sut.add( 'foo', 'bar' )
+ .then( () => sut.get( 'foo' ) )
+ ).to.eventually.equal( 'bar' );
+ } );
+
+
+ // prevent stampeding and concurrency issues
+ it( 'shares promise given concurrent miss requests', () =>
+ {
+ let n = 0;
+ let resolve = null;
+
+ const p = new Promise( r => resolve = r );
+
+ // return our mock promise, which should only be once (after
+ // that, the SUT should have cached the promise)
+ function miss()
+ {
+ if ( n++ > 0 ) throw Error( 'Miss called more than once' );
+ return p;
+ }
+
+ const sut = Store.use( Sut( miss ) )();
+
+ // set of three promises, each on the same key
+ const misses = [ 1, 2, 3 ].map( i => sut.get( 'foo' ) );
+
+ // we don't really care what promises were returned to us
+ // (that's an implementation detail), but we do care that they
+ // all resolve once we resolve our promise
+ resolve( true );
+
+ return Promise.all( misses );
+ } );
+
+
+ it( 'does not share old promise after miss resolves', () =>
+ {
+ let missret = {};
+
+ const key = 'foo';
+ const miss1 = {};
+ const miss2 = {};
+
+ function miss()
+ {
+ return Promise.resolve( missret );
+ }
+
+ const sut = Store.use( Sut( miss ) )();
+
+ missret = miss1;
+
+ return sut.get( key )
+ .then( val => expect( val ).to.equal( miss1 ) )
+ .then( () =>
+ {
+ sut.clear();
+
+ missret = miss2;
+ return sut.get( key )
+ .then( val => expect( val ).to.equal( miss2 ) )
+ } );
+ } );
+} );