intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

7 files changed, 1502 insertions, 0 deletions

diff --git a/library/cpp/cache/cache.cpp b/library/cpp/cache/cache.cpp
new file mode 100644
index 0000000000..05b26b0cf8
--- /dev/null
+++ b/library/cpp/cache/cache.cpp
@@ -0,0 +1 @@
+#include "cache.h"
diff --git a/library/cpp/cache/cache.h b/library/cpp/cache/cache.h
new file mode 100644
index 0000000000..6dc997076d
--- /dev/null
+++ b/library/cpp/cache/cache.h
@@ -0,0 +1,649 @@
+#pragma once
+
+#include <util/generic/algorithm.h>
+#include <util/generic/ptr.h>
+#include <util/generic/intrlist.h>
+#include <util/generic/hash_set.h>
+#include <util/generic/vector.h>
+#include <util/generic/yexception.h>
+#include <utility>
+
+template <class TValue>
+struct TUniformSizeProvider {
+    size_t operator()(const TValue&) {
+        return 1;
+    }
+};
+
+template <typename TKey, typename TValue, class TSizeProvider = TUniformSizeProvider<TValue>>
+class TLRUList {
+public:
+    TLRUList(size_t maxSize, const TSizeProvider& sizeProvider = TSizeProvider())
+        : List()
+        , SizeProvider(sizeProvider)
+        , ItemsAmount(0)
+        , TotalSize(0)
+        , MaxSize(maxSize)
+    {
+    }
+
+public:
+    struct TItem: public TIntrusiveListItem<TItem> {
+        typedef TIntrusiveListItem<TItem> TBase;
+        TItem(const TKey& key, const TValue& value = TValue())
+            : TBase()
+            , Key(key)
+            , Value(value)
+        {
+        }
+
+        TItem(const TItem& rhs)
+            : TBase()
+            , Key(rhs.Key)
+            , Value(rhs.Value)
+        {
+        }
+
+        bool operator<(const TItem& rhs) const {
+            return Key < rhs.Key;
+        }
+
+        bool operator==(const TItem& rhs) const {
+            return Key == rhs.Key;
+        }
+
+        TKey Key;
+        TValue Value;
+
+        struct THash {
+            size_t operator()(const TItem& item) const {
+                return ::THash<TKey>()(item.Key);
+            }
+        };
+    };
+
+public:
+    TItem* Insert(TItem* item) {
+        List.PushBack(item);
+        ++ItemsAmount;
+        TotalSize += SizeProvider(item->Value);
+
+        return RemoveIfOverflown();
+    }
+
+    TItem* RemoveIfOverflown() {
+        TItem* deleted = nullptr;
+        if (TotalSize > MaxSize && ItemsAmount > 1) {
+            deleted = GetOldest();
+            Erase(deleted);
+        }
+        return deleted;
+    }
+
+    TItem* GetOldest() {
+        typename TListType::TIterator it = List.Begin();
+        Y_ASSERT(it != List.End());
+        return &*it;
+    }
+
+    void Erase(TItem* item) {
+        item->Unlink();
+        --ItemsAmount;
+        TotalSize -= SizeProvider(item->Value);
+    }
+
+    void Promote(TItem* item) {
+        item->Unlink();
+        List.PushBack(item);
+    }
+
+    size_t GetSize() const {
+        return ItemsAmount;
+    }
+
+    size_t GetTotalSize() const {
+        return TotalSize;
+    }
+
+    size_t GetMaxSize() const {
+        return MaxSize;
+    }
+
+    // It does not remove current items if newSize is less than TotalSize.
+    // Caller should use RemoveIfOverflown to clean up list in this case
+    void SetMaxSize(size_t newSize) {
+        MaxSize = newSize;
+    }
+
+private:
+    typedef TIntrusiveList<TItem> TListType;
+    TListType List;
+    TSizeProvider SizeProvider;
+    size_t ItemsAmount;
+    size_t TotalSize;
+    size_t MaxSize;
+};
+
+template <typename TKey, typename TValue>
+class TLFUList {
+public:
+    TLFUList(size_t maxSize)
+        : List()
+        , ListSize(0)
+        , MaxSize(maxSize)
+    {
+    }
+
+    struct TItem: public TIntrusiveListItem<TItem> {
+        typedef TIntrusiveListItem<TItem> TBase;
+        TItem(const TKey& key, const TValue& value = TValue())
+            : TBase()
+            , Key(key)
+            , Value(value)
+            , Counter(0)
+        {
+        }
+
+        TItem(const TItem& rhs)
+            : TBase()
+            , Key(rhs.Key)
+            , Value(rhs.Value)
+            , Counter(rhs.Counter)
+        {
+        }
+
+        bool operator<(const TItem& rhs) const {
+            return Key < rhs.Key;
+        }
+
+        bool operator==(const TItem& rhs) const {
+            return Key == rhs.Key;
+        }
+
+        TKey Key;
+        TValue Value;
+        size_t Counter;
+
+        struct THash {
+            size_t operator()(const TItem& item) const {
+                return ::THash<TKey>()(item.Key);
+            }
+        };
+    };
+
+public:
+    TItem* Insert(TItem* item) {
+        List.PushBack(item); // give a chance for promotion
+        ++ListSize;
+
+        return RemoveIfOverflown();
+    }
+
+    TItem* RemoveIfOverflown() {
+        TItem* deleted = nullptr;
+        if (ListSize > MaxSize) {
+            deleted = GetLeastFrequentlyUsed();
+            Erase(deleted);
+        }
+        return deleted;
+    }
+
+    TItem* GetLeastFrequentlyUsed() {
+        typename TListType::TIterator it = List.Begin();
+        Y_ASSERT(it != List.End());
+        return &*it;
+    }
+
+    void Erase(TItem* item) {
+        item->Unlink();
+        --ListSize;
+    }
+
+    void Promote(TItem* item) {
+        size_t counter = ++item->Counter;
+        typename TListType::TIterator it = item;
+        while (it != List.End() && counter >= it->Counter) {
+            ++it;
+        }
+        item->LinkBefore(&*it);
+    }
+
+    size_t GetSize() const {
+        return ListSize;
+    }
+
+    size_t GetMaxSize() const {
+        return MaxSize;
+    }
+
+    // It does not remove current items if newSize is less than TotalSize.
+    // Caller should use RemoveIfOverflown to clean up list in this case
+    void SetMaxSize(size_t newSize) {
+        MaxSize = newSize;
+    }
+
+private:
+    typedef TIntrusiveList<TItem> TListType;
+    TListType List;
+    size_t ListSize;
+    size_t MaxSize;
+};
+
+// Least Weighted list
+// discards the least weighted items first
+// doesn't support promotion
+template <typename TKey, typename TValue, typename TWeight, typename TWeighter>
+class TLWList {
+public:
+    TLWList(size_t maxSize)
+        : Size(0)
+        , MaxSize(maxSize)
+    {
+    }
+
+    struct TItem {
+        TItem(const TKey& key, const TValue& value = TValue())
+            : Key(key)
+            , Value(value)
+            , Weight(TWeighter::Weight(value))
+        {
+        }
+
+        TItem(const TItem& rhs)
+            : Key(rhs.Key)
+            , Value(rhs.Value)
+            , Weight(rhs.Weight)
+        {
+        }
+
+        bool operator<(const TItem& rhs) const {
+            return Key < rhs.Key;
+        }
+
+        bool operator==(const TItem& rhs) const {
+            return Key == rhs.Key;
+        }
+
+        TKey Key;
+        TValue Value;
+        TWeight Weight;
+
+        struct THash {
+            size_t operator()(const TItem& item) const {
+                return ::THash<TKey>()(item.Key);
+            }
+        };
+    };
+
+    struct THeapComparator {
+        bool operator()(TItem* const item1, TItem* const item2) const {
+            return item1->Weight > item2->Weight;
+        }
+    };
+
+public:
+    TItem* Insert(TItem* item) {
+        FixHeap();
+
+        if (Size >= MaxSize && item->Weight < GetLightest()->Weight) {
+            return item;
+        }
+
+        Heap.push_back(item);
+        PushHeap(Heap.begin(), Heap.end(), THeapComparator());
+        ++Size;
+
+        return RemoveIfOverflown();
+    }
+
+    TItem* RemoveIfOverflown() {
+        if (Size <= MaxSize) {
+            return nullptr;
+        }
+
+        auto lightest = GetLightest();
+        Erase(lightest);
+        PopHeap(Heap.begin(), Heap.end(), THeapComparator());
+        return lightest;
+    }
+
+    TItem* GetLightest() {
+        FixHeap();
+
+        Y_ASSERT(!Heap.empty());
+
+        return Heap.front();
+    }
+
+    // This method doesn't remove items from the heap.
+    // Erased items are stored in Removed set
+    // and will be deleted on-access (using FixHeap method)
+    void Erase(TItem* item) {
+        Y_ASSERT(Size > 0);
+
+        --Size;
+        Removed.insert(item);
+    }
+
+    void Promote(TItem*) {
+        // do nothing
+    }
+
+    [[nodiscard]] size_t GetSize() const {
+        return Size;
+    }
+
+    size_t GetMaxSize() const {
+        return MaxSize;
+    }
+
+    // It does not remove current items if newSize is less than TotalSize.
+    // Caller should use RemoveIfOverflown to clean up list in this case
+    void SetMaxSize(size_t newSize) {
+        MaxSize = newSize;
+    }
+
+    void Clear() {
+        Heap.clear();
+        Removed.clear();
+        Size = 0;
+    }
+
+private:
+    // Physically remove erased elements from the heap
+    void FixHeap() {
+        if (Removed.empty()) {
+            return;
+        }
+
+        Heap.erase(std::remove_if(Heap.begin(), Heap.end(), [this](TItem* item) {
+                       return this->Removed.contains(item);
+                   }),
+                   Heap.end());
+        MakeHeap(Heap.begin(), Heap.end(), THeapComparator());
+        Removed.clear();
+        Size = Heap.size();
+    }
+
+private:
+    TVector<TItem*> Heap;
+    THashSet<TItem*> Removed;
+
+    size_t Size;
+    size_t MaxSize;
+};
+
+template <typename TKey, typename TValue, typename TListType, typename TDeleter>
+class TCache {
+    typedef typename TListType::TItem TItem;
+    typedef typename TItem::THash THash;
+    typedef THashMultiSet<TItem, THash> TIndex;
+    typedef typename TIndex::iterator TIndexIterator;
+    typedef typename TIndex::const_iterator TIndexConstIterator;
+
+public:
+    class TIterator {
+    public:
+        explicit TIterator(const TIndexConstIterator& iter)
+            : Iter(iter)
+        {
+        }
+
+        TValue& operator*() {
+            return const_cast<TValue&>(Iter->Value);
+        }
+
+        TValue* operator->() {
+            return const_cast<TValue*>(&Iter->Value);
+        }
+
+        bool operator==(const TIterator& rhs) const {
+            return Iter == rhs.Iter;
+        }
+
+        bool operator!=(const TIterator& rhs) const {
+            return Iter != rhs.Iter;
+        }
+
+        TIterator& operator++() {
+            ++Iter;
+            return *this;
+        }
+
+        const TKey& Key() const {
+            return Iter->Key;
+        }
+
+        const TValue& Value() const {
+            return Iter->Value;
+        }
+
+        friend class TCache<TKey, TValue, TListType, TDeleter>;
+
+    private:
+        TIndexConstIterator Iter;
+    };
+
+    TCache(TListType&& list, bool multiValue = false)
+        : Index()
+        , List(std::move(list))
+        , MultiValue(multiValue)
+    {
+    }
+
+    ~TCache() {
+        Clear();
+    }
+
+    size_t Size() const {
+        return Index.size();
+    }
+
+    TIterator Begin() const {
+        return TIterator(Index.begin());
+    }
+
+    TIterator End() const {
+        return TIterator(Index.end());
+    }
+
+    TIterator Find(const TKey& key) {
+        TIndexIterator it = Index.find(TItem(key));
+        if (it != Index.end())
+            List.Promote(const_cast<TItem*>(&*it));
+        return TIterator(it);
+    }
+
+    TIterator FindWithoutPromote(const TKey& key) const {
+        return TIterator(Index.find(TItem(key)));
+    }
+
+    // note: it shouldn't touch 'value' if it returns false.
+    bool PickOut(const TKey& key, TValue* value) {
+        Y_ASSERT(value);
+        TIndexIterator it = Index.find(TItem(key));
+        if (it == Index.end())
+            return false;
+        *value = it->Value;
+        List.Erase(const_cast<TItem*>(&*it));
+        Index.erase(it);
+        Y_ASSERT(Index.size() == List.GetSize());
+        return true;
+    }
+
+    bool Insert(const std::pair<TKey, TValue>& p) {
+        return Insert(p.first, p.second);
+    }
+
+    bool Insert(const TKey& key, const TValue& value) {
+        TItem tmpItem(key, value);
+        if (!MultiValue && Index.find(tmpItem) != Index.end())
+            return false;
+        TIndexIterator it = Index.insert(tmpItem);
+
+        TItem* insertedItem = const_cast<TItem*>(&*it);
+        auto removedItem = List.Insert(insertedItem);
+        auto insertedWasRemoved = removedItem == insertedItem;
+        if (removedItem) {
+            EraseFromIndex(removedItem);
+            while ((removedItem = List.RemoveIfOverflown())) {
+                insertedWasRemoved = insertedWasRemoved || insertedItem == removedItem;
+                EraseFromIndex(removedItem);
+            }
+        }
+
+        Y_ASSERT(Index.size() == List.GetSize());
+        return !insertedWasRemoved;
+    }
+
+    void Update(const TKey& key, const TValue& value) {
+        if (MultiValue)
+            ythrow yexception() << "TCache: can't \"Update\" in multicache";
+        TIterator it = Find(key);
+        if (it != End()) {
+            Erase(it);
+        }
+        Insert(key, value);
+
+        Y_ASSERT(Index.size() == List.GetSize());
+    }
+
+    void Erase(TIterator it) {
+        TItem* item = const_cast<TItem*>(&*it.Iter);
+        List.Erase(item);
+        TDeleter::Destroy(item->Value);
+        Index.erase(it.Iter);
+
+        Y_ASSERT(Index.size() == List.GetSize());
+    }
+
+    bool Empty() const {
+        return Index.empty();
+    }
+
+    void Clear() {
+        for (TIndexIterator it = Index.begin(); it != Index.end(); ++it) {
+            TItem* item = const_cast<TItem*>(&*it);
+            List.Erase(item);
+            TDeleter::Destroy(item->Value);
+        }
+        Y_ASSERT(List.GetSize() == 0);
+        Index.clear();
+    }
+
+    void SetMaxSize(size_t newSize) {
+        List.SetMaxSize(newSize);
+
+        TItem* removedItem = nullptr;
+        while ((removedItem = List.RemoveIfOverflown())) {
+            EraseFromIndex(removedItem);
+        }
+        Y_ASSERT(Index.size() == List.GetSize());
+    }
+
+    size_t GetMaxSize() const {
+        return List.GetMaxSize();
+    }
+
+protected:
+    TIndex Index;
+    TListType List;
+    bool MultiValue;
+
+    TIterator FindByItem(TItem* item) {
+        std::pair<TIndexIterator, TIndexIterator> p = Index.equal_range(*item);
+        // we have to delete the exact unlinked item (there may be multiple items for one key)
+        TIndexIterator it;
+        for (it = p.first; it != p.second; ++it)
+            if (&*it == item)
+                break;
+        return (it == p.second ? End() : TIterator(it));
+    }
+
+    void EraseFromIndex(TItem* item) {
+        TDeleter::Destroy(item->Value);
+        TIterator it = FindByItem(item);
+        Y_ASSERT(it != End());
+        Index.erase(it.Iter);
+    }
+};
+
+struct TNoopDelete {
+    template <class T>
+    static inline void Destroy(const T&) noexcept {
+    }
+};
+
+template <typename TKey, typename TValue, typename TDeleter = TNoopDelete, class TSizeProvider = TUniformSizeProvider<TValue>>
+class TLRUCache: public TCache<TKey, TValue, TLRUList<TKey, TValue, TSizeProvider>, TDeleter> {
+    using TListType = TLRUList<TKey, TValue, TSizeProvider>;
+    typedef TCache<TKey, TValue, TListType, TDeleter> TBase;
+
+public:
+    TLRUCache(size_t maxSize, bool multiValue = false, const TSizeProvider& sizeProvider = TSizeProvider())
+        : TBase(TListType(maxSize, sizeProvider), multiValue)
+    {
+    }
+
+public:
+    typedef typename TBase::TIterator TIterator;
+
+    TValue& GetOldest() {
+        return TBase::List.GetOldest()->Value;
+    }
+
+    TIterator FindOldest() {
+        return TBase::Empty() ? TBase::End() : this->FindByItem(TBase::List.GetOldest());
+    }
+
+    size_t TotalSize() const {
+        return TBase::List.GetTotalSize();
+    }
+};
+
+template <typename TKey, typename TValue, typename TDeleter = TNoopDelete>
+class TLFUCache: public TCache<TKey, TValue, TLFUList<TKey, TValue>, TDeleter> {
+    typedef TCache<TKey, TValue, TLFUList<TKey, TValue>, TDeleter> TBase;
+    using TListType = TLFUList<TKey, TValue>;
+
+public:
+    typedef typename TBase::TIterator TIterator;
+
+    TLFUCache(size_t maxSize, bool multiValue = false)
+        : TBase(TListType(maxSize), multiValue)
+    {
+    }
+
+    TValue& GetLeastFrequentlyUsed() {
+        return TBase::List.GetLeastFrequentlyUsed()->Value;
+    }
+
+    TIterator FindLeastFrequentlyUsed() {
+        return TBase::Empty() ? TBase::End() : this->FindByItem(TBase::List.GetLeastFrequentlyUsed());
+    }
+};
+
+// Least Weighted cache
+// discards the least weighted items first
+// doesn't support promotion
+template <typename TKey, typename TValue, typename TWeight, typename TWeighter, typename TDeleter = TNoopDelete>
+class TLWCache: public TCache<TKey, TValue, TLWList<TKey, TValue, TWeight, TWeighter>, TDeleter> {
+    typedef TCache<TKey, TValue, TLWList<TKey, TValue, TWeight, TWeighter>, TDeleter> TBase;
+    using TListType = TLWList<TKey, TValue, TWeight, TWeighter>;
+
+public:
+    typedef typename TBase::TIterator TIterator;
+
+    TLWCache(size_t maxSize, bool multiValue = false)
+        : TBase(TListType(maxSize), multiValue)
+    {
+    }
+
+    TValue& GetLightest() {
+        return TBase::List.GetLightest()->Value;
+    }
+
+    TIterator FindLightest() {
+        return TBase::Empty() ? TBase::End() : this->FindByItem(TBase::List.GetLightest());
+    }
+};
diff --git a/library/cpp/cache/thread_safe_cache.cpp b/library/cpp/cache/thread_safe_cache.cpp
new file mode 100644
index 0000000000..de47076d6b
--- /dev/null
+++ b/library/cpp/cache/thread_safe_cache.cpp
@@ -0,0 +1 @@
+#include "thread_safe_cache.h"
diff --git a/library/cpp/cache/thread_safe_cache.h b/library/cpp/cache/thread_safe_cache.h
new file mode 100644
index 0000000000..71e1442717
--- /dev/null
+++ b/library/cpp/cache/thread_safe_cache.h
@@ -0,0 +1,201 @@
+#pragma once
+
+#include "cache.h"
+
+#include <util/generic/singleton.h>
+#include <util/system/rwlock.h>
+
+namespace NPrivate {
+    // We are interested in getters promotion policy _here_ because of Read-Write-Lock optimizations.
+    enum class EGettersPromotionPolicy {
+        Promoted,   // LRU, TLRU, MRU, etc.
+        Unpromoted  // FIFO, LIFO, LW, etc.
+    };
+
+    template <class Key, class Value, template <class, class> class List, EGettersPromotionPolicy GettersPromotionPolicy, class... TArgs>
+    class TThreadSafeCache {
+    public:
+        using TPtr = TAtomicSharedPtr<Value>;
+
+        class ICallbacks {
+        public:
+            using TKey = Key;
+            using TValue = Value;
+            using TOwner = TThreadSafeCache<Key, Value, List, GettersPromotionPolicy, TArgs...>;
+
+        public:
+            virtual ~ICallbacks() = default;
+            virtual TKey GetKey(TArgs... args) const = 0;
+            virtual TValue* CreateObject(TArgs... args) const = 0;
+        };
+
+    public:
+        TThreadSafeCache(const ICallbacks& callbacks, size_t maxSize = Max<size_t>())
+            : Callbacks(callbacks)
+            , Cache(maxSize)
+        {
+        }
+
+        bool Insert(const Key& key, const TPtr& value) {
+            if (!Contains(key)) {
+                TWriteGuard w(Mutex);
+                return Cache.Insert(key, value);
+            }
+            return false;
+        }
+
+        void Update(const Key& key, const TPtr& value) {
+            TWriteGuard w(Mutex);
+            Cache.Update(key, value);
+        }
+
+        const TPtr Get(TArgs... args) const {
+            return GetValue<true>(args...);
+        }
+
+        const TPtr GetUnsafe(TArgs... args) const {
+            return GetValue<false>(args...);
+        }
+
+        void Clear() {
+            TWriteGuard w(Mutex);
+            Cache.Clear();
+        }
+
+        void Erase(TArgs... args) {
+            Key key = Callbacks.GetKey(args...);
+            if (!Contains(key)) {
+                return;
+            }
+            TWriteGuard w(Mutex);
+            typename TInternalCache::TIterator i = Cache.Find(key);
+            if (i == Cache.End()) {
+                return;
+            }
+            Cache.Erase(i);
+        }
+
+        bool Contains(const Key& key) const {
+            TReadGuard r(Mutex);
+            auto iter = Cache.FindWithoutPromote(key);
+            return iter != Cache.End();
+        }
+
+        template <class TCallbacks>
+        static const TPtr Get(TArgs... args) {
+            return TThreadSafeCacheSingleton<TCallbacks>::Get(args...);
+        }
+
+        template <class TCallbacks>
+        static const TPtr Erase(TArgs... args) {
+            return TThreadSafeCacheSingleton<TCallbacks>::Erase(args...);
+        }
+
+        template <class TCallbacks>
+        static void Clear() {
+            return TThreadSafeCacheSingleton<TCallbacks>::Clear();
+        }
+
+        size_t GetMaxSize() const {
+            TReadGuard w(Mutex);
+            return Cache.GetMaxSize();
+        }
+
+        void SetMaxSize(size_t newSize) {
+            TWriteGuard w(Mutex);
+            Cache.SetMaxSize(newSize);
+        }
+
+    private:
+        template <bool AllowNullValues>
+        const TPtr GetValue(TArgs... args) const {
+            Key key = Callbacks.GetKey(args...);
+            switch (GettersPromotionPolicy) {
+                case EGettersPromotionPolicy::Promoted:
+                    break;
+                case EGettersPromotionPolicy::Unpromoted: {
+                    TReadGuard r(Mutex);
+                    typename TInternalCache::TIterator i = Cache.FindWithoutPromote(key);
+                    if (i != Cache.End()) {
+                        return i.Value();
+                    }
+                    break;
+                }
+            }
+            TWriteGuard w(Mutex);
+            typename TInternalCache::TIterator i = Cache.Find(key);
+            if (i != Cache.End()) {
+                return i.Value();
+            }
+            TPtr value = Callbacks.CreateObject(args...);
+            if (value || AllowNullValues) {
+                Cache.Insert(key, value);
+            }
+            return value;
+        }
+
+    private:
+        using TInternalCache = TCache<Key, TPtr, List<Key, TPtr>, TNoopDelete>;
+
+        template <class TCallbacks>
+        class TThreadSafeCacheSingleton {
+        public:
+            static const TPtr Get(TArgs... args) {
+                return Singleton<TThreadSafeCacheSingleton>()->Cache.Get(args...);
+            }
+
+            static const TPtr Erase(TArgs... args) {
+                return Singleton<TThreadSafeCacheSingleton>()->Cache.Erase(args...);
+            }
+
+            static void Clear() {
+                return Singleton<TThreadSafeCacheSingleton>()->Cache.Clear();
+            }
+
+            TThreadSafeCacheSingleton()
+                : Cache(Callbacks)
+            {
+            }
+
+        private:
+            TCallbacks Callbacks;
+            typename TCallbacks::TOwner Cache;
+        };
+
+    private:
+        TRWMutex Mutex;
+        const ICallbacks& Callbacks;
+        mutable TInternalCache Cache;
+    };
+
+    struct TLWHelper {
+        template <class TValue>
+        struct TConstWeighter {
+            static int Weight(const TValue& /*value*/) {
+                return 0;
+            }
+        };
+
+        template <class TKey, class TValue>
+        using TListType = TLWList<TKey, TValue, int, TConstWeighter<TValue>>;
+
+        template <class TKey, class TValue, class... TArgs>
+        using TCache = TThreadSafeCache<TKey, TValue, TListType, EGettersPromotionPolicy::Unpromoted, TArgs...>;
+    };
+
+    struct TLRUHelper {
+        template <class TKey, class TValue>
+        using TListType = TLRUList<TKey, TValue>;
+
+        template <class TKey, class TValue, class... TArgs>
+        using TCache = TThreadSafeCache<TKey, TValue, TListType, EGettersPromotionPolicy::Promoted, TArgs...>;
+    };
+
+}
+
+template <class TKey, class TValue, class... TArgs>
+using TThreadSafeCache = typename NPrivate::TLWHelper::template TCache<TKey, TValue, TArgs...>;
+
+template <class TKey, class TValue, class... TArgs>
+using TThreadSafeLRUCache = typename NPrivate::TLRUHelper::template TCache<TKey, TValue, TArgs...>;
+
diff --git a/library/cpp/cache/ut/cache_ut.cpp b/library/cpp/cache/ut/cache_ut.cpp
new file mode 100644
index 0000000000..329872cfde
--- /dev/null
+++ b/library/cpp/cache/ut/cache_ut.cpp
@@ -0,0 +1,618 @@
+#include <library/cpp/cache/cache.h>
+#include <library/cpp/cache/thread_safe_cache.h>
+#include <library/cpp/testing/unittest/registar.h>
+
+struct TStrokaWeighter {
+    static size_t Weight(const TString& s) {
+        return s.size();
+    }
+};
+
+Y_UNIT_TEST_SUITE(TCacheTest) {
+    Y_UNIT_TEST(LRUListTest) {
+        typedef TLRUList<int, TString> TListType;
+        TListType list(2);
+
+        TListType::TItem x1(1, "ttt");
+        list.Insert(&x1);
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 1);
+
+        TListType::TItem x2(2, "yyy");
+        list.Insert(&x2);
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 1);
+
+        list.Promote(list.GetOldest());
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 2);
+
+        TListType::TItem x3(3, "zzz");
+        list.Insert(&x3);
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 1);
+    }
+
+    Y_UNIT_TEST(LRUListWeightedTest) {
+        typedef TLRUList<int, TString, size_t (*)(const TString&)> TListType;
+        TListType list(7, [](auto& string) {
+            return string.size();
+        });
+
+        TListType::TItem x1(1, "ttt");
+        list.Insert(&x1);
+        while (list.RemoveIfOverflown()) {
+        }
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 1);
+
+        TListType::TItem x2(2, "yyy");
+        list.Insert(&x2);
+        while (list.RemoveIfOverflown()) {
+        }
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 1);
+
+        list.Promote(list.GetOldest());
+        while (list.RemoveIfOverflown()) {
+        }
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 2);
+
+        TListType::TItem x3(3, "zzz");
+        list.Insert(&x3);
+        while (list.RemoveIfOverflown()) {
+        }
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 1);
+
+        TListType::TItem x4(4, "longlong");
+        list.Insert(&x4);
+        while (list.RemoveIfOverflown()) {
+        }
+        UNIT_ASSERT_EQUAL(list.GetOldest()->Key, 4);
+    }
+
+    Y_UNIT_TEST(LFUListTest) {
+        typedef TLFUList<int, TString> TListType;
+        TListType list(2);
+
+        TListType::TItem x1(1, "ttt");
+        list.Insert(&x1);
+        UNIT_ASSERT_EQUAL(list.GetLeastFrequentlyUsed()->Key, 1);
+
+        TListType::TItem x2(2, "yyy");
+        list.Insert(&x2);
+        UNIT_ASSERT_EQUAL(list.GetLeastFrequentlyUsed()->Key, 1);
+
+        list.Promote(list.GetLeastFrequentlyUsed());
+        UNIT_ASSERT_EQUAL(list.GetLeastFrequentlyUsed()->Key, 2);
+
+        TListType::TItem x3(3, "zzz");
+        list.Insert(&x3);
+        UNIT_ASSERT_EQUAL(list.GetLeastFrequentlyUsed()->Key, 1);
+    }
+
+    Y_UNIT_TEST(LWListTest) {
+        typedef TLWList<int, TString, size_t, TStrokaWeighter> TListType;
+        TListType list(2);
+
+        TListType::TItem x1(1, "tt");
+        list.Insert(&x1);
+        UNIT_ASSERT_EQUAL(list.GetLightest()->Key, 1);
+        UNIT_ASSERT_EQUAL(list.GetSize(), 1);
+
+        TListType::TItem x2(2, "yyyy");
+        list.Insert(&x2);
+        UNIT_ASSERT_EQUAL(list.GetLightest()->Key, 1);
+        UNIT_ASSERT_EQUAL(list.GetSize(), 2);
+
+        TListType::TItem x3(3, "z");
+        list.Insert(&x3);
+        UNIT_ASSERT_EQUAL(list.GetLightest()->Key, 1);
+        UNIT_ASSERT_EQUAL(list.GetSize(), 2);
+
+        TListType::TItem x4(4, "xxxxxx");
+        list.Insert(&x4);
+        UNIT_ASSERT_EQUAL(list.GetLightest()->Key, 2);
+        UNIT_ASSERT_EQUAL(list.GetSize(), 2);
+
+        list.Erase(&x2);
+        UNIT_ASSERT_EQUAL(list.GetLightest()->Key, 4);
+        UNIT_ASSERT_EQUAL(list.GetSize(), 1);
+    }
+
+    Y_UNIT_TEST(SimpleTest) {
+        typedef TLRUCache<int, TString> TCache;
+        TCache s(2); // size 2
+        s.Insert(1, "abcd");
+        UNIT_ASSERT(s.Find(1) != s.End());
+        UNIT_ASSERT_EQUAL(*s.Find(1), "abcd");
+        s.Insert(2, "defg");
+        UNIT_ASSERT(s.GetOldest() == "abcd");
+        s.Insert(3, "hjkl");
+        UNIT_ASSERT(s.GetOldest() == "defg");
+        // key 1 will be deleted
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) != s.End());
+        UNIT_ASSERT(*s.Find(2) == "defg");
+        UNIT_ASSERT(s.Find(3) != s.End());
+        UNIT_ASSERT(*s.Find(3) == "hjkl");
+
+        UNIT_ASSERT(!s.Insert(3, "abcd"));
+        UNIT_ASSERT(*s.Find(3) == "hjkl");
+        s.Update(3, "abcd");
+        UNIT_ASSERT(*s.Find(3) == "abcd");
+
+        TCache::TIterator it = s.Find(3);
+        s.Erase(it);
+        UNIT_ASSERT(s.Find(3) == s.End());
+    }
+
+    Y_UNIT_TEST(LRUWithCustomSizeProviderTest) {
+        typedef TLRUCache<int, TString, TNoopDelete, size_t(*)(const TString&)> TCache;
+        TCache s(10, false, [](auto& string) { return string.size(); }); // size 10
+        s.Insert(1, "abcd");
+        UNIT_ASSERT(s.Find(1) != s.End());
+        UNIT_ASSERT_EQUAL(*s.Find(1), "abcd");
+        s.Insert(2, "defg");
+        UNIT_ASSERT(s.GetOldest() == "abcd");
+        s.Insert(3, "2c");
+        UNIT_ASSERT(s.GetOldest() == "abcd");
+        s.Insert(4, "hjkl");
+        UNIT_ASSERT(s.GetOldest() == "defg");
+        // key 1 will be deleted
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) != s.End());
+        UNIT_ASSERT(*s.Find(2) == "defg");
+        UNIT_ASSERT(s.Find(3) != s.End());
+        UNIT_ASSERT(*s.Find(3) == "2c");
+        UNIT_ASSERT(s.Find(4) != s.End());
+        UNIT_ASSERT(*s.Find(4) == "hjkl");
+
+        UNIT_ASSERT(!s.Insert(3, "abcd"));
+        UNIT_ASSERT(*s.Find(3) == "2c");
+        s.Update(3, "abcd");
+        UNIT_ASSERT(*s.Find(3) == "abcd");
+
+        TCache::TIterator it = s.Find(3);
+        s.Erase(it);
+        UNIT_ASSERT(s.Find(3) == s.End());
+    }
+
+    Y_UNIT_TEST(LRUSetMaxSizeTest) {
+        typedef TLRUCache<int, TString> TCache;
+        TCache s(2); // size 2
+        s.Insert(1, "abcd");
+        s.Insert(2, "efgh");
+        s.Insert(3, "ijkl");
+        UNIT_ASSERT(s.GetOldest() == "efgh");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) != s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+
+        // Increasing size should not change anything
+        s.SetMaxSize(3);
+        UNIT_ASSERT(s.GetOldest() == "efgh");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) != s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+
+        // And we should be able to add fit more entries
+        s.Insert(4, "mnop");
+        s.Insert(5, "qrst");
+        UNIT_ASSERT(s.GetOldest() == "ijkl");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+        UNIT_ASSERT(s.Find(4) != s.End());
+        UNIT_ASSERT(s.Find(5) != s.End());
+
+        // Decreasing size should remove oldest entries
+        s.SetMaxSize(2);
+        UNIT_ASSERT(s.GetOldest() == "mnop");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) == s.End());
+        UNIT_ASSERT(s.Find(4) != s.End());
+        UNIT_ASSERT(s.Find(5) != s.End());
+
+        // Ano no more entries will fit
+        s.Insert(6, "uvwx");
+        UNIT_ASSERT(s.GetOldest() == "qrst");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) == s.End());
+        UNIT_ASSERT(s.Find(4) == s.End());
+        UNIT_ASSERT(s.Find(5) != s.End());
+        UNIT_ASSERT(s.Find(6) != s.End());
+    }
+
+    Y_UNIT_TEST(LWSetMaxSizeTest) {
+        typedef TLWCache<int, TString, size_t, TStrokaWeighter> TCache;
+        TCache s(2); // size 2
+        s.Insert(1, "a");
+        s.Insert(2, "aa");
+        s.Insert(3, "aaa");
+        UNIT_ASSERT(s.GetLightest() == "aa");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) != s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+
+        // Increasing size should not change anything
+        s.SetMaxSize(3);
+        UNIT_ASSERT(s.GetLightest() == "aa");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) != s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+
+        // And we should be able to add fit more entries
+        s.Insert(4, "aaaa");
+        s.Insert(5, "aaaaa");
+        UNIT_ASSERT(s.GetLightest() == "aaa");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+        UNIT_ASSERT(s.Find(4) != s.End());
+        UNIT_ASSERT(s.Find(5) != s.End());
+
+        // Decreasing size should remove oldest entries
+        s.SetMaxSize(2);
+        UNIT_ASSERT(s.GetLightest() == "aaaa");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) == s.End());
+        UNIT_ASSERT(s.Find(4) != s.End());
+        UNIT_ASSERT(s.Find(5) != s.End());
+
+        // Ano no more entries will fit
+        s.Insert(6, "aaaaaa");
+        UNIT_ASSERT(s.GetLightest() == "aaaaa");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) == s.End());
+        UNIT_ASSERT(s.Find(4) == s.End());
+        UNIT_ASSERT(s.Find(5) != s.End());
+        UNIT_ASSERT(s.Find(6) != s.End());
+    }
+
+    Y_UNIT_TEST(LFUSetMaxSizeTest) {
+        typedef TLFUCache<int, TString> TCache;
+        TCache s(2); // size 2
+        s.Insert(1, "abcd");
+        s.Insert(2, "efgh");
+        s.Insert(3, "ijkl");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) != s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+
+        // Increasing size should not change anything
+        s.SetMaxSize(3);
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) != s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+
+        // And we should be able to add fit more entries
+        s.Insert(4, "mnop");
+        s.Insert(5, "qrst");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+        UNIT_ASSERT(s.Find(4) != s.End());
+        UNIT_ASSERT(s.Find(5) != s.End());
+
+        // Decreasing size should remove oldest entries
+        s.SetMaxSize(2);
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+        UNIT_ASSERT(s.Find(4) == s.End());
+        UNIT_ASSERT(s.Find(5) != s.End());
+
+        // Ano no more entries will fit
+        s.Insert(6, "uvwx");
+        UNIT_ASSERT(s.Find(1) == s.End());
+        UNIT_ASSERT(s.Find(2) == s.End());
+        UNIT_ASSERT(s.Find(3) != s.End());
+        UNIT_ASSERT(s.Find(4) == s.End());
+        UNIT_ASSERT(s.Find(5) == s.End());
+        UNIT_ASSERT(s.Find(6) != s.End());
+    }
+
+    Y_UNIT_TEST(MultiCacheTest) {
+        typedef TLRUCache<int, TString> TCache;
+        TCache s(3, true);
+        UNIT_ASSERT(s.Insert(1, "abcd"));
+        UNIT_ASSERT(s.Insert(1, "bcde"));
+        UNIT_ASSERT(s.Insert(2, "fghi"));
+        UNIT_ASSERT(s.Insert(2, "ghij"));
+        // (1, "abcd") will be deleted
+        UNIT_ASSERT(*s.Find(1) == "bcde");
+        // (1, "bcde") will be promoted
+        UNIT_ASSERT(*s.FindOldest() == "fghi");
+    }
+
+    struct TMyDelete {
+        static int count;
+        template <typename T>
+        static void Destroy(const T&) {
+            ++count;
+        }
+    };
+    int TMyDelete::count = 0;
+
+    Y_UNIT_TEST(DeleterTest) {
+        typedef TLRUCache<int, TString, TMyDelete> TCache;
+        TCache s(2);
+        s.Insert(1, "123");
+        s.Insert(2, "456");
+        s.Insert(3, "789");
+        UNIT_ASSERT(TMyDelete::count == 1);
+        TCache::TIterator it = s.Find(2);
+        UNIT_ASSERT(it != s.End());
+        s.Erase(it);
+        UNIT_ASSERT(TMyDelete::count == 2);
+    }
+
+    Y_UNIT_TEST(PromoteOnFind) {
+        typedef TLRUCache<int, TString> TCache;
+        TCache s(2);
+        s.Insert(1, "123");
+        s.Insert(2, "456");
+        UNIT_ASSERT(s.Find(1) != s.End());
+        s.Insert(3, "789");
+        UNIT_ASSERT(s.Find(1) != s.End()); // Key 2 should have been deleted
+    }
+}
+
+Y_UNIT_TEST_SUITE(TThreadSafeCacheTest) {
+    typedef TThreadSafeCache<ui32, TString, ui32> TCache;
+
+    const char* VALS[] = {"abcd", "defg", "hjkl"};
+
+    class TCallbacks: public TCache::ICallbacks {
+    public:
+        TKey GetKey(ui32 i) const override {
+            return i;
+        }
+        TValue* CreateObject(ui32 i) const override {
+            Creations++;
+            return new TString(VALS[i]);
+        }
+
+        mutable i32 Creations = 0;
+    };
+
+    Y_UNIT_TEST(SimpleTest) {
+        for (ui32 i = 0; i < Y_ARRAY_SIZE(VALS); ++i) {
+            const TString data = *TCache::Get<TCallbacks>(i);
+            UNIT_ASSERT(data == VALS[i]);
+        }
+    }
+
+    Y_UNIT_TEST(InsertUpdateTest) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, 10);
+
+        cache.Insert(2, MakeAtomicShared<TString>("hj"));
+        TAtomicSharedPtr<TString> item = cache.Get(2);
+
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hj");
+
+        cache.Insert(2, MakeAtomicShared<TString>("hjk"));
+        item = cache.Get(2);
+
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hj");
+
+        cache.Update(2, MakeAtomicShared<TString>("hjk"));
+        item = cache.Get(2);
+
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hjk");
+    }
+}
+
+Y_UNIT_TEST_SUITE(TThreadSafeCacheUnsafeTest) {
+    typedef TThreadSafeCache<ui32, TString, ui32> TCache;
+
+    const char* VALS[] = {"abcd", "defg", "hjkl"};
+    const ui32 FAILED_IDX = 1;
+
+    class TCallbacks: public TCache::ICallbacks {
+    public:
+        TKey GetKey(ui32 i) const override {
+            return i;
+        }
+        TValue* CreateObject(ui32 i) const override {
+            if (i == FAILED_IDX) {
+                return nullptr;
+            }
+            return new TString(VALS[i]);
+        }
+    };
+
+    Y_UNIT_TEST(SimpleTest) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, Y_ARRAY_SIZE(VALS));
+        for (ui32 i = 0; i < Y_ARRAY_SIZE(VALS); ++i) {
+            const TString* data = cache.GetUnsafe(i).Get();
+            if (i == FAILED_IDX) {
+                UNIT_ASSERT(data == nullptr);
+            } else {
+                UNIT_ASSERT(*data == VALS[i]);
+            }
+        }
+    }
+}
+
+Y_UNIT_TEST_SUITE(TThreadSafeLRUCacheTest) {
+    typedef TThreadSafeLRUCache<size_t, TString, size_t> TCache;
+
+    TVector<TString> Values = {"zero", "one", "two", "three", "four"};
+
+    class TCallbacks: public TCache::ICallbacks {
+    public:
+        TKey GetKey(size_t i) const override {
+            return i;
+        }
+        TValue* CreateObject(size_t i) const override {
+            UNIT_ASSERT(i < Values.size());
+            Creations++;
+            return new TString(Values[i]);
+        }
+
+        mutable size_t Creations = 0;
+    };
+
+    Y_UNIT_TEST(SimpleTest) {
+        for (size_t i = 0; i < Values.size(); ++i) {
+            const TString data = *TCache::Get<TCallbacks>(i);
+            UNIT_ASSERT(data == Values[i]);
+        }
+    }
+
+    Y_UNIT_TEST(InsertUpdateTest) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, 10);
+
+        cache.Insert(2, MakeAtomicShared<TString>("hj"));
+        TAtomicSharedPtr<TString> item = cache.Get(2);
+
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hj");
+
+        cache.Insert(2, MakeAtomicShared<TString>("hjk"));
+        item = cache.Get(2);
+
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hj");
+
+        cache.Update(2, MakeAtomicShared<TString>("hjk"));
+        item = cache.Get(2);
+
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hjk");
+    }
+
+    Y_UNIT_TEST(LRUTest) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, 3);
+
+        UNIT_ASSERT_EQUAL(cache.GetMaxSize(), 3);
+
+        for (size_t i = 0; i < Values.size(); ++i) {
+            TAtomicSharedPtr<TString> item = cache.Get(i);
+            UNIT_ASSERT(*item == Values[i]);
+        }
+        UNIT_ASSERT(callbacks.Creations == Values.size());
+
+        size_t expectedCreations = Values.size();
+        TAtomicSharedPtr<TString> item;
+
+
+        item = cache.Get(4);
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "four");
+
+        item = cache.Get(2);
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "two");
+
+        item = cache.Get(0);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "zero");
+
+        UNIT_ASSERT(cache.Contains(1) == false);
+        UNIT_ASSERT(cache.Contains(3) == false);
+        UNIT_ASSERT(cache.Contains(4));
+        UNIT_ASSERT(cache.Contains(2));
+        UNIT_ASSERT(cache.Contains(0));
+
+        item = cache.Get(3);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "three");
+
+        item = cache.Get(2);
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "two");
+
+        item = cache.Get(0);
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "zero");
+
+        item = cache.Get(1);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "one");
+
+        item = cache.Get(2);
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "two");
+
+        item = cache.Get(4);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "four");
+    }
+
+    Y_UNIT_TEST(ChangeMaxSizeTest) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, 3);
+
+        UNIT_ASSERT_EQUAL(cache.GetMaxSize(), 3);
+
+        for (size_t i = 0; i < Values.size(); ++i) {
+            TAtomicSharedPtr<TString> item = cache.Get(i);
+            UNIT_ASSERT(*item == Values[i]);
+        }
+
+        size_t expectedCreations = Values.size();
+        TAtomicSharedPtr<TString> item;
+
+        item = cache.Get(4);
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "four");
+
+        item = cache.Get(3);
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "three");
+
+        item = cache.Get(2);
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "two");
+
+        item = cache.Get(1);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "one");
+
+        cache.SetMaxSize(4);
+
+        item = cache.Get(0);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "zero");
+
+        item = cache.Get(4);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "four");
+
+        item = cache.Get(3);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "three");
+        UNIT_ASSERT(cache.Contains(2) == false);
+
+        cache.SetMaxSize(2);
+        UNIT_ASSERT(cache.Contains(3));
+        UNIT_ASSERT(cache.Contains(4));
+        UNIT_ASSERT(cache.Contains(2) == false);
+        UNIT_ASSERT(cache.Contains(1) == false);
+        UNIT_ASSERT(cache.Contains(0) == false);
+
+        item = cache.Get(0);
+        expectedCreations++;
+        UNIT_ASSERT_EQUAL(callbacks.Creations, expectedCreations);
+        UNIT_ASSERT(*item == "zero");
+        UNIT_ASSERT(cache.Contains(4) == false);
+        UNIT_ASSERT(cache.Contains(3));
+        UNIT_ASSERT(cache.Contains(0));
+    }
+}
diff --git a/library/cpp/cache/ut/ya.make b/library/cpp/cache/ut/ya.make
new file mode 100644
index 0000000000..f660872369
--- /dev/null
+++ b/library/cpp/cache/ut/ya.make
@@ -0,0 +1,16 @@
+UNITTEST()
+
+OWNER(
+    g:util
+    vskipin
+)
+
+PEERDIR(
+    library/cpp/cache
+)
+
+SRCS(
+    cache_ut.cpp
+)
+
+END()
diff --git a/library/cpp/cache/ya.make b/library/cpp/cache/ya.make
new file mode 100644
index 0000000000..fd73032bf8
--- /dev/null
+++ b/library/cpp/cache/ya.make
@@ -0,0 +1,16 @@
+LIBRARY()
+
+OWNER(
+    g:util
+)
+
+SRCS(
+    cache.cpp
+    thread_safe_cache.cpp
+)
+
+END()
+
+RECURSE_FOR_TESTS(
+    ut
+)