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

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

Сообщений: 5589



« Ответ #20 : 22 февраля 2007, 09:02:17 »

Перечитал свой пост еще раз... И снова не нашел выделенное красным?! Непонимаю

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

Что и как будет работать с этим многотысячным списком - переносить и удалять в нем строки, искать нужные строки по URL в списке отсортированном по дате?
Как ты оцениваешь затраты системных ресурсов на эти постоянные операции?
Сообщить модератору   Записан
Oneri
Новичок
*

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

Сообщений: 34


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

1. думаю что имелось в виду не список а отсортированный по размеру каталогов и дате доступа  граф - затрат на поиск по индексу и вставку и перевещение (вставка) в графе не так уж и велика. (ну или БД)
2. производит эту процедуру постоянно не нужно, достаточно только счетчик  - и по его параметрам можно проводить очистку

Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #22 : 22 февраля 2007, 13:31:23 »

DenZzz
Oneri
Пока сам писал ответ, глядь - "Внимание - пока Вы просматривали тему, появился новый ответ. Вы можете изменить Ваше сообщение." а ответ уже есть! В точку.
Сообщить модератору   Записан
DIGGER
Старожил
****

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

Сообщений: 312



« Ответ #23 : 23 февраля 2007, 10:50:27 »

Проблемы начинаются, когда начинаешь думать как это реализовать. Грустный
Не вижу не одной!
Поясню как мне видится алгоритм:
• В папке с HC создаётся файл для хранения дат последнего обращения к URL
• Сктруктура файла:
1 строка: дата, время
2 строка: URL
и т. д. чередование.

• При обращении к URL обновляется дата (В файле происходит поиск по URL, этот тип поиска быстрый)
• Как вариант: создание нескольких индексных файлов. (По частоте посещаимости(1_файл=1000 самых посещаемых URL; 2_файл=5000 менее посещаемых и т.д.))
• При очистке кеша... думаю, тут всё понятно.

P.S. На NTFS проблем не должно быть, а в Win9x/Me — может... нужно смотреть на ограничения FS FAT32
Сообщить модератору   Записан
Rick
Администратор
*****

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

Сообщений: 868


WWW
« Ответ #24 : 23 февраля 2007, 11:11:44 »

1 строка: дата, время
2 строка: URL
и т. д. чередование.
1. Нужно еще хранить размер. Основная причина, из-за чего поднимается вопрос об улучшении очистки кэша - это потребность ограничить размер кэша верхней планкой.
2. Что-то не пойму твою структуру: _несколько_ строк для информации об _одном_ файле? Может под "строками" ты имел в виду "столбцы"?
3. Расшифруй плз "и т. д. чередование."

Цитировать
Не вижу не одной!
Файлы в кэше могут появиться путем ручного копирования пользователем. И так же могут быть удалены им. Проблема в степени достоверности хранящихся сведений о файлах кэша.

Цитировать
На NTFS проблем не должно быть, а в Win9x/Me — может... нужно смотреть на ограничения FS FAT32
Тоже не пойму: какие возможные проблемы отсутствуют/могут быть в зависимости от FS - т.е. какие случаи ты рассматриваешь?
Сообщить модератору   Записан
DIGGER
Старожил
****

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

Сообщений: 312



« Ответ #25 : 23 февраля 2007, 17:33:16 »

1. Как узнать АБСОЛЮТНО все поля которые нужно хранить в кеше? (У кого? или Где?)
2.0. Индексный файл должен быть текстовым? (Что бы пользователь мог смотреть его и редактировать..., хотя зачем такое пользователю?)
2.1. Если текстовым, то файл должен быть в Unicode. Однозначно.
2.2. По _несколько_ строк на URL: так надёжнее + быстрее перебирать при поиске.

Цитировать
Расшифруй плз "и т. д. чередование."
пПоскольку строк планировалось две, то значит они чередуются. Улыбка  А так всё классически:структура за структурой, если нет записи после структуры знач. конец файла.

Цитировать
Файлы в кэше могут появиться путем ручного копирования пользователем. И так же могут быть удалены им. Проблема в степени достоверности хранящихся сведений о файлах кэша.
И что? Никак не нарушает логику работы кеша. (могу попытатся пояснить, просто много писать Не в себе) А если пользователь вручную принёс файлы, то после добавления в кеш он(пользователь) нажмёт кнопку Переиндексация кеша. И новые файлы добавятся в индексный файл с текущей датой(хотя можно придусмотреть что бы пользователь мог устанавливать дату для вручную принесённых файлов) и своим размером + можно придусмотреть "слияние кешей": что-то вроде: импорт-экспорт.

Цитировать
Тоже не пойму: какие возможные проблемы отсутствуют/могут быть в зависимости от FS - т.е. какие случаи ты рассматриваешь?
Win98/Me используют сейчас в основном на "слабых" машинах, т.е.: мало памяти, ме-е-едленный HDD и т.д.
Кеш маленький у Windows'а + если пользователь активно использует HDD, то и кеш винды постоянно будет очищатся (например: навигация по папкам, просмотр фотографий и т.д.), а в WinXP+NTFS(сжатия) такого нет(хотя может возникать дополнительная нагрузка на проц., но, как правило, это не критично).

Кто мне -1 в "Репутация" поставил? За что? Я уверен, что подобные действия нужно пояснять! (Хотя бы в личку)
Сообщить модератору   Записан
Rick
Администратор
*****

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

Сообщений: 868


WWW
« Ответ #26 : 23 февраля 2007, 21:25:23 »

1. Как узнать АБСОЛЮТНО все поля которые нужно хранить в кеше? (У кого? или Где?)
Пока в процессе обсуждения - так-что можешь не стесняться в предложениях, рамок нет.

Цитировать
2.0. Индексный файл должен быть текстовым? (Что бы пользователь мог смотреть его и редактировать..., хотя зачем такое пользователю?)
Текстовый? Нет, не думаю. Редактировать руками в нем действительно нечего, главное - меньший объем и большая скорость обработки.

Цитировать
А если пользователь вручную принёс файлы, то после добавления в кеш он(пользователь) нажмёт кнопку Переиндексация кеша. И новые файлы добавятся в индексный файл с текущей датой(хотя можно придусмотреть что бы пользователь мог устанавливать дату для вручную принесённых файлов) и своим размером + можно придусмотреть "слияние кешей": что-то вроде: импорт-экспорт.
Твоими бы устами да мед пить. Улыбка

Цитировать
Кто мне -1 в "Репутация" поставил? За что? Я уверен, что подобные действия нужно пояснять! (Хотя бы в личку)
Пока нет возможности узнать. Со временем поставлю мод - будет записывать кто кому и за что.
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #27 : 26 февраля 2007, 13:21:02 »

Что-то затих топик. Предлагаю такой начальный вариант, от которого можно отталкиваться.
Храним в файле записи вида имя хоста - дата последнего доступа, отсортированные по дате в порядке убывания (последние затребованные хосты в начале, давние - в конце). В начале файла хранится текущий размер кэша.
При загрузке НС грузим данные из этого файла в память, создавая связный список, каждый элемент которого имеет вид:
    - ссылка на следующий элемент;
    - дата последнего доступа;
    - имя хоста.
Размер кэша присваиваем переменной CurrentCacheSize. Другой переменной присваиваем ссылку на первый элемент списка.
Действия в реалтайме:
1. Если размер кэша подошел к критическому, удалить папку с самым старым временем последнего доступа:
    - идем по цепочке от начального элемента к конечному и удаляем его;
    - физически удаляем соответствующую папку;
    - уменьшаем соответственно значение переменной CurrentCacheSize.
2. Если папки в кэше не было и мы ее создаем:
    - создаем новый элемент списка, указателю начала списка присваиваем ссылку на этот элемент, дату доступа устанавливаем в текущую системную;
    - физически создаем папку.
3. Папка в кэше есть и мы пишем/читаем оттуда файл:
    - находим элемент по имени хоста последовательным перебором от начала списка;
    - меняем в нем дату последнего доступа на текущую;
    - переносим элемент в начало списка. Для этого достаточно просто изменить три ссылки;
    - в случае необходимости меняем значение переменной CurrentCacheSize.
Указанный список по ходу пьесы периодически сохраняем в файл.
При значительном таймауте в работе программы сбрасываем список на дсик и очищаем память.
« Последнее редактирование: 26 февраля 2007, 14:07:49 от Михаил » Сообщить модератору   Записан
DIGGER
Старожил
****

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

Сообщений: 312



« Ответ #28 : 27 февраля 2007, 00:20:10 »

Михаил, затраты памяти посчитай. И всё станет ясно, о каких затратах идёт речь. + Какой размер файла будет на диске? (Для кеша на 2гига)
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #29 : 27 февраля 2007, 00:57:59 »

Михаил, затраты памяти посчитай. И всё станет ясно, о каких затратах идёт речь. + Какой размер файла будет на диске? (Для кеша на 2гига)
Если имеешь ввиду, что ты их посчитал, то почему не привел?  Непонимаю
Сам прикидываю так: беру свой "пессимистический" вариант кэша - 5500 имен хостов на 1 ГБ кэша. Тогда для кэша на 2 ГБ - 11 000 записей в списке. Каждая запись потянет в среднем примерно на 32(размер ссылки)+8(размер даты)+17(размер имени хоста)=57 байт. Итого затрат RAM при таком раскладе ~57*11000=627 КБ. Затрат на диске будет на 32 байта на запись меньше (не будет ссылки): ~25*11000=275 КБ.
В кэше Дема будут такие цифры: на его 13 ГБ! кэша ~57*8500=484,5 КБ в RAM и ~25*8500= 212,5 КБ на диске.
Данных от других пользователей не поступало.
Как? По-моему, вполне приемлемо.
« Последнее редактирование: 27 февраля 2007, 01:44:37 от Михаил » Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #30 : 27 февраля 2007, 02:28:02 »

Дополнение:
Кстати, есть подозрение, что размер ссылки может быть гораздо меньше 32. Кто может внести ясность?
Сообщить модератору   Записан
DIGGER
Старожил
****

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

Сообщений: 312



« Ответ #31 : 27 февраля 2007, 10:43:55 »

На гиг у меня ~74646, а на 2=149292 (только НЕ хостов, а файлов в папке с кешем)
Перечитал твой пост: ты предлагаеш сохранять дату доступа по хостово, а не по доступу к каждому файлу? не катит. У меня сайты по 30-40 метров и если я запросил один файл из этой кучи, то что? получается что мне нужно всё остальное? бред...
Хотя... если добавить к этой идее "деревовидность", то получтся всё очень хорошо.(то есть: Всё сортируется по хостам, а в каждом хосте по URL-внутренему)
Нужно посчитать затраты памяти...
+ что это за :
Цитировать
32(размер ссылки)+8(размер даты)+17(размер имени хоста)=57 байт
Никакой "статики"!!! Все размеры должны даваться по необходимости. Это повысит нагрузку на проц, НО и сократит потребляемость в памяти + стабильность(а то вдруг отркоем о-очень длинный адресок Улыбка)
+На вскидку: в файл это всё будет проблематично сохранять. (из-за динамики)
вообщем надо автору над этим подумать.

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

P.S. может чего и пропустил в своей логике: на работу пора...  Веселый
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #32 : 27 февраля 2007, 11:04:52 »

DIGGER_KSS
Цитировать
бред...
Непонимаю Как-то нехорошо звучит по отношению к кому бы то ни было. Не находишь?
Цитировать
Никакой "статики"!!! Все размеры должны даваться по необходимости.
Хоть убей не вижу, где мной написано про статику. Все выделяется динамически.
То, что лучше было бы удалять не "похостово" а "пофайлово" - факт. Остается предложить конкретный малозатратный алгоритм. А вот с этим сложнее.
« Последнее редактирование: 27 февраля 2007, 11:55:27 от Михаил » Сообщить модератору   Записан
DIGGER
Старожил
****

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

Сообщений: 312



« Ответ #33 : 27 февраля 2007, 14:33:20 »

Цитировать
Как-то нехорошо звучит по отношению к кому бы то ни было. Не находишь?
Если обидел — прости. Впредь не буду комментировать и высказывать своё отношение к бредовым идеям...  Подмигивающий

Цитировать
32(размер ссылки)+8(размер даты)+17(размер имени хоста)=57 байт
Это не "статика"? 57 КОНСТАНТА!! или нет? Ты предлагаеш выделять динамичести 57 байт, а я против этого. (Вообщем я не про ту статику)
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #34 : 27 февраля 2007, 14:43:04 »

DIGGER_KSS
Цитировать
Если обидел — прости. Впредь не буду комментировать и высказывать своё отношение к
бредовым идеям...
Идея компромиссная. -1 открыто и без обиняков.
Цитировать
Это не "статика"? 57 КОНСТАНТА!! или нет? Ты предлагаеш выделять динамичести 57 байт, а я против этого.
Это не константа.
Я писАл следующее:
Цитировать
Каждая запись потянет в среднем примерно на 32(размер ссылки)+8(размер даты)+17(размер имени хоста)=57 байт.
Читай внимательно. Жирным выделено то, что ты пропустил. Речь велась о приближенной численной оценке расходуемой алгоритмом памяти/диска.

PS Еще вот правила с отрицательным критерием свежести вносят толику беспокойства. Надо б обдумать, что вообще при любой очистке (автоматической или ручной) надо с такими URL делать...
« Последнее редактирование: 27 февраля 2007, 14:51:55 от Михаил » Сообщить модератору   Записан
DIGGER
Старожил
****

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

Сообщений: 312



« Ответ #35 : 27 февраля 2007, 21:04:21 »

Цитировать
Идея компромиссная. -1 открыто и без обиняков.
Ок. (Язык мой — враг мой!  Прикольно)

До выхода следующей версии HC я молчу. (Потому как всё уже сказано)
Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #36 : 08 марта 2007, 17:27:42 »

Если память отводить статически, то достигнем еще меньшего ее расходования (в сравнении с динамическим выделением, обозначенным ранее). Тогда ссылка превратится из абсолютной в относительную (относительно начала выделенного сегмента памяти) и займет 4 байта вместо 32. В итоге расход RAM сократится почти в 2 раза (с ~57 байт на хост до ~29 байт на хост). Единственная незначительная потеря при этом - необходимость заранее резервировать блок памяти, больший на ~5%, для возможного добавления новых записей. В качестве еще одного плюса - уйдем от фрагментации памяти.
« Последнее редактирование: 08 марта 2007, 17:32:01 от Михаил » Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #37 : 09 марта 2007, 02:12:07 »

Вроде созрело приблизительное решение для автоматической очистки не целыми каталогами, а точечно файлами.
Внутри НС предусматриваем ведение переменной CurrentCacheSize (ее значение, кстати. полезно будет выводить в статистике). Хочу заметить, как только мы озабочиваемся удержанием кэша в пределах заданных размеров, нам, видимо, придется отказаться от возможности безболезненно добавлять/удалять файлы в кэше вручную.
Создаем на диске (например, в папке НС) файл Last_Access_Times.dat. Он содержит полные имена (с путями от корневой папки кэша) всех файлов кэша, расположенные в порядке последнего доступа к этим файлам (начиная со старых). С учетом того, что Last_Access_Times.dat потенциально большой, весь его держать в памяти не стоит. В памяти будем оперировать информацией только о N1 самых старых файлах и максимум N2 самых свежих (N1 и N2 надо оговорить сразу при обсуждении алгоритма). При старте НС грузим из Last_Access_Times.dat в RAM первые N1 записей и помещаем их в созданный в статической памяти связный список List1 (он будет содержать имена файлов с самым давним временем последнего доступа) вида: ссылка на следующий элемент, имя файла. Создаем список List2 - структурно похожий, но пока пустой (здесь будем накапливать имена свежих файлов, но в обратной сортировке).
Действия в реалтайме при обращении к файлу в кэше/записи в кэш:
1. если список List1 пустой, пересчитываем файл Last_Access_Times.dat (примерную методику см. ниже), получаем новый List1. List2 очищаем;
2. последовательным перебором проверяем, есть ли запись с именем рассматриваемого файла в List1.
    2.1. если да - переносим эту запись в начало списка List2 (потребуется лишь изменить три-четыре ссылки). Если список List1 стал при этом пустым или Length(List2)>N2, пересчитываем файл Last_Access_Times.dat (примерную методику см. ниже), получаем новый List1. List2 очищаем;
    2.2. если нет, проверяем List2. Если там есть такая запись, переносим ее в начало списка. Для этого также достаточно изменить три ссылки;
3. если было только чтение файла/атрибутов без записи файла в кэш, то ВЫХОД.
4. соответствующим образом меняем значение переменной CurrentCacheSize.
5. Если размер кэша подошел к критическому, удаляем файл с самым старым временем последнего доступа:
    5.1. удаляем 1-й элемент списка List1;
    5.2. физически удаляем соответствующий файл;
    5.3. уменьшаем соответственно значение переменной CurrentCacheSize;
    5.4. если значение CurrentCacheSize все еще не удовлетворяет, выполняем п.1 и возвращаемся к п.5.1.

Пересчет файла Last_Access_Times.dat производится следующим образом. Удаляем в нем первые N1-Length(List1) записей. Удаляем записи, соответствующие записям списка List2. Дописываем в конец записи из списка List2 в обратном порядке. Сохраняем новый Last_Access_Times.dat.
Пересчет помимо указанных выше случаев надо производить при закрытии НС, а также по определенному таймауту.
На мой взгляд, приемлемыми значениями N1 и N2 (максимально допустимый размер списков соответственно List1 и List2) являются 1500 и 6000 записей. Чем они будут больше, тем возможно реже придется делать трудоемкую операцию пересчета, но возрастет расход RAM.
Давайте обсудим...
« Последнее редактирование: 09 марта 2007, 02:17:57 от Михаил » Сообщить модератору   Записан
DenZzz
Модератор
*****

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

Сообщений: 5589



« Ответ #38 : 09 марта 2007, 08:56:45 »

С учетом того, что Last_Access_Times.dat потенциально большой, весь его держать в памяти не стоит. В памяти будем оперировать информацией только о N1 самых старых файлах и максимум N2 самых свежих (N1 и N2 надо оговорить сразу при обсуждении алгоритма).
...
На мой взгляд, приемлемыми значениями N1 и N2 (максимально допустимый размер списков соответственно List1 и List2) являются 1500 и 6000 записей. Чем они будут больше, тем возможно реже придется делать трудоемкую операцию пересчета, но возрастет расход RAM.
Давайте обсудим...

Посчитаем:

1 Гб кэша содержит обычно не менее 100 000 файлов.
1500+6000=7500 записей = 7,5% от общего числа файлов на 1 Гб кэша.
Вероятность, найти в этих списках файл, который уже есть в кэше, - всего 7,5% !
Для 92,5% файлов нам придется лезть в Last_Access_Times.dat, чтобы выяснить размер нужного нам файла и изменить его реквизиты при перезаписи файла!
А как быть с новыми файлами, которых еще нет в кэше? Где их искать и когда?

Таким образом, эффективность держания в памяти только List1 и List2 будет крайне низка!
А держать в памяти все сотни тысяч записей из Last_Access_Times.dat - крайне ресурсоемко!

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

Вряд ли это возможно! Не забывай об "армии" пользователей, которые:
- переносят кэш по частям с работы домой и т.п.
- перед чисткой кэша предпочитают просмотреть вручную удаляемые файлы (в Историке или еще где), чтобы случайно не удалить лишнего
- любят вручную править/удалять/переносить файлы, например, после добавления новых правил в списки HC
и т.д.
« Последнее редактирование: 09 марта 2007, 09:10:21 от DenZzz » Сообщить модератору   Записан
Михаил
Gold beta tester
*****

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

Сообщений: 5513



« Ответ #39 : 09 марта 2007, 11:42:01 »

DenZzz
Цитировать
Вероятность, найти в этих списках файл, который уже есть в кэше, - всего 7,5% !
Для 92,5% файлов нам придется лезть в Last_Access_Times.dat, чтобы выяснить размер нужного нам файла и изменить его реквизиты при перезаписи файла!
А как быть с новыми файлами, которых еще нет в кэше? Где их искать и когда?
Подожди. В Last_Access_Times.dat не хранятся ни размеры, ни реквизиты. Только имена файлов и все. Ты о чем? Зачем нам туда лазить? Что искать? Я недопонял.
Цитировать
Вряд ли это возможно! Не забывай об "армии" пользователей, которые:
- переносят кэш по частям с работы домой и т.п.
- перед чисткой кэша предпочитают просмотреть вручную удаляемые файлы (в Историке или еще где), чтобы случайно не удалить лишнего
- любят вручную править/удалять/переносить файлы, например, после добавления новых правил в списки HC
и т.д.
Посмотреть файлы никто не запрещает. Чтение файла картины не изменит. Перенос кэша целиком с одного компьютера на другой - тоже. Изменит картину удаление/добавление/изменение размера файла. Если мы хотим держать размер кэша в определенных рамках, то какой бы ни был для этого алгоритм, он должен в реальном времени считать текущий размер кэша. Как это делать, если пользователь будет самостоятельно орудовать в кэше? Я не вижу возможности. Мож, кто подскажет, и мы это учтем.
Для слияния кэшей можно сделать мастер. Если кто-то все же не может не менять кэш вручную (хоть мне и непонятно, для каких целей это может быть нужно), пусть после этих действий жмет специальную кнопку в программе и Last_Access_Times.dat будет создаваться с нуля, что займет n-ное количество времени.
« Последнее редактирование: 09 марта 2007, 12:05:17 от Михаил » Сообщить модератору   Записан
Страниц: 1 [2] 3 4 ... 6   Вверх
  Отправить эту тему    Печать  

 
Перейти в: