+  HandyCache форум
|-+  Главная категория» Новые предложения» Индексирование кэша
Имя пользователя:
Пароль:
Страниц: [1] 2 3 ... 6   Вниз
  Отправить эту тему    Печать  
Автор Тема: Индексирование кэша  (Прочитано 77203 раз)
0 Пользователей и 1 Гость смотрят эту тему.
DenZzz
Модератор
*****

Репутация: +179/-11
Offline Offline

Сообщений: 5589



« : 12 января 2007, 23:24:40 »

Индексирование кэша для ускорения работы с диском и хранения дополнительных атрибутов


Предпосылки создания индексов, а не NTFS-потоков или парных файлов-паспортов:

  • Создание индексов позволит по мере необходимости загружать их в память и проверять наличие файлов в кэше и их атрибутов без обращения к диску, что ускорит работу HC;
  • Индексирование должно работать на всех операционных и файловых системах без ограничений:
    • Хранение дополнительных атрибутов в NTFS-потоках неприемлемо из-за невозможности их хранения на FAT32, сетевом сервере, сложностей с переносом кэша на флешке, CD/DVD-RW и т.д. (Линк)
    • Использование парных файлов-паспортов на FAT32 нецелесообразно из-за ее архитектуры; (Линк1, Линк2)



Пожелания:

  • При первом запросе файлов сайта загружать индекс в память и временами сохранять его на диск. При отсутствии запросов в течение n минут выгружать неиспользуемый индекс из памяти; (Линк)
  • Для уменьшения размера индекса не хранить в нем "лишних" данных. Например, пользователей пусть хранит "Историк", "Content-Type" не нужен для известных форматов, даты доступа хватит одной на папку и т.д. (Линк)
  • Предпочтительно создавать по отдельному индексу на корневую папку сайта (хоста) в кэше. Это лучше, чем постоянно лопатить один большой индекс. Удаление одной папки или порча ее индекса не приведет к утрате всей информации по кэшу; (Линк)
  • Для защиты от случайного удаления/порчи индексов предусмотреть возможность создания резервных копий. При порче индекса предусмотреть возможность его восстановления из резерва, либо по файлам в кэше с восстановлением возможных атрибутов. Сохранять на диск признак открытия индекса, чтобы в случае ненормального завершения работы HC (зависания) при перезапуске проверить "плохие" индексы по файлам кэша;
  • Для копирования индексов с разных компьютеров предусмотреть возможность уникальных названий (например, index1.idx, index2.idx и т.д.). При наличии после копирования кэша 2-х таких индексов в одной папке производить их слияние в один общий; (Линк)


Что хранить в индексе:

  • URL;
  • Дату модификации файла (для быстрой проверки "критерия свежести" и формирования заголовка "If-Modified-Since");
  • Дату доступа к папке с файлами (для чистки кэша от "старых" файлов);
  • "Content-Type" для неизвестных HC форматов (для заголовочных правил и формирования ответа HC при загрузке из кэша).


=== Перенесено с Wiki ===
Сообщить модератору   Записан
Сергей
Beta tester
*****

Репутация: +9/-2
Offline Offline

Сообщений: 621



« Ответ #1 : 13 января 2007, 11:47:03 »

Ты под индексом понимаешь базу, в которой хранятся все эти сведения?
Это же памяти много съест!
Надо использовать методы поисковиков. Когда индекс не содержит самих данных, но позволяет узнать где они лежат.
За основу можно взять исходные коды программы locate, которая портирована из unix и позволяет мгновенно искать файлы на диске по имени или другим аттрибутам.
Сообщить модератору   Записан
Дем
Постоялец
***

Репутация: +6/-3
Offline Offline

Сообщений: 167



« Ответ #2 : 13 января 2007, 13:04:35 »

Цитировать
Надо использовать методы поисковиков. Когда индекс не содержит самих данных, но позволяет узнать где они лежат.
И где они лежат, интересно? Улыбка

И индекс наверно лучше делать в виде какого-нибудь Embedded-SQL, как например у историка.
Сообщить модератору   Записан
Сергей
Beta tester
*****

Репутация: +9/-2
Offline Offline

Сообщений: 621



« Ответ #3 : 13 января 2007, 13:18:48 »

Главное, чтобы не снизилась скорость поиска.
И расход памяти не увеличился слишком сильно.
Иначе смысла в введении индексов не будет.
Сообщить модератору   Записан
DenZzz
Модератор
*****

Репутация: +179/-11
Offline Offline

Сообщений: 5589



« Ответ #4 : 13 января 2007, 13:20:04 »

Сергей

Цитировать
Это же памяти много съест!

Не так уж и много! Зато это ускорит работу и уменьшит количество обращений к диску, который и без того работает медленно!
Кстати, кроме прочего, использование RAM-кэша уменьшает загрузку процессора!

Цитировать
Надо использовать методы поисковиков. Когда индекс не содержит самих данных, но позволяет узнать где они лежат.

HC всегда знает, где у него лежат файлы (данные)! Он их не ищет по всему диску, а проверяет конкретный путь! Поэтому метод поисковиков в HC не применим!

К тому же, в индексе будет храниться не так уж и много данных: URL, даты, Content-Type (где потребуется)...
Сообщить модератору   Записан
Сергей
Beta tester
*****

Репутация: +9/-2
Offline Offline

Сообщений: 621



« Ответ #5 : 13 января 2007, 13:35:44 »

DenZzz
RAM кэш фактически уже выполняет эту функцию. Нет смысла хранить в памяти список всех файлов кэша.
Цитировать
Он их не ищет по всему диску, а проверяет конкретный путь!
Конкретный путь мы сразу по URL узнать не в состоянии.
Алгоритм URL2File предполагает, как минимум, несколько обращений к диску для проверки существования файлов/каталогов.
Сообщить модератору   Записан
DenZzz
Модератор
*****

Репутация: +179/-11
Offline Offline

Сообщений: 5589



« Ответ #6 : 13 января 2007, 13:50:22 »

Сергей

Цитировать
RAM кэш фактически уже выполняет эту функцию. Нет смысла хранить в памяти список всех файлов кэша.

Согласен! Идея индексов кэша активно обсуждалась еще до появления RAM-кэша!

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

Еще надо хранить где-то "Content-Type" для неизвестных HC форматов...

Цитировать
Конкретный путь мы сразу по URL узнать не в состоянии.

Почему же? Преобразовали URL - получили точный путь к файлу - проверили на диске.
Иногда, конечно, еще вспомогательные файлы надо проверить (типа #m), но это уже частность...
Сообщить модератору   Записан
Дем
Постоялец
***

Репутация: +6/-3
Offline Offline

Сообщений: 167



« Ответ #7 : 13 января 2007, 16:34:07 »

Цитировать
Еще надо хранить где-то "Content-Type" для неизвестных HC форматов...
А почему только для неизвестных? Можно и для всех. Тогда не надо будет проверять сигнатуру, да и правила на основе типа можно сделать...
Тем более что хранить стоит не саму строку - а только её номер в списке - т е 4 байта.

Цитировать
Почему же? Преобразовали URL - получили точный путь к файлу - проверили на диске.
Иногда, конечно, еще вспомогательные файлы надо проверить (типа #m), но это уже частность...
А тут кстати интересная возможность вырисовывается - уже загруженные файлы останутся доступны при изменении правил...
Да и преобразование имени в соответствии с новыми правилами можно сделать (отдельной программой)
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

Репутация: +337/-14
Offline Offline

Сообщений: 5513



« Ответ #8 : 09 февраля 2007, 21:41:22 »

DenZzz
Цитировать
Сейчас индексы уже не так актуальны
Тем не менее, на мой взгляд, очень даже актуальны. Вот еще одна польза их применения.
Сейчас НС не может использовать заложенный в HTTP механизм времени устаревания (expiration). Сервер часто посылает в ответе в поле "Expires:" или "Cache-Control: max-age=" дату/время, до истечения которой файл точно изменяться не будет. До этого времени мы смело можем не обращаться к серверу невзирая на содержание списков "Только из кэша" и "Не обновлять", не проверять If-Modified-Since, а смело выдавать файл из кэша. Для этого нам надо сохранять указанное поле (max-age, а при его отсутствии Expires) в индексе.
Сообщить модератору   Записан
pka2001
Новичок
*

Репутация: +0/-0
Offline Offline

Сообщений: 4


« Ответ #9 : 16 февраля 2007, 10:02:05 »

Индексы это интересно, но как это все будет работать в том случае когда у кучи юзверей стоит HC с общим кеше на сервере? Как бы не получилось так, что при попытке записать индекс одним из юзверей файл окажеться занят другим ...
Сообщить модератору   Записан
DenZzz
Модератор
*****

Репутация: +179/-11
Offline Offline

Сообщений: 5589



« Ответ #10 : 16 февраля 2007, 11:20:03 »

Индексы это интересно, но как это все будет работать в том случае когда у кучи юзверей стоит HC с общим кеше на сервере? Как бы не получилось так, что при попытке записать индекс одним из юзверей файл окажеться занят другим ...

Так и не может получиться! Т.к. при правильной настройке писать в кэш может только один юзер, а все остальные только читают из него - у них общий кэш настроен в строке "Только для чтения"!
Если у вас в сети иначе, то конфликты неизбежны и без всяких индексов!
Сообщить модератору   Записан
Дем
Постоялец
***

Репутация: +6/-3
Offline Offline

Сообщений: 167



« Ответ #11 : 16 февраля 2007, 11:42:53 »

Для более-менее серьёзного кеша - с индексом нужно через БД работать, тогда и проблемы с доступом автоматом решатся
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

Репутация: +337/-14
Offline Offline

Сообщений: 5513



« Ответ #12 : 21 февраля 2007, 13:31:38 »

С учетом необходимости экономии памяти предлагаю рассмотреть вопрос создания двухуровневого индекса.
Уровень 1: индекс по всем хостам (грузится в память при запуске программы и постоянно находится там), хранится в корневой папке кэша. Включает следующие поля:
- имя (имена) хоста;
- IP-адрес(а) хоста (первые два пункта - то, что сейчас итак хранится в кэше DNS, так что кэш DNS при этом уйдет);
- дата последнего доступа к хосту (для предварительного отсева URL по критерию свежести и возможно для целей грубой автоматической очистки);
- если нужна какая-то реалтаймовая статистика в разрезе по сайтам, то данные этой статистики по конкретному хосту.
Если какого-то сайта нет в индексе, то уже на этом этапе мы принимаем решение об отсутствии файла в кэше.
Уровень 2: индекс по всем URL данного хоста, находится в корневой папке хоста. Здесь уже можно хранить все, что ни придумаем по конкретному URL. Подгружается в память по мере надобности; выгружается, например, по таймауту либо по принципу FIFO при превышении заранее заданного размера занимаемой RAM.

На примере собственного кэша (стоИт "писать в кэш все") пронаблюдал ориентировочный порядок цифр:
Кэш - 900 МБ.
Папок в корневой директории - 5 000 (число записей в индексе 1 уровня).
Файлов - 90 000.
"Среднее число" хостов на 1 МБ кэша - 5,5 (т.е. кэш объемом 10 ГБ будет содержать ~55 тыс. записей в индексе 1 уровня: по-моему, в достаточной степени немного).
Среднее число URL на хост - 18 (т.е. среднее количество записей в индексе 2 уровня. Немного, т.е. можно хранить много атрибутов, не особенно скупясь и беспокоясь о том, что при загрузке в память это сожрет все ресурсы).

Еще вопрос, не будет ли часть всего этого пересекаться/дублироваться с RAM-кэш? Если да, то это надо учитывать. К сожалению, подробности организации RAM-кэша мне не известны, поэтому вывода делать пока не могу.

Давайте обсудим...
« Последнее редактирование: 21 февраля 2007, 13:43:14 от Михаил » Сообщить модератору   Записан
Rick
Администратор
*****

Репутация: +15/-1
Offline Offline

Сообщений: 868


WWW
« Ответ #13 : 21 февраля 2007, 19:29:44 »

Михаил
В теории это все и так более-менее ясно. Проблемы начинаются при попытке обдумать практическую сторону:
  • в каком формате хранить эти индексные файлы?
  • как синхронизировать индекс и фактический кэш: т.е. если запись в индексе есть, а в кэше хоста нет - и наоборот.

"Среднее число" хостов на 1 МБ кэша - 5,5 (т.е. кэш объемом 10 ГБ будет содержать ~55 тыс. записей в индексе 1 уровня: по-моему, в достаточной степени немного).
Если грубо, то одна запись минимум полкилобайта в лучшем случае, а то и больше - смотря как и в каком формате хранить. 30-50М - это достаточно много или достаточно НЕмного для хранения в RAM?
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

Репутация: +337/-14
Offline Offline

Сообщений: 5513



« Ответ #14 : 21 февраля 2007, 19:54:29 »

Rick
Цитировать
Если грубо, то одна запись минимум полкилобайта в лучшем случае, а то и больше - смотря как и в каком формате хранить. 30-50М - это достаточно много или достаточно НЕмного для хранения в RAM?
Почему полкило? Речь ведь об индексе 1 уровня, в каждой записи которого хранится существенно меньше - только то, что относимо к сайту в целом.
А в индексе 2 уровня 18 записей. И пусть они будут хоть по 10 килобайт каждая: 1. их мало. 2. этот индекс выгружается при необходимости.
Цитировать
в каком формате хранить эти индексные файлы?
Какие варианты рассматриваются?
Цитировать
как синхронизировать индекс и фактический кэш: т.е. если запись в индексе есть, а в кэше хоста нет - и наоборот
Ты имеешь ввиду форс-мажор? Если да, то вижу так:
- если запись в индексе есть, а файла нет - качаем файл, корректируем попутно значения переменных типа "размер кэша";
- если есть файл, но он не обозначен в индексе, то мы это обнаружить вроде как не в состоянии.
Почему этот вопрос сопряжен с трудностями?
Если же ты имеешь ввиду не форс-мажор, а целенаправленную правку/удаление юзером файлов/каталогов, то предлагаю считать это все равно форс-мажором Подмигивающий. Зачем ему туда влазить врукопашную?
Сообщить модератору   Записан
Rick
Администратор
*****

Репутация: +15/-1
Offline Offline

Сообщений: 868


WWW
« Ответ #15 : 21 февраля 2007, 20:43:44 »

Почему полкило? Речь ведь об индексе 1 уровня, в каждой записи которого хранится существенно меньше - только то, что относимо к сайту в целом.
Ну сам посчитай то, что ты предлагаешь:
Цитировать
- имя (имена) хоста;
- IP-адрес(а) хоста (первые два пункта - то, что сейчас итак хранится в кэше DNS, так что кэш DNS при этом уйдет);
- дата последнего доступа к хосту (для предварительного отсева URL по критерию свежести и возможно для целей грубой автоматической очистки);
- если нужна какая-то реалтаймовая статистика в разрезе по сайтам, то данные этой статистики по конкретному хосту.
Учитывая, что IP-адресов может быть несколько (как и имен на одном IP), имя домена до 254 символов, дата, статистика.

Цитировать
Какие варианты рассматриваются?
Какие предложишь - такие и рассмотрим.

Цитировать
- если запись в индексе есть, а файла нет - качаем файл, корректируем попутно значения переменных типа "размер кэша";
Зачем его качать? Может он никому не нужен - за что и был удален пользователем из кэша.

Цитировать
- если есть файл, но он не обозначен в индексе, то мы это обнаружить вроде как не в состоянии.
Если искать файл в кэше независимо от наличия/отсутствия записи в индексе - можем.

Цитировать
Если же ты имеешь ввиду не форс-мажор, а целенаправленную правку/удаление юзером файлов/каталогов, то предлагаю считать это все равно форс-мажором Подмигивающий. Зачем ему туда влазить врукопашную?
Мне тоже хотелось бы так думать, да не получается: есть и охотники до ручных ковыряний, есть и те, кто переносят кэш с одного компа на другой и/или объединяют кэши простым копированием.
Сообщить модератору   Записан
Дем
Постоялец
***

Репутация: +6/-3
Offline Offline

Сообщений: 167



« Ответ #16 : 21 февраля 2007, 21:25:42 »

Цитировать
На примере собственного кэша (стоИт "писать в кэш все") пронаблюдал ориентировочный порядок цифр:
Кэш - 900 МБ.
Папок в корневой директории - 5 000 (число записей в индексе 1 уровня).
Файлов - 90 000.
"Среднее число" хостов на 1 МБ кэша - 5,5 (т.е. кэш объемом 10 ГБ будет содержать ~55 тыс. записей в индексе 1 уровня: по-моему, в достаточной степени немного).

Не совсем так, например у меня:
Кеш - 13 Гб
сайтов в корне - 8500
файлов - 400.000

ЗЫ: Убрал нафиг все сайты с контентом менее 64К - кеш похудел на 100М, 5000 сайтов и 21000 файлов Улыбка
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

Репутация: +337/-14
Offline Offline

Сообщений: 5513



« Ответ #17 : 21 февраля 2007, 21:29:28 »

Rick
Цитировать
Ну сам посчитай то, что ты предлагаешь:
Считаем:
- средняя длина имени хоста - 15,23 символа (посчитал на примере собственного кэша). Берем 16 байт;
- IP-адрес - 4 байта. Не знаю точно, но думаю, что 2 адреса - редкость. Но пусть соотношение 1/4. Тогда в среднем - 5 байт;
- дата - пусть 10 байт;
- статистика - пусть 20 байт (5 целых чисел).
Итого: в среднем 51 байт. Вполне!
Цитировать
Если искать файл в кэше независимо от наличия/отсутствия записи в индексе - можем.
А есть ли острая необходимость? Если да, можно, конечно, и поискать. Но чем обуcловлена надобность?
Цитировать
Мне тоже хотелось бы так думать, да не получается: есть и охотники до ручных ковыряний, есть и те, кто переносят кэш с одного компа на другой и/или объединяют кэши простым копированием.
Могут ли охотники пересмотреть свои позиции, если им предложить взамен ускорение работы НС, статистику, автоматическую очистку кэша? Настолько ли неизменны их позиции? Это вообще изучалось? Если нет, давай обозначим этот вопрос здесь и сейчас.

Дем
Тогда у тебя индекс 1 уровня будет существенно меньшим (относительно размера кэша).
А я вот не чистил кэш уже сто лет. Могу рассматриваться как пессимистический прогноз Подмигивающий.
« Последнее редактирование: 21 февраля 2007, 21:44:37 от Михаил » Сообщить модератору   Записан
DenZzz
Модератор
*****

Репутация: +179/-11
Offline Offline

Сообщений: 5589



« Ответ #18 : 21 февраля 2007, 22:13:44 »

С учетом необходимости экономии памяти предлагаю рассмотреть вопрос создания двухуровневого индекса.
Уровень 1: индекс по всем хостам (грузится в память при запуске программы и постоянно находится там), хранится в корневой папке кэша.

Ты серьезно считаешь, что индекс 1 уровня, который будет постоянно находиться в памяти, способствует ее экономии?!

Цитировать
Включает следующие поля:
- имя (имена) хоста;
- IP-адрес(а) хоста (первые два пункта - то, что сейчас итак хранится в кэше DNS, так что кэш DNS при этом уйдет);

Кэш DNS содержит ограниченное число записей (у меня max=500), он автоматически чистится и обновляется - эх, не хотел бы я, чтобы в нем были все 55 000 записей! Подмигивающий

Цитировать
- дата последнего доступа к хосту (для предварительного отсева URL по критерию свежести и возможно для целей грубой автоматической очистки);

Во-первых, критерий свежести работает по дате модификации файла, а не по дате доступа к нему! Читать можно часто, а писать редко...
Во-вторых, у некоторых браузеров есть привычка последним загружать favicon.ico - вот тебе и обновление даты доступа к хосту, а все остальные файлы точно старее!

В общем, в большинстве случаев предварительная проверка критерия свежести по этой дате - лишняя операция, т.к. она нам ничего не даст!

Цитировать
- если нужна какая-то реалтаймовая статистика в разрезе по сайтам, то данные этой статистики по конкретному хосту.

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

Цитировать
Уровень 2: индекс по всем URL данного хоста, находится в корневой папке хоста. Здесь уже можно хранить все, что ни придумаем по конкретному URL. Подгружается в память по мере надобности; выгружается, например, по таймауту либо по принципу FIFO при превышении заранее заданного размера занимаемой RAM.

Ну, в общем, все что перечислено в первом посте этого топика, рожденное коллективным мозговым штурмом... Улыбка

Цитировать
Еще вопрос, не будет ли часть всего этого пересекаться/дублироваться с RAM-кэш? Если да, то это надо учитывать. К сожалению, подробности организации RAM-кэша мне не известны, поэтому вывода делать пока не могу.

Принцип работы RAM-кэша описан в ФАКе! Там же упомянуто то, что в нем хранится...

Опять же, у RAM-кэша свои критерии освобождения памяти - макс. размер RAM-кэша, а у индексов свои - "по таймауту либо по принципу FIFO при превышении заранее заданного размера занимаемой RAM" этими индексами. Может случиться так, что индекс пора выгружать, а в RAM еще его файлы остались! Синхронизировать их накладно!

Цитировать
Если же ты имеешь ввиду не форс-мажор, а целенаправленную правку/удаление юзером файлов/каталогов, то предлагаю считать это все равно форс-мажором.

М-да... Опять началось навязывание другим своих моделей поведения! Если бы этот вопрос звучал на ру-борде, тебя бы там просто "разорвали"! Подмигивающий Кто? Да тот же rs (автор Историка), unreal666 и другие любители поковыряться в кэше, переносить его части в архивах на флешке и чистить кэш сторонними программами (Историком и т.п.) мимо HC...

Хоть я всегда выступал в поддержку индексов, но, похоже, противника опять придется изображать мне за отсутствием их кворума на нашем форуме... Улыбка
« Последнее редактирование: 21 февраля 2007, 22:22:41 от DenZzz » Сообщить модератору   Записан
Rick
Администратор
*****

Репутация: +15/-1
Offline Offline

Сообщений: 868


WWW
« Ответ #19 : 21 февраля 2007, 23:16:06 »

- средняя длина имени хоста - 15,23 символа (посчитал на примере собственного кэша). Берем 16 байт;
Смотря как хранить - в каком формате.

Цитировать
Не знаю точно, но думаю, что 2 адреса - редкость.
Сделай nslookup www.ya.ru - 2 IP адреса и один алиас.
А посмотри то же для www.microsoft.com - 7 (семь) IP адресов и три алиаса.

Но в общем-то, думаю, вообще нет необходимости хранить IP адреса. Заменить собой DNS кэш индекс не сможет - и не надо.

Цитировать
- дата - пусть 10 байт;
8

Цитировать
А есть ли острая необходимость? Если да, можно, конечно, и поискать. Но чем обуcловлена надобность?
Именно тем, что в кэше может быть файл, о котором индекс "не в курсе".

Цитировать
Могут ли охотники пересмотреть свои позиции, если им предложить взамен ускорение работы НС, статистику, автоматическую очистку кэша? Настолько ли неизменны их позиции? Это вообще изучалось? Если нет, давай обозначим этот вопрос здесь и сейчас.
В том и беда, что не хотят/не могут. И получается с одной стороны все хотят некий индекс, а с другой - всегда будет вероятность того, что его актуальность ничтожна. У меня пессимистичный взгляд на перспективу индекса.

Кэш DNS содержит ограниченное число записей (у меня max=500), он автоматически чистится и обновляется - эх, не хотел бы я, чтобы в нем были все 55 000 записей! Подмигивающий
И не только это. Кэш DNS нельзя заменить данными из индексного файла в принципе. В индексном файле данные только о том, что _хранится_ в кэше.
Сообщить модератору   Записан
Страниц: [1] 2 3 ... 6   Вверх
  Отправить эту тему    Печать  

 
Перейти в: