MB-31975 Use golang's concurrent map in utils.Cache.
MB-31975 Use golang's concurrent map in utils.Cache.

It is optimized for the usage pattern that is similar to ours: most of
the time the map is static, the map is append-only. If these
conditions are satisfied, then reads for the keys that are present in
the map require two atomic reads and don't need to acquire a mutually
exclusive lock even in the presence of concurrent writes. Reads that
"miss" may get slowed down buy the concurrent writes, but that's a
slow path already: we actually need to go to ns_server to decide how
to populate the cache for the missed item.

A key observation is that we indeed use this cache in such mostly
append-only manner. The reason being that the keys that are stored in
the cache are paired with some notion of "database version", whenever
the version changes, all keys that are currently stored in the cache
are implicitly invalidated.

For the same reason, in most cases we probably don't get to benefit
from LRU eviction policy: the entire cache is invalidated in a single
sweep. So this patch changes the eviction policy to evict the keys in
their corresponding creation order.

In the absence of version changes, it's possible to come up with a
workload that would perform worse under the simplified eviction
policy (the opposite is also true). But if there's indeed a set of
dormant cached values that result in eviction of recent items (those
that wouldn't get evicted under the LRU policy), the observation is
that it can only happen once per "wrongfully evicted" item: next cache
miss on such an item will put it behind the dormant items in the
eviction queue.

The benchmark results comparing different proposed cache improvements
follow. NB: I actually believe that the mixed workload benchmark
doesn't do justice to this implementation, since reads and writes are
measured and averaged together, so one can't actually see how only
reads perform in the presence of concurrent writes. But writing a
better benchmark proved more time-consuming than what I'd have
hoped.

Tested implementations:

 - Concurrent map (this patch)
 - Partial LRU (http://review.couchbase.org/#/c/101645/)
 - LRU with 5 seconds delay (http://review.couchbase.org/#/c/103798/)
 - Vanilla LRU (the original implementation prior to any changes)

BENCHMARK                                                   CONCURRENT MAP    PARTIAL LRU    5 SECONDS LRU    VANILLA LRU    UNIT
BenchmarkCacheGet/threads_=_16-8                                      9.72           50.0             49.5            165    ns/op
BenchmarkCacheGet/threads_=_104-8                                     9.59           49.7             49.9            245    ns/op
BenchmarkCacheGet/threads_=_1000-8                                    9.89           49.6             63.6            164    ns/op
BenchmarkCacheGet/threads_=_10000-8                                   10.3           49.6             80.9            734    ns/op
BenchmarkCacheGet/threads_=_100000-8                                  10.6           49.6              222            632    ns/op
BenchmarkCacheAddGet/threads_=_16,_hit_rate_=_100%-8                  17.7           52.6             56.3            227    ns/op
BenchmarkCacheAddGet/threads_=_104,_hit_rate_=_100%-8                 17.5           52.6             56.6            282    ns/op
BenchmarkCacheAddGet/threads_=_1000,_hit_rate_=_100%-8                17.5           53.5             59.4            277    ns/op
BenchmarkCacheAddGet/threads_=_10000,_hit_rate_=_100%-8               17.7           54.6             75.3            837    ns/op
BenchmarkCacheAddGet/threads_=_100000,_hit_rate_=_100%-8              18.6           63.1              154            702    ns/op
BenchmarkCacheAddGet/threads_=_16,_hit_rate_=_99%-8                   21.9            104              184            227    ns/op
BenchmarkCacheAddGet/threads_=_104,_hit_rate_=_99%-8                  23.7           83.7              180            267    ns/op
BenchmarkCacheAddGet/threads_=_1000,_hit_rate_=_99%-8                 29.5           88.4              193            270    ns/op
BenchmarkCacheAddGet/threads_=_10000,_hit_rate_=_99%-8                30.1           93.2              206            911    ns/op
BenchmarkCacheAddGet/threads_=_100000,_hit_rate_=_99%-8               97.6           95.1              229            723    ns/op
BenchmarkCacheAddGet/threads_=_16,_hit_rate_=_95%-8                   46.8            119              219            230    ns/op
BenchmarkCacheAddGet/threads_=_104,_hit_rate_=_95%-8                  47.1            113              219            259    ns/op
BenchmarkCacheAddGet/threads_=_1000,_hit_rate_=_95%-8                  119            116              243            288    ns/op
BenchmarkCacheAddGet/threads_=_10000,_hit_rate_=_95%-8                 122            142              291            920    ns/op
BenchmarkCacheAddGet/threads_=_100000,_hit_rate_=_95%-8                138            148              321            969    ns/op
BenchmarkCacheAddGet/threads_=_16,_hit_rate_=_90%-8                   77.7            129              238            240    ns/op
BenchmarkCacheAddGet/threads_=_104,_hit_rate_=_90%-8                  79.6            129              244            262    ns/op
BenchmarkCacheAddGet/threads_=_1000,_hit_rate_=_90%-8                  156            152              312            307    ns/op
BenchmarkCacheAddGet/threads_=_10000,_hit_rate_=_90%-8                 184            199              398            983    ns/op
BenchmarkCacheAddGet/threads_=_100000,_hit_rate_=_90%-8                198            217              427            811    ns/op
BenchmarkCacheAddGet/threads_=_16,_hit_rate_=_80%-8                    129            163              287            264    ns/op
BenchmarkCacheAddGet/threads_=_104,_hit_rate_=_80%-8                   134            167              298            277    ns/op
BenchmarkCacheAddGet/threads_=_1000,_hit_rate_=_80%-8                  226            231              445            350    ns/op
BenchmarkCacheAddGet/threads_=_10000,_hit_rate_=_80%-8                 291            318              626           1101    ns/op
BenchmarkCacheAddGet/threads_=_100000,_hit_rate_=_80%-8                292            332              664            934    ns/op
BenchmarkCacheAdd/threads_=_16-8                                       370            383              392            375    ns/op
BenchmarkCacheAdd/threads_=_104-8                                      381            396              405            385    ns/op
BenchmarkCacheAdd/threads_=_1000-8                                     700            703              663            614    ns/op
BenchmarkCacheAdd/threads_=_10000-8                                   1154           1074             1104           1135    ns/op
BenchmarkCacheAdd/threads_=_100000-8                                  1195           1174             1208           1209    ns/op

Change-Id: I73f02738ce0745d952edd8d3b59bf8675085fc2b
Reviewed-on: http://review.couchbase.org/104933
Well-Formed: Build Bot <80754af91bfb6d1073585b046fe0a474ce868509@couchbase.com>
Tested-by: Aliaksey Artamonau <ce14b1c16e0fd654f926118eb8addbec5aff4ffa@couchbase.com>
Reviewed-by: Artem Stemkovski <15a0730a27c69f62ab86f2b6c639fca202166c02@couchbase.com>

couchbase/cbauth,couchbase/cbauth