Шаблон для одновременного совместного использования кэша

Question

Хорошо, я был немного не уверен, как лучше назвать эту проблему :) Но предположим, что в этом сценарии вы выходите и получаете какую-то веб-страницу (с различными URL-адресами) и кешируете ее локально.Часть кеша довольно легко решить даже с несколькими потоками.

Однако представьте, что один поток начинает извлекать URL-адрес, а через пару миллисекунд другой хочет получить тот же URL-адрес.Есть ли хороший способ заставить метод секундного потока ждать, пока первый извлечет страницу, вставить ее в кеш и вернуть, чтобы вам не приходилось выполнять несколько запросов.С небольшими накладными расходами, которые стоит делать даже для запросов, которые занимают около 300-700 мс?И без блокирования запросов на другие URL

В основном, когда запросы на идентичные URL-адреса поступают тесно друг за другом, я хочу, чтобы второй запрос «совмещал» первый запрос

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

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

Существует ли какой-либо общий шаблон и решения для подобных сценариев?

Неправильное поведение с разбивкой:

Поток 1: проверкикеша, он не существует, поэтому начинает извлекать URL

Поток 2: начинает извлекать тот же URL, поскольку он все еще не существует в Cache

Поток 1: завершен и вставляется в кеш,возвращает страницу

Поток 2: завершает, а также вставляет в кэш (или удаляет его), возвращает страницу

Правильное поведение разбивки:

Поток 1: проверяет кэш,он не существует, поэтому начинает извлекать URL-адрес

Поток 2: хочет тот же URL-адрес, но видит, что он в настоящее время извлекается, поэтому ожидает в потоке 1

Поток 1: завершен и вставляет iв кэш возвращает страницу

Поток 2: замечает, что поток 1 завершен, и возвращает поток страницы 1, который он выбрал

РЕДАКТИРОВАТЬ

БольшинствоРешения sofar, кажется, неправильно понимают проблему и обращаются только к кешированию, поскольку я сказал, что это не проблема, проблема заключается в том, что при выполнении внешней выборки через Интернет выполняется вторая выборка , которая выполняется до того, как первая кэширует ее использовать результат первого, а не второго

Answer 1

Вы можете использовать ConcurrentDictionary<K,V> и вариант двойная проверка блокировки :

public static string GetUrlContent(string url)
{
    object value1 = _cache.GetOrAdd(url, new object());

    if (value1 == null)    // null check only required if content
        return null;       // could legitimately be a null string

    var urlContent = value1 as string;
    if (urlContent != null)
        return urlContent;    // got the content

    // value1 isn't a string which means that it's an object to lock against
    lock (value1)
    {
        object value2 = _cache[url];

        // at this point value2 will *either* be the url content
        // *or* the object that we already hold a lock against
        if (value2 != value1)
            return (string)value2;    // got the content

        urlContent = FetchContentFromTheWeb(url);    // todo
        _cache[url] = urlContent;
        return urlContent;
    }
}

private static readonly ConcurrentDictionary<string, object> _cache =
                                  new ConcurrentDictionary<string, object>();

Answer 2

РЕДАКТИРОВАТЬ: Мой код сейчас немного страшнее, но использует отдельную блокировку для URL.Это позволяет асинхронно получать разные URL, однако каждый URL будет выбираться только один раз.

public class UrlFetcher
{
    static Hashtable cache = Hashtable.Synchronized(new Hashtable());

    public static String GetCachedUrl(String url)
    {
        // exactly 1 fetcher is created per URL
        InternalFetcher fetcher = (InternalFetcher)cache[url];
        if( fetcher == null )
        {
            lock( cache.SyncRoot )
            {
                fetcher = (InternalFetcher)cache[url];
                if( fetcher == null )
                {
                    fetcher = new InternalFetcher(url);
                    cache[url] = fetcher;
                }
            }
        }
        // blocks all threads requesting the same URL
        return fetcher.Contents;
    }

    /// <summary>Each fetcher locks on itself and is initilized with null contents.
    /// The first thread to call fetcher.Contents will cause the fetch to occur, and
    /// block until completion.</summary>
    private class InternalFetcher
    {
        private String url;
        private String contents;

        public InternalFetcher(String url)
        {
            this.url = url;
            this.contents = null;
        }

        public String Contents
        {
            get
            {
                if( contents == null )
                {
                    lock( this ) // "this" is an instance of InternalFetcher...
                    {
                        if( contents == null )
                        {
                            contents = FetchFromWeb(url);
                        }
                    }
                }
                return contents;
            }
        }
    }
}

Answer 3

Отказ от ответственности: это может быть n00bish ответ.Пожалуйста, простите меня, если это так.

Я бы рекомендовал использовать некоторый общий словарь с блокировками, чтобы отслеживать URL-адрес, который в данный момент выбирается или уже был получен.

• При каждом запросе проверяйте URL-адрес этого объекта.

• Если имеется запись для URL-адреса, проверьте кэш.(это означает, что один из потоков либо извлек его, либо в настоящее время извлекает его)

• Если он доступен в кеше, используйте его, иначе переведите текущий поток в спящий режим на некоторое время изайдите снова.(если он не находится в кеше, какой-то поток все еще извлекает его, поэтому подождите, пока он не завершится)

• Если запись не найдена в объекте словаря, добавьте в нее URL-адрес и отправьтезапрос.Как только он получит ответ, добавьте его в кеш.

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

Answer 4

Это не совсем для одновременных кэшей, но для всех кэшей:

«Кэш с неправильной политикой - это еще одно название утечки памяти» (Рэймонд Чен)

Answer 5

Будет ли Semaphore, пожалуйста, встаньте!вставать!встать!

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

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

в обоих сценариях вы столкнетесь с проблемами.

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

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