Решение для задачи, а не наоборот Решение для задачи, а не наоборот




НазваниеРешение для задачи, а не наоборот Решение для задачи, а не наоборот
Дата конвертации04.03.2013
Размер445 b.
ТипРешение





Нью-Йоркская фондовая биржа генерирует около терабайта данных в день

  • Нью-Йоркская фондовая биржа генерирует около терабайта данных в день

  • Объем хранилищ Facebook каждый день увеличивается на 50 ТБ

  • Internet Archive уже хранит 2 ПБ данных и прирастает 20 ТБ в месяц

  • Эксперименты на БАК могут генерировать до 1 ПБ данных в секунду!







Упор на дисковое хранение и индексацию

  • Упор на дисковое хранение и индексацию

  • Многопоточность, чтобы скрыть задержки

  • Блокировки

  • Журнализация транзакций

  • Немасштабируемы















Отказ от строгой консистентности

  • Отказ от строгой консистентности

  • Уход от нормализации и внедрение избыточности

  • Потеря выразительности SQL и моделирование части функций программно

  • Усложнение клиентского ПО

  • Сложность поддержания работоспособности и отказоустойчивости



NoSQL – это не бездумный отказ от реляционной модели!

  • NoSQL – это не бездумный отказ от реляционной модели!

  • “NoSQL” - название реляционной СУБД, не использующей SQL (1998 г.)

  • Бум NoSQL обусловлен ростом Интернет-индустрии



Решение для задачи, а не наоборот

  • Решение для задачи, а не наоборот

  • Неограниченное горизонтальное масштабирование

  • Свободная схема или ее отсутствие

  • Консистентность в жертву производительности

  • Простота развертывания и администрирования

  • Большинство программ императивные







Простая модель данных – ассоциативный массив

  • Простая модель данных – ассоциативный массив

  • Доступ к данным только по ключу

  • Информация о структуре занчений не сохраняется

  • Обычно все данные хранятся в памяти с возможностью сохранения на диск



“Документ” – множество пар ключ-значение

  • “Документ” – множество пар ключ-значение

  • Документы могут быть вложены и объединяться в коллекции

  • Отсутствие схемы как в документе, так и в коллекции

  • Доступ к значениям по ключу или с помощью языка запросов

  • MapReduce



Все изменения пишутся в конец файла

  • Все изменения пишутся в конец файла

  • При ошибках всегда можно восстановить последнее состояние

  • Запись не блокирует чтение



Таблица – упорядоченный ассоциативный массив строк

  • Таблица – упорядоченный ассоциативный массив строк

  • Строка – ассоциативный массив семейств колонок

  • Семейство колонок – ассоциативный массив колонок с зафиксированными ключами

  • Колонка – кортеж <ключ, значение, временная метка>





Данные естественным образом представляются графом

  • Данные естественным образом представляются графом

  • Граф – это вершины с аттрибутами и ребра со свойствами

  • Доступ к вершинам и ребрам по индексам на аттрибутах и свойствах

  • Вычисления – обход графа по ребрам с заданными свойствами











Средняя производительность HDD ~100МБ/c

  • Средняя производительность HDD ~100МБ/c

  • Прочесть 1 ТБ ~ 2.5 часа

  • Прочесть 1 ТБ параллельно со 100 дисков ~ 2 минуты

  • Произвольный доступ к диску медленный

  • Последовательный доступ быстрый!





2002 – поисковый движок Nutch

  • 2002 – поисковый движок Nutch

  • 2003 – GFS (Google)

  • 2004 – Nutch Distributed File System (NDFS)

  • 2004 – MapReduce (Google)

  • 2005 – Nutch MapReduce

  • 2006 – Nutch → Hadoop

  • 2008 – Yahoo! анонсирует Hadoop кластер

  • 2008 – Apache Hadoop



Очень большие файлы (ГБ, ТБ, ПБ)

  • Очень большие файлы (ГБ, ТБ, ПБ)

  • Пакетный доступ к данным (пишем один раз, читаем много)

  • Аппаратные сбои неизбежны (репликация и лог для метаданных)

  • Локальность вычислений











Hive – распределенное хранилище (HDFS, HiveQL)

  • Hive – распределенное хранилище (HDFS, HiveQL)

  • Pig – среда исполнения и язык программирования вычислений

  • Hbase – распределенное колоночное хранилище

  • ZooKeeper – высокодоступный координационный сервис



Функциональный ЯП

  • Функциональный ЯП

  • Создавался Ericsson для управления коммутационным оборудованием

  • Легковесные процессы взаимодействуют в соответствии с моделью акторов

  • Порождение 200000 процессов ~ 10 мкс

  • Отказоустойчивость оборудования – 99.9999999% (Ericsson)



Фреймворк MapReduce вычислений на больших данных (Nokia Research Center)

  • Фреймворк MapReduce вычислений на больших данных (Nokia Research Center)

  • Ключевое свойство - простота:

    • Нет планировщика
    • Облегченный доступ к локальным ресурсам
    • Независимый от ЯП протокол
    • Упрощенная DDFS с децентрализацией метаданных










Анализ данных в реальном времени

  • Анализ данных в реальном времени

  • Высокочастотная торговля

  • Поисковые системы реального времени

  • Социальные сети

  • Персонализация контента

  • ...



Предоставить простой интерфейс поточной обработки данных

  • Предоставить простой интерфейс поточной обработки данных

  • Обеспечить горизонтальное масштабирование и высокую доступность кластера

  • Минимизировать задержки, используя только оперативную память узлов

  • Создать децентрализованное, симметричное решение без единой точки отказа



Вычисление – граф

  • Вычисление – граф

  • Вершины – вычислительные элементы (PE)

  • Ребра – потоки событий

  • PE – это актор с изолированным состоянием



Событие – кортеж именованных значений

  • Событие – кортеж именованных значений

  • События группируются по именам значений в кортеже

  • Группировка важна, потому что состояние хранится в памяти узла и изолировано

  • PE может или создать новый поток, или опубликовать результат





Storm (Twitter) – распределенная система вычислений в реальном времени

  • Storm (Twitter) – распределенная система вычислений в реальном времени

  • Первый публичный релиз через год после S4

  • Устраняет недостатки S4



Два варианта использования:

  • Два варианта использования:

    • обработка потоков событий
    • распределенный RPC
  • Прозрачное горизонтальное масштабирование

  • Гарантия обработки сообщений

  • Отказоустойчивость, перераспределение вычислений

  • Независимость от ЯП



Вычисление – топология (граф)

  • Вычисление – топология (граф)

  • Ребра – маршруты передачи данных

  • Вершины:

    • трубы (spout) – генерируют данные
    • молнии (bolt) – производят вычисления


Событие – кортеж (как в S4)

  • Событие – кортеж (как в S4)

  • Кортеж полность обработан, если обработан каждый кортеж дерева

  • Избежать повторных вычислений можно с помощью транзакций





Классификация:

  • Классификация:

    • Логистическая регрессия
    • Байесовские классификаторы
    • Случайный лес
  • Кластеризация

    • K-Means
    • Иерархическая кластеризация
    • MinHash


Понижение размерности:

  • Понижение размерности:

    • SVD
    • PCA
  • Рекомендательные алгоритмы:

    • Фильтрация по схожести пользователей
    • Фильтрация по схожести объектов
    • Slope One
  • И многие другие...



Найти пользователей, чьи интересы наиболее схожы с интересами данного пользователя

  • Найти пользователей, чьи интересы наиболее схожы с интересами данного пользователя

  • На основе рейтингов K наиболее похожих пользователей предсказать рейтинг, который поставит данный пользователь предметам, которые он еще не видел

  • Порекомендовать предметы с наибольшим предсказанным рейтингом







Сложность O(MN)

  • Сложность O(MN)

  • На практике – O(M+N), т.к. векторы очень разрежены

  • Слишком медленный для Веба

  • Предварительное вычисление матрицы схожести сильно влияет на качество







Сложность O(N2M)

  • Сложность O(N2M)

  • На практике O(NM), т.к. у большинства пользователей мало оценок

  • Более устойчив к предварительному вычислению матрицы схожести

  • Применяется Amazon (2003 г.)









































Кузнецов Сергей Дмитриевич

  • Кузнецов Сергей Дмитриевич

  • Добров Борис Викторович

  • Когаловский Михаил Рувимович

  • Калиниченко Леонид Андреевич





Похожие:

Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconРешение творческих задач фоминых И. Б. Гу роснии ит и ап fomin77@land ru «Настоящая теория возникает как ересь, а заканчивается как предрассудок»
Решение задачи формирование представления на основе признаков, задающихся условиями задачи (предикатами)
Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconФизика. «Две задачи». Постовалова Марина Владимировна
Задачи сгруппированы по 2 из раздела. На первый взгляд они одинаковы, но решение и ответ различны
Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconЗадачи. Задачи
«Коммуникация», содержание которой направлено на достижение целей овладения конструктивными способами и средствами взаимодействия...
Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconРеологические свойства крови. Возрастные изменения системы крови. Реология это наука о текучести жидкостей
Соэ и наоборот; в насыщение эритроцитов гемоглобином: гипохромные эритроциты медленнее оседают и наоборот
Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconРешение для клиента Решение для клиента
Гибкую платформу Метро-сетей C/dwdm, предназначенную для передачи данных систем хранения
Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconРешение типовой задачи посредством пакета FlowVision
Программный комплекс FlowVision предназначен для моделирования задач аэро- и гидродинамики
Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconРешение текстовых задач арифметическим способом. Задачи, содержащие отношения «больше на (в)», «меньше на (в)». Задачи, содержащие зависимость, характеризующую процессы: движения (скорость, время, пройденный путь)

Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconРазработка программного обеспечения (Software Engineering) Ian Sommervillle Часть Требования к по: модели систем
Эти модели используют графические представления, показывающие решение как исходной задачи, для которой создается система, так и разрабатываемой...
Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconРешение задач повышенной сложности за 7класс на составление уравнений» Подготовили учащиеся 7 «В» класса Детчинской ср школы Аксёнов. А., Ермачкова. А
Решение математической задачи- это изобретение специально ведущего к поставленной цели рассуждения- это творческий процесс,пусть...
Решение для задачи, а не наоборот Решение для задачи, а не наоборот iconИспользование здоровьесберегающих технологий в работе педагога доу цель семинара
Технологии, направленные на решение приоритетной задачи современного дошкольного образования-задачи сохранения, поддержания и обогащения...
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница