Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
93.69% covered (success)
93.69%
683 / 729
70.69% covered (warning)
70.69%
41 / 58
CRAP
0.00% covered (danger)
0.00%
0 / 1
WANObjectCache
93.69% covered (success)
93.69%
683 / 729
70.69% covered (warning)
70.69%
41 / 58
233.27
0.00% covered (danger)
0.00%
0 / 1
 __construct
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
2
 setLogger
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 newEmpty
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 get
100.00% covered (success)
100.00%
18 / 18
100.00% covered (success)
100.00%
1 / 1
4
 getMulti
95.45% covered (success)
95.45%
21 / 22
0.00% covered (danger)
0.00%
0 / 1
5
 fetchKeys
98.51% covered (success)
98.51%
66 / 67
0.00% covered (danger)
0.00%
0 / 1
17
 processCheckKeys
100.00% covered (success)
100.00%
15 / 15
100.00% covered (success)
100.00%
1 / 1
4
 set
100.00% covered (success)
100.00%
17 / 17
100.00% covered (success)
100.00%
1 / 1
2
 setMainValue
98.68% covered (success)
98.68%
75 / 76
0.00% covered (danger)
0.00%
0 / 1
21
 delete
100.00% covered (success)
100.00%
9 / 9
100.00% covered (success)
100.00%
1 / 1
3
 getCheckKeyTime
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 getMultiCheckKeyTime
100.00% covered (success)
100.00%
19 / 19
100.00% covered (success)
100.00%
1 / 1
4
 touchCheckKey
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
2
 resetCheckKey
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
2
 getWithSetCallback
100.00% covered (success)
100.00%
23 / 23
100.00% covered (success)
100.00%
1 / 1
8
 fetchOrRegenerate
100.00% covered (success)
100.00%
129 / 129
100.00% covered (success)
100.00%
1 / 1
26
 claimStampedeLock
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
1
 yieldStampedeLock
100.00% covered (success)
100.00%
3 / 3
100.00% covered (success)
100.00%
1 / 1
2
 makeSisterKeys
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
2
 makeSisterKey
83.33% covered (warning)
83.33%
5 / 6
0.00% covered (danger)
0.00%
0 / 1
3.04
 isExtremelyNewValue
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
3
 getInterimValue
66.67% covered (warning)
66.67%
8 / 12
0.00% covered (danger)
0.00%
0 / 1
5.93
 setInterimValue
91.67% covered (success)
91.67%
11 / 12
0.00% covered (danger)
0.00%
0 / 1
2.00
 resolveBusyValue
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
2
 getMultiWithSetCallback
100.00% covered (success)
100.00%
21 / 21
100.00% covered (success)
100.00%
1 / 1
2
 getMultiWithUnionSetCallback
90.20% covered (success)
90.20%
46 / 51
0.00% covered (danger)
0.00%
0 / 1
9.08
 makeGlobalKey
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 makeKey
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 hash256
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 makeMultiKeys
91.67% covered (success)
91.67%
11 / 12
0.00% covered (danger)
0.00%
0 / 1
5.01
 multiRemap
40.00% covered (danger)
40.00%
2 / 5
0.00% covered (danger)
0.00%
0 / 1
4.94
 watchErrors
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 getLastError
0.00% covered (danger)
0.00%
0 / 8
0.00% covered (danger)
0.00%
0 / 1
30
 clearLastError
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 clearProcessCache
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 useInterimHoldOffCaching
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 getQoS
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 adaptiveTTL
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
2
 getWarmupKeyMisses
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 relayVolatilePurge
100.00% covered (success)
100.00%
9 / 9
100.00% covered (success)
100.00%
1 / 1
2
 relayNonVolatilePurge
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
2
 prependRoute
66.67% covered (warning)
66.67%
2 / 3
0.00% covered (danger)
0.00%
0 / 1
2.15
 scheduleAsyncRefresh
53.33% covered (warning)
53.33%
8 / 15
0.00% covered (danger)
0.00%
0 / 1
3.91
 isAcceptablyFreshValue
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
4
 isLotteryRefreshDue
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
2
 worthRefreshPopular
54.55% covered (warning)
54.55%
6 / 11
0.00% covered (danger)
0.00%
0 / 1
7.35
 worthRefreshExpiring
100.00% covered (success)
100.00%
9 / 9
100.00% covered (success)
100.00%
1 / 1
5
 isValid
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
2
 wrap
100.00% covered (success)
100.00%
9 / 9
100.00% covered (success)
100.00%
1 / 1
2
 unwrap
100.00% covered (success)
100.00%
28 / 28
100.00% covered (success)
100.00%
1 / 1
6
 determineKeyGroupForStats
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
1
 parsePurgeValue
90.91% covered (success)
90.91%
10 / 11
0.00% covered (danger)
0.00%
0 / 1
5.02
 makeTombstonePurgeValue
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 makeCheckPurgeValue
100.00% covered (success)
100.00%
3 / 3
100.00% covered (success)
100.00%
1 / 1
1
 getProcessCache
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
3
 getNonProcessCachedMultiKeys
100.00% covered (success)
100.00%
8 / 8
100.00% covered (success)
100.00%
1 / 1
5
 fetchWrappedValuesForWarmupCache
63.64% covered (warning)
63.64%
7 / 11
0.00% covered (danger)
0.00%
0 / 1
6.20
 timeSinceLoggedMiss
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
3
 getCurrentTime
n/a
0 / 0
n/a
0 / 0
2
 setMockTime
n/a
0 / 0
n/a
0 / 0
2
1<?php
2/**
3 * This program is free software; you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation; either version 2 of the License, or
6 * (at your option) any later version.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License along
14 * with this program; if not, write to the Free Software Foundation, Inc.,
15 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
16 * http://www.gnu.org/copyleft/gpl.html
17 *
18 * @file
19 * @ingroup Cache
20 */
21
22use Liuggio\StatsdClient\Factory\StatsdDataFactoryInterface;
23use Psr\Log\LoggerAwareInterface;
24use Psr\Log\LoggerInterface;
25use Psr\Log\NullLogger;
26use Wikimedia\LightweightObjectStore\ExpirationAwareness;
27use Wikimedia\LightweightObjectStore\StorageAwareness;
28use Wikimedia\ObjectCache\BagOStuff;
29use Wikimedia\ObjectCache\EmptyBagOStuff;
30use Wikimedia\ObjectCache\IStoreKeyEncoder;
31
32/**
33 * Multi-datacenter aware caching interface
34 *
35 * ### Using WANObjectCache
36 *
37 * This class intends to boost performance of code paths by using cache-aside logic
38 * for data potentially derived from source databases subject to replication lag. Callers
39 * will generally make use of the getWithSetCallback() method.
40 *
41 * All operations go to the local datacenter cache, except for delete(), touchCheckKey(),
42 * and resetCheckKey(), which are also broadcasted to caches in all datacenters.
43 *
44 * To ensure consumers of the cache see new values in a timely manner, you need to
45 * follow either the validation strategy, or the purge strategy.
46 *
47 * The validation strategy refers to the natural avoidance of stale data
48 * by one of the following means:
49 *
50 *   - A) The cached value is immutable.
51 *        If the consumer has access to an identifier that uniquely describes a value,
52 *        cached value need not change. Instead, the key can change. This also allows
53 *        all servers to access their perceived current version. This is important
54 *        in context of multiple deployed versions of your application and/or cross-dc
55 *        database replication, to ensure deterministic values without oscillation.
56 *   - B) Validity is checked against the source after get().
57 *        This is the inverse of A. The unique identifier is embedded inside the value
58 *        and validated after on retrieval. If outdated, the value is recomputed.
59 *   - C) The value is cached with a modest TTL (without validation).
60 *        If value recomputation is reasonably performant, and the value is allowed to
61 *        be stale, one should consider using TTL only – using the value's age as
62 *        method of validation.
63 *
64 * The purge strategy refers to the approach whereby your application knows that source
65 * data has changed and can react by purging the relevant cache keys. Since purges are
66 * expensive, this strategy should be avoided if possible. The simplest purge method is
67 * delete().
68 *
69 * In any case, callers must not assume that updates and purges are immediately visible
70 * to all application servers. It should be treated like a replica database in this regard.
71 * If such semantics are required, then solutions must be sought outside WANObjectCache.
72 *
73 * Note that write operations, such as set() and delete(), are allowed to return true as
74 * soon as the command could be sent or buffered via an open socket to the relevant cache
75 * backend server. If that server is a proxy, then it is responsible for detecting
76 * and tracking downed servers.
77 *
78 * @anchor wanobjectcache-deployment
79 * ### Deploying WANObjectCache
80 *
81 * There are two supported ways to set up broadcasted operations:
82 *
83 *   - A) Set up mcrouter as the cache backend, with a memcached BagOStuff class for the 'cache'
84 *        parameter, and a wildcard routing prefix for the 'broadcastRoutingPrefix' parameter.
85 *        Configure mcrouter as follows:
86 *          - Define a "<datacenter>" pool of memcached servers for each datacenter.
87 *          - Define a "<datacenter>/wan" route to each datacenter, using "AllSyncRoute" for the
88 *            routes that go to the local datacenter pool and "AllAsyncRoute" for the routes that
89 *            go to remote datacenter pools. The child routes should use "HashRoute|<datacenter>".
90 *            This allows for the use of a wildcard route for 'broadcastRoutingPrefix'. See
91 *            https://github.com/facebook/mcrouter/wiki/Routing-Prefix and
92 *            https://github.com/facebook/mcrouter/wiki/Multi-cluster-broadcast-setup.
93 *          - In order to reroute operations from "down" servers to spare ("gutter") servers, use
94 *            "FailoverWithExptimeRoute" (failover_exptime=60) instead of "HashRoute|<datacenter>"
95 *            in the "AllSyncRoute"/"AllAsyncRoute" child routes.
96 *            The "gutter" pool is a set of memcached servers that only handle failover traffic.
97 *            Such servers should be carefully spread over different rows and racks. See
98 *            https://github.com/facebook/mcrouter/wiki/List-of-Route-Handles#failoverroute
99 *   - B) Set up dynomite as the cache backend, using a memcached BagOStuff class for the 'cache'
100 *        parameter. Note that with this setup, all key setting operations will be broadcasted,
101 *        rather than just purges. Writes will be eventually consistent via the Dynamo replication
102 *        model. See https://github.com/Netflix/dynomite.
103 *
104 * Broadcasted operations like delete() and touchCheckKey() are intended to run
105 * immediately in the local datacenter and asynchronously in remote datacenters.
106 *
107 * This means that callers in all datacenters may see older values for however many
108 * milliseconds that the purge took to reach that datacenter. As with any cache, this
109 * should not be relied on for cases where reads are used to determine writes to source
110 * (e.g. non-cache) data stores, except when reading immutable data.
111 *
112 * Internally, access to a given key actually involves the use of one or more "sister" keys.
113 * A sister key is constructed by prefixing the base key with "WANCache:" (used to distinguish
114 * WANObjectCache formatted keys) and suffixing a colon followed by a single-character sister
115 * key type. The sister key types include the following:
116 *
117 * - `v`: used to store "regular" values (metadata-wrapped) and temporary purge "tombstones".
118 * - `t`: used to store "last purge" timestamps for "check" keys.
119 * - `m`: used to store temporary mutex locks to avoid cache stampedes.
120 * - `i`: used to store temporary interim values (metadata-wrapped) for tombstoned keys.
121 * - `c`: used to store temporary "cool-off" indicators, which specify a period during which
122 *        values cannot be stored, neither regularly nor using interim keys.
123 *
124 * @ingroup Cache
125 * @newable
126 * @since 1.26
127 */
128class WANObjectCache implements
129    ExpirationAwareness,
130    StorageAwareness,
131    IStoreKeyEncoder,
132    LoggerAwareInterface
133{
134    /** @var BagOStuff The local datacenter cache */
135    protected $cache;
136    /** @var MapCacheLRU[] Map of group PHP instance caches */
137    protected $processCaches = [];
138    /** @var LoggerInterface */
139    protected $logger;
140    /** @var StatsdDataFactoryInterface */
141    protected $stats;
142    /** @var callable|null Function that takes a WAN cache callback and runs it later */
143    protected $asyncHandler;
144
145    /**
146     * Routing prefix for operations that should be broadcasted to all data centers.
147     *
148     * If null, the there is only one datacenter or a backend proxy broadcasts everything.
149     *
150     * @var string|null
151     */
152    protected $broadcastRoute;
153    /** @var bool Whether to use "interim" caching while keys are tombstoned */
154    protected $useInterimHoldOffCaching = true;
155    /** @var float Unix timestamp of the oldest possible valid values */
156    protected $epoch;
157    /** @var string Stable secret used for hashing long strings into key components */
158    protected $secret;
159    /** @var int Scheme to use for key coalescing (Hash Tags or Hash Stops) */
160    protected $coalesceScheme;
161
162    /** @var array<int,array> List of (key, UNIX timestamp) tuples for get() cache misses */
163    private $missLog;
164
165    /** @var int Callback stack depth for getWithSetCallback() */
166    private $callbackDepth = 0;
167    /** @var mixed[] Temporary warm-up cache */
168    private $warmupCache = [];
169    /** @var int Key fetched */
170    private $warmupKeyMisses = 0;
171
172    /** @var float|null */
173    private $wallClockOverride;
174
175    /** Max expected seconds to pass between delete() and DB commit finishing */
176    private const MAX_COMMIT_DELAY = 3;
177    /** Max expected seconds of combined lag from replication and "view snapshots" */
178    private const MAX_READ_LAG = 7;
179    /** Seconds to tombstone keys on delete() and to treat keys as volatile after purges */
180    public const HOLDOFF_TTL = self::MAX_COMMIT_DELAY + self::MAX_READ_LAG + 1;
181
182    /** Consider regeneration if the key will expire within this many seconds */
183    private const LOW_TTL = 60;
184    /** Max TTL, in seconds, to store keys when a data source has high replication lag */
185    public const TTL_LAGGED = 30;
186
187    /** Expected time-till-refresh, in seconds, if the key is accessed once per second */
188    private const HOT_TTR = 900;
189    /** Minimum key age, in seconds, for expected time-till-refresh to be considered */
190    private const AGE_NEW = 60;
191
192    /** Idiom for getWithSetCallback() meaning "no cache stampede mutex" */
193    private const TSE_NONE = -1;
194
195    /** Idiom for set()/getWithSetCallback() meaning "no post-expiration persistence" */
196    public const STALE_TTL_NONE = 0;
197    /** Idiom for set()/getWithSetCallback() meaning "no post-expiration grace period" */
198    public const GRACE_TTL_NONE = 0;
199    /** Idiom for delete()/touchCheckKey() meaning "no hold-off period" */
200    public const HOLDOFF_TTL_NONE = 0;
201
202    /** @var float Idiom for getWithSetCallback() meaning "no minimum required as-of timestamp" */
203    public const MIN_TIMESTAMP_NONE = 0.0;
204
205    /** Default process cache name and max key count */
206    private const PC_PRIMARY = 'primary:1000';
207
208    /** Idiom for get()/getMulti() to return extra information by reference */
209    public const PASS_BY_REF = [];
210
211    /** Use twemproxy-style Hash Tag key scheme (e.g. "{...}") */
212    private const SCHEME_HASH_TAG = 1;
213    /** Use mcrouter-style Hash Stop key scheme (e.g. "...|#|") */
214    private const SCHEME_HASH_STOP = 2;
215
216    /** Seconds to keep dependency purge keys around */
217    private const CHECK_KEY_TTL = self::TTL_YEAR;
218    /** Seconds to keep interim value keys for tombstoned keys around */
219    private const INTERIM_KEY_TTL = 2;
220
221    /** Seconds to keep lock keys around */
222    private const LOCK_TTL = 10;
223    /** Seconds to ramp up the chance of regeneration due to expected time-till-refresh */
224    private const RAMPUP_TTL = 30;
225
226    /** @var float Tiny negative float to use when CTL comes up >= 0 due to clock skew */
227    private const TINY_NEGATIVE = -0.000001;
228    /** @var float Tiny positive float to use when using "minTime" to assert an inequality */
229    private const TINY_POSITIVE = 0.000001;
230
231    /** Min millisecond set() backoff during hold-off (far less than INTERIM_KEY_TTL) */
232    private const RECENT_SET_LOW_MS = 50;
233    /** Max millisecond set() backoff during hold-off (far less than INTERIM_KEY_TTL) */
234    private const RECENT_SET_HIGH_MS = 100;
235
236    /** Consider value generation somewhat high if it takes this many seconds or more */
237    private const GENERATION_HIGH_SEC = 0.2;
238
239    /** Key to the tombstone entry timestamp */
240    private const PURGE_TIME = 0;
241    /** Key to the tombstone entry hold-off TTL */
242    private const PURGE_HOLDOFF = 1;
243
244    /** Cache format version number */
245    private const VERSION = 1;
246
247    /** Version number attribute for a key; keep value for b/c (< 1.36) */
248    public const KEY_VERSION = 'version';
249    /** Generation completion timestamp attribute for a key; keep value for b/c (< 1.36) */
250    public const KEY_AS_OF = 'asOf';
251    /** Logical TTL attribute for a key */
252    public const KEY_TTL = 'ttl';
253    /** Remaining TTL attribute for a key; keep value for b/c (< 1.36) */
254    public const KEY_CUR_TTL = 'curTTL';
255    /** Tomstone timestamp attribute for a key; keep value for b/c (< 1.36) */
256    public const KEY_TOMB_AS_OF = 'tombAsOf';
257    /** Highest "check" key timestamp for a key; keep value for b/c (< 1.36) */
258    public const KEY_CHECK_AS_OF = 'lastCKPurge';
259
260    /** Value for a key */
261    private const RES_VALUE = 0;
262    /** Version number attribute for a key */
263    private const RES_VERSION = 1;
264    /** Generation completion timestamp attribute for a key */
265    private const RES_AS_OF = 2;
266    /** Logical TTL attribute for a key */
267    private const RES_TTL = 3;
268    /** Tomstone timestamp attribute for a key */
269    private const RES_TOMB_AS_OF = 4;
270    /** Highest "check" key timestamp for a key */
271    private const RES_CHECK_AS_OF = 5;
272    /** Highest "touched" timestamp for a key */
273    private const RES_TOUCH_AS_OF = 6;
274    /** Remaining TTL attribute for a key */
275    private const RES_CUR_TTL = 7;
276
277    /** Key to WAN cache version number; stored in blobs */
278    private const FLD_FORMAT_VERSION = 0;
279    /** Key to the cached value; stored in blobs */
280    private const FLD_VALUE = 1;
281    /** Key to the original TTL; stored in blobs */
282    private const FLD_TTL = 2;
283    /** Key to the cache timestamp; stored in blobs */
284    private const FLD_TIME = 3;
285    /** Key to the flags bit field (reserved number) */
286    private const /** @noinspection PhpUnusedPrivateFieldInspection */ FLD_FLAGS = 4;
287    /** Key to collection cache version number; stored in blobs */
288    private const FLD_VALUE_VERSION = 5;
289    private const /** @noinspection PhpUnusedPrivateFieldInspection */ FLD_GENERATION_TIME = 6;
290
291    /** Single character component for value keys */
292    private const TYPE_VALUE = 'v';
293    /** Single character component for timestamp check keys */
294    private const TYPE_TIMESTAMP = 't';
295    /** Single character component for mutex lock keys */
296    private const TYPE_MUTEX = 'm';
297    /** Single character component for interium value keys */
298    private const TYPE_INTERIM = 'i';
299
300    /** Value prefix of purge values */
301    private const PURGE_VAL_PREFIX = 'PURGED';
302
303    /**
304     * @stable to call
305     * @param array $params
306     *   - cache    : BagOStuff object for a persistent cache
307     *   - logger   : LoggerInterface object
308     *   - stats    : StatsdDataFactoryInterface object
309     *   - asyncHandler : A function that takes a callback and runs it later. If supplied,
310     *       whenever a preemptive refresh would be triggered in getWithSetCallback(), the
311     *       current cache value is still used instead. However, the async-handler function
312     *       receives a WAN cache callback that, when run, will execute the value generation
313     *       callback supplied by the getWithSetCallback() caller. The result will be saved
314     *       as normal. The handler is expected to call the WAN cache callback at an opportune
315     *       time (e.g. HTTP post-send), though generally within a few 100ms. [optional]
316     *   - broadcastRoutingPrefix: a routing prefix used to broadcast certain operations to all
317     *       datacenters; See also <https://github.com/facebook/mcrouter/wiki/Config-Files>.
318     *       This prefix takes the form `/<datacenter>/<name of wan route>/`, where `datacenter`
319     *       is usually a wildcard to select all matching routes (e.g. the WAN cluster in all DCs).
320     *       See also <https://github.com/facebook/mcrouter/wiki/Multi-cluster-broadcast-setup>.
321     *       This is required when using mcrouter as a multi-region backing store proxy. [optional]
322     *   - epoch: lowest UNIX timestamp a value/tombstone must have to be valid. [optional]
323     *   - secret: stable secret used for hashing long strings into key components. [optional]
324     *   - coalesceScheme: which key scheme to use in order to encourage the backend to place any
325     *       "helper" keys for a "value" key within the same cache server. This reduces network
326     *       overhead and reduces the chance the a single downed cache server causes disruption.
327     *       Use "hash_stop" with mcrouter and "hash_tag" with dynomite. [default: "hash_stop"]
328     */
329    public function __construct( array $params ) {
330        $this->cache = $params['cache'];
331        $this->broadcastRoute = $params['broadcastRoutingPrefix'] ?? null;
332        $this->epoch = $params['epoch'] ?? 0;
333        $this->secret = $params['secret'] ?? (string)$this->epoch;
334        if ( ( $params['coalesceScheme'] ?? '' ) === 'hash_tag' ) {
335            // https://redis.io/topics/cluster-spec
336            // https://github.com/twitter/twemproxy/blob/v0.4.1/notes/recommendation.md#hash-tags
337            // https://github.com/Netflix/dynomite/blob/v0.7.0/notes/recommendation.md#hash-tags
338            $this->coalesceScheme = self::SCHEME_HASH_TAG;
339        } else {
340            // https://github.com/facebook/mcrouter/wiki/Key-syntax
341            $this->coalesceScheme = self::SCHEME_HASH_STOP;
342        }
343
344        $this->setLogger( $params['logger'] ?? new NullLogger() );
345        $this->stats = $params['stats'] ?? new NullStatsdDataFactory();
346        $this->asyncHandler = $params['asyncHandler'] ?? null;
347
348        $this->missLog = array_fill( 0, 10, [ '', 0.0 ] );
349    }
350
351    /**
352     * @param LoggerInterface $logger
353     */
354    public function setLogger( LoggerInterface $logger ) {
355        $this->logger = $logger;
356    }
357
358    /**
359     * Get an instance that wraps EmptyBagOStuff
360     *
361     * @return WANObjectCache
362     */
363    public static function newEmpty() {
364        return new static( [ 'cache' => new EmptyBagOStuff() ] );
365    }
366
367    /**
368     * Fetch the value of a key from cache
369     *
370     * If supplied, $curTTL is set to the remaining TTL (current time left):
371     *   - a) INF; if $key exists, has no TTL, and is not purged by $checkKeys
372     *   - b) float (>=0); if $key exists, has a TTL, and is not purged by $checkKeys
373     *   - c) float (<0); if $key is tombstoned, stale, or existing but purged by $checkKeys
374     *   - d) null; if $key does not exist and is not tombstoned
375     *
376     * If a key is tombstoned, $curTTL will reflect the time since delete().
377     *
378     * The timestamp of $key will be checked against the last-purge timestamp
379     * of each of $checkKeys. Those $checkKeys not in cache will have the last-purge
380     * initialized to the current timestamp. If any of $checkKeys have a timestamp
381     * greater than that of $key, then $curTTL will reflect how long ago $key
382     * became invalid. Callers can use $curTTL to know when the value is stale.
383     * The $checkKeys parameter allow mass key purges by updating a single key:
384     *   - a) Each "check" key represents "last purged" of some source data
385     *   - b) Callers pass in relevant "check" keys as $checkKeys in get()
386     *   - c) When the source data that "check" keys represent changes,
387     *        the touchCheckKey() method is called on them
388     *
389     * Source data entities might exists in a DB that uses snapshot isolation
390     * (e.g. the default REPEATABLE-READ in innoDB). Even for mutable data, that
391     * isolation can largely be maintained by doing the following:
392     *   - a) Calling delete() on entity change *and* creation, before DB commit
393     *   - b) Keeping transaction duration shorter than the delete() hold-off TTL
394     *   - c) Disabling interim key caching via useInterimHoldOffCaching() before get() calls
395     *
396     * However, pre-snapshot values might still be seen if an update was made
397     * in a remote datacenter but the purge from delete() didn't relay yet.
398     *
399     * Consider using getWithSetCallback(), which has cache slam avoidance and key
400     * versioning features, instead of bare get()/set() calls.
401     *
402     * Do not use this method on versioned keys accessed via getWithSetCallback().
403     *
404     * When using the $info parameter, it should be passed in as WANObjectCache::PASS_BY_REF.
405     * In that case, it becomes a key metadata map. Otherwise, for backwards compatibility,
406     * $info becomes the value generation timestamp (null if the key is nonexistant/tombstoned).
407     * Key metadata map fields include:
408     *   - WANObjectCache::KEY_VERSION: value version number; null if key is nonexistant
409     *   - WANObjectCache::KEY_AS_OF: value generation timestamp (UNIX); null if key is nonexistant
410     *   - WANObjectCache::KEY_TTL: assigned TTL (seconds); null if key is nonexistant/tombstoned
411     *   - WANObjectCache::KEY_CUR_TTL: remaining TTL (seconds); null if key is nonexistant
412     *   - WANObjectCache::KEY_TOMB_AS_OF: tombstone timestamp (UNIX); null if key is not tombstoned
413     *   - WANObjectCache::KEY_CHECK_AS_OF: highest "check" key timestamp (UNIX); null if none
414     *
415     * @param string $key Cache key made with makeKey()/makeGlobalKey()
416     * @param float|null &$curTTL Seconds of TTL left [returned]
417     * @param string[] $checkKeys Map of (integer or cache key => "check" key(s));
418     *  "check" keys must also be made with makeKey()/makeGlobalKey()
419     * @param array &$info Metadata map [returned]
420     * @return mixed Value of cache key; false on failure
421     */
422    final public function get( $key, &$curTTL = null, array $checkKeys = [], &$info = [] ) {
423        // Note that an undeclared variable passed as $info starts as null (not the default).
424        // Also, if no $info parameter is provided, then it doesn't matter how it changes here.
425        $legacyInfo = ( $info !== self::PASS_BY_REF );
426
427        $now = $this->getCurrentTime();
428        $res = $this->fetchKeys( [ $key ], $checkKeys, $now )[$key];
429
430        $curTTL = $res[self::RES_CUR_TTL];
431        $info = $legacyInfo
432            ? $res[self::RES_AS_OF]
433            : [
434                self::KEY_VERSION => $res[self::RES_VERSION],
435                self::KEY_AS_OF => $res[self::RES_AS_OF],
436                self::KEY_TTL => $res[self::RES_TTL],
437                self::KEY_CUR_TTL => $res[self::RES_CUR_TTL],
438                self::KEY_TOMB_AS_OF => $res[self::RES_TOMB_AS_OF],
439                self::KEY_CHECK_AS_OF => $res[self::RES_CHECK_AS_OF]
440            ];
441
442        if ( $curTTL === null || $curTTL <= 0 ) {
443            // Log the timestamp in case a corresponding set() call does not provide "walltime"
444            unset( $this->missLog[array_key_first( $this->missLog )] );
445            $this->missLog[] = [ $key, $this->getCurrentTime() ];
446        }
447
448        return $res[self::RES_VALUE];
449    }
450
451    /**
452     * Fetch the value of several keys from cache
453     *
454     * $curTTLs becomes a map of only present/tombstoned $keys to their current time-to-live.
455     *
456     * $checkKeys holds the "check" keys used to validate values of applicable keys. The
457     * integer indexes hold "check" keys that apply to all of $keys while the string indexes
458     * hold "check" keys that only apply to the cache key with that name. The logic of "check"
459     * keys otherwise works the same as in WANObjectCache::get().
460     *
461     * When using the $info parameter, it should be passed in as WANObjectCache::PASS_BY_REF.
462     * In that case, it becomes a mapping of all the $keys to their metadata maps, each in the
463     * style of WANObjectCache::get(). Otherwise, for backwards compatibility, $info becomes a
464     * map of only present/tombstoned $keys to their value generation timestamps.
465     *
466     * @see WANObjectCache::get()
467     *
468     * @param string[] $keys List/map with makeKey()/makeGlobalKey() cache keys as values
469     * @param array<string,float> &$curTTLs Map of (key => seconds of TTL left) [returned]
470     * @param string[]|string[][] $checkKeys Map of (integer or cache key => "check" key(s));
471     *  "check" keys must also be made with makeKey()/makeGlobalKey()
472     * @param array<string,array> &$info Map of (key => metadata map) [returned]
473     * @return array<string,mixed> Map of (key => value) for existing values in order of $keys
474     */
475    final public function getMulti(
476        array $keys,
477        &$curTTLs = [],
478        array $checkKeys = [],
479        &$info = []
480    ) {
481        // Note that an undeclared variable passed as $info starts as null (not the default).
482        // Also, if no $info parameter is provided, then it doesn't matter how it changes here.
483        $legacyInfo = ( $info !== self::PASS_BY_REF );
484
485        $curTTLs = [];
486        $info = [];
487        $valuesByKey = [];
488
489        $now = $this->getCurrentTime();
490        $resByKey = $this->fetchKeys( $keys, $checkKeys, $now );
491        foreach ( $resByKey as $key => $res ) {
492            if ( $res[self::RES_VALUE] !== false ) {
493                $valuesByKey[$key] = $res[self::RES_VALUE];
494            }
495
496            if ( $res[self::RES_CUR_TTL] !== null ) {
497                $curTTLs[$key] = $res[self::RES_CUR_TTL];
498            }
499            $info[$key] = $legacyInfo
500                ? $res[self::RES_AS_OF]
501                : [
502                    self::KEY_VERSION => $res[self::RES_VERSION],
503                    self::KEY_AS_OF => $res[self::RES_AS_OF],
504                    self::KEY_TTL => $res[self::RES_TTL],
505                    self::KEY_CUR_TTL => $res[self::RES_CUR_TTL],
506                    self::KEY_TOMB_AS_OF => $res[self::RES_TOMB_AS_OF],
507                    self::KEY_CHECK_AS_OF => $res[self::RES_CHECK_AS_OF]
508                ];
509        }
510
511        return $valuesByKey;
512    }
513
514    /**
515     * Fetch the value and key metadata of several keys from cache
516     *
517     * $checkKeys holds the "check" keys used to validate values of applicable keys.
518     * The integer indexes hold "check" keys that apply to all of $keys while the string
519     * indexes hold "check" keys that only apply to the cache key with that name.
520     *
521     * @param string[] $keys List/map with makeKey()/makeGlobalKey() cache keys as values
522     * @param string[]|string[][] $checkKeys Map of (integer or cache key => "check" key(s));
523     *  "check" keys must also be made with makeKey()/makeGlobalKey()
524     * @param float $now The current UNIX timestamp
525     * @param callable|null $touchedCb Callback yielding a UNIX timestamp from a value, or null
526     * @return array<string,array> Map of (key => WANObjectCache::RESULT_* map) in order of $keys
527     * @note Callable type hints are not used to avoid class-autoloading
528     */
529    protected function fetchKeys( array $keys, array $checkKeys, float $now, $touchedCb = null ) {
530        $resByKey = [];
531
532        // List of all sister keys that need to be fetched from cache
533        $allSisterKeys = [];
534        // Order-corresponding value sister key list for the base key list ($keys)
535        $valueSisterKeys = [];
536        // List of "check" sister keys to compare all value sister keys against
537        $checkSisterKeysForAll = [];
538        // Map of (base key => additional "check" sister key(s) to compare against)
539        $checkSisterKeysByKey = [];
540
541        foreach ( $keys as $key ) {
542            $sisterKey = $this->makeSisterKey( $key, self::TYPE_VALUE );
543            $allSisterKeys[] = $sisterKey;
544            $valueSisterKeys[] = $sisterKey;
545        }
546
547        foreach ( $checkKeys as $i => $checkKeyOrKeyGroup ) {
548            // Note: avoid array_merge() inside loop in case there are many keys
549            if ( is_int( $i ) ) {
550                // Single "check" key that applies to all base keys
551                $sisterKey = $this->makeSisterKey( $checkKeyOrKeyGroup, self::TYPE_TIMESTAMP );
552                $allSisterKeys[] = $sisterKey;
553                $checkSisterKeysForAll[] = $sisterKey;
554            } else {
555                // List of "check" keys that apply to a specific base key
556                foreach ( (array)$checkKeyOrKeyGroup as $checkKey ) {
557                    $sisterKey = $this->makeSisterKey( $checkKey, self::TYPE_TIMESTAMP );
558                    $allSisterKeys[] = $sisterKey;
559                    $checkSisterKeysByKey[$i][] = $sisterKey;
560                }
561            }
562        }
563
564        if ( $this->warmupCache ) {
565            // Get the wrapped values of the sister keys from the warmup cache
566            $wrappedBySisterKey = $this->warmupCache;
567            $sisterKeysMissing = array_diff( $allSisterKeys, array_keys( $wrappedBySisterKey ) );
568            if ( $sisterKeysMissing ) {
569                $this->warmupKeyMisses += count( $sisterKeysMissing );
570                $wrappedBySisterKey += $this->cache->getMulti( $sisterKeysMissing );
571            }
572        } else {
573            // Fetch the wrapped values of the sister keys from the backend
574            $wrappedBySisterKey = $this->cache->getMulti( $allSisterKeys );
575        }
576
577        // List of "check" sister key purge timestamps to compare all value sister keys against
578        $ckPurgesForAll = $this->processCheckKeys(
579            $checkSisterKeysForAll,
580            $wrappedBySisterKey,
581            $now
582        );
583        // Map of (base key => extra "check" sister key purge timestamp(s) to compare against)
584        $ckPurgesByKey = [];
585        foreach ( $checkSisterKeysByKey as $keyWithCheckKeys => $checkKeysForKey ) {
586            $ckPurgesByKey[$keyWithCheckKeys] = $this->processCheckKeys(
587                $checkKeysForKey,
588                $wrappedBySisterKey,
589                $now
590            );
591        }
592
593        // Unwrap and validate any value found for each base key (under the value sister key)
594        reset( $keys );
595        foreach ( $valueSisterKeys as $valueSisterKey ) {
596            // Get the corresponding base key for this value sister key
597            $key = current( $keys );
598            next( $keys );
599
600            if ( array_key_exists( $valueSisterKey, $wrappedBySisterKey ) ) {
601                // Key exists as either a live value or tombstone value
602                $wrapped = $wrappedBySisterKey[$valueSisterKey];
603            } else {
604                // Key does not exist
605                $wrapped = false;
606            }
607
608            $res = $this->unwrap( $wrapped, $now );
609            $value = $res[self::RES_VALUE];
610
611            foreach ( array_merge( $ckPurgesForAll, $ckPurgesByKey[$key] ?? [] ) as $ckPurge ) {
612                $res[self::RES_CHECK_AS_OF] = max(
613                    $ckPurge[self::PURGE_TIME],
614                    $res[self::RES_CHECK_AS_OF]
615                );
616                // Timestamp marking the end of the hold-off period for this purge
617                $holdoffDeadline = $ckPurge[self::PURGE_TIME] + $ckPurge[self::PURGE_HOLDOFF];
618                // Check if the value was generated during the hold-off period
619                if ( $value !== false && $holdoffDeadline >= $res[self::RES_AS_OF] ) {
620                    // How long ago this value was purged by *this* "check" key
621                    $ago = min( $ckPurge[self::PURGE_TIME] - $now, self::TINY_NEGATIVE );
622                    // How long ago this value was purged by *any* known "check" key
623                    $res[self::RES_CUR_TTL] = min( $res[self::RES_CUR_TTL], $ago );
624                }
625            }
626
627            if ( $touchedCb !== null && $value !== false ) {
628                $touched = $touchedCb( $value );
629                if ( $touched !== null && $touched >= $res[self::RES_AS_OF] ) {
630                    $res[self::RES_CUR_TTL] = min(
631                        $res[self::RES_CUR_TTL],
632                        $res[self::RES_AS_OF] - $touched,
633                        self::TINY_NEGATIVE
634                    );
635                }
636            } else {
637                $touched = null;
638            }
639
640            $res[self::RES_TOUCH_AS_OF] = max( $res[self::RES_TOUCH_AS_OF], $touched );
641
642            $resByKey[$key] = $res;
643        }
644
645        return $resByKey;
646    }
647
648    /**
649     * @param string[] $checkSisterKeys List of "check" sister keys
650     * @param mixed[] $wrappedBySisterKey Preloaded map of (sister key => wrapped value)
651     * @param float $now UNIX timestamp
652     * @return array[] List of purge value arrays
653     */
654    private function processCheckKeys(
655        array $checkSisterKeys,
656        array $wrappedBySisterKey,
657        float $now
658    ) {
659        $purges = [];
660
661        foreach ( $checkSisterKeys as $timeKey ) {
662            $purge = isset( $wrappedBySisterKey[$timeKey] )
663                ? $this->parsePurgeValue( $wrappedBySisterKey[$timeKey] )
664                : null;
665
666            if ( $purge === null ) {
667                // No holdoff when lazy creating a check key, use cache right away (T344191)
668                $wrapped = $this->makeCheckPurgeValue( $now, self::HOLDOFF_TTL_NONE, $purge );
669                $this->cache->add(
670                    $timeKey,
671                    $wrapped,
672                    self::CHECK_KEY_TTL,
673                    $this->cache::WRITE_BACKGROUND
674                );
675            }
676
677            $purges[] = $purge;
678        }
679