суббота, 3 мая 2008 г.

Кеш с гибридными ссылками

Иногда приходится задумываться о том, что выделять новые объекты каждый раз слишком дорого. Особенно это относится к байтовым и пр. буферам. В таком случае, целесообразно организовать некий пул и брать оттуда объекты, возвращая их после использования.
Госпожа Maoni Stephens (http://blogs.msdn.com/maoni/) предлагает использовать двухуровневый кеш:

use a 2-level caching mechanism:
· Maintain a strong reference for the cached items for x amount of time;
· After x amount of time is up, convert the strong references to weak references. Weak references will be considered to be kicked out of the cache before strong references are considered.

У нас нет оснований не доверять этой уважаемой даме, которая, между прочим, performance PM in the CLR department.

Реализаций одноуровневых кешей может быть достаточно много. Все они сводятся к тому, что есть некая коллекция, куда записываются объекты вместо удаления и откуда они извлекаются для работы. Чаще всего используется очередь, но иногда это бывает стек или простой список. Проблема таких пулов в уровне полезной нагрузки. Например, каждую минуту из пула считывается 1000 объектов и 1000 возвращается. Это значит, что достаточно иметь в коллекции около 1000 позиций для нормальной работы. Если происходит "всплеск" и за секунду будет запрошено 10000 объектов, будет создано 9000 новых объектов и затем они вернутся в пул. Когда нагрузка станет снова 1000 операций в секунду, в пуле будет 10000 объектов, что в 10 раз больше нужного уровня. Это пустая трата, а также не неужная фрагментация памяти.
Если у нас пул основан на очереди (модель First-In-First-Out), то все 10000 объектов будут по кругу перебираться и использоваться, что не очень оптимально. Если же в пуле задействован стек (модель First-In-Last-Out), то 9000 объектов использоваться не будут, и просто будут занимать память.
Хорошим вариантом может быть использование слабых ссылок (Weak Reference) в коллекции пула. Такие ссылки будут указывать на объекты пула до сборки мусора GC. После нее они станут не валидными. Это приемлимо, но не оптимально, потому есть смысл рассматривать гибридные варианты, о которых и говорится в цитате в начале статьи.

Если реализовывать двухуровневый кеш в таком виде, как предлагает Маони, то с некоторым интервалом нам придется пробегать эту коллекцию и проверять каждую ссылку, чтобы знать, не пора ли ей переходить из режима Strong reference в Weak reference. В подобном переборе нет ничего противозаконного, кроме того, что эта операция не потокобезопасна и должна проводиться с обязательной синхронизацией. Правильнее всего ставить блокировку на саму операцию перебора коллекции, а также на все операции по извлечению/возврату кешируемых объектов.
Как обычно, нормальных людей такой вариант вполне устроит, но членам общества Анонимных Параноиков, к которым я принадлежу, покажется, что это довольно дорого и необоснованно. :)

Долгое время я искал различные сложные решения, пытался регистрировать гибридные ссылки в отдельных коллекциях, делал копию коллекции пула перед перебором и т.п., но все это не удовлетворяло по сложности и скорости работы.
Выход сегодня был найден, причем довольно неожиданный. Ранее я упирался в поиск комплексного решения, искал подходы в чистом программировании, но найденное решение лежало на поверхности.
Оно не относится к "честным" методам: при возвращении объекта в кеш, я добавляю в пул слабую ссылку на него (WeakReference), а в отдельный список - обычную сильную ссылку. При этом, я не задумываюсь о таких тонкостях, как был ли объект ранее в этом вспомогательном списке, никогда не удаляю оттуда объекты, никогда не перебираю этот список. Единственная операция, которую я делаю с этой вспомогательной коллекцией - очищаю ее раз в несколько минут.
Это звучит несколько странно, но смысл довольно прост: я не даю объектам в пуле умереть в течение некоторого времени. Если объект извлекли из пула для работы, то на его время жизни эта коллекция никак не повлияет. Если же объект "ушел на дно", т.е. находится в хвосте стека, или в середине очереди, то мы убираем единственную сильную ссылку на него, а слабая ссылка умрет при сборке мусора.
Таким образом, через какое-то время после "всплеска" пул будет содержать только то количество объектов, которое нужно для работы, вплоть до полного очищения - отмирания всех ссылок, когда пул не используется.

Такое использование памяти кажется мне наиболее оптимальным, пусть решение и не на 100% соответствует канонам ООП.

P.S. Я рекомендую использовать для пула стек, а не очередь. Этот подход дает больше нагрузки на "ближние" объекты стека, но "дальние" почти никогда не используются и могут быть очищены сборкой мусора. Если вы не хотите сразу выделять много памяти для этого стека, можно посмотреть в сторону идей господина Justin Rogers.
P.P.S. Для обеспечения нужного времени жизни объектов в пуле есть смысл использовать более сложные методы, чем одна ссылочная колекция. Например, хранить две коллекции и в методе очистки основную заменять вспомогательной, а старую вспомогательную удалять. Таким образом любой объект гарантированно будет иметь сильную ссылку на время не меньше интервала очистки.