Skip to main content

meta_srv/service/store/
cached_kv.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::any::Any;
16use std::collections::HashSet;
17use std::sync::atomic::{AtomicUsize, Ordering};
18use std::sync::{Arc, RwLock};
19
20use common_meta::error::{Error, Result};
21use common_meta::key::CACHE_KEY_PREFIXES;
22use common_meta::kv_backend::memory::MemoryKvBackend;
23use common_meta::kv_backend::txn::{Txn, TxnOp, TxnRequest, TxnResponse};
24use common_meta::kv_backend::{
25    KvBackend, KvBackendRef, ResettableKvBackend, ResettableKvBackendRef, TxnService,
26};
27use common_meta::range_stream::{DEFAULT_PAGE_SIZE, PaginationStream};
28use common_meta::rpc::KeyValue;
29use common_meta::rpc::store::{
30    BatchDeleteRequest, BatchDeleteResponse, BatchGetRequest, BatchGetResponse, BatchPutRequest,
31    BatchPutResponse, CompareAndPutRequest, CompareAndPutResponse, DeleteRangeRequest,
32    DeleteRangeResponse, PutRequest, PutResponse, RangeRequest, RangeResponse,
33};
34use futures::TryStreamExt;
35
36use crate::metrics;
37use crate::state::State;
38
39pub type CheckLeaderRef = Arc<dyn CheckLeader>;
40
41pub trait CheckLeader: Sync + Send {
42    fn check(&self) -> bool;
43}
44
45struct AlwaysLeader;
46
47impl CheckLeader for AlwaysLeader {
48    fn check(&self) -> bool {
49        true
50    }
51}
52
53impl CheckLeader for RwLock<State> {
54    fn check(&self) -> bool {
55        self.read().unwrap().enable_leader_cache()
56    }
57}
58
59/// A cache dedicated to a Leader node, in order to cache some metadata.
60///
61/// To use this cache, the following constraints must be followed:
62///   1. The leader node can create this metadata.
63///   2. The follower node can create this metadata. The leader node can lazily retrieve
64///      the corresponding data through the caching loading mechanism.
65///   3. Only the leader node can update this metadata, as the cache cannot detect
66///      modifications made to the data on the follower node.
67///   4. Only the leader node can delete this metadata for the same reason mentioned above.
68pub struct LeaderCachedKvBackend {
69    check_leader: CheckLeaderRef,
70    store: KvBackendRef,
71    cache: ResettableKvBackendRef,
72    /// Incremented before and after each store mutation, also while the cache is
73    /// disabled. The first increment detects overlapping writers; the second
74    /// invalidates cache fills and loads that read the old value while the
75    /// store mutation was in flight.
76    version: AtomicUsize,
77    name: String,
78}
79
80impl LeaderCachedKvBackend {
81    pub fn new(check_leader: CheckLeaderRef, store: KvBackendRef) -> Self {
82        let name = format!("LeaderCached({})", store.name());
83        Self {
84            check_leader,
85            store,
86            cache: Arc::new(MemoryKvBackend::new()),
87            version: AtomicUsize::new(0),
88            name,
89        }
90    }
91
92    /// With a leader checker which always returns true when checking,
93    /// mainly used in test scenarios.
94    pub fn with_always_leader(store: KvBackendRef) -> Self {
95        Self::new(Arc::new(AlwaysLeader), store)
96    }
97
98    /// Loads the cached prefixes. Writes may run meanwhile: a prefix whose load overlapped a
99    /// write is dropped from the cache again, and read through later.
100    pub async fn load(&self) -> Result<()> {
101        for prefix in &CACHE_KEY_PREFIXES[..] {
102            let _timer =
103                metrics::METRIC_META_LEADER_CACHED_KV_LOAD_ELAPSED.with_label_values(&[prefix]);
104            let ver = self.get_version();
105
106            // TODO(weny): Refactors PaginationStream's output to unary output.
107            let stream = PaginationStream::new(
108                self.store.clone(),
109                RangeRequest::new().with_prefix(prefix.as_bytes()),
110                DEFAULT_PAGE_SIZE,
111                Ok,
112            )
113            .into_stream();
114
115            let kvs = stream.try_collect::<Vec<_>>().await?;
116            let keys = kvs.iter().map(|kv| kv.key.clone()).collect::<Vec<_>>();
117
118            self.cache
119                .batch_put(BatchPutRequest {
120                    kvs,
121                    prev_kv: false,
122                })
123                .await?;
124            // A write while loading may have changed what was read.
125            if !self.validate_version(ver) {
126                self.invalid_keys(keys).await?;
127            }
128        }
129
130        Ok(())
131    }
132
133    #[inline]
134    fn is_leader(&self) -> bool {
135        self.check_leader.check()
136    }
137
138    #[inline]
139    async fn invalid_key(&self, key: Vec<u8>) -> Result<()> {
140        let _ = self.cache.delete(&key, false).await?;
141        Ok(())
142    }
143
144    #[inline]
145    async fn invalid_keys(&self, keys: Vec<Vec<u8>>) -> Result<()> {
146        let txn = Txn::new().and_then(keys.into_iter().map(TxnOp::Delete).collect::<Vec<_>>());
147        let _ = self.cache.txn(txn).await?;
148        Ok(())
149    }
150
151    #[inline]
152    fn get_version(&self) -> usize {
153        self.version.load(Ordering::Relaxed)
154    }
155
156    #[inline]
157    fn create_new_version(&self) -> usize {
158        self.version.fetch_add(1, Ordering::Relaxed) + 1
159    }
160
161    #[inline]
162    fn validate_version(&self, version: usize) -> bool {
163        version == self.version.load(Ordering::Relaxed)
164    }
165}
166
167#[async_trait::async_trait]
168impl KvBackend for LeaderCachedKvBackend {
169    fn name(&self) -> &str {
170        &self.name
171    }
172
173    fn as_any(&self) -> &dyn Any {
174        self
175    }
176
177    async fn range(&self, req: RangeRequest) -> Result<RangeResponse> {
178        if !self.is_leader() {
179            return self.store.range(req).await;
180        }
181
182        // We can only cache for exact key queries (i.e. get requests)
183        // because we cannot confirm if a range response is complete.
184        if !req.range_end.is_empty() {
185            return self.store.range(req).await;
186        }
187
188        let res = self.cache.range(req.clone()).await?;
189        if !res.kvs.is_empty() {
190            return Ok(res);
191        }
192
193        let ver = self.get_version();
194
195        let res = self
196            .store
197            .range(RangeRequest {
198                // ignores `keys_only`
199                keys_only: false,
200                ..req.clone()
201            })
202            .await?;
203        if !res.kvs.is_empty() {
204            let KeyValue { key, value } = res.kvs[0].clone();
205            let put_req = PutRequest {
206                key: key.clone(),
207                value,
208                ..Default::default()
209            };
210            let _ = self.cache.put(put_req).await?;
211
212            if !self.validate_version(ver) {
213                self.invalid_key(key).await?;
214            }
215        }
216
217        return Ok(res);
218    }
219
220    async fn put(&self, req: PutRequest) -> Result<PutResponse> {
221        let ver = self.create_new_version();
222
223        let res = self.store.put(req.clone()).await?;
224        self.create_new_version();
225        let _ = self.cache.put(req.clone()).await?;
226
227        // Only our own completion increment may follow the starting version.
228        if !self.validate_version(ver + 1) {
229            self.invalid_key(req.key).await?;
230        }
231
232        Ok(res)
233    }
234
235    async fn batch_put(&self, req: BatchPutRequest) -> Result<BatchPutResponse> {
236        let ver = self.create_new_version();
237
238        let res = self.store.batch_put(req.clone()).await?;
239        self.create_new_version();
240        let _ = self.cache.batch_put(req.clone()).await?;
241
242        // Only our own completion increment may follow the starting version.
243        if !self.validate_version(ver + 1) {
244            let keys = req.kvs.into_iter().map(|kv| kv.key).collect::<Vec<_>>();
245            self.invalid_keys(keys).await?;
246        }
247
248        Ok(res)
249    }
250
251    async fn batch_get(&self, req: BatchGetRequest) -> Result<BatchGetResponse> {
252        if !self.is_leader() {
253            return self.store.batch_get(req).await;
254        }
255
256        let cached_res = self.cache.batch_get(req.clone()).await?;
257        let hit_keys = cached_res
258            .kvs
259            .iter()
260            .map(|kv| kv.key.clone())
261            .collect::<HashSet<_>>();
262
263        metrics::METRIC_META_KV_CACHE_HIT
264            .with_label_values(&["batch_get"])
265            .inc_by(hit_keys.len() as u64);
266
267        // The cache hit all keys
268        if cached_res.kvs.len() == req.keys.len() {
269            return Ok(cached_res);
270        }
271
272        let missed_keys = req
273            .keys
274            .iter()
275            .filter(|key| !hit_keys.contains(*key))
276            .cloned()
277            .collect::<Vec<_>>();
278        metrics::METRIC_META_KV_CACHE_MISS
279            .with_label_values(&["batch_get"])
280            .inc_by(missed_keys.len() as u64);
281
282        let remote_req = BatchGetRequest { keys: missed_keys };
283
284        let ver = self.get_version();
285
286        let remote_res = self.store.batch_get(remote_req).await?;
287        let put_req = BatchPutRequest {
288            kvs: remote_res.kvs.clone().into_iter().collect(),
289            ..Default::default()
290        };
291        let _ = self.cache.batch_put(put_req).await?;
292
293        if !self.validate_version(ver) {
294            let keys = remote_res
295                .kvs
296                .iter()
297                .map(|kv| kv.key().to_vec())
298                .collect::<Vec<_>>();
299            self.invalid_keys(keys).await?;
300        }
301
302        let mut merged_res = cached_res;
303        merged_res.kvs.extend(remote_res.kvs);
304        Ok(merged_res)
305    }
306
307    async fn compare_and_put(&self, req: CompareAndPutRequest) -> Result<CompareAndPutResponse> {
308        let _ = self.create_new_version();
309
310        let key = req.key.clone();
311        let res = self.store.compare_and_put(req).await?;
312        self.create_new_version();
313        // Delete key in the cache.
314        //
315        // Cache can not deal with the CAS operation, because it does
316        // not contain full data, so we need to delete the key.
317        self.invalid_key(key).await?;
318        Ok(res)
319    }
320
321    async fn delete_range(&self, req: DeleteRangeRequest) -> Result<DeleteRangeResponse> {
322        let _ = self.create_new_version();
323
324        let res = self.store.delete_range(req.clone()).await?;
325        self.create_new_version();
326        let _ = self.cache.delete_range(req).await?;
327        Ok(res)
328    }
329
330    async fn batch_delete(&self, req: BatchDeleteRequest) -> Result<BatchDeleteResponse> {
331        let _ = self.create_new_version();
332
333        let res = self.store.batch_delete(req.clone()).await?;
334        self.create_new_version();
335        let _ = self.cache.batch_delete(req).await?;
336        Ok(res)
337    }
338}
339
340#[async_trait::async_trait]
341impl TxnService for LeaderCachedKvBackend {
342    type Error = Error;
343
344    async fn txn(&self, txn: Txn) -> Result<TxnResponse> {
345        let _ = self.create_new_version();
346
347        // A transaction may commit even if the backend returns an error.
348        let res = self.store.txn(txn.clone()).await;
349        self.create_new_version();
350        let TxnRequest {
351            success, failure, ..
352        } = txn.into();
353        let mut all = success;
354        all.extend(failure);
355        // Delete all keys in the cache.
356        //
357        // Cache can not deal with the txn operation, because it does
358        // not contain full data, so we need to delete both keys.
359        let mut keys = Vec::with_capacity(all.len());
360        for txn_op in all {
361            match txn_op {
362                TxnOp::Put(key, _) => {
363                    keys.push(key);
364                }
365                TxnOp::Delete(key) => {
366                    keys.push(key);
367                }
368                TxnOp::Get(_) => {}
369            }
370        }
371        let invalidation = self.invalid_keys(keys).await;
372        // Preserve the backend error after completing cache invalidation.
373        let res = res?;
374        invalidation?;
375
376        Ok(res)
377    }
378
379    fn max_txn_ops(&self) -> usize {
380        self.store.max_txn_ops()
381    }
382}
383
384impl ResettableKvBackend for LeaderCachedKvBackend {
385    fn reset(&self) {
386        self.create_new_version();
387        self.cache.reset()
388    }
389
390    fn as_kv_backend_ref(self: Arc<Self>) -> KvBackendRef<Self::Error> {
391        self
392    }
393}
394
395#[cfg(test)]
396mod tests {
397    use std::sync::Mutex;
398
399    use common_meta::kv_backend::txn::{Compare, CompareOp};
400    use common_meta::rpc::KeyValue;
401    use futures::poll;
402    use tokio::sync::oneshot;
403
404    use super::*;
405
406    /// Pauses one backend call at a known point, without relying on task scheduling.
407    #[derive(Default)]
408    struct Pause {
409        receiver: Mutex<Option<oneshot::Receiver<()>>>,
410    }
411
412    impl Pause {
413        fn arm(&self) -> oneshot::Sender<()> {
414            let (sender, receiver) = oneshot::channel();
415            assert!(self.receiver.lock().unwrap().replace(receiver).is_none());
416            sender
417        }
418
419        async fn wait(&self) {
420            let receiver = self.receiver.lock().unwrap().take();
421            if let Some(receiver) = receiver {
422                receiver.await.unwrap();
423            }
424        }
425    }
426
427    #[derive(Clone, Copy)]
428    enum TxnError {
429        BeforeCommit,
430        AfterCommit,
431    }
432
433    #[derive(Default)]
434    struct ControlledBackend {
435        inner: MemoryKvBackend<Error>,
436        before_write: Pause,
437        after_write: Pause,
438        after_read: Pause,
439        txn_error: Mutex<Option<TxnError>>,
440    }
441
442    #[async_trait::async_trait]
443    impl TxnService for ControlledBackend {
444        type Error = Error;
445
446        async fn txn(&self, txn: Txn) -> Result<TxnResponse> {
447            let error = self.txn_error.lock().unwrap().take();
448            self.before_write.wait().await;
449            if matches!(error, Some(TxnError::BeforeCommit)) {
450                return common_meta::error::UnexpectedSnafu {
451                    err_msg: "injected transaction error",
452                }
453                .fail();
454            }
455            let res = self.inner.txn(txn).await;
456            self.after_write.wait().await;
457            if matches!(error, Some(TxnError::AfterCommit)) {
458                return common_meta::error::UnexpectedSnafu {
459                    err_msg: "injected transaction error",
460                }
461                .fail();
462            }
463            res
464        }
465
466        fn max_txn_ops(&self) -> usize {
467            self.inner.max_txn_ops()
468        }
469    }
470
471    #[async_trait::async_trait]
472    impl KvBackend for ControlledBackend {
473        fn name(&self) -> &str {
474            "ControlledBackend"
475        }
476
477        fn as_any(&self) -> &dyn Any {
478            self
479        }
480
481        async fn range(&self, req: RangeRequest) -> Result<RangeResponse> {
482            let res = self.inner.range(req).await;
483            self.after_read.wait().await;
484            res
485        }
486
487        async fn batch_get(&self, req: BatchGetRequest) -> Result<BatchGetResponse> {
488            let res = self.inner.batch_get(req).await;
489            self.after_read.wait().await;
490            res
491        }
492
493        async fn put(&self, req: PutRequest) -> Result<PutResponse> {
494            self.before_write.wait().await;
495            let res = self.inner.put(req).await;
496            self.after_write.wait().await;
497            res
498        }
499
500        async fn batch_put(&self, req: BatchPutRequest) -> Result<BatchPutResponse> {
501            self.before_write.wait().await;
502            let res = self.inner.batch_put(req).await;
503            self.after_write.wait().await;
504            res
505        }
506
507        async fn delete_range(&self, req: DeleteRangeRequest) -> Result<DeleteRangeResponse> {
508            self.before_write.wait().await;
509            let res = self.inner.delete_range(req).await;
510            self.after_write.wait().await;
511            res
512        }
513
514        async fn batch_delete(&self, req: BatchDeleteRequest) -> Result<BatchDeleteResponse> {
515            self.before_write.wait().await;
516            let res = self.inner.batch_delete(req).await;
517            self.after_write.wait().await;
518            res
519        }
520    }
521
522    #[derive(Clone, Copy, Debug)]
523    enum Write {
524        Txn,
525        TxnFailure,
526        Put,
527        BatchPut,
528        CompareAndPut,
529        DeleteRange,
530        BatchDelete,
531    }
532
533    const WRITES: [Write; 7] = [
534        Write::Txn,
535        Write::TxnFailure,
536        Write::Put,
537        Write::BatchPut,
538        Write::CompareAndPut,
539        Write::DeleteRange,
540        Write::BatchDelete,
541    ];
542    /// Under the first prefix the leader cache loads.
543    const KEY: &[u8] = b"__table_name/1";
544
545    impl Write {
546        async fn execute(self, store: &LeaderCachedKvBackend, value: &[u8]) {
547            match self {
548                Self::Txn => {
549                    store
550                        .txn(Txn::new().and_then(vec![TxnOp::Put(KEY.to_vec(), value.to_vec())]))
551                        .await
552                        .unwrap();
553                }
554                Self::TxnFailure => {
555                    let res = store
556                        .txn(
557                            Txn::new()
558                                .when(vec![Compare::with_value_not_exists(
559                                    KEY.to_vec(),
560                                    CompareOp::Equal,
561                                )])
562                                .or_else(vec![TxnOp::Put(KEY.to_vec(), value.to_vec())]),
563                        )
564                        .await
565                        .unwrap();
566                    assert!(!res.succeeded);
567                }
568                Self::Put => {
569                    store
570                        .put(PutRequest::new().with_key(KEY).with_value(value))
571                        .await
572                        .unwrap();
573                }
574                Self::BatchPut => {
575                    store
576                        .batch_put(BatchPutRequest {
577                            kvs: vec![KeyValue {
578                                key: KEY.to_vec(),
579                                value: value.to_vec(),
580                            }],
581                            ..Default::default()
582                        })
583                        .await
584                        .unwrap();
585                }
586                Self::CompareAndPut => {
587                    let res = store
588                        .compare_and_put(
589                            CompareAndPutRequest::new()
590                                .with_key(KEY)
591                                .with_expect(b"old")
592                                .with_value(value),
593                        )
594                        .await
595                        .unwrap();
596                    assert!(res.success);
597                }
598                Self::DeleteRange => {
599                    store
600                        .delete_range(DeleteRangeRequest::new().with_key(KEY))
601                        .await
602                        .unwrap();
603                }
604                Self::BatchDelete => {
605                    store
606                        .batch_delete(BatchDeleteRequest {
607                            keys: vec![KEY.to_vec()],
608                            prev_kv: false,
609                        })
610                        .await
611                        .unwrap();
612                }
613            }
614        }
615    }
616
617    async fn read(store: &LeaderCachedKvBackend, batch: bool) -> Option<KeyValue> {
618        if batch {
619            store
620                .batch_get(BatchGetRequest {
621                    keys: vec![KEY.to_vec()],
622                })
623                .await
624                .unwrap()
625                .kvs
626                .pop()
627        } else {
628            store.get(KEY).await.unwrap()
629        }
630    }
631
632    #[tokio::test]
633    async fn test_txn_error_invalidates_both_branches() {
634        const OTHER_KEY: &[u8] = b"__table_name/2";
635        for error in [TxnError::BeforeCommit, TxnError::AfterCommit] {
636            for success in [false, true] {
637                let backing = Arc::new(ControlledBackend::default());
638                let store = LeaderCachedKvBackend::with_always_leader(backing.clone());
639                for key in [KEY, OTHER_KEY] {
640                    store
641                        .put(PutRequest::new().with_key(key).with_value(b"old"))
642                        .await
643                        .unwrap();
644                    assert!(store.cache.get(key).await.unwrap().is_some());
645                }
646                *backing.txn_error.lock().unwrap() = Some(error);
647                let txn = Txn::new()
648                    .when(vec![Compare::with_value(
649                        KEY.to_vec(),
650                        CompareOp::Equal,
651                        if success {
652                            b"old".to_vec()
653                        } else {
654                            b"missing".to_vec()
655                        },
656                    )])
657                    .and_then(vec![TxnOp::Put(KEY.to_vec(), b"new".to_vec())])
658                    .or_else(vec![TxnOp::Delete(OTHER_KEY.to_vec())]);
659                let err = store.txn(txn).await.err().unwrap();
660                assert!(matches!(err, Error::Unexpected { err_msg, .. }
661                    if err_msg == "injected transaction error"));
662                for key in [KEY, OTHER_KEY] {
663                    assert!(store.cache.get(key).await.unwrap().is_none());
664                    assert_eq!(
665                        store.get(key).await.unwrap(),
666                        backing.inner.get(key).await.unwrap()
667                    );
668                }
669                let expected = if matches!(error, TxnError::AfterCommit) && success {
670                    b"new".as_slice()
671                } else {
672                    b"old".as_slice()
673                };
674                assert_eq!(store.get(KEY).await.unwrap().unwrap().value(), expected);
675                assert_eq!(
676                    store.get(OTHER_KEY).await.unwrap().is_none(),
677                    matches!(error, TxnError::AfterCommit) && !success
678                );
679            }
680        }
681    }
682
683    #[tokio::test]
684    async fn test_txn_error_invalidates_overlapping_cache_fill() {
685        for batch in [false, true] {
686            let backing = Arc::new(ControlledBackend::default());
687            backing
688                .inner
689                .put(PutRequest::new().with_key(KEY).with_value(b"old"))
690                .await
691                .unwrap();
692            let store = LeaderCachedKvBackend::with_always_leader(backing.clone());
693            *backing.txn_error.lock().unwrap() = Some(TxnError::AfterCommit);
694            let commit = backing.before_write.arm();
695            let writer =
696                store.txn(Txn::new().and_then(vec![TxnOp::Put(KEY.to_vec(), b"new".to_vec())]));
697            tokio::pin!(writer);
698            assert!(poll!(writer.as_mut()).is_pending());
699
700            let return_read = backing.after_read.arm();
701            let reader = read(&store, batch);
702            tokio::pin!(reader);
703            assert!(poll!(reader.as_mut()).is_pending());
704            commit.send(()).unwrap();
705            assert!(writer.await.is_err());
706            return_read.send(()).unwrap();
707            assert_eq!(reader.await.unwrap().value(), b"old");
708            assert_eq!(read(&store, batch).await.unwrap().value(), b"new");
709        }
710    }
711
712    /// A cache miss reads the old value after a writer starts, then returns after
713    /// the writer has committed and updated/invalidated the cache (#9548).
714    #[tokio::test]
715    async fn test_cache_miss_overlaps_write() {
716        for write in WRITES {
717            for batch in [true, false] {
718                let backing = Arc::new(ControlledBackend::default());
719                backing
720                    .inner
721                    .put(PutRequest::new().with_key(KEY).with_value(b"old"))
722                    .await
723                    .unwrap();
724                let store = LeaderCachedKvBackend::with_always_leader(backing.clone());
725
726                let commit = backing.before_write.arm();
727                let writer = write.execute(&store, b"new");
728                tokio::pin!(writer);
729                assert!(poll!(writer.as_mut()).is_pending());
730
731                let return_read = backing.after_read.arm();
732                let reader = read(&store, batch);
733                tokio::pin!(reader);
734                assert!(poll!(reader.as_mut()).is_pending());
735
736                commit.send(()).unwrap();
737                writer.await;
738                return_read.send(()).unwrap();
739                assert_eq!(reader.await.unwrap().value(), b"old");
740
741                let durable = backing.inner.get(KEY).await.unwrap();
742                assert_eq!(
743                    read(&store, batch).await,
744                    durable,
745                    "{write:?}, batch={batch}"
746                );
747            }
748        }
749    }
750
751    /// Start order, commit order and response order can all differ. An older
752    /// put response must not overwrite the cache after a newer mutation.
753    #[tokio::test]
754    async fn test_overlapping_writes() {
755        for first in [Write::Put, Write::BatchPut] {
756            for second in WRITES {
757                for reverse_commit in [false, true] {
758                    let backing = Arc::new(ControlledBackend::default());
759                    backing
760                        .inner
761                        .put(PutRequest::new().with_key(KEY).with_value(b"old"))
762                        .await
763                        .unwrap();
764                    let store = LeaderCachedKvBackend::with_always_leader(backing.clone());
765
766                    let resume = if reverse_commit {
767                        backing.before_write.arm()
768                    } else {
769                        backing.after_write.arm()
770                    };
771                    // Keep the initial value so the second CAS succeeds.
772                    let writer = first.execute(&store, b"old");
773                    tokio::pin!(writer);
774                    assert!(poll!(writer.as_mut()).is_pending());
775                    second.execute(&store, b"new").await;
776                    resume.send(()).unwrap();
777                    writer.await;
778
779                    let durable = backing.inner.get(KEY).await.unwrap();
780                    assert_eq!(
781                        read(&store, true).await,
782                        durable,
783                        "{first:?}, {second:?}, reverse_commit={reverse_commit}"
784                    );
785                }
786            }
787        }
788    }
789
790    /// The later-started put commits first but returns last, after its stored
791    /// value has already been replaced by the first writer.
792    #[tokio::test]
793    async fn test_write_response_reordering() {
794        for first in WRITES {
795            for second in [Write::Put, Write::BatchPut] {
796                let backing = Arc::new(ControlledBackend::default());
797                backing
798                    .inner
799                    .put(PutRequest::new().with_key(KEY).with_value(b"old"))
800                    .await
801                    .unwrap();
802                let store = LeaderCachedKvBackend::with_always_leader(backing.clone());
803
804                let commit_first = backing.before_write.arm();
805                let first_writer = first.execute(&store, b"new");
806                tokio::pin!(first_writer);
807                assert!(poll!(first_writer.as_mut()).is_pending());
808
809                let return_second = backing.after_write.arm();
810                let second_writer = second.execute(&store, b"old");
811                tokio::pin!(second_writer);
812                assert!(poll!(second_writer.as_mut()).is_pending());
813
814                commit_first.send(()).unwrap();
815                first_writer.await;
816                return_second.send(()).unwrap();
817                second_writer.await;
818
819                let durable = backing.inner.get(KEY).await.unwrap();
820                assert_eq!(read(&store, true).await, durable, "{first:?}, {second:?}");
821            }
822        }
823    }
824
825    struct EnableCache(std::sync::atomic::AtomicBool);
826
827    impl CheckLeader for EnableCache {
828        fn check(&self) -> bool {
829            self.0.load(Ordering::Relaxed)
830        }
831    }
832
833    /// A write made while the cache is disabled overlaps the load: the load reads the old value
834    /// either before the write commits and installs it afterwards, or while the write is in
835    /// flight and completes, with the cache enabled, before the write commits.
836    #[tokio::test]
837    async fn test_load_overlaps_write() {
838        for write in WRITES {
839            for write_first in [false, true] {
840                let backing = Arc::new(ControlledBackend::default());
841                backing
842                    .inner
843                    .put(PutRequest::new().with_key(KEY).with_value(b"old"))
844                    .await
845                    .unwrap();
846                let enabled = Arc::new(EnableCache(Default::default()));
847                let store = LeaderCachedKvBackend::new(enabled.clone(), backing.clone());
848
849                if write_first {
850                    let commit = backing.before_write.arm();
851                    let writer = write.execute(&store, b"new");
852                    tokio::pin!(writer);
853                    assert!(poll!(writer.as_mut()).is_pending());
854                    store.load().await.unwrap();
855                    enabled.0.store(true, Ordering::Relaxed);
856                    commit.send(()).unwrap();
857                    writer.await;
858                } else {
859                    let return_read = backing.after_read.arm();
860                    let loader = store.load();
861                    tokio::pin!(loader);
862                    assert!(poll!(loader.as_mut()).is_pending());
863                    write.execute(&store, b"new").await;
864                    return_read.send(()).unwrap();
865                    loader.await.unwrap();
866                    enabled.0.store(true, Ordering::Relaxed);
867                }
868
869                let durable = backing.inner.get(KEY).await.unwrap();
870                assert_eq!(
871                    read(&store, false).await,
872                    durable,
873                    "{write:?}, write_first={write_first}"
874                );
875            }
876        }
877    }
878
879    #[tokio::test]
880    async fn test_cache_miss_overlaps_reset() {
881        for batch in [true, false] {
882            let backing = Arc::new(ControlledBackend::default());
883            backing
884                .inner
885                .put(PutRequest::new().with_key(KEY).with_value(b"old"))
886                .await
887                .unwrap();
888            let store = LeaderCachedKvBackend::with_always_leader(backing.clone());
889
890            let return_read = backing.after_read.arm();
891            let reader = read(&store, batch);
892            tokio::pin!(reader);
893            assert!(poll!(reader.as_mut()).is_pending());
894            store.reset();
895            return_read.send(()).unwrap();
896            reader.await;
897            assert!(store.cache.get(KEY).await.unwrap().is_none());
898        }
899    }
900
901    fn create_leader_cached_kv_backend() -> LeaderCachedKvBackend {
902        let store = Arc::new(MemoryKvBackend::new());
903        LeaderCachedKvBackend::with_always_leader(store)
904    }
905
906    #[tokio::test]
907    async fn test_get_put_delete() {
908        let cached_store = create_leader_cached_kv_backend();
909        let inner_store = cached_store.store.clone();
910        let inner_cache = cached_store.cache.clone();
911
912        let key = "test_key".to_owned().into_bytes();
913        let value = "value".to_owned().into_bytes();
914
915        let put_req = PutRequest {
916            key: key.clone(),
917            value: value.clone(),
918            ..Default::default()
919        };
920        let _ = inner_store.put(put_req).await.unwrap();
921
922        let cached_value = inner_cache.get(&key).await.unwrap();
923        assert!(cached_value.is_none());
924
925        let cached_value = cached_store.get(&key).await.unwrap().unwrap();
926        assert_eq!(cached_value.value(), value);
927
928        let cached_value = inner_cache.get(&key).await.unwrap().unwrap();
929        assert_eq!(cached_value.value(), value);
930
931        let res = cached_store.delete(&key, true).await.unwrap().unwrap();
932        assert_eq!(res.value(), value);
933
934        let cached_value = inner_cache.get(&key).await.unwrap();
935        assert!(cached_value.is_none());
936    }
937
938    #[tokio::test]
939    async fn test_batch_get_put_delete() {
940        let cached_store = create_leader_cached_kv_backend();
941        let inner_store = cached_store.store.clone();
942        let inner_cache = cached_store.cache.clone();
943
944        let kvs = (1..3)
945            .map(|i| {
946                let key = format!("test_key_{}", i).into_bytes();
947                let value = format!("value_{}", i).into_bytes();
948                KeyValue { key, value }
949            })
950            .collect::<Vec<_>>();
951
952        let batch_put_req = BatchPutRequest {
953            kvs: kvs.clone(),
954            ..Default::default()
955        };
956
957        let _ = inner_store.batch_put(batch_put_req).await.unwrap();
958
959        let keys = (1..5)
960            .map(|i| format!("test_key_{}", i).into_bytes())
961            .collect::<Vec<_>>();
962
963        let batch_get_req = BatchGetRequest { keys };
964
965        let cached_values = inner_cache.batch_get(batch_get_req.clone()).await.unwrap();
966        assert!(cached_values.kvs.is_empty());
967
968        let cached_values = cached_store.batch_get(batch_get_req.clone()).await.unwrap();
969        assert_eq!(cached_values.kvs.len(), 2);
970
971        let cached_values = inner_cache.batch_get(batch_get_req.clone()).await.unwrap();
972        assert_eq!(cached_values.kvs.len(), 2);
973
974        cached_store.reset();
975
976        let cached_values = inner_cache.batch_get(batch_get_req).await.unwrap();
977        assert!(cached_values.kvs.is_empty());
978    }
979
980    #[tokio::test]
981    async fn test_txn() {
982        let cached_store = create_leader_cached_kv_backend();
983        let inner_cache = cached_store.cache.clone();
984
985        let kvs = (1..5)
986            .map(|i| {
987                let key = format!("test_key_{}", i).into_bytes();
988                let value = format!("value_{}", i).into_bytes();
989                KeyValue { key, value }
990            })
991            .collect::<Vec<_>>();
992
993        let batch_put_req = BatchPutRequest {
994            kvs: kvs.clone(),
995            ..Default::default()
996        };
997        let _ = cached_store.batch_put(batch_put_req).await.unwrap();
998
999        let keys = (1..5)
1000            .map(|i| format!("test_key_{}", i).into_bytes())
1001            .collect::<Vec<_>>();
1002        let batch_get_req = BatchGetRequest { keys };
1003        let cached_values = inner_cache.batch_get(batch_get_req.clone()).await.unwrap();
1004        assert_eq!(cached_values.kvs.len(), 4);
1005
1006        let put_ops = (1..5)
1007            .map(|i| {
1008                let key = format!("test_key_{}", i).into_bytes();
1009                let value = format!("value_{}", i).into_bytes();
1010                TxnOp::Put(key, value)
1011            })
1012            .collect::<Vec<_>>();
1013        let txn = Txn::new().and_then(put_ops);
1014        let _ = cached_store.txn(txn).await.unwrap();
1015
1016        let cached_values = inner_cache.batch_get(batch_get_req).await.unwrap();
1017        assert!(cached_values.kvs.is_empty());
1018    }
1019}