| /* |
| * Copyright 2013 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| // Author: jmarantz@google.com (Joshua Marantz) |
| |
| #ifndef NET_INSTAWEB_UTIL_PUBLIC_PURGE_SET_H_ |
| #define NET_INSTAWEB_UTIL_PUBLIC_PURGE_SET_H_ |
| |
| #include <algorithm> |
| #include <cstddef> |
| |
| #include "pagespeed/kernel/base/basictypes.h" |
| #include "pagespeed/kernel/base/scoped_ptr.h" |
| #include "pagespeed/kernel/base/string.h" |
| #include "pagespeed/kernel/base/timer.h" |
| #include "pagespeed/kernel/cache/lru_cache_base.h" |
| |
| namespace net_instaweb { |
| |
| |
| |
| // Maintains a bounded collection of cache-purge records. These can |
| // be used to validate data read from a cache. |
| // |
| // The entire cache can be flushed as of a certain point in time by |
| // calling UpdateInvalidationTimestampMs. |
| // |
| // We bound the cache-purge data to a certain number of bytes. When |
| // we exceed that, we discard old invalidation records, and bump up |
| // the global invalidation timestamp to cover the evicted purges. |
| class PurgeSet { |
| class InvalidationTimestampHelper; |
| typedef LRUCacheBase<int64, InvalidationTimestampHelper> Lru; |
| |
| public: |
| typedef Lru::Iterator Iterator; |
| |
| // Used for sanity checking timestamps read from the cache.flush file, |
| // allowing for small skew and system clock adjustments. Setting this |
| // to 10 minutes means that we can prevent any cache entries from |
| // being valid for 10 minutes, disabling whatever functionality is |
| // dependent on that. |
| static const int64 kClockSkewAllowanceMs = 10 * Timer::kMinuteMs; |
| |
| // Initial value used for the global timestamp. This means there |
| // is no valid timestamp. |
| static const int64 kInitialTimestampMs = -1; |
| |
| // The default constructor makes a 1-byte invalidation set. Use |
| // set_max_size after construction. The default constructor is |
| // needed for CopyOnWrite. |
| PurgeSet(); |
| |
| explicit PurgeSet(size_t max_size); |
| PurgeSet(const PurgeSet& src); |
| ~PurgeSet(); |
| |
| // Call this immediately after construction. |
| void set_max_size(size_t x) { lru_->set_max_bytes_in_cache(x); } |
| |
| PurgeSet& operator=(const PurgeSet& src); |
| |
| // Flushes any item in the cache older than timestamp_ms. |
| // |
| // |
| // Returns false if this request represents an excessive warp back in |
| // time. |
| bool UpdateGlobalInvalidationTimestampMs(int64 timestamp_ms); |
| |
| // Adds a new cache purge record to the set. If we spill over our |
| // invalidation limit, we will reset the global cache purge-point based |
| // on the evicted node. |
| // |
| // Returns false if this request represents an excessive warp back in |
| // time. |
| bool Put(const GoogleString& key, int64 timestamp_ms); |
| |
| // Merge two invalidation records. |
| void Merge(const PurgeSet& src); |
| |
| // Validates a key against specific invalidation records for that |
| // key, and against the overall invalidation timestamp/ |
| bool IsValid(const GoogleString& key, int64 timestamp_ms) const; |
| |
| int64 global_invalidation_timestamp_ms() const { |
| return global_invalidation_timestamp_ms_; |
| } |
| |
| bool has_global_invalidation_timestamp_ms() const { |
| return global_invalidation_timestamp_ms_ != kInitialTimestampMs; |
| } |
| |
| Iterator Begin() const { return lru_->Begin(); } |
| Iterator End() const { return lru_->End(); } |
| |
| int num_elements() const { return lru_->num_elements(); } |
| void Clear(); |
| void Swap(PurgeSet* that); |
| |
| bool Equals(const PurgeSet& that) const; |
| bool empty() const; |
| |
| GoogleString ToString() const; |
| |
| private: |
| class InvalidationTimestampHelper { |
| public: |
| explicit InvalidationTimestampHelper(PurgeSet* purge_set) |
| : purge_set_(purge_set) { |
| } |
| |
| size_t size(int64 value) const { |
| return sizeof(value); |
| } |
| bool Equal(int64 a, int64 b) const { |
| return a == b; |
| } |
| |
| // Update global invalidation timestamp whenever a purge record is |
| // evicted to guarantee that that resource remains purged. |
| void EvictNotify(int64 evicted_record_timestamp_ms) { |
| purge_set_->EvictNotify(evicted_record_timestamp_ms); |
| } |
| |
| // Only replace purge records if the new one is newer. |
| bool ShouldReplace(int64 old_timestamp_ms, int64 new_timestamp_ms) const { |
| return new_timestamp_ms > old_timestamp_ms; |
| } |
| |
| void Swap(InvalidationTimestampHelper* that) { |
| std::swap(purge_set_, that->purge_set_); |
| } |
| |
| private: |
| PurgeSet* purge_set_; |
| }; |
| |
| friend class InvalidationTimestampHelper; |
| |
| void EvictNotify(int64 evicted_record_timestamp_ms); |
| |
| // Determines whether this timestamp is monotonically increasing from |
| // previous ones encountered. Small amounts of time-reversal are handled |
| // by setting them to a recently observed time. Large amounts of |
| // time-reversal cause false to be returned. |
| // |
| // Here several scenarios: |
| // 1. Time goes backward by a few minutes or less: |
| // a. On purge requests, force monotonically increasing time. |
| // b. IsValid: we may report false negatives, disabling PageSpeed |
| // for a few minutes. |
| // 2. Time moves backward by a large amount (>10 minutes): |
| // a. Purge requests: rejected until time is corrected. The only |
| // sure-fire remedy is to delete all caches, restart memcached |
| // and pagespeed servers. |
| // b. IsValid: returns false, disabling PageSpeed until the situation |
| // is corrected. We view it as unacceptable to bring purged cache |
| // entries back from the dead. |
| // TODO(jmarantz): add a statistic that gets bumped from IsValid when |
| // a far-future expires is detected. |
| bool SanitizeTimestamp(int64* timestamp_ms); |
| |
| // Global invalidation timestamp value. Anything with a timestamp older than |
| // this is considered purged already. |
| int64 global_invalidation_timestamp_ms_; |
| |
| // last_invalidation_timestamp_ms is used to keep the data structure invariant |
| // in the face of time jumping backwards. That can happen if someone resets |
| // the system-clock or there is a correction due to NTP sync, etc. |
| int64 last_invalidation_timestamp_ms_; |
| |
| InvalidationTimestampHelper helper_; |
| scoped_ptr<Lru> lru_; |
| |
| // Explicit copy-constructor and assign-operator are provided so |
| // this class can be used for CopyOnWrite. |
| }; |
| |
| } // namespace net_instaweb |
| |
| #endif // NET_INSTAWEB_UTIL_PUBLIC_PURGE_SET_H_ |