Предыдущие две задачки уже отгаданы (про полнотекстовый поиск и гоблина на озере). Пришло время третьей. Нечётные задачки будут про компьютеры. Итак, поехали.
Есть M компьютеров в сети. На них хранятся некие файлы разных типов и размеров. Каждый файл хранится в количестве N копий. Все копии лежат на разных машинах. (Следовательно, M ≥ N.)
Задача: реализовать команды Read и Create (чтение файла, создание нового файла), при условиях:
1) Система остается работоспособной (все файлы доступны, сохранение файлов работает) при отключении от 1 до N-1 машины ("из розетки").
2) Балансировка нагрузки: количество обращений к каждой машине за любыми файлами — почти одинаково.
3) При подключении любого числа новых машин, они сразу включаются в работу и через некий ограниченный переходный промежуток времени (24 часа максимум) нагрузка на все машины, и новые, и старые, сравнивается.
22 июля 2007 в 13:00
Ну, походу, здесь вопрос исчерпан, Олег, давай следующую…
17 июля 2007 в 9:02
У Таненбаума есть книга интересная "Распределенные системы. Принципы и парадигмы" – там есть интересные алгоритмы репликации данных в распределенных системах.
16 июля 2007 в 21:05
GFS меня тоже впечатлила. Раз он у них стоитзначит система однозначно роботоспособна. Но лично мое мнение система имеет так и преимущества так и недостатки(ну это как всегда). Вопрос о эффективнойфайловой системе для больших распределенных систем остается открытым, желаю удачи всем кто занимается решением этой проблемы=))
16 июля 2007 в 16:00
Идея GFS мне нравится все больше.А еще есть MogileFS, который для ЖЖ написан. Попроще гфс-а.
16 июля 2007 в 11:02
Если информация о том, с какой машины брать файл, кешируется, то в итоге маршрутизатор через некоторое время будет знать, что у него и где лежит (работа ведь только на создание и чтение, всяких там изменений-перемещений нет, так?). А пока он ничего не знает, единственный способ найти файл – искать по всем машинам, и тут уж не до балансировки.
16 июля 2007 в 8:02
1) Информация о том, с какой машины брать файл кешируется.
2) Маршрутизатор, если говорить о GFS, является клиентом системы, а не мастер-сервером. Почему? Потому что другим клиентом такого же мастер-сервера является приложение, сохраняющее файл в GFS. И вся идея мастер-сервера лишь в том, чтобы иметь единственную машину, хранящую метаинформацию обо всех файлах. Это противоречит начальным условиям, но гугловцы решили, что сделать Operation Log и хитрую схему восстановления мастера проще, чем разыскивать файлы в одноранговой сети. Плюс, мастер может выполнять мониторинг чанк-серверов, раздавать задания по ререпликации и ребалансировке. В GFS, чтобы облегчить нагрузку на мастер, во-первых, вся метаинформация лежит в оперативной памяти, во-вторых, расположение чанков кешируется клиентом и чтение-запись производится с них, в-третьих, при совершении записи и репликации процессом руководит назначенный первичным чанк-сервер. Таким образом, для 100 одновременных записей используются 100 руководителей-чанксерверов, а не 1 мастер-сервер. Лизинг выдается на время и может быстро отбираться мастер-сервером, если потребуется гарантия того, что операции над данным файлом контролируются мастером (перед снэпшотом, например).
16 июля 2007 в 3:00
"Ок, небольшое дополнение. Маршрутизатор не знает, на какой из машин лежит запрашиваемый файл."
КАК ЭТО? ему говорят "дай ко мне тот_самый_файл" а он "5 сек" и давай искать n копий этого файла на m машинах…. я конечно допускаю такую ситуацию, в жизни всякое бывает, но зачем себе жизнь усложнять? Если с него спрашивают этот файл то он должен точно знать на каких машинах он храниться этот файл, он должен знать какие из них сейчас работают, и должен хранить статистику обращений к машинам,чтобы выбрать комп который загружен меньше всего.
Иначе вся это система будет по мягко говоря не эффективна.
Эффективно решить данную задачу имхо можно написав сервисную прогу основная работа которой будет заключаться в ведении базы данных компов,файлов и их пересечении.Его спрашивают, он делает пару запросов к базе и все. насколько это все будет эффективно зависит от нюансов про которые имеет смысл говорить только на стадии реализации.
Например:
Присоздания файла встанет вопрос где и в каком количестве размещать файлы. Решить можно примернотак: по итогам нескольких дней выбирается комп с наименьшей загрузкой, делается поправка на доступное дисковое пространство машины, проверяется работает ли он вообще. если да то на нем создается файл. Дальше если обращение к этому файлу в день(условно) превышает какого то значения то копия файла создается на другой машине(по алгоритму создания нового файла).
В основном если хотите по-извращаться задача идеальна для подключения какого нить нейроалгоритмадля высчитывания нагрузки на компы
согласен ответ слишком абстрактен и по сути говоря тривиален…. какой привет, такой ответ
16 июля 2007 в 2:02
Для справки: //labs.google.com/papers/gfs.html
У гугла схема такая: есть клиент, он обращается к мастер-серверу, спрашивает расположение интересующего файла. Мастер-сервер выдает информацию по файлу и список чанк-серверов. Клиент кэширует эти данные и далее работает только с чанк-серверами.
Я еще не дочитал про GFS до конца, так что не могу составить свое резюме на этот счет.
16 июля 2007 в 0:03
Подобные задачи решают протоколы пиринговых сетей. ИМХО для равномерного распределения нагрузки нужен "сервер", единое место куда стекалась бы статистика по файлам т.е. расчеты что с кого скопировать и(или) удалить может проводить и клиент но отчетность концентрировать в одом месте, что существенно сократит трафик и упростит внешний доступ. Но в маленьких сетях (десяток машин) может быть дешевле обойтись без сервера.
15 июля 2007 в 21:05
Ок, небольшое дополнение. Маршрутизатор не знает, на какой из машин лежит запрашиваемый файл.
15 июля 2007 в 20:00
Не очень понятно, где именно задача. Ни одно из трех условий навскидку не составляет проблемы реализовать, соль в средствах и нюансах их использования.
// Задачи решают, загадки отгадывают
15 июля 2007 в 14:02
1) Сервер, принимающий запросы из внешнего мира, есть. Но это, по сути, маршрутизатор. Он может упасть и вся система встанет, но его единственная задача – перенаправлять запросы.
2) Файлы запрашиваются из внешнего мира через главный маршрутизатор.
3) Нет.
15 июля 2007 в 13:03
несколько уточняющих вопросов:
1) требуется ли равноправие всех компьютеров в сети?
(возможно ли существование "сервера" куда будут приходить запросы из внешного мира, и который будет индексировать все файлы )
2) эти файлы кто-нибудь запрашивает из внешнего мира или или они нужны только внутри локальной сети?
3) эта задача моделирует хранение фотографий на данном сайте?
(так чисто из любопытства)
15 июля 2007 в 13:02
Где подвох? Отмеряем нагрузку на машины. При создании файла копии размещаем на машинах с минимальной нагрузкой. При чтении… Можно сохранять последовательность обращений к копиям (длиной не более N) чтобы опеределять, к какой из копий мы не обращались дольше всех. Или я что-то не догнал?