anchor.diff:      [F(X) || X <- lists:seq(1,10)],
       consistency_check(C).
   
  -consistency_check(#kv_lru { cache = Cache,
  -			    age_idx = AgeCache,
  -			    bucket_idx = BucketIdx }) ->
  -    S = ets:info(Cache, size),
  -    S = ets:info(AgeCache, size),
  -    S = ets:info(BucketIdx, size),
  -    true.
  +%% Make sure that riak_kv_lru is correct under concurrent modification
  +%% by spawning 10 processes that each do 1000 puts on the same LRU, then
  +%% checking that the size limit of the cache has been respected
  +%% (added to check https://issues.basho.com/show_bug.cgi?id=969)
  +concurrency_test() ->
  +    Size = 10,
  +    C = riak_kv_lru:new(Size),
  +    Pids = [ spawn_link(concurrent_incrementer(C, K, self()))
  +             || K <- lists:seq(10000, 10010) ],
  +    wait_for_incrementers(Pids),
  +    consistency_check(C),
  +    ?assertEqual(Size, riak_kv_lru:size(C)).
  +
  +concurrent_incrementer(C, K, Test) ->
  +    fun() ->
  +            [ riak_kv_lru:put(C, N+K, N+K, N+K)
  +              || N <- lists:seq(1, 1000) ],
  +            Test ! {increment_done, self()}
  +    end.
  +
  +wait_for_incrementers([]) -> ok;
  +wait_for_incrementers(Pids) ->
  +    receive {increment_done, Pid} ->
  +            wait_for_incrementers(lists:delete(Pid, Pids))
  +    after 5000 ->
  +            throw(incrementer_timeout)
  +    end.
  +
  +consistency_check(LRU) ->
  +    Ts = table_sizes(LRU),
  +    %% make sure all tables report same size
  +    UniqueSizes = lists:usort([ Size || {_Name, Size} <- Ts]),
  +    ?assertEqual(1, length(UniqueSizes)).
   
   -endif.
  
positive.code:          max_size/1,
           clear/1,
           clear_bkey/2,
           destroy/1]).
  
  -record(kv_lru, {max_size,
                   bucket_idx,
  
negative.code:                        ts}).
  
  new(0) ->
      nocache;
  new(Size) ->
      {ok, Pid} = gen_server:start_link(?MODULE, [Size], []),
      Pid.
  
  put(nocache, _BKey, _Key, _Value) ->
      ok;
  put(Pid, BKey, Key, Value) ->
      gen_server:cast(Pid, {put, BKey, Key, Value}).
  
  fetch(nocache, _BKey, _Key) ->
      notfound;
  fetch(Pid, BKey, Key) ->
      gen_server:call(Pid, {fetch, BKey, Key}).
  
  remove(nocache, _BKey, _Key) ->
      ok;
  remove(Pid, BKey, Key) ->
      gen_server:cast(Pid, {remove, BKey, Key}).
  
  size(nocache) ->
      0;
  size(Pid) ->
      gen_server:call(Pid, size).
  
  max_size(nocache) ->
      0;
  max_size(Pid) ->
      gen_server:call(Pid, max_size).
  
  clear(nocache) ->
      ok;
  clear(Pid) ->
      gen_server:cast(Pid, clear).
  
  clear_bkey(nocache, _BKey) ->
      ok;
  clear_bkey(Pid, BKey) ->
      gen_server:cast(Pid, {clear_bkey, BKey}).
  
  destroy(nocache) ->
      ok;
  destroy(Pid) ->
      gen_server:call(Pid, destroy).
  
  %% for test usage
  table_sizes(Pid) ->
      gen_server:call(Pid, table_sizes).
  
  init([Size]) ->
      IdxName = pid_to_list(self()) ++ "_cache_age_idx",
      BucketIdxName = pid_to_list(self()) ++ "_bucket_idx",
      CacheName = pid_to_list(self()) ++ "_cache",
      Idx = ets:new(list_to_atom(IdxName), [ordered_set, private]),
      BucketIdx = ets:new(list_to_atom(BucketIdxName), [bag, private]),
      Cache = ets:new(list_to_atom(CacheName), [private, {keypos, 2}]),
      {ok, #kv_lru{max_size=Size, age_idx=Idx, bucket_idx=BucketIdx, cache=Cache}}.
  
  handle_call({fetch, BKey, Key}, _From, State) ->
      Reply = fetch_internal(State, BKey, Key),
      {reply, Reply, State};
  handle_call(size, _From, State) ->
      Reply = size_internal(State),
      {reply, Reply, State};
  handle_call(max_size, _From, State) ->
      Reply = max_size_internal(State),
      {reply, Reply, State};
  handle_call(destroy, _From, State) ->
      {Reply, NewState} = destroy_internal(State),
      {stop, normal, Reply, NewState};
  handle_call(table_sizes, _From, State) ->
      Reply = table_sizes_internal(State),
      {reply, Reply, State};
  handle_call(_Request, _From, State) ->
      {reply, ok, State}.
  
  handle_cast({put, BKey, Key, Value}, State) ->
      put_internal(State, BKey, Key, Value),
      {noreply, State};
  handle_cast({remove, BKey, Key}, State) ->
      remove_internal(State, BKey, Key),
      {noreply, State};
  handle_cast(clear, State) ->
      clear_internal(State),
      {noreply, State};
  handle_cast({clear_bkey, BKey}, State) ->
      clear_bkey_internal(State, BKey),
      {noreply, State};
  handle_cast(_Request, State) ->
      {noreply, State}.
  
  handle_info(_Info, State) ->
      {noreply, State}.
  
  terminate(_Reason, State) ->
      destroy_internal(State),
      ok.
  
  put_internal(#kv_lru{max_size=MaxSize, age_idx=Idx,
                       bucket_idx=BucketIdx, cache=Cache},
               BKey, Key, Value) ->
      remove_existing(Idx, BucketIdx, Cache, BKey, Key),
      insert_value(Idx, BucketIdx, Cache, BKey, Key, Value),
      prune_oldest_if_needed(MaxSize, Idx, BucketIdx, Cache).
  
  fetch_internal(#kv_lru{cache=Cache}=LRU, BKey, Key) ->
      case fetch_value(Cache, BKey, Key) of
          notfound ->
              notfound;
          Value ->
              %% Do a put to update the timestamp in the cache
              put_internal(LRU, BKey, Key, Value),
              Value
      end.
  
  remove_internal(#kv_lru{age_idx=Idx, bucket_idx=BucketIdx, cache=Cache},
                  BKey, Key) ->
      remove_existing(Idx, BucketIdx, Cache, BKey, Key),
      ok.
  
  size_internal(#kv_lru{age_idx=Idx}) ->
      ets:info(Idx, size).
  
  max_size_internal(#kv_lru{max_size=MaxSize}) ->
      MaxSize.
  
  clear_internal(#kv_lru{age_idx=Idx, cache=Cache}) ->
      ets:delete_all_objects(Idx),
      ets:delete_all_objects(Cache),
      ok.
  
  clear_bkey_internal(#kv_lru{bucket_idx=BucketIdx}=LRU, BKey) ->
      R = ets:match(BucketIdx, {BKey, '$1'}),
       case R of
          [] ->
              ok;
          Keys ->
              [remove_internal(LRU, BKey, Key) || [Key] <- Keys],
              ok
      end.
  
  destroy_internal(#kv_lru{age_idx=undefined, bucket_idx=undefined, cache=undefined}=State) ->
      {ok, State};
  destroy_internal(#kv_lru{age_idx=Idx, bucket_idx=BucketIdx, cache=Cache}) ->
      ets:delete(Idx),
      ets:delete(BucketIdx),
      ets:delete(Cache),
      {ok, #kv_lru{age_idx=undefined, bucket_idx=undefined, cache=undefined}}.
  
  table_sizes_internal(#kv_lru{age_idx=Idx, bucket_idx=BucketIdx, cache=Cache}) ->
      [{age_idx, ets:info(Idx, size)},
       {bucket_idx, ets:info(BucketIdx, size)},
       {cache, ets:info(Cache, size)}].
  
  %% Internal functions
  remove_existing(Idx, BucketIdx, Cache, BKey, Key) ->
  