Кэш и хэш в чем отличие
Кэш, хэш и няш-меш
UPD0 (2016-07-19 23-31): судя по всему, первая половина моей статьи — успешно изобретённый велосипед. Спасибо хабравчанам за ссылку на спецификацию
Статья ценна не более, чем вольное описание уже придуманной технологии.
Предыстория
Недолгое гугление привело на официальный гугловский мануал. Целиком пересказывать его не буду; скорее всего, дело было в том, что браузер прилежно ждал, когда сервер передаст ETags, а ответ сервера затерялся в переполненных триджунглях.
Через пару дней, возвращаясь душным днём из кафе, я придумал рацпредложение, которое решает эту (и несколько других проблем), которое и излагаю в данной статье.
Суть предложения
Найдя в теле веб-страницы подобный тэг, браузер смотрит, есть ли объект с таким хэшем в кэше, и если есть, то не отправлять никаких запросов вообще: и так понятно, что файл — ровно тот, который требуется. Файлы в кэше браузера лучше сразу хранить с именами, соответствующими их хэшам, как это делает тот же git.
Обратная совместимость предлагаемого решения очевидна.
Какие проблемы это решает?
Пресловутая угадайка: актуален ли файл в кэше?
Дилемма: jQuery со своего домена или с CDN?
Владельцам малых сайтов часто приходится выбирать: либо подключать jQuery и/или подобные ей библиотеки с CDN (гугловского, например), или со своего домена.
В первом случае уменьшается время загрузки сайта (в том числе первичной, т.е. при первом заходе посетителя на сайт) за счёт того, что файл с серверов Гугла с большой долей вероятности уже есть в кэше браузера. Но, например, разработчики WordPress придерживаются второго варианта, ставя во главу угла автономность. И в условиях, когда CDN падают, блокируются и т.д., их можно понять.
Теперь от такой проблемы можно будет избавиться навсегда: не всё ли равно, откуда получен файл, если его содержимое — это ровно то, что нужно html-странице, и она это удостоверяет? Можно смело указывать свой домен, и если библиотека есть в кэше (неважно, загруженная с этого сайта, другого «малого» сайта или из какого-нибудь CDN) — она подхватится.
Смешанный HTTPS/HTTP-контент
Одна из причин запрета загрузки HTTP-ресурсов на HTTPS-страницах — возможность подмены HTTP-контента. Теперь это больше не преграда: браузер может получить требуемый контент и сверить его хэш с хэшем, переданным по HTTP. Отмена запрета на смешанный контент (при наличии и совпадении хэша) позволит ускорить распространение HTTPS.
Косвенное определение истории по времени загрузки статики
На что это не влияет?
Идеология
Как обычно (математик я, что уж тут поделать) сформулируем аксиомы, которые вкладываются в предложение:
Перспективы
Обещанный няш-меш
Зная хэш требуемого вспомогательно файла, можно почти смело запрашивать его у кого угодно; основная опасность: если опрашиваемый узел действительно имеет требуемый файл, то он знает его содержимое и, скорее всего, как минимум один URI-адрес, по которому требуемый файл может (или мог) быть получен. Имеем два варианта использования предлагаемой технологии с учётом этой угрозы с целью плавного подхода к няш-меш сети:
Доверенные устройства
Например, в офисе работают программисты, ЭВМ которых объединены в локальную сеть. Программист Вася приходит рано утром, открывает гитхаб и получает в кэш стили от нового дизайна, который выкатили ночью (у нас — ночь, там — день). Когда в офис приходит программист Петя и тоже загружает html-код гитхабовской странички, его ЭВМ спрашивает у всех ЭВМ в сети: «А нет ли у вас файла с таким-то хэшем?» «Лови!» — отвечает Васина ЭВМ, экономя тем самым трафик.
Потом наступает перерыв, Вася и Петя лезут смотреть котиков и пересылают фотографии друг другу. Но каждый котик скачивается через канал офиса только один раз.
Анонимный разделяемый кэш
Дальнейший переход к няш-мешу
Фотография в соцсети может быть представлена как блоб, содержаший хэш и адрес собственно изображения (возможно, в нескольких различных размерах), а также список комментариев и лайков. Этот блоб тоже можно рассматривать как вспомогательный файл, кэшировать и передавать друг другу.
Более того, альбом фотографий тоже легко превращается в блоб: список хэшей изображений + список хэшей блобов-фотографий (первое нужно, чтобы при добавлении лайка/комментария показывать фотографии сразу, а метаинформацию — по мере её получения).
Останется только реализовать электронную подпись и поля вида «замещает блоб такой-то» — и готова няш-меш-социалочка.
Компактизация хэша
Поведение при несовпадении
Возможна ситуация, когда хэш полученного файла не совпал с требуемым. В таком случае разумно бы было предусмотреть мета-тэги, указывающие браузеру, следует ли такой файл использовать (по умолчанию — нет) и следует ли сообщить об инциденте серверу (по умолчанию — нет).
Файлы-альтернативы
В некоторых случаях можно использовать любой из нескольких файлов с разными хэшами. Например, на сайте используется минифицированная jQuery, но если в кэше браузера есть неминифицированная — что мешает использовать её?
Превентивное кэширование
Многие устройства работают в двух режимах: когда интернет условно-безлимитен (например, мобильный телефон в вай-фай сети) и когда интернет ограничен (лимит по трафику или узкий канал). Браузер или расширение к нему может, пользуясь безлимитным подключением, заранее скачивать популярные библиотеки (наподобие jQuery и плагинов к ней), также по мере необходимости их обновлять. Это ли не мечта многих, чтобы jQuery была включена в браузер?
Заключение
Выдвигаемое рацпредложение актуально, так как борьба за оптимизацию загрузки сайтов идёт полным ходом. Более всего выиграют малые и средние сайты за счёт разделяемых библиотек (и, может быть, некоторых часто используемых изображений) в кэше. Уменьшится потребление трафика мобильными устройствами, что важно с учётом ограниченной пропускной способности каналов сотового интернета. Крупные сайты также могут уменьшить нагрузку на свои серверы в случае, если будут внедрены mesh-технологии.
Таким образом, поддержка предлагаемой технологии выгодна и вебмастерам, чьи сайты будут грузиться быстрее, и производителям браузеров, которые тоже будут быстрее отображать страницы, и провайдерам, у которых уменьшится потребление полосы (пусть и не столь значительно, но от провайдеров активных действий и не требуется).
Хеш+кэш: оптимизация «потоковой» обработки
Что делать, если в базу хочется записать массу «фактов» много большего объема, чем она способна выдержать? Сначала, конечно, приводим данные к более экономичной нормальной форме и получаем «словари», в которые будем писать однократно. Но как это делать наиболее эффективно?
Именно с таким вопросом мы столкнулись при разработке мониторинга и анализа логов серверов PostgreSQL, когда остальные способы оптимизации записи в БД оказались исчерпаны.
Сразу оговоримся, что наши коллекторы работают под управлением Node.js, поэтому с процессорными регистрами и кэшами мы никак не взаимодействуем. А вариант использования «стораджей» или внешних кэширующих сервисов/БД дает слишком большие задержки при входящих потоках в несколько сотен Mbps.
Поэтому мы стараемся кэшировать все в RAM, конкретно — в памяти JavaScript-процесса. Про то, как эффективнее это организовать, и пойдет речь дальше.
Кэширование наличия
Наша основная задача — сделать так, чтобы в БД попал по возможности единственный экземпляр какого-либо объекта. Такими у нас выступают многократно повторяющиеся оригинальные тексты SQL-запросов, шаблоны планов их выполнения, узлов этих планов — короче, какие-то текстовые блоки.
То есть само оригинальное текстовое значение нам хранить не требуется (а иногда оно занимает десятки килобайт) — достаточно всего лишь самого факта наличия соответствующего хеша в словаре.
Словарь ключей
Но вполне очевидно, что мы тут явно храним лишнее — то самое значение ключа, которое никому не нужно. А что если его — вообще не хранить? Так и появился объект Set.
Set с тем же содержимым — 2632 байта:
То есть Set работает быстрее и при этом занимает в 2.5 раза меньше памяти — победитель очевиден.
Оптимизируем хранение UUID-ключей
Вообще, в природе распределенных систем UUID-ключи достаточно распространены — у нас в СБИСе они, как минимум, применяются для идентификации документов и регламентов в электронном документообороте, персон в обмене сообщениями,…
Давайте теперь еще раз внимательно посмотрим на картинку выше — каждый UUID-ключ, хранимый в hex-представлении, «стоит» нам 56 байт памяти. Но у нас их — сотни тысяч, поэтому резонно спросить: «А меньше — можно?»
Для начала вспомним, что UUID — это 16-байтовый идентификатор. По сути, кусок бинарных данных. А для передачи по email, например, двоичные данные кодируются в base64 — попробуем его применить:
Уже по 48 байт — лучше, но неидеально. Давайте попробуем перевести шестнадцатиричное представление прямо в строку:
Вместо 56 байт на каждый ключ — 40 байт, экономия почти 30%!
Master, worker — где хранить словари?
Учитывая, что словарные данные от воркеров достаточно сильно пересекаются, мы сделали хранение словарей и запись их в БД в мастер-процессе, а передачу данных от воркеров через механизм IPC-сообщений.
Однако существенная доля времени мастера тратилась на channel.onread — то есть на обработку получения пакетов со «словарной» информацией от дочерних процессов:
Двойной Set-барьер от записи
Теперь на секунду задумаемся — воркеры шлют и шлют мастеру одни и те же словарные данные (в основном — это шаблоны планов и повторяющиеся тела запросов), он их в поте лица парсит и… ничего не делает, потому что они в БД уже были отправлены раньше!
Собственно, что и было сделано, и сократило втрое прямые издержки на обслуживание канала обмена:
Но ведь теперь воркеры делают вроде как больше работы — хранят словари и фильтруют по ним? Или нет. На самом деле, работать они стали существенно меньше, поскольку сама передача больших объемов (даже по IPC!) — это не дешево.
Приятный бонус
Поскольку мастер теперь стал принимать гораздо меньший объем информации, то и памяти под эти контейнеры стал выделять гораздо меньше — а, значит, затраты времени на работу Garbage Collector’а сильно снизились, что положительно повлияло на latency системы в целом.
Ускоряем вычисление хешей
В нашей архитектуре весь поток логов с одного сервера PostgreSQL обрабатывает один воркер.
То есть один сервер — это одна задача на воркере. При этом загрузка воркеров балансируется назначением задач-серверов так чтобы потребление CPU воркерами всех коллекторов было примерно одинаковым. Этим занимается отдельный сервис диспетчера.
«В среднем» каждый воркер обрабатывает несколько десятков задач, которые дают примерно одинаковую суммарную нагрузку. Однако, есть сервера, которые по количеству записей в логе значительно превосходят остальные. И даже в том случае, если диспетчер оставляет эту задачу единственной на воркере, его загрузка сильно выше остальных:
Сняли CPU-профайл этого воркера:
На верхних строках — вычисление MD5-хешей. А их действительно вычисляется огромное количество — для всего потока входящих объектов.
xxHash
Как оптимизировать эту часть, если не считать эти хеши мы не можем?
Решили попробовать другую хеш-функцию — xxHash, реализующую Extremely fast non-cryptographic hash algorithm. И модуль для Node.js — xxhash-addon, который использует свежую версию библиотеки xxHash 0.7.3 с новым алгоритмом XXH3.
Проверим, прогнав каждый вариант на наборе строк разной длины:
Как и ожидалось, xxhash3 оказался намного быстрее MD5!
Осталось проверить на стойкость к коллизиям. Секции таблиц словарей у нас создаются новые на каждый день, поэтому за рамками суток мы спокойно можем допустить пересечение хешей.
Но на всякий случай проверили с запасом на интервале в три дня — ни одной коллизии, что нас более чем устраивает.
Подмена хешей
Но просто взять и поменять в таблицах-словарях старые UUID-поля на новый хеш мы не можем — ведь и база, и существующий frontend ждут, что объекты продолжат идентифицироваться по UUID.
Поэтому добавим в коллекторе еще один кэш — для уже посчитанных MD5. Теперь это будет Map, в котором ключи — xxhash3, значения — MD5. Для одинаковых строк мы не пересчитываем заново «дорогой» MD5, а берем его из кэша:
Снимаем профайл — доля времени вычисления хешей заметно снизилась, ура!
Так что теперь мы считаем xxhash3, затем проверяем кэш MD5 и получаем искомый MD5, а затем проверяем кэш словаря — если там этого md5 нет, то отправляем на запись в БД.
Что-то слишком много проверок… Зачем проверять кэш словаря, если уже проверили кэш MD5? Выходит, все кэши словарей теперь не нужны и достаточно иметь всего один кэш — для MD5, с которым и будут производиться все основные операции:
В итоге, мы заменили проверку в нескольких кэшах «объектных» словарей одним кэшем MD5, а ресурсоемкую операцию расчета MD5-хеша выполняем только для новых записей, используя для входящего потока гораздо более эффективный xxhash.
Спасибо Kilor за помощь в подготовке статьи.
Чудеса хеширования
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, защиту файлов и даже обнаружение зловредного ПО. Как они работают и где применяются?
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, проверку целостности данных, защиту файлов и даже обнаружение зловредного ПО. Существует масса алгоритмов хеширования, отличающихся криптостойкостью, сложностью, разрядностью и другими свойствами. Считается, что идея хеширования принадлежит сотруднику IBM, появилась около 50 лет назад и с тех пор не претерпела принципиальных изменений. Зато в наши дни хеширование обрело массу новых свойств и используется в очень многих областях информационных технологий.
Что такое хеш?
Если коротко, то криптографическая хеш-функция, чаще называемая просто хешем, — это математический алгоритм, преобразовывающий произвольный массив данных в состоящую из букв и цифр строку фиксированной длины. Причем при условии использования того же типа хеша длина эта будет оставаться неизменной, вне зависимости от объема вводных данных. Криптостойкой хеш-функция может быть только в том случае, если выполняются главные требования: стойкость к восстановлению хешируемых данных и стойкость к коллизиям, то есть образованию из двух разных массивов данных двух одинаковых значений хеша. Интересно, что под данные требования формально не подпадает ни один из существующих алгоритмов, поскольку нахождение обратного хешу значения — вопрос лишь вычислительных мощностей. По факту же в случае с некоторыми особо продвинутыми алгоритмами этот процесс может занимать чудовищно много времени.
Как работает хеш?
Например, мое имя — Brian — после преобразования хеш-функцией SHA-1 (одной из самых распространенных наряду с MD5 и SHA-2) при помощи онлайн-генератора будет выглядеть так: 75c450c3f963befb912ee79f0b63e563652780f0. Как вам скажет, наверное, любой другой Брайан, данное имя нередко пишут с ошибкой, что в итоге превращает его в слово brain (мозг). Это настолько частая опечатка, что однажды я даже получил настоящие водительские права, на которых вместо моего имени красовалось Brain Donohue. Впрочем, это уже другая история. Так вот, если снова воспользоваться алгоритмом SHA-1, то слово Brain трансформируется в строку 97fb724268c2de1e6432d3816239463a6aaf8450. Как видите, результаты значительно отличаются друг от друга, даже несмотря на то, что разница между моим именем и названием органа центральной нервной системы заключается лишь в последовательности написания двух гласных. Более того, если я преобразую тем же алгоритмом собственное имя, но написанное уже со строчной буквы, то результат все равно не будет иметь ничего общего с двумя предыдущими: 760e7dab2836853c63805033e514668301fa9c47.
Впрочем, кое-что общее у них все же есть: каждая строка имеет длину ровно 40 символов. Казалось бы, ничего удивительного, ведь все введенные мною слова также имели одинаковую длину — 5 букв. Однако если вы захешируете весь предыдущий абзац целиком, то все равно получите последовательность, состоящую ровно из 40 символов: c5e7346089419bb4ab47aaa61ef3755d122826e2. То есть 1128 символов, включая пробелы, были ужаты до строки той же длины, что и пятибуквенное слово. То же самое произойдет даже с полным собранием сочинений Уильяма Шекспира: на выходе вы получите строку из 40 букв и цифр. При всем этом не может существовать двух разных массивов данных, которые преобразовывались бы в одинаковый хеш.
Вот как это выглядит, если изобразить все вышесказанное в виде схемы:
Для чего используется хеш?
Отличный вопрос. Однако ответ не так прост, поскольку криптохеши используются для огромного количества вещей.
Для нас с вами, простых пользователей, наиболее распространенная область применения хеширования — хранение паролей. К примеру, если вы забыли пароль к какому-либо онлайн-сервису, скорее всего, придется воспользоваться функцией восстановления пароля. В этом случае вы, впрочем, не получите свой старый пароль, поскольку онлайн-сервис на самом деле не хранит пользовательские пароли в виде обычного текста. Вместо этого он хранит их в виде хеш-значений. То есть даже сам сервис не может знать, как в действительности выглядит ваш пароль. Исключение составляют только те случаи, когда пароль очень прост и его хеш-значение широко известно в кругах взломщиков. Таким образом, если вы, воспользовавшись функцией восстановления, вдруг получили старый пароль в открытом виде, то можете быть уверены: используемый вами сервис не хеширует пользовательские пароли, что очень плохо.
Вы даже можете провести простой эксперимент: попробуйте при помощи специального сайта произвести преобразование какого-нибудь простого пароля вроде «123456» или «password» из их хеш-значений (созданных алгоритмом MD5) обратно в текст. Вероятность того, что в базе хешей найдутся данные о введенных вами простых паролях, очень высока. В моем случае хеши слов «brain» (8b373710bcf876edd91f281e50ed58ab) и «Brian» (4d236810821e8e83a025f2a83ea31820) успешно распознались, а вот хеш предыдущего абзаца — нет. Отличный пример, как раз для тех, кто все еще использует простые пароли.
Еще один пример, покруче. Не так давно по тематическим сайтам прокатилась новость о том, что популярный облачный сервис Dropbox заблокировал одного из своих пользователей за распространение контента, защищенного авторскими правами. Герой истории тут же написал об этом в твиттере, запустив волну негодования среди пользователей сервиса, ринувшихся обвинять Dropbox в том, что он якобы позволяет себе просматривать содержимое клиентских аккаунтов, хотя не имеет права этого делать.
Впрочем, необходимости в этом все равно не было. Дело в том, что владелец защищенного копирайтом контента имел на руках хеш-коды определенных аудио- и видеофайлов, запрещенных к распространению, и занес их в список блокируемых хешей. Когда пользователь предпринял попытку незаконно распространить некий контент, автоматические сканеры Dropbox засекли файлы, чьи хеши оказались в пресловутом списке, и заблокировали возможность их распространения.
Где еще можно использовать хеш-функции помимо систем хранения паролей и защиты медиафайлов? На самом деле задач, где используется хеширование, гораздо больше, чем я знаю и тем более могу описать в одной статье. Однако есть одна особенная область применения хешей, особо близкая нам как сотрудникам «Лаборатории Касперского»: хеширование широко используется для детектирования зловредных программ защитным ПО, в том числе и тем, что выпускается нашей компанией.
Как при помощи хеша ловить вирусы?
Примерно так же, как звукозаписывающие лейблы и кинопрокатные компании защищают свой контент, сообщество создает списки зловредов (многие из них доступны публично), а точнее, списки их хешей. Причем это может быть хеш не всего зловреда целиком, а лишь какого-либо его специфического и хорошо узнаваемого компонента. С одной стороны, это позволяет пользователю, обнаружившему подозрительный файл, тут же внести его хеш-код в одну из подобных открытых баз данных и проверить, не является ли файл вредоносным. С другой — то же самое может сделать и антивирусная программа, чей «движок» использует данный метод детектирования наряду с другими, более сложными.
Криптографические хеш-функции также могут использоваться для защиты от фальсификации передаваемой информации. Иными словами, вы можете удостовериться в том, что файл по пути куда-либо не претерпел никаких изменений, сравнив его хеши, снятые непосредственно до отправки и сразу после получения. Если данные были изменены даже всего на 1 байт, хеш-коды будут отличаться, как мы уже убедились в самом начале статьи. Недостаток такого подхода лишь в том, что криптографическое хеширование требует больше вычислительных мощностей или времени на вычисление, чем алгоритмы с отсутствием криптостойкости. Зато они в разы надежнее.
Кстати, в повседневной жизни мы, сами того не подозревая, иногда пользуемся простейшими хешами. Например, представьте, что вы совершаете переезд и упаковали все вещи по коробкам и ящикам. Погрузив их в грузовик, вы фиксируете количество багажных мест (то есть, по сути, количество коробок) и запоминаете это значение. По окончании выгрузки на новом месте, вместо того чтобы проверять наличие каждой коробки по списку, достаточно будет просто пересчитать их и сравнить получившееся значение с тем, что вы запомнили раньше. Если значения совпали, значит, ни одна коробка не потерялась.
Русские Блоги
Хеш-хэш-хэш Различия и подключение структуры пружинного кэша
Кэш зимующего уровня
Ключ кэша первого класса является идентификатором (первичный ключ).
При выполнении нагрузки / Get / List / ITERATOR / SOVE / UPDATE / BAFEORUPDATE, полученный объект объекта размещен в кэш первого уровня (поддерживается только кеш объекта объекта, а кэш атрибута не поддерживается), а затем тот же сеанс Диапазон Hibernate не будет переходить в базу данных при выполнении запросов (исключая список) запросов (исключая список).
Когда программа сохраняется или изменяет объект, он не будет немедленно синхронизирован с базой данных, но сохраняется в кэше первого уровня, только программа отображает метод SESSE SHICK () или CLACK (), также будет обновляться в базе данных, которая также будет обновляться Может уменьшить взаимодействие базы данных, улучшенную производительность доступа базы данных.
Метод очистки кэша первого класса:
Сернат вторичный кэш
Вторичный кэш требует реализации кеша, таких как EHCACHE, и указать, какие классы объектов используют аннотацию @Cache, чтобы включить вторичный кэш, и указать политику кэша (вообще OMY_ONLY).
Политика кэша Hibernate (уровень изоляции):
Механизм кэширования пружины
Весенний кеш требует реализации кеша (например, ehcache).
Для получения кэша поддержки, пружина приведет его к значению после того, как он призван, чтобы убедиться, что в следующий раз может использоваться тот же параметр, чтобы получить результат непосредственно из кэша без необходимости снова выполнять метод.
Ключ кэширования генерируется KeyGenerator, а его стратегия генерации по умолчанию выглядит следующим образом:
Пользовательское стратегия генерации ключей требуется в реальном использовании, например
Сравнение среднего вторичного кеша и весеннего кэша
По сравнению со входом второго уровня сессионного заседательного капитала в SessionFactory SessionFactory, пружинный кэш имеет более высокий уровень, а пружинный кеш может быть кэширован на уровне компонента контроллера или бизнес-логике, так что нет необходимости повторять основной компонент DAO (например, в режиме реализации Hibernate).
Интеллектуальная рекомендация
Частота амплитуды FFT и характеристики фазовой частоты
Подробное описание построения среды FLEX-BlazeDS-Java
Один. вести Многие люди задавали некоторые вопросы о создании проекта Flex + LCDS (FDS) в сообщениях и группах. Из-за операции ее трудно четко объяснить, поэтому я написал простой учебник (я обещал эт.
PhoneURLConnectGEt
package com.example.phonehttp; import android.os.Bundle; import android.os.Handler; import android.app.Activity; import android.widget.ScrollView; import android.widget.TextView; public class MainActi.