Система кэширования

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

Синтез данных – у меня поступает какой-то запрос, я получаю ответ. Если это пассивная сущность, например ЖД. Запрос – адрес блока, ответ – содержимое блока. Если интернет: запрос – URL, ответ – страница по URL. Не суть важно, как ответы генерируются, мне нужно просто взять и отдать.

Может ответ генерироваться на лету, например СУБД «дай поле 422». Для меня это неважно, я лишь получаю ответ на каждый новый запрос.

НО есть одно важное свойство: пары запрос-ответ неизменны. На каждый запрос всегда существует ответ, и только один ответ, неизменный. Всегда на один и тот же запрос даётся один и тот же ответ.

Всегда есть потребитель – нечто, что генерируется запросы и получает ответы. Он генерирует запросы, когда хочет и хочет получить ответы из набора данных.

Запрос – имя книги, ответ содержимое книги.

Потребитель

Потребитель

Т

p

Кэш

ответ

запрос

Набор данных

Кэш-память

Синтез данных на основе запросов

Набор данных

Синтез данных на основе запросов

ответ

запрос

Также есть важные параметры: время исполнения запроса и вероятность повторения запроса (p). Если мы можем посчитать время исполнения запроса и сделать статистику запросов, и вероятность, а ещё лучше составить формулу. Если у нас есть эти характеристики, то система кэширования нужна, если нет, то незачем тыкаться.

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

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

Природу на кривой козе не объедешь.

От системы кэширования не стоит ждать чудес. Не бывает вероятности 0,99. Аппаратный кэш делают на процессорах, на жёстких дисках, у браузеров. В некоторых, очень исключительных задачах либо слишком T разбегаются, либо я знаю формулу генерации запросов.

Почему включают аппаратный кэш процессора?

Когда процессор считывает команды, он их считывает большими блоками с запасом вперед и сразу размещает их в кэше, потому что команды выполняются подряд, и только goto прыгает. Если у нас есть переменная цикла, то у нас её использование будет 10000 раз, первый раз мы считаем её из памяти, а затем из кэша.

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

Нужен кэщ или не нужен, мы определяем циферками.

Т реальное = p*tпопадания в кэш + (1-р)(tпопаданиявкэш + Тбезкэширования)

1. Как рассчитать вероятность попадания в кэш?
Нужно понимать, какие идут запросы и какой объем кэш-памяти у нас есть. Вероятность строится на формуле запроса и объеме кэш-памяти.
Если объем кэш памяти почти такой же как и основной, то вероятность стремится к единице, НО стоимость намного дороже
Чем больше объем, тем больше вероятность попадания в кэш, тем больше стоимость
Объем кэш-памяти необходимо выбирать таким образом, чтобы не терять производительность и не переплачивать за нее

2. Как её повысить?

Memtest 86+

Д/з протестировать ноут утилитой memtest, которая проверяет микросхемы, также выдает скорость работы нашей ОЗУ и скорость работы кэшей всех уровней

Производители процессоров постоянно тестируют на процессорах разные программы, обкатывают этот объём кэш-памяти, и если будет её больше и не будет давать производительность, то её уберут, потому что смысл платить больше за одну и ту же производительность?

Для некоторых приложений кэш памяти слишком мало, и приложение не может реализоваться полностью. Как решить эти проблемы?

1. Купить процессор с большей кэш-памятью

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

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

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

Также можно изменить структуры данных.

Подсчёт попадания в кэш производить только экспериментом!

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

Можно поменять структуру данных, где видеопоток – это один большой файл, где есть данные которые читаются и пишутся. У меня эффективная структура данных и я записываю на диск со скоростью 100 Мбайт/с. Я могут записывать данные с множества камер.

Как повысить алгоритмы?

1. Локализация во времени

2. Локализация в пространстве

Это направления, над которыми нужно подумать.

Пример: у нас есть 100 матриц, нам нужно сделать над ними множество действий. Я могу запрограммировать, как 4 цикла, каждый из которых содержит 100 матриц (цикл поворота, цикл умножения на константу и т.д.)

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

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

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

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

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

Пример с одноклассниками.

1,5 млрд фотографий в одном холодильнике

Лаба 5

Есть две программы. Каждая из них наследуется от JFrame и реализует интерфейс Runnable. При нажатии на клавишу идет notify на читатель. Если читатель данные не получил, то идет wait на писателя.

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

Классический кэш на чтение (храним информацию, чтобы она у нас была)

1. Как можно дольше хранить ответ в кэше

Записываем блок данных на ЖД (идет запрос на систему кэширования, если его ещё в кэше нет, то надо сохранить, то есть вначале я ищу в кэше есть ли этот блок. Если такой блок есть, то я его перезаписываю). Перезапись – скоростная операция.

Если данных внутри кэша нет, то записываем.

После того, как устройство выполнило запись, оно даёт подтверждение.

Если у нас при записи кэш работает в параллель, то при прохождении запроса, он идет на сохранение, параллельно с этим происходит поиск (есть ли такой блок данных внутри кэша), если есть, то записываем сверху, если нет, то записываем, как новый блок.

В общем случае,, тогда получится T+T+T.

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

p – вероятность попадания в кэш

При записи в кэш, вероятность становится выше.

если мы не попали в кэш

если попали в кэш

Мы рассмотрели кэширование по записи, кэширование по чтению

Как можно улучшить эти системы кэширования?

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

Медотика №1: кэш с отложенной записью

Схема та же самая: потребитель, кэш, получатель. Потребитель сгенерировал запрос на запись, и он заходит в систем у кэширования, она говорит «Выполнено», без малейшего замедления и делает t^s. Если t^s показывает, что данные есть, то ОК, а если показывает, что нету, то потом идет запись на диск.

А что если я даю запросы на запись чаще, чем система кэширования может с ними справляться?
Система кэширования тогда сохранит их в память, и потом ОК

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

Имеют название «грязный кэш» (в кэше новые значение, а в системе старые)

Кэш со сквозной записью на чтение – «чистый кэш»

Грязный кэш может не изменять свое состояние часами.

Мы говорим об одной порции данных

3 типа кэшей

1. Кэш на чтение
Читаем из кэша быстро, потому что данные локализованы во времени, за счёт этого повышается вероятность (чтение-чтение-чтение)
Если одно чтение в начале, а потом в конце, то данные могут быть перетёрты

2. Кэш со сквозной записью
Повышает быстродействие за счёт опять-таки локализации по времени (чтение-запись, чтение-запись)

3. Кэш с отложенной записью
Повышает быстродействие за счёт локализации во времени

Оперативка

У меня есть устройство, которое мне выдает данные. Например: оперативная память. Данные локализованы в пространстве (рядом в памяти). Когда выполняю запрос, то идет t^s, потом обращение к памяти Т, потом запись данных в кэш t^w, теперь я могу черпать из кэша, как t^s. Я получил 4 блока данных по 4 байта на шине 16 байт, и считал за Т их на халяву. Следующие блоки я считаю за t^s.

Хард

Запрос-Поиск в кэше-потом головка перемещается на нужный цилиндр и идет ожидание, пока сектор подъедет под нужную позицию

Получаем почти на халяву, поскольку tсектора микроскопическое

25.04.2013

Виртуальная память – тоже кэш. Файл подкачки – медленная большая память. ОЗУ – быстрая маленькая память. ЦП – потребитель

Есть потребитель, файлы (быстрое и маленькое устройство). Когда объём файлов разрастается до больших размеров, вводят третий компонент – накопитель на магнитных лентах для хранения ненужных данных. Мы кэшируем магнитные ленты жёсткими дисками.

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

ЦП – к1- к2 – к3 – ОЗУ – кэш контр. – SSD диск – механический диск – сервер – RAID-система – магнитная лента. Технология кэширования пронизывает всю информационную систему и имеет десяток уровней

Методики (каким образом всё рассчитать)

Необходимо обладать справочной информацией о стоимости и т.д.

Мы можем решить, если знаем стоимость железа и объемы информации

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

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

OpenStreetMap

Майкрософт сбрасывает страницы в swap, если они не использовались. И это иногда даёт проблемы, например при чтении фото для отправки на печать, вытесняются нужные страницы и 35 минут происходит печать. Есть API-функции, которые позволяют заблокировать страницы и не отдавать их для устранения проблемы пробуксовки в кэше.

Не лезь сюда, дура, я сам знаю, когда страницы выгружать

Вот тут нос, вот тут хвост, мне нужно 10 секунд, чтобы подвинуть головку

Стандартный драйвер NTFS позволяет узнать номер блока на диске, где хранится файл.

Дата добавления: 2014-01-06