LruCache<TKey, TElement> - C# LRU cache (hashmap + doubly linked list, O(1), zero-allocation node recycling)

README.md

LruCache<TKey, TElement>

C#으로 구현한 최소한의 LRU(Least Recently Used) 캐시. 모든 핵심 연산이 O(1)이다.

구조

정석적인 hashmap + 이중 연결 리스트 조합이다.

• LinkedList<(TKey, TElement)> timeline — 앞쪽이 MRU(most recently used), 뒤쪽이 LRU
• Dictionary<TKey, LinkedListNode<...>> index — 키에서 노드로 O(1) 조회

조회하면 해당 노드를 리스트 맨 앞으로 옮기고, 용량이 넘치면 맨 뒤 노드를 축출한다.

특징

노드 재활용

축출할 때 떼어낸 LinkedListNode 인스턴스를 버리지 않고 값만 덮어써서 재사용한다.

while (this.timeline.Count >= this.MaxCount)
{
    node = this.timeline.Last!;   // 캐시 크기가 넘치면, 기존의 node를 재활용한다.
    this.timeline.RemoveLast();
    this.index.Remove(node.Value.Key);
}

if (node != null)
{
    node.Value = (key, element);
}
else
{
    node = new LinkedListNode<(TKey, TElement)>((key, element));
}

흔한 예제 구현은 AddFirst((key, value))로 매번 새 노드를 할당하지만, 여기서는 캐시가 만원인 정상 상태에서 노드 할당이 0이라 GC 압력이 없다.

Program.cs의 마지막 테스트가 GC.GetAllocatedBytesForCurrentThread()로 이를 실측한다. 가득 찬 캐시에 1000회 삽입했을 때 할당량은 정확히 0바이트다.

LinkedList.Remove 계열이 노드의 List 참조를 끊어주기 때문에, 떼어낸 노드를 AddFirst(node)로 다시 붙이는 것이 유효하다.

Insert / Upsert 분리

대부분의 구현은 덮어쓰기만 하는 Put 하나를 제공하지만, 여기서는 두 가지로 나눴다. 둘 다 timeline(최근 사용 순서)은 갱신하며, 반환값은 "새로 삽입되었는가"이다.

메서드	키가 없을 때	키가 이미 있을 때
Insert	삽입하고 true	값을 유지하고 false
Upsert	삽입하고 true	값을 덮어쓰고 false

API

var cache = new LruCache<int, string>(maxCount: 100);

cache.Insert(1, "a");                  // true  (신규)
cache.Insert(1, "b");                  // false (값은 "a" 유지)
cache.Upsert(1, "c");                  // false (값이 "c"로 변경)

if (cache.TryGetValue(1, out var v))   // 조회 성공 시 MRU로 이동
{
    // ...
}

cache.Remove(1);

int count = cache.Count;               // 현재 보관 개수
int max = cache.MaxCount;              // 최대 용량
var values = cache.Values;             // MRU -> LRU 순서

IEqualityComparer<TKey>를 받는 생성자 오버로드도 있다.

실행

Program.cs가 외부 테스트 프레임워크 없이 도는 자체 검증 러너다. 파일을 한 디렉터리에 받고 실행하면 된다.

dotnet run -c Release

각 검증 항목이 PASS/FAIL로 출력되고, 하나라도 실패하면 종료 코드 1을 돌려준다. 검증 범위는 다음과 같다.

• 용량 유지와 LRU 순서 축출
• TryGetValue의 touch 효과 (조회한 항목이 축출을 피하는지)
• Insert(값 유지) 대 Upsert(값 덮어쓰기)
• Remove, 없는 키 조회/삭제, 삭제한 키의 재삽입
• IEqualityComparer<TKey> 오버로드
• 노드 재활용 시 할당 0바이트

net8.0을 타깃하지만 RollForward를 걸어둬서 상위 런타임만 있어도 실행된다.

원문 대비 차이

아래 참고 링크의 GFG 원문은 세 가지 접근(배열 / 해시 + 힙 / 해시맵 + 이중 연결 리스트)을 소개하고 마지막을 최적해로 제시한다. 이 구현은 그 최적해와 자료구조와 복잡도가 동일하다. 조회와 삽입 모두 O(1), 공간은 O(capacity). 갈리는 지점은 네 가지다.

1. 노드 재활용 (원문에 없는 최적화)

원문은 축출할 때 tail 노드를 "제거"하고 새 항목을 head에 "삽입"한다고만 기술한다. 이 구현은 축출한 LinkedListNode 인스턴스를 재사용하므로 캐시가 만원인 정상 상태에서 할당이 0이다. Program.cs가 이를 실측한다.

2. put 하나 대신 Insert / Upsert

원문의 put은 중복 키면 값을 덮어쓴다. 이 구현은 둘로 나뉘고, Insert는 원문 put과 동작이 다르다.

	키가 없을 때	키가 이미 있을 때
원문 put	삽입	값을 덮어씀
Insert	삽입	값을 유지
Upsert	삽입	값을 덮어씀 (원문 put과 동일)

값 갱신을 기대하고 Insert를 쓰면 조용히 실패하므로 주의할 것.

3. 조회 실패 표현

원문 get은 키를 찾지 못하면 -1을 돌려준다. 값이 정수일 때만 통하는 관례다. 이 구현은 bool 반환 + out 파라미터의 TryGetValue 패턴이라 값 타입에 제약이 없다.

4. LinkedList<T> 사용

원문은 이중 연결 리스트를 직접 구현한다. 여기서는 .NET의 LinkedList<T>를 쓴다. Remove(node)가 O(1)이라 복잡도는 같고, 노드가 리스트에서 떨어질 때 내부 List 참조가 끊기는 덕분에 위의 노드 재활용이 성립한다.

정리하면 알고리즘은 원문과 같고, 할당 최적화와 API 설계에서 갈린다.

한계

실전 캐시 라이브러리(BitFaster.Caching 등)를 대체하려는 코드가 아니다. 다음이 없다.

• 스레드 안전성. 읽기처럼 보이는 TryGetValue도 리스트를 재정렬하므로, 동시 접근하려면 외부 락이 필요하다.
• 축출 콜백. 캐시 아웃되는 요소를 알 방법이 없어서 IDisposable 값을 담으면 정리할 수 없다.
• TTL / 만료. 용량 기반 축출만 한다.
• Clear(), Keys, ContainsKey.
• MaxCount 검증. 0 이하로 생성하면 첫 삽입에서 예외가 난다.

또한 Values는 지연 평가되는 IEnumerable이라, 순회 도중 TryGetValue를 호출하면 컬렉션이 변경되어 예외가 발생한다. 순회 중 조회가 필요하면 먼저 ToArray()로 스냅샷을 뜰 것.

비고

네임스페이스는 LruCacheSample로 두었다. 가져다 쓸 때는 프로젝트에 맞게 바꾸면 된다.

참고

• https://www.geeksforgeeks.org/lru-cache-implementation/

LruCache.cs

namespace LruCacheSample
{
    using System.Collections.Generic;
    using System.Diagnostics.CodeAnalysis;
    using System.Linq;

    // 참고 : https://www.geeksforgeeks.org/lru-cache-implementation/
    public sealed class LruCache<TKey, TElement> where TKey : notnull
    {
        private readonly LinkedList<(TKey Key, TElement Value)> timeline = new LinkedList<(TKey, TElement)>();
        private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TElement Value)>> index;

        public LruCache(int maxCount)
        {
            this.index = new Dictionary<TKey, LinkedListNode<(TKey, TElement)>>(maxCount);
            this.MaxCount = maxCount;
        }

        public LruCache(int maxCount, IEqualityComparer<TKey> comparer)
        {
            this.index = new Dictionary<TKey, LinkedListNode<(TKey, TElement)>>(maxCount, comparer);
            this.MaxCount = maxCount;
        }

        public int Count => this.timeline.Count;
        public IEnumerable<TElement> Values => this.timeline.Select(e => e.Value);
        public int MaxCount { get; }

        public bool TryGetValue(TKey key, out TElement result)
        {
            if (this.index.TryGetValue(key, out var node) == false)
            {
                result = default!;
                return false;
            }

            result = node.Value.Value;
            this.timeline.Remove(node);
            this.timeline.AddFirst(node);
            return true;
        }

        public bool Insert(TKey key, [DisallowNull] TElement element)
        {
            bool insert = false;
            if (this.index.TryGetValue(key, out var node) == false) //// 기존에 값이 존재하지 않음.
            {
                while (this.timeline.Count >= this.MaxCount) //// delete least recently used element
                {
                    node = this.timeline.Last!; // 캐시 크기가 넘치면, 기존의 node를 재활용한다.
                    this.timeline.RemoveLast();
                    this.index.Remove(node.Value.Key);
                }

                if (node != null)
                {
                    node.Value = (key, element);
                }
                else
                {
                    node = new LinkedListNode<(TKey, TElement)>((key, element));
                }

                this.index.Add(key, node);
                insert = true;
            }
            else //// 기존에 값이 존재했다면 timeline을 최신화 해준다.
            {
                this.timeline.Remove(node);
                // node.Value = (key, element); // insert는 기존 값을 변경하지 않는다. 아래 Upsert만 값을 바꾼다.
            }

            this.timeline.AddFirst(node);
            return insert;
        }

        public bool Upsert(TKey key, TElement element)
        {
            bool insert = false;
            if (this.index.TryGetValue(key, out var node) == false) //// 기존에 값이 존재하지 않음.
            {
                while (this.timeline.Count >= this.MaxCount) //// delete least recently used element
                {
                    node = this.timeline.Last!; // 캐시 크기가 넘치면, 기존의 node를 재활용한다.
                    this.timeline.RemoveLast();
                    this.index.Remove(node.Value.Key);
                }

                insert = true;
            }
            else //// 기존에 값이 존재했다면 timeline을 최신화 해준다.
            {
                this.timeline.Remove(node);
            }

            if (node != null)
            {
                node.Value = (key, element);
            }
            else
            {
                node = new LinkedListNode<(TKey, TElement)>((key, element));
            }

            this.timeline.AddFirst(node);
            this.index[key] = node;
            return insert;
        }

        public void Remove(TKey key)
        {
            if (this.index.TryGetValue(key, out var node) == false) //// 기존에 값이 존재하지 않음.
            {
                return;
            }

            this.timeline.Remove(node);
            this.index.Remove(key);
        }
    }
}

LruCacheSample.csproj

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net8.0</TargetFramework>
    <Nullable>enable</Nullable>
    <!-- net8.0 런타임이 없어도 상위 버전에서 실행되도록 한다. -->
    <RollForward>LatestMajor</RollForward>
    <ImplicitUsings>disable</ImplicitUsings>
    <RootNamespace>LruCacheSample</RootNamespace>
    <AssemblyName>LruCacheSample</AssemblyName>
  </PropertyGroup>

</Project>

Program.cs

namespace LruCacheSample
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// LruCache 동작 검증. 외부 테스트 프레임워크 의존이 없다.
    /// 실행: dotnet run
    /// </summary>
    public static class Program
    {
        private static int passed;
        private static int failed;

        public static int Main()
        {
            TestCountAndMaxCount();
            TestInsertDoesNotGrowOnDuplicateKey();
            TestEvictsLeastRecentlyUsed();
            TestTryGetValueTouchesEntry();
            TestInsertKeepsValueUpsertReplacesIt();
            TestUpsertAlsoEvicts();
            TestRemove();
            TestMissingKey();
            TestCustomComparer();
            TestNodeRecyclingDoesNotAllocate();

            Console.WriteLine();
            Console.WriteLine($"통과 {Program.passed} / 실패 {Program.failed}");
            return Program.failed == 0 ? 0 : 1;
        }

        //// ---------------------------------------------------------------- 테스트

        /// <summary>Count 는 보관 중인 개수를 따라가고 MaxCount 를 넘지 않는다.</summary>
        private static void TestCountAndMaxCount()
        {
            var cache = new LruCache<int, int>(maxCount: 10);
            Check("빈 캐시의 Count 는 0", cache.Count == 0);
            Check("MaxCount 가 보존됨", cache.MaxCount == 10);

            for (int i = 0; i < 10; ++i)
            {
                Check($"신규 키 {i} 삽입은 true", cache.Insert(i, i));
            }

            Check("가득 찬 뒤 Count 는 MaxCount", cache.Count == 10);

            for (int i = 100; i < 120; ++i)
            {
                cache.Insert(i, i);
            }

            Check("초과 삽입해도 Count 는 MaxCount 유지", cache.Count == 10);
        }

        /// <summary>같은 키를 다시 넣어도 개수는 늘지 않고 false 를 돌려준다.</summary>
        private static void TestInsertDoesNotGrowOnDuplicateKey()
        {
            var cache = new LruCache<int, int>(maxCount: 10);
            Check("첫 삽입은 true", cache.Insert(1, 1));
            Check("중복 삽입은 false", cache.Insert(1, 1) == false);
            Check("중복 삽입 후에도 Count 는 1", cache.Count == 1);
        }

        /// <summary>용량이 넘치면 가장 오래 전에 쓰인 항목부터 빠진다.</summary>
        private static void TestEvictsLeastRecentlyUsed()
        {
            var cache = new LruCache<int, int>(maxCount: 10);
            for (int i = 0; i < 10; ++i)
            {
                cache.Insert(i, i * 10);
            }

            for (int i = 10; i < 20; ++i)
            {
                cache.Insert(i, i);
            }

            Check("Count 는 그대로 10", cache.Count == 10);
            Check("먼저 넣은 0 은 축출됨", cache.TryGetValue(0, out _) == false);
            Check("나중에 넣은 19 는 남아 있음", cache.TryGetValue(19, out _));

            // Values 는 MRU -> LRU 순서라, 뒤집으면 오래된 것부터가 된다.
            int[] values = cache.Values.Reverse().ToArray();
            Check("남은 값은 10..19", values.SequenceEqual(Enumerable.Range(10, count: 10)));
        }

        /// <summary>조회에 성공하면 해당 항목이 최신으로 올라와 축출을 피한다.</summary>
        private static void TestTryGetValueTouchesEntry()
        {
            var cache = new LruCache<int, int>(maxCount: 10);
            for (int i = 0; i < 10; ++i)
            {
                cache.Insert(i, i);
            }

            for (int i = 10; i < 15; ++i)
            {
                cache.Insert(i, i);
            }

            // 남아 있는 가장 오래된 그룹(5..9) 중 하나를 조회해 최신으로 끌어올린다.
            Check("5 는 아직 살아 있음", cache.TryGetValue(5, out int touched));
            Check("조회한 값이 맞음", touched == 5);
            Check("조회는 Count 를 바꾸지 않음", cache.Count == 10);

            for (int i = 15; i < 20; ++i)
            {
                cache.Insert(i, i);
            }

            int[] values = cache.Values.Reverse().ToArray();
            int[] expected = new[] { 11, 12, 13, 14, 5, 15, 16, 17, 18, 19 };
            Check("touch 한 5 가 살아남음", values.SequenceEqual(expected));
        }

        /// <summary>Insert 는 기존 값을 지키고, Upsert 만 덮어쓴다. 둘 다 순서는 갱신한다.</summary>
        private static void TestInsertKeepsValueUpsertReplacesIt()
        {
            var cache = new LruCache<int, string>(maxCount: 10);
            cache.Insert(1, "a");
            Check("Insert 로 들어간 값", cache.TryGetValue(1, out string v1) && v1 == "a");

            Check("기존 키 Insert 는 false", cache.Insert(1, "b") == false);
            Check("Insert 는 값을 바꾸지 않음", cache.TryGetValue(1, out string v2) && v2 == "a");

            Check("기존 키 Upsert 도 false", cache.Upsert(1, "c") == false);
            Check("Upsert 는 값을 바꿈", cache.TryGetValue(1, out string v3) && v3 == "c");

            Check("없는 키 Upsert 는 true", cache.Upsert(2, "d"));
            Check("Upsert 로 삽입된 값", cache.TryGetValue(2, out string v4) && v4 == "d");
        }

        /// <summary>Upsert 로만 채워도 축출이 동일하게 동작한다.</summary>
        private static void TestUpsertAlsoEvicts()
        {
            var cache = new LruCache<int, int>(maxCount: 3);
            cache.Upsert(1, 1);
            cache.Upsert(2, 2);
            cache.Upsert(3, 3);
            cache.Upsert(4, 4);

            Check("Upsert 축출 후 Count 는 3", cache.Count == 3);
            Check("가장 오래된 1 이 빠짐", cache.TryGetValue(1, out _) == false);
            Check("2,3,4 는 남음", cache.Values.OrderBy(e => e).SequenceEqual(new[] { 2, 3, 4 }));
        }

        /// <summary>Remove 는 항목을 지우고, 없는 키에 대해서는 조용히 넘어간다.</summary>
        private static void TestRemove()
        {
            var cache = new LruCache<int, int>(maxCount: 10);
            cache.Insert(1, 1);
            cache.Insert(2, 2);

            cache.Remove(1);
            Check("삭제 후 Count 감소", cache.Count == 1);
            Check("삭제한 키는 조회되지 않음", cache.TryGetValue(1, out _) == false);
            Check("남은 키는 그대로", cache.TryGetValue(2, out _));

            cache.Remove(999); // 없는 키 삭제는 예외 없이 무시된다.
            Check("없는 키 삭제는 무해함", cache.Count == 1);

            // 지운 자리에 다시 넣을 수 있어야 한다.
            Check("삭제한 키 재삽입은 true", cache.Insert(1, 11));
            Check("재삽입한 값이 반영됨", cache.TryGetValue(1, out int v) && v == 11);
        }

        /// <summary>없는 키 조회는 false 와 기본값을 돌려준다.</summary>
        private static void TestMissingKey()
        {
            var cache = new LruCache<int, string>(maxCount: 4);
            Check("빈 캐시 조회는 false", cache.TryGetValue(1, out string missing) == false);
            Check("실패 시 out 은 기본값", missing == null);
        }

        /// <summary>IEqualityComparer 오버로드가 키 비교에 실제로 쓰인다.</summary>
        private static void TestCustomComparer()
        {
            var cache = new LruCache<string, int>(maxCount: 4, StringComparer.OrdinalIgnoreCase);
            cache.Insert("Key", 1);

            Check("대소문자 무시 조회", cache.TryGetValue("KEY", out int v) && v == 1);
            Check("대소문자 다른 키는 중복 취급", cache.Insert("key", 2) == false);
            Check("항목은 하나만 존재", cache.Count == 1);
        }

        /// <summary>
        /// 캐시가 가득 찬 정상 상태에서는 축출된 LinkedListNode 를 재사용하므로
        /// 삽입이 새 할당을 만들지 않는다.
        /// </summary>
        private static void TestNodeRecyclingDoesNotAllocate()
        {
            var cache = new LruCache<int, int>(maxCount: 64);
            for (int i = 0; i < 64; ++i)
            {
                cache.Insert(i, i); // 워밍업: 여기까지는 노드를 할당한다.
            }

            long before = GC.GetAllocatedBytesForCurrentThread();
            for (int i = 1000; i < 2000; ++i)
            {
                cache.Insert(i, i); // 만원 상태 -> 축출한 노드를 재활용한다.
            }

            long allocated = GC.GetAllocatedBytesForCurrentThread() - before;
            Check($"가득 찬 뒤 1000회 삽입 할당량 0바이트 (실측 {allocated})", allocated == 0);
            Check("재활용 후에도 Count 유지", cache.Count == 64);
            Check("재활용된 노드의 값이 정확함", cache.TryGetValue(1999, out int last) && last == 1999);
        }

        //// ---------------------------------------------------------------- 헬퍼

        private static void Check(string description, bool condition)
        {
            if (condition)
            {
                Program.passed++;
                Console.WriteLine($"  PASS  {description}");
                return;
            }

            Program.failed++;
            Console.WriteLine($"  FAIL  {description}");
        }
    }
}