Алгоритмы (боремся с разжижением мозга)

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

Вот моя задача:
есть сервис, которые предоставляет данные для других сайтов. В данные входит: описание товара, цена, путь к картинке, артикул.
Товаров не более 120 тыс
Объем описания одного товара не более 5 килобайт
Частота запросов с партнерских магазинов 800-1300 тыс запросов в сутки.
База в SQL, меняется хз когда и как (не так важно)
Ка реализовать выдачу данных с супер скоростью?

Для фиксированных и больших выборок (например, весь каталог, один или несколько разделов, группа товаров по какому-то признаку), наверное, лучше всего отдавать архивированные xml-файлы (например, в формате yml) и разбирать их на стороне клиента. Файлы готовим в момент записи в БД или, если точное соответствие не критично, то, например, по крону.
А отдельные товары или призвольные выборки придется отдавать напрямую. В этом случае запрос к БД будет работать намного быстрее, чем создание такого количества файлов и поиск в них. Создание представлений (view) тут тоже вряд ли поможет.

Купить алгоритм у гугла

Цитата ("ArtPro"):

...Ка реализовать выдачу данных с супер скоростью?

Что такое "супер-скорость": в каких единицах измеряется и какие значения Вы хотите получить?

>Ка реализовать выдачу данных с супер скоростью?
Мощный сервер, а лучше несколько... хорошо продуманная база данных MyISAM (вот только надо про бэкап не забывать) + xml отдача. ну вот и все) а что тут еще мудрить? (запрос на выдачу принимает nginx + php-fpm)

Предлагаю доставлять эксель-файл наложенным платежом по почте России!

Цитата ("ArtPro"):

Ка реализовать выдачу данных с супер скоростью?

На ум приходит только одно - если супер-скорость супер-важна, значит есть бабло на сервер и на ОЗУ, отсюда и сливать БД в оперативку и оттуда выдавать данные, когда содержимое sql-таблицы изменяется - сразу же меняем тот кусок что в озу.
Можно или сразу всё сливать в память сервера, или по мере надобности.. в общем суть передал, сам алгоритм не так важен .. короче при запросе данных почти никогда не обращаемся к sql

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

Цитата ("ArtPro"):

Ка реализовать выдачу данных с супер скоростью?

Только что хотел бурно отреагировать на такую формулировку вопроса, но, посмотрев Ваш профиль, я понял, что Вы вряд ли являетесь программистом, так что простительно.
В общем, такая формулировка задачи "нужна супер скорость" для программиста — это то же самое что и для дизайнера "нужно чтобы получилось круто".
У каждого же свои критерии, понимаете?

Более подробно можно ответить только зная детали задания.
Обычно в таких случаях программисту нужно:
— Иметь информацию о природе данных. То есть знать, что собой данные представляют, чтобы выяснить есть ли зависимости, дублирования, возможны ли те или иные оптимизации, и т.д. Для этого нужен дамп с примерами.
— Иметь информацию об объемах данных (это Вы сказали).
— Иметь информацию о каждом типе запросов к данным. Например, какие возможны поисковые запросы, по каким параметрам.
— Иметь примерную инфомацию о частоте каждого типа запросов.

После этого имеет смысл заниматься построением хранилища данных.

Цитата ("ArtPro"):

Товаров не более 120 тыс
Объем описания одного товара не более 5 килобайт
Частота запросов с партнерских магазинов 800-1300 тыс запросов в сутки.

Получается, суммарный объем данных менее гигабайта.
Вместе с индексами это будет вряд ли более двух гигабайт.
Значит напрашивается очевидный вывод — все данные размещать в памяти.

Для этого есть много вариантов реализаций, можно средствами СУБД (если используете MySQL — то например MEMORY таблицы с BTREE и HASH индексами в зависимости от типов запросов), или можно использовать Memcache, или любую другую реализацию внешнего кеша, их множество.
Соединение с БД или кешем в данном случае нужно делать перманентным.
Вариант с кешем может работать быстрее, но если нужно реализовывать поиск по тем или иным сложным критериям, то придется самому реализовывать работу с индексами.

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

1300 тыс запросов в сутки — это может означать в среднем 15 запросов в секунду, или, возможно, до 150-200 запросов в секунду на пике. Для этого идеально походят аппликейшен сервера Java/JEE. Плюс, в этом случае, если в будущем возрастет нагрузка, вопрос решится просто постановкой дополнительных серверов в кластер, между которыми нагрузка будет распределяться лоад балансером. То есть покупкой дополнительного железа, без доработки кода.
Также возможны варианты реализации на PHP, Perl, C++ и т.д., кажый вариант со своими достоинствами и недостатками.
Какое именно решение принимать зависит уже от планов заказчика по дальнейшему развитию данного сервиса, от наличия у заказчика тех или иных специалистов, и т.д.

Цитата ("elosoft"):

, наверное, лучше всего отдавать архивированные xml-файлы (например, в формате yml) и разбирать их на стороне клиента.

Нагрузка на диск будет такой, что отдача будет намного медленнее, чем отдача sql

Цитата ("Illarion_SA"):

Что такое "супер-скорость": в каких единицах измеряется и какие значения Вы хотите получить?

число запросов есть в условии

Цитата ("Enkvist"):

Мощный сервер, а лучше несколько... хорошо продуманная база данных MyISAM (вот только надо про бэкап не забывать) + xml отдача. ну вот и все) а что тут еще мудрить? (запрос на выдачу принимает nginx + php-fpm)

Хорошо продуманная база - это уже не MyISAM по ряду причин.
nginx + php-fpm - ????? чем апач не угодил? (аргумент что апач медленнее я легко разобью тестами)

Цитата ("tvv"):

В общем, такая формулировка задачи "нужна супер скорость" для программиста — это то же самое что и для дизайнера "нужно чтобы получилось круто".
У каждого же свои критерии, понимаете?

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


Про мемкэш упоминание было (кстати по статистике из 18 программеров на веблансере умеют с ним работать только 3)
Про то, что nginx может напрямую брать данные из мемекэша - пока никто не упомянул.

Возвращаясь к реальным данным.
База размером в 2 гига всего, памяти на сервере 4 гига, проца выделено 3Ghz, канал 1гигабит (пока хватает)

Логика работы простая:
есть мемкэш, nginx и стороннее приложение для управления товарами с умением выдавать данные на порт по запросу
клиент может запросить товар в виде
site.ru/tovar/id - в ответ сам nginx отдает данные из мемкэша, если они стухли (таймаут в 200 минут), то запрос идет приложению (написано на php и представляет собой строк 200 кода для работы системы + неважная для решения задачи часть по редактированию товаров), и оно выдает значение из sql + добавляет запись мемкэш с ключем tovarXXXXXXX - где XXXXXXX - это ID товара
чтение категорий товаров идет по адресу site.ru/category/ - в ответ так же из мемкэша отдается массив в категориями и их id
nginx нагружает процессор не более чем на 60% при пиковой нагрузке (пока пики до 7 тыс запросов в секунду были)

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

Цитата ("tvv"):

если используете MySQL — то например MEMORY таблицы с BTREE и HASH индексами в зависимости от типов запросов

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

Сергею Беззубу приветы

Цитата ("ArtPro"):

Про мемкэш упоминание было (кстати по статистике из 18 программеров на веблансере умеют с ним работать только 3)
Про то, что nginx может напрямую брать данные из мемекэша - пока никто не упомянул.

Так все же зависит от того, какие возможны запросы. Я об этом и написал выше, что нужны детали.
Я же не знаю Вашего задания, поэтому по-умолчанию советую более общее решение. Потому я и написал: "Обычно в таких случаях программисту нужно: ...".

Например, если запросы идут только по ключу, то конечно nginx+memcache достаточно.
А если нужно например выдать количество товаров в категории "книги" по городу "Москва"? Тут уже придется делать запрос с поиском по индексу. Простой связкой nginx+memcache тут никак не отделаетесь.

Задачка номер 2:

создаем гуглкарты (яндекскарты)
Как бы вы организовали логику хранения изображений карт с учетом масштабов. Не забываем и то, что логика выборки данных должна быть максимально простой, что бы это легко мог бы делать несложный js на стороне клиента.
и еще момент, на карте есть объекты, при масштабировании должна работать кластеризация + быстрая выборка из базы

Цитата ("ArtPro"):

Сергею Беззубу приветы

Вы его знаете? ))

Цитата ("ArtPro"):

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

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

Цитата ("tvv"):

А если нужно например выдать количество товаров в категории "книги" по городу "Москва"? Тут уже придется делать запрос с поиском по индексу.

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

т.е. что бы узнать все книги в москве смотрим ветку "москва"->"книги". а там обход дерева при поиске, а при простом серфе по сайту смотрим текущий уровень вложений. у книг как раз будут разделы книг, в них есть подразделы по разным факторам (пересекаются товары: 1 товар может быть в Бестселлерах и он же в разделе "современная литература"- "фантастика" и т.п.)

Цитата ("tvv"):

В нашем случае, по условию Вашей задачи, памяти хватит.

ага, проверяли, сначала только при старте сервера все тормозит, а потом устаканивается.

Цитата ("tvv"):

Вы его знаете? ))

Кто-то рассказывал, фамилия запомнилась, может и не он,но фамилия редкая.

Цитата ("ArtPro"):

т.е. что бы узнать все книги в москве смотрим ветку "москва"->"книги". а там обход дерева при поиске, а при простом серфе по сайту смотрим текущий уровень вложений. у книг как раз будут разделы книг, в них есть подразделы по разным факторам (пересекаются товары: 1 товар может быть в Бестселлерах и он же в разделе "современная литература"- "фантастика" и т.п.)

А если клиентам нужен результат запроса "показать все новинки во всех категориях товаров, добавленные последние 2 дня"?
Или "показать все товары по всем категориям от производителя Samsung"?

Понимаете к чему я клоню, нельзя дать конкретного решения для хранилища (например nginx+memcache) не имея полного списка типов запросов.
Так что зря Вы плохо относитесь к тем, кто при Вашей постановке задачи не упомянул весьма частное решение с nginx.
Уточняйте задачу, и тогда получите более четкий ответ.

Цитата ("ArtPro"):

И все же я программист и все же неплохой, судя по моей работе. , но пиписьками мерятся не будем, так как у меня она одна, и мало у кого их больше

Ну тогда прошу прощения, что написал что Вы, возможно, не програмист. Я этот вывод сделал на основании Вашего профиля на Веблансере, предположил что студия дизайна, или занимаетесь SЕО, или 1С, и т.д. Ошибся, бывает.

Кстати вот задачка 3:
найдите максимально быстрый вариант выборки случайных значений из таблицы
SELECT * FROM tTable ORDER BY RAND() LIMIT 10; - вариант для новичка.
усложним задачу тем, что id не непрерывны.

В своё время решение нашёл в гугле, эту задачу можно считать простой, давай что-нибудь сложнее.
И когда zeen обещанный в сентябре того года будет?

Цитата ("AlekartRu"):

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

задача №2
пока ответов нет