1/* 2 * 3 * Copyright 2020 gRPC authors. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 19// Package cache provides an LRU cache implementation to be used by the RLS LB 20// policy to cache RLS response data. 21package cache 22 23import ( 24 "container/list" 25 "sync" 26 "time" 27 28 "google.golang.org/grpc/balancer" 29 "google.golang.org/grpc/grpclog" 30 "google.golang.org/grpc/internal/backoff" 31) 32 33// Key represents the cache key used to uniquely identify a cache entry. 34type Key struct { 35 // Path is the full path of the incoming RPC request. 36 Path string 37 // KeyMap is a stringified version of the RLS request keys built using the 38 // RLS keyBuilder. Since map is not a Type which is comparable in Go, it 39 // cannot be part of the key for another map (the LRU cache is implemented 40 // using a native map type). 41 KeyMap string 42} 43 44// Entry wraps all the data to be stored in a cache entry. 45type Entry struct { 46 // Mu synchronizes access to this particular cache entry. The LB policy 47 // will also hold another mutex to synchronize access to the cache as a 48 // whole. To avoid holding the top-level mutex for the whole duration for 49 // which one particular cache entry is acted upon, we use this entry mutex. 50 Mu sync.Mutex 51 // ExpiryTime is the absolute time at which the data cached as part of this 52 // entry stops being valid. When an RLS request succeeds, this is set to 53 // the current time plus the max_age field from the LB policy config. An 54 // entry with this field in the past is not used to process picks. 55 ExpiryTime time.Time 56 // BackoffExpiryTime is the absolute time at which an entry which has gone 57 // through backoff stops being valid. When an RLS request fails, this is 58 // set to the current time plus twice the backoff time. The cache expiry 59 // timer will only delete entries for which both ExpiryTime and 60 // BackoffExpiryTime are in the past. 61 BackoffExpiryTime time.Time 62 // StaleTime is the absolute time after which this entry will be 63 // proactively refreshed if we receive a request for it. When an RLS 64 // request succeeds, this is set to the current time plus the stale_age 65 // from the LB policy config. 66 StaleTime time.Time 67 // BackoffTime is the absolute time at which the backoff period for this 68 // entry ends. The backoff timer is setup with this value. No new RLS 69 // requests are sent out for this entry until the backoff period ends. 70 BackoffTime time.Time 71 // EarliestEvictTime is the absolute time before which this entry should 72 // not be evicted from the cache. This is set to a default value of 5 73 // seconds when the entry is created. This is required to make sure that a 74 // new entry added to the cache is not evicted before the RLS response 75 // arrives (usually when the cache is too small). 76 EarliestEvictTime time.Time 77 // CallStatus stores the RPC status of the previous RLS request for this 78 // entry. Picks for entries with a non-nil value for this field are failed 79 // with the error stored here. 80 CallStatus error 81 // Backoff contains all backoff related state. When an RLS request 82 // succeeds, backoff state is reset. 83 Backoff BackoffState 84 // HeaderData is received in an RLS response and is to be sent in the 85 // X-Google-RLS-Data header for matching RPCs. 86 HeaderData string 87 // ChildPicker is a very thin wrapper around the child policy wrapper. 88 // The type is declared as a Picker interface since the users of 89 // the cache only care about the picker provided by the child policy, and 90 // this makes it easy for testing. 91 ChildPicker balancer.Picker 92 93 // size stores the size of this cache entry. Uses only a subset of the 94 // fields. See `entrySize` for this is computed. 95 size int64 96 // key contains the cache key corresponding to this entry. This is required 97 // from methods like `removeElement` which only have a pointer to the 98 // list.Element which contains a reference to the cache.Entry. But these 99 // methods need the cache.Key to be able to remove the entry from the 100 // underlying map. 101 key Key 102} 103 104// BackoffState wraps all backoff related state associated with a cache entry. 105type BackoffState struct { 106 // Retries keeps track of the number of RLS failures, to be able to 107 // determine the amount of time to backoff before the next attempt. 108 Retries int 109 // Backoff is an exponential backoff implementation which returns the 110 // amount of time to backoff, given the number of retries. 111 Backoff backoff.Strategy 112 // Timer fires when the backoff period ends and incoming requests after 113 // this will trigger a new RLS request. 114 Timer *time.Timer 115 // Callback provided by the LB policy to be notified when the backoff timer 116 // expires. This will trigger a new picker to be returned to the 117 // ClientConn, to force queued up RPCs to be retried. 118 Callback func() 119} 120 121// LRU is a cache with a least recently used eviction policy. It is not safe 122// for concurrent access. 123type LRU struct { 124 maxSize int64 125 usedSize int64 126 onEvicted func(Key, *Entry) 127 128 ll *list.List 129 cache map[Key]*list.Element 130} 131 132// NewLRU creates a cache.LRU with a size limit of maxSize and the provided 133// eviction callback. 134// 135// Currently, only the cache.Key and the HeaderData field from cache.Entry 136// count towards the size of the cache (other overhead per cache entry is not 137// counted). The cache could temporarily exceed the configured maxSize because 138// we want the entries to spend a configured minimum amount of time in the 139// cache before they are LRU evicted (so that all the work performed in sending 140// an RLS request and caching the response is not a total waste). 141// 142// The provided onEvited callback must not attempt to re-add the entry inline 143// and the RLS LB policy does not have a need to do that. 144// 145// The cache package trusts the RLS policy (its only user) to supply a default 146// minimum non-zero maxSize, in the event that the ServiceConfig does not 147// provide a value for it. 148func NewLRU(maxSize int64, onEvicted func(Key, *Entry)) *LRU { 149 return &LRU{ 150 maxSize: maxSize, 151 onEvicted: onEvicted, 152 ll: list.New(), 153 cache: make(map[Key]*list.Element), 154 } 155} 156 157// Resize sets the size limit of the LRU to newMaxSize and removes older 158// entries, if required, to comply with the new limit. 159func (lru *LRU) Resize(newMaxSize int64) { 160 lru.maxSize = newMaxSize 161 lru.removeToFit(0) 162} 163 164// TODO(easwars): If required, make this function more sophisticated. 165func entrySize(key Key, value *Entry) int64 { 166 return int64(len(key.Path) + len(key.KeyMap) + len(value.HeaderData)) 167} 168 169// removeToFit removes older entries from the cache to make room for a new 170// entry of size newSize. 171func (lru *LRU) removeToFit(newSize int64) { 172 now := time.Now() 173 for lru.usedSize+newSize > lru.maxSize { 174 elem := lru.ll.Back() 175 if elem == nil { 176 // This is a corner case where the cache is empty, but the new entry 177 // to be added is bigger than maxSize. 178 grpclog.Info("rls: newly added cache entry exceeds cache maxSize") 179 return 180 } 181 182 entry := elem.Value.(*Entry) 183 if t := entry.EarliestEvictTime; !t.IsZero() && t.Before(now) { 184 // When the oldest entry is too new (it hasn't even spent a default 185 // minimum amount of time in the cache), we abort and allow the 186 // cache to grow bigger than the configured maxSize. 187 grpclog.Info("rls: LRU eviction finds oldest entry to be too new. Allowing cache to exceed maxSize momentarily") 188 return 189 } 190 lru.removeElement(elem) 191 } 192} 193 194// Add adds a new entry to the cache. 195func (lru *LRU) Add(key Key, value *Entry) { 196 size := entrySize(key, value) 197 elem, ok := lru.cache[key] 198 if !ok { 199 lru.removeToFit(size) 200 lru.usedSize += size 201 value.size = size 202 value.key = key 203 elem := lru.ll.PushFront(value) 204 lru.cache[key] = elem 205 return 206 } 207 208 existing := elem.Value.(*Entry) 209 sizeDiff := size - existing.size 210 lru.removeToFit(sizeDiff) 211 value.size = size 212 elem.Value = value 213 lru.ll.MoveToFront(elem) 214 lru.usedSize += sizeDiff 215} 216 217// Remove removes a cache entry wth key key, if one exists. 218func (lru *LRU) Remove(key Key) { 219 if elem, ok := lru.cache[key]; ok { 220 lru.removeElement(elem) 221 } 222} 223 224func (lru *LRU) removeElement(e *list.Element) { 225 entry := e.Value.(*Entry) 226 lru.ll.Remove(e) 227 delete(lru.cache, entry.key) 228 lru.usedSize -= entry.size 229 if lru.onEvicted != nil { 230 lru.onEvicted(entry.key, entry) 231 } 232} 233 234// Get returns a cache entry with key key. 235func (lru *LRU) Get(key Key) *Entry { 236 elem, ok := lru.cache[key] 237 if !ok { 238 return nil 239 } 240 lru.ll.MoveToFront(elem) 241 return elem.Value.(*Entry) 242} 243