Уникальные идентификаторы для контента

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

• использовать данные генератора случайных чисел (не удобно так как не возможно четко контролировать результат);
• использовать псевдослучайные значения, например время, процесс/поток с последующим преобразованием в символьное имя;
• символьное имя очень полезно - так как позволяет лучше при отладке отличать идентификаторы (числа в любом виде хуже отображают отличия);
  

, а можно учитывать специфику:

• имена должны поддерживаться файловой системой(запрет на использование спец символов);
• максимально короткие эффективные имена(снижение затрат памяти), использование всего пространства допустимых символов,
• близкие по времени создания и исходному значению имена должны быть максимально случайны по результату - то есть использовать максимально эффективный хеш-функцию - обычно достигается использованием хеш значений от псевдослучайных факторов времени создания, процесса/потока и идентификатора хранилища;
• решение противоречивой в общем-то задачи:
  • максимального разброса имени контента для сохранения;
    
  • и возможности по имени определить максимально быстро наиболее вероятное хранилище в распределенной системе можно использовать 2 имени - внутреннее и внешнее;
    
  • внутреннее должно быть максимально эффективно дробить множество доступных вариантов размещения в локальной системе с разбиением на подкатологи с минимальной вероятностью превышения пределов на одновременное количество вложенных каталогов. Это ограничение возникает как из-за временных затрат при работе с большими каталогами, вытекающее иногда в невозможность добавления данных в каталог, и удобства конечного владельца системы, хоть и редко, но удобнее ходить по маленьким каталогам. Также при максимальном разбросе можно разместить часть каталогов на другом разделе и реализовать дешёвое подобие RAID.
  • внешнее - не противоречить правилам для протокола доступа, например не содержать спец символов специфичных для http и html разметки. Позволять легко определить максимально вероятное место расположения в распределенной системе для быстрого выявления не корректно отвечающей части, также при дублировании на другие ресурсы - можно легко удалить данные не специфичные узлу при окончании ресурсов.
    

Очень желательно, чтобы в внутреннем имени присутствовали хеш функция от размера данных (можно просто выделение остатка от деления на какое-то число с получением base64 + как подкаталог base64 от полного размера) и его контента (для снижение количества коллизий лучше сразу два хеш значения от контента). В результате можно быстро найти подобный контент найдя подобную запись в списке преобразований внутреннее имя <-> внешнее имя или, что должно работать гораздо быстрее при большом количестве разнообразного контента, присутствия такого каталога на диске. В дальнейшем можно проверить его содержимого на совпадение с добавляемыми данными. Как результат мы не будем забивать хранилище дубликатами и при желании сможем сообщать, что пользователь пытается снизить энтропию вселенной.

Маленькие выводы по кэшированию

Или временное завершение этой темы...

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

Пример архитектуры кэширования(Caching Architecture)

Общую структуру кэширования и получения контента можно представить в таком виде:

• Красным цветом отображены наиболее критичные части без которых система не может функционировать в нормальном состоянии.

• Синим цветом соответственно представлены все части отвечающие за стабильное(нормальное) состояние сервиса.
• Зеленым цветом - наиболее производительный вариант работы.

Каждый овал может представлять как отдельный сервер, так и несколько овалов может быть размещено на одном сервере, кроме вариантов дублирования веток обработки.

Контент любого сервиса можно разделить на 3 составляющие: статический контент, медиа контент и динамический контент.

Статический контент

Статический контент - изменяется редко, и создается разработчиками ресурса и изменяется только при смене версии ресурса. И как следствие его желательно отдавать легковесным сервером с максимальной производительностью и поддержкой системных вызовов(writev, sendfile). Для запросов на эти файлы вебсервер должен выдавать последнюю дату изменения, при последующих запросах сервер выдает Not Changed.

Медиафайлы

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

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

Методы кэширования: при приходе запроса на получение файла без заголовков(HTTP_IF_MODIFIED_SINCE) - выдать файл с указанием времени создания(Last-Modified) для локального файла или указания даты формирования ответа для файла полученного с другого зеркала, и указания для дополнительных заголовков (Cache-Control: max-age=28800). При приходе заголовка (HTTP_IF_MODIFIED_SINCE), если файл с того времени не обновился выдается что контент не изменился(HTTP/1.x 304 Not Modified). Это позволяет дать возможность закешировать файл на месяц и более - причем первый месяц браузер не будет делать никаких запросов к серверу. Желательно иметь одно запасное синхронизируемое зеркало, чтобы при проблемах с основным на него можно было перевести запросы.

Динамические страницы

Запрос поступает на frontend сервер, для всех запросов которые могут попасть под кэшируемость, который запрашивает этот файл с Memcached. Если файл там присутствует, то он возвращается с указанием, что его можно в течении 15 секунд не запрашивать - это блокирует повторных запрос от браузера на это контент на 15 секунд (Cache-Control: max-age=15). Если контент в кэше отсутствует, то выполняется запрос к backend, который повторно запрашивает контент от кеша, так как исходный url может не совпадать с результирующим url идущим на обработку. При отсутствии данных в кеше или не кэшируемости запроса запрос перенаправляется в SlaveDb. Возвращенный от туда запрос при возможности кэширования сохраняется в кэше с указанием времени кэширования определяемого для этого url, для примера: 30 секунд главная страница, 90 - страницы второго уровня. В ответе для кэшируемых станиц указывается в значении max-age тоже время, что указывалось для времени хранения. Как следствие мы получаем, что все станицы кэшироватся в браузере пользователя первым подавшим запрос на полное время, все последующие до окончания времени кэширования на 15 секунд.

Вторая ветвь(зеленая) нужна для снижения нагрузки на slave, так как на всех slave должен быть одинаковый контент, то при разнесении запросов на несколько сервером мы должны получить ~2 увеличение скорости обработки. Memcached - один, так как при использовании 2 экземпляров для каждого slave приведет к дублированию контента на каждом.

Пример кода

function exitIfNotModifiedSince($last_modified) {
    if(@array_key_exists("HTTP_IF_MODIFIED_SINCE",$_SERVER)) {
            $if_modified_since=@strtotime(@preg_replace('/;.*$/','',$_SERVER["HTTP_IF_MODIFIED_SINCE"]));
            if($if_modified_since >= $last_modified) {                                       
                    header("HTTP/1.x 304 Not Modified");                                     
                    header("Last-Modified: ".date("D, j M Y G:i:s T", $last_modified));      
                    exit();                                                                  
             }                                                                               
    }                                                                                        
}                                                                                                


function dump_foto_content($photo) {
    exitIfNotModifiedSince(strtotime("now")- 100000);
    // send the right headers
    header("Content-Type: ".$photo["mime"]);
    header("Content-Length: ".strlen($photo["photo_data"]));
    header("Last-Modified: ".date("D, j M Y G:i:s T"));
    header("Cache-Control: max-age=28800");     
    echo $photo["photo_data"];                  
    exit;
}

P.S.: Для разрешения кэширования на промежуточных серверах нужно добавить параметр:

header("Cache-control: public");

Оптимизация времени кэширования

1. Оптимизация времени кэширования под количество запросов, обычно пользователей загрузивших страницу можно разделить на 2 группы: зашедших на страницу с другой станицы или непосредственно на страницу и другую группу обновляющих станицу в ожидании изменений. Первой группе не столь важно сколько кэшируеться страница им более важна скорость получения страницы и можно использовать максимальное допустимое время кэширования. Для второй же группы нужно кэшировать минимальное время - их можно определить по referer и тому что у них будет стоять заголовок "if not modifined since" - используя эти особенности можно при приходе первого типа запроса использовать удвоенное время кэширования, а для вторых одинарное - в результате вторая группа получает всегда обновленной контент, а первая скорость(и при совпадении запросов обоих групп еще и более быстрое обновлении, но они этого не замечают так видят страницу первый раз).
2. При появлении запроса с заголовками не изменилось ли что то ("if not modifined since"), если еще существует кэш этого запроса можно сравнивать указанный в запросе хеш с возвращенным после обработки и стараться возвратить не изменилось так как это позволит быстрее освободить ресурсы.
3. При варианте, когда контент уже существует на диске и его расположение высчитывается скриптом, более разумно использовать не хеш, а дату изменения и стараться, если это возможно не выдавать, а перенаправлять пользователя на это контент, в результате мы получаем минимальное потребление памяти и скорость отработки близкую к отображению статики. Перенаправлять желательно даже, если результат находиться на другом ресурсе, меньше посредников быстрее ресурс освободиться.
4. Очень желательно кэшировать результаты запросов не на самодельных скриптах кэширования, а использовать более распостраннённые системы кэширования написаные на компилируемых языках - так больше вероятность, что выдача будет максимально быстро отдаваться и не нужно тратить время на создание велосипеда и его тестирование. Как следствие лучше перенаправить на кэш или файловую систему, чем генерировать контент скриптом - так больше вероятность, что будет использована максимально эффективная стратегия отдачи контента.

Использование общего отображения

В отношении кросплатформенных систем,
например: приложение и веб.

Достоинства:

• Возможность описания поведения на псевдоязыке(если нет общего языка) общего для всех видов отображения;
• Возможность быстро переносить логику между системами,
• Достаточно быстрое создание логики на новой системе, если она где-то уже используется.

Недостатки полное следствие достоинств:

• Нужно искать или создавать общий язык для описания логики и зависимостей между формами - для простой логики создать достаточно просто, но зачем для простой логики городить сложности - можно просто написать на языке наиболее удобном для каждой платформы, но при этом получиться, что логика реализована 2 раза и исправление ошибки или изменение автоматически не отобразиться на другой платформе;
• Проблемы отображения - нужно преобразовывать отображения с одного вида в другой - не всегда это удается получить отображение которое будет отображаться в удобном виде. Пример: шаблон отображения приложения использует позиции элементов друг в друга - но в случае веб отображения или другой системы отображения нужно указывать порядок вложенности и\или размеры - и для поддержки нового отображения нужно переделывать всю систему преобразования шаблона в разметку на всех платформах для поддержки всех ограничений или особенностей системы. В результате получается, что кроссплатформенная система отображения содержит все ограничения и общности всех платформ (возможно одна из проблем проблем из-за которой google отказался от идеи использовать кроссплатформенное отображения для своего браузера).

А в остальном получается удобная система получения новой функциональности на другой платформе(если она уже есть на одой из версий системы), но можно портировать только ограниченное количество функциональности - так как функциональность существующая в одной из версий приложения может быть слишком сложной для другой - регистрация на сайте и возможности настроек для веб отображения гораздо проще чем в системе в виде установленного приложения с указанием кучи специфических, не нужных обычному пользователю с веба возможностей. А создание новой системы быстрого создания офисных приложений вряд ли окупит себя, так нужно конкурировать с 1C или Microsoft, и проще создать простое, но максимально эффективное приложения для каждой платформы. Или простое максимально эфективное ограничено кросплатформенное приложение максимально соответствующее требованиям, но без излишней универсальности.

WebOs

Заготовка к 3 выступлению, которая не понадобилась.
Глубокие исследования не проводились,
только в теории.

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

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

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

Основными требованиями к данному хранилищу является:

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

Все существующее методы обеспечения и реализации удаленного рабочего стола обладают некоторыми недостатками:

1. во время работы в такой среде требуется, чтобы на удаленном компьютере уже стояли полностью настроенные браузеры с установленными java и flash плагинами- что не во всех случаях доступно конечному пользователю.
2. требование поддержки данными браузерами определенных технологий(javascript), что приводит к невозможности использования некоторых браузеров, если на них не было изначально рассчитано приложение.
3. некоторые системы требуют установки дополнительных компонентов, контролировать работу которых сложно.
4. большой объем пересылаемой информации на сервер, так как некоторые функции выполнить на локальном компьютере через браузер сложно;
5. закрытость архитектуры – что, зачем, и куда отсылается;
6. закрытость процедуры аутентификации, невозможно проверить ее надежность.
7. не полная поддержка функций требующихся обычному пользователю (отсутствие интеграции компонентов и не полнота функций), например, существует: календарь, internet messenger, редактор текстов и изображений и почта, с возможность использования как хранилище документов, но они организованы как web-портал c упрощением многих функций. Это хорошо для возможности доступа с любой точки земного шара, но для постоянной работы не подходит;
8. отсутствие гарантий конфиденциальности и неразглашения информации;
9. реализация на основе систем удаленного рабочего стола, приводит к передаче больших объемов информации (действия пользователя + изображение с сервера), хоть и выполняется после сжатия и шифрования, представляют существенный объем, и не позволяют передавать звук и мультимедиа информацию;
10. не реализована возможность работы при утере связи.

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

Проектирование

Цветная версия картинки про проектирование - раньше я видел только черно-белые.
Кто исходный автор не знаю. На автора есть ссылка только в этом посте. Различные версии этого изображения можно поискать по ссылке.
А сама картинка я думаю понятна без коментариев.

Исследование алгоритмов взаимодействия параллельных процессов

В.И.Дужий, ст.преп;Д.В.Паук, студент
Национальный аэрокосмический университет им. Н.Е.Жуковского "ХАИ"
ИКТМ'2005

С целью повышения эффективности использования вычислительных систем и расширения их функциональности в настоящее время значительное количество программного обеспечения разрабатывается с использованием параллельных вычислений. Для реализации параллелизма используют различные алгоритмы. Анализ алгоритмов, обеспечивающих различные аспекты параллелизма с целью доказательства их корректности, является задачей не тривиальной и включает значительную долю эвристики. Зачастую для анализа алгоритмов используют их моделирование.

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

В данной работе был выполнен анализ и классификация методов взаимодействия процессов и аномалий, возникающих в процессе такого взаимодействия. Кроме того, проведен анализ и классификация аномалий параллелизма и причины их возникновения. Для анализа алгоритмов взаимодействия предложен подход, заключающийся в формальном описании алгоритмов с помощью различных средств UML-диаграмм, с последующим преобразованием их в сеть Петри и исследования алгоритма с помощью методов, принятых в сетях Петри.

В дальнейшем планируется создать метод и инструментальные средства описания и анализа параллельных алгоритмов, позволяющий выявить наиболее вероятные места возникновения аномалий. Основой для построения и визуализации алгоритмов предлагается использовать язык UML. Для этого необходимо исследовать, какие средства UML-диаграмм наиболее адекватно позволяют описывать алгоритмы межпроцессорного взаимодействия, а также оценить возможности определения корректности алгоритмов непосредственно по UML-диаграмме.