Оптимизировать кеш с несколькими ключами в С# - удалить дублирование объектов

Ответ 1

Возможно, мы могли бы переформулировать эту проблему по двум отдельным вопросам...

1. выполнение вызова для каждой комбинации и
2. сохраняя n раз идентичный результат, теряя тонны памяти

Для 1 я не имею ни малейшего представления о том, как мы могли бы предотвратить это, поскольку мы не знаем до выполнения, если мы будем извлекать дубликат в этой настройке. Нам потребуется дополнительная информация, основанная на том, когда эти значения меняются, что может быть или может быть невозможно.

Для 2 одного решения было бы переопределить hashcode, чтобы он основывался на фактических возвращаемых значениях. Хорошее решение было бы общим и проходило через дерево объектов (что, вероятно, может быть дорогостоящим). Хотелось бы знать, есть ли какие-либо готовые решения для этого на самом деле.

Ответ 2

Этот ответ специально предназначен для возврата List<TItem> s, а не только отдельных TItem s, и он избегает дублирования любого TItem а также любого List<T>. Он использует массивы, потому что вы пытаетесь сохранить память, а массивы будут использовать меньше, чем List.

Обратите внимание, что для этого (и любого решения действительно) для работы вы ДОЛЖНЫ переопределить Equals и GetHashCode на TItem, чтобы он знал, что такое дублирующийся элемент. (Если поставщик данных не возвращает один и тот же объект каждый раз, что маловероятно.) Если у вас нет контроля над TItem, но вы сами можете определить, равны ли два TItem, вы можете использовать IEqualityComparer для этого, но ниже решение необходимо будет немного изменить, чтобы сделать это.

Просмотрите решение с базовым тестом по адресу: https://dotnetfiddle.net/pKHLQP

public class DuplicateFreeCache<TKey, TItem> where TItem : class
{
    private ConcurrentDictionary<TKey, int> Primary { get; } = new ConcurrentDictionary<TKey, int>();
    private List<TItem> ItemList { get; } = new List<TItem>();
    private List<TItem[]> ListList { get; } = new List<TItem[]>();
    private Dictionary<TItem, int> ItemDict { get; } = new Dictionary<TItem, int>();
    private Dictionary<IntArray, int> ListDict { get; } = new Dictionary<IntArray, int>();

    public IReadOnlyList<TItem> GetOrAdd(TKey key, Func<TKey, IEnumerable<TItem>> getFunc)
    {
        int index = Primary.GetOrAdd(key, k =>
        {
            var rawList = getFunc(k);

            lock (Primary)
            {
                int[] itemListByIndex = rawList.Select(item =>
                {
                    if (!ItemDict.TryGetValue(item, out int itemIndex))
                    {
                        itemIndex = ItemList.Count;
                        ItemList.Add(item);
                        ItemDict[item] = itemIndex;
                    }
                    return itemIndex;
                }).ToArray();

                var intArray = new IntArray(itemListByIndex);

                if (!ListDict.TryGetValue(intArray, out int listIndex))
                {
                    lock (ListList)
                    {
                        listIndex = ListList.Count;
                        ListList.Add(itemListByIndex.Select(ii => ItemList[ii]).ToArray());
                    }
                    ListDict[intArray] = listIndex;
                }

                return listIndex;
            }
        });

        lock (ListList)
        {
            return ListList[index];
        }
    }


    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        sb.AppendLine($"A cache with:");
        sb.AppendLine($"{ItemList.Count} unique Items;");
        sb.AppendLine($"{ListList.Count} unique lists of Items;");
        sb.AppendLine($"{Primary.Count} primary dictionary items;");
        sb.AppendLine($"{ItemDict.Count} item dictionary items;");
        sb.AppendLine($"{ListDict.Count} list dictionary items;");
        return sb.ToString();
    }

    //We have this to make Dictionary lookups on int[] find identical arrays.
    //One could also just make an IEqualityComparer, but I felt like doing it this way.
    public class IntArray
    {
        private readonly int _hashCode;
        public int[] Array { get; }
        public IntArray(int[] arr)
        {
            Array = arr;
            unchecked
            {
                _hashCode = 0;
                for (int i = 0; i < arr.Length; i++)
                    _hashCode = (_hashCode * 397) ^ arr[i];
            }
        }

        protected bool Equals(IntArray other)
        {
            return Array.SequenceEqual(other.Array);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            if (obj.GetType() != this.GetType()) return false;
            return Equals((IntArray)obj);
        }

        public override int GetHashCode() => _hashCode;
    }
}

Мне пришло в голову, что ReaderWriterLockSlim будет лучше, чем lock(ListList), если lock вызывает отставание в производительности, но это немного сложнее.

Ответ 3

Подобно @MineR, это решение выполняет операцию "двойного кэширования": он кэширует ключевые списки (lookups), а также отдельные объекты - выполняет автоматическую дедупликацию.

Это довольно простое решение, использующее два ConcurrentDictionaries - один из которых действует как HashSet а другой - как ключевой поиск. Это позволяет большинству проблем с потоками обрабатываться каркасом.

Вы также можете передавать и делиться хэш-настройкой между несколькими Cachedlookups что позволяет выполнять поиск с помощью разных ключей.

Обратите внимание, что для выполнения любой такой функции решения требуется равенство объектов или IEqualityComparer.

Учебный класс:

public class CachedLookup<T, TKey>
{        
    private readonly ConcurrentDictionary<T, T> _hashSet;
    private readonly ConcurrentDictionary<TKey, List<T>> _lookup = new ConcurrentDictionary<TKey, List<T>>();

    public CachedLookup(ConcurrentDictionary<T, T> hashSet)
    {
        _hashSet = hashSet;
    }   

    public CachedLookup(IEqualityComparer<T> equalityComparer = default)
    {
        _hashSet = equalityComparer is null ? new ConcurrentDictionary<T, T>() : new ConcurrentDictionary<T, T>(equalityComparer);
    }

    public List<T> Get(TKey key) => _lookup.ContainsKey(key) ? _lookup[key] : null;

    public List<T> Get(TKey key, Func<TKey, List<T>> getData)
    {
        if (_lookup.ContainsKey(key))
            return _lookup[key];

        var result = DedupeAndCache(getData(key));

        _lookup.TryAdd(key, result);

        return result;
    }
    public async ValueTask<List<T>> GetAsync(TKey key, Func<TKey, Task<List<T>>> getData)
    {
        if (_lookup.ContainsKey(key))
            return _lookup[key];

        var result = DedupeAndCache(await getData(key));

        _lookup.TryAdd(key, result);

        return result;
    }

    public void Add(T value) => _hashSet.TryAdd(value, value);

    public List<T> AddOrUpdate(TKey key, List<T> data)
    {            
        var deduped = DedupeAndCache(data);

        _lookup.AddOrUpdate(key, deduped, (k,l)=>deduped);

        return deduped;
    }

    private List<T> DedupeAndCache(IEnumerable<T> input) => input.Select(v => _hashSet.GetOrAdd(v,v)).ToList();
}

Пример использования:

public class ExampleUsage
{
    private readonly CachedLookup<LanguageInfoModel, (string frontendId, string languageId, string accessId)> _lookup 
        = new CachedLookup<LanguageInfoModel, (string frontendId, string languageId, string accessId)>(new LanguageInfoModelComparer());

    public ValueTask<List<LanguageInfoModel>> GetLanguagesAsync(string frontendId, string languageId, string accessId)
    {
        return _lookup.GetAsync((frontendId, languageId, accessId), GetLanguagesFromDB(k));
    }

    private async Task<List<LanguageInfoModel>> GetLanguagesFromDB((string frontendId, string languageId, string accessId) key) => throw new NotImplementedException();
}

public class LanguageInfoModel
{
    public string FrontendId { get; set; }
    public string LanguageId { get; set; }
    public string AccessId { get; set; }
    public string SomeOtherUniqueValue { get; set; }
}

public class LanguageInfoModelComparer : IEqualityComparer<LanguageInfoModel>
{
    public bool Equals(LanguageInfoModel x, LanguageInfoModel y)
    {
        return (x?.FrontendId, x?.AccessId, x?.LanguageId, x?.SomeOtherUniqueValue)
            .Equals((y?.FrontendId, y?.AccessId, y?.LanguageId, y?.SomeOtherUniqueValue));
    }

    public int GetHashCode(LanguageInfoModel obj) => 
        (obj.FrontendId, obj.LanguageId, obj.AccessId, obj.SomeOtherUniqueValue).GetHashCode();
}

Заметки:

Класс CachedLookup является общим как по значению, так и по ключу. Пример использования ValueTuple упрощает ValueTuple составных клавиш. Я также использовал ValueTuple для упрощения сравнений равенства.

Это использование ValueTask прекрасно сочетается с намеченной целью, возвращая кеш-список синхронно.

Если у вас есть доступ к уровню доступа к данным более низкого уровня, одна оптимизация будет заключаться в том, чтобы перенести дедупликацию до того, как объекты будут созданы (на основе равенства стоимости свойства). Это уменьшит распределение и нагрузку на GC.

Ответ 4

Если у вас есть контроль над полным решением, вы можете сделать что-то вроде этого.

1. Какой бы объект не мог храниться в кеше. Вы должны это идентифицировать. Все такие объекты реализуют общий интерфейс.

   public interface ICacheable 
   {
       string ObjectId(); // This will implement logic to calculate each object identity. You can count hash code but you have to add some other value to.
   }
   

2. Теперь, когда вы храните объект в кеше. Вы делаете две вещи.

   • Храните вещи в два раза. Как один кеш-хранилище ObjectId для ключа.

   • Другой будет содержать ObjectId для Object.

   • Общая идея заключается в том, что когда вы получаете объект. Вы выполняете поиск в первом кеше и видите, что ключ, который вы хотите, существует против ObjectId. Если да, то никаких дальнейших действий в противном случае вам нужно создать новую запись в First Cache для ObjectId на Key Map.

   • Если объект отсутствует, вам необходимо создать запись в обоих кешках

Примечание. Вам необходимо решить проблему производительности. Потому что ваши ключи - это своего рода список, поэтому он создает проблему во время поиска.

Ответ 5

Мне кажется, что вам нужно реализовать какой-то индекс. Предполагая, что ваша модель довольно большая, поэтому вы хотите сохранить память, тогда вы можете сделать это с помощью двух параллельных словарей.

Первым будет ConcurrentDictionary<string, int> (или любой уникальный идентификатор применим к вашему объекту модели) и будет содержать ваши значения ключа. Каждый ключ, очевидно, будет отличаться в соответствии со всеми вашими комбинациями, но вы только дублируя int уникальный ключ для всех ваших объектов, а не весь объект.

Второй словарь будет ConcurrentDictionary<int, object> или ConcurrentDictionary<int, T> и будет содержать ваши уникальные большие объекты, индексированные через их уникальный ключ.

При создании кеша вам нужно будет заполнить оба словаря, точный метод будет зависеть от того, как вы это делаете в данный момент.

Чтобы получить объект, вы должны создать ключ, как вы делаете в данный момент, получить значение хэш-кода из первого словаря, а затем использовать его для поиска фактического объекта из второго словаря.

Также можно аннулировать один ключ без аннулирования основного объекта, который также использует его другой ключ, хотя он требует, чтобы вы перебирали словарь индекса, чтобы проверить, указывает ли какой-либо другой ключ на тот же объект.

Ответ 6

Я думаю, что это не проблема кэширования, когда одна ключевая карта относится к одной и только одной информации. В этом случае твое не так. Вы пытаетесь манипулировать локальным хранилищем данных в памяти как кэшированные данные. Вы пытаетесь создать карты между ключами и объектами, загружаемыми с удаленного устройства. Один ключ способен сопоставлять многие объекты. Один объект может отображаться многими ключами, поэтому отношение n <======>> n

Я создал образец модального выражения следующим образом

Key, KeyMyModel и MyModel - это классы для кэширующего обработчика. RemoteModel - это класс, который вы получили от удаленного сервиса

С помощью этих моделей вы можете выполнить требования. Это использует идентификатор объекта для указания объекта, не требует хеширования для указания дублирования. Это очень просто, что я реализовал метод set. Invaildate ключ очень похож. Вы должны написать код, который также обеспечит безопасность потоков

public class MyModel
    {
        public RemoteModel RemoteModel { get; set; }
        public List<KeyMyModel> KeyMyModels { get; set; }
    }
    public class RemoteModel
    {
        public string Id { get; set; } // Identity property this get from remote service
        public string DummyProperty { get; set; } // Some properties returned by remote service
    }
    public class KeyMyModel
    {
        public string Key { get; set; }
        public string MyModelId { get; set; }
    }
    public class Key
    {
        public string KeyStr { get; set; }
        public List<KeyMyModel> KeyMyModels { get; set; }
    }

    public interface ICacheService
    {
        List<RemoteModel> Get(string key);
        List<RemoteModel> Get(string key, Func<List<RemoteModel>> getdata);
        Task<List<RemoteModel>> Get(string key, Func<Task<List<RemoteModel>>> getdata);
        void AddOrUpdate(string key, object value);
    }

    public class CacheService : ICacheService
    {
        public List<MyModel> MyModels { get; private set; }
        public List<Key> Keys { get; private set; }
        public List<KeyMyModel> KeyMyModels { get; private set; }

        public CacheService()
        {
            MyModels = new List<MyModel>();
            Keys = new List<Key>();
            KeyMyModels = new List<KeyMyModel>();
        }
        public List<RemoteModel> Get(string key)
        {
            return MyModels.Where(s => s.KeyMyModels.Any(t => t.Key == key)).Select(s => s.RemoteModel).ToList();
        }

        public List<RemoteModel> Get(string key, Func<List<RemoteModel>> getdata)
        {
            var remoteData = getdata();
            Set(key, remoteData);

            return MyModels.Where(s => s.KeyMyModels.Any(t => t.Key == key)).Select(t => t.RemoteModel).ToList();
        }

        public Task<List<RemoteModel>> Get(string key, Func<Task<List<RemoteModel>>> getdata)
        {
            throw new NotImplementedException();
        }

        public void AddOrUpdate(string key, object value)
        {
            throw new NotImplementedException();
        }

        public void Invalidate(string key)
        {

        }

        public void Set(string key, List<RemoteModel> data)
        {
            var Key = Keys.FirstOrDefault(s => s.KeyStr == key) ?? new Key()
            {
                KeyStr = key
            };

            foreach (var remoteModel in data)
            {
                var exist = MyModels.FirstOrDefault(s => s.RemoteModel.Id == remoteModel.Id);
                if (exist == null)
                {
                    // add data to the cache
                    var myModel = new MyModel()
                    {
                        RemoteModel = remoteModel
                    };
                    var keyMyModel = new KeyMyModel()
                    {
                        Key = key,
                        MyModelId = remoteModel.Id
                    };
                    myModel.KeyMyModels.Add(keyMyModel);
                    Key.KeyMyModels.Add(keyMyModel);
                    Keys.Add(Key);
                }
                else
                {
                    exist.RemoteModel = remoteModel;
                    var existKeyMyModel =
                        KeyMyModels.FirstOrDefault(s => s.Key == key && s.MyModelId == exist.RemoteModel.Id);
                    if (existKeyMyModel == null)
                    {
                        existKeyMyModel = new KeyMyModel()
                        {
                            Key = key,
                            MyModelId = exist.RemoteModel.Id
                        };
                        Key.KeyMyModels.Add(existKeyMyModel);
                        exist.KeyMyModels.Add(existKeyMyModel);
                        KeyMyModels.Add(existKeyMyModel);
                    }
                }
            }

            // Remove MyModels if need
            var remoteIds = data.Select(s => s.Id);
            var currentIds = KeyMyModels.Where(s => s.Key == key).Select(s => s.MyModelId);
            var removingIds = currentIds.Except(remoteIds);
            var removingKeyMyModels = KeyMyModels.Where(s => s.Key == key && removingIds.Any(i => i == s.MyModelId)).ToList();
            removingKeyMyModels.ForEach(s =>
            {
                KeyMyModels.Remove(s);
                Key.KeyMyModels.Remove(s);
            });
        }
    }

    class CacheConsumer
    {
        private readonly CacheService _cacheService = new CacheService();

        public List<RemoteModel> GetMyModels(string frontendId, string languageId, string accessId)
        {
            var key = $"{frontendId}_{languageId}_{accessId}";
            return _cacheService.Get(key, () =>
            {
                // call to remote service here
                return new List<RemoteModel>();
            });
        }
    }