Как создать расширяемую распределённую систему
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Как создать расширяемую распределённую систему - 2009-06-23 20:56:27.706666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Необходимо создать распределённую систему из n узлов для хранения и поиска информации. Каждый узел представляет собой один или несколько серверов, возможно объединённых в кластер. Количество узлов - от 200. Вопрос в том, как заставить их работать вместе.
Классические распределённые алгоритмы, такие как Map/Reduce, предполагают master/slave архитектуру. Однако в данном случае она неприменима, т.к. каждый узел должен иметь возможность инициализировать поиск по всей сети (пользователь ищет информацию сначала на одном узле, если его не удовлетворяет результат, он повторяет поиск по всей сети).
Естественно, запрос от одного узла сразу всем остальным не катит из-за огромного их количества.
Есть вариант выделить центральный узел, который и будет выполнять роль master'а. Тут две проблемы:
1) кто будет отвечать за центральный узел? Ну, допустим, нашлась такая организация. Теперь работоспособность всей системы зависит исключетельно от неё, что не есть хорошо (вспоминаем все недостатки топологии "звезда");
2) нагрузка на этот центральный узел будет колоссальной, даже если он будет просто распределять запросы и собирать результирующую информацию. Кроме того, система должна быть расширяемой, то есть всегда должна оставаться возможность свободно регистрировать новые узлы.
Собственно, в какую сторону смотреть, что читать, на какие технологии обратить внимание?
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-23 23:05:12.423333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
http://en.wikipedia.org/wiki/Peer-to-peer
http://www.google.com/search?q=decentralized+peer+to+peer
там много вариантов реализации на самом деле
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-24 04:40:27.290000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Упс, пардон, забыл упомянуть, что речь идёт в первую очередь о полнотекстовом поиске по документам. Соответственно, использование хабов для хранения индексной информации невозможно: размер индекса равен примерно 20-30% от исходного текста, а если учесть, что потенциальным источником информации для индекса может быть, например, Библиотека Конгресса США, то индексы могут быть огого каких размеров. Плюс производительность - помножь среднее время поиска по одному индексу на их количество, да на количество одновременных запросов и получишь совсем уж не радостную картину. Ну и главная проблема - расширяемость. Если система может работать с 200 узлами, сможет ли она работать с 2000?
Если же брать чистый p2p, то получаем гигантский траффик. Если на каждый из n узлов поступает один запрос от пользователя в секунду, то общее количество запросов, генерируемых всеми узлами, будет равно (n - 1) * n. Если n = 200, количество запросов равно почти 40000. Это не считая ответов.
Преимущества схемы со списком хабов, как в G2, тоже незначительны. Главный плюс, который она даёт, это возможность прекратить поиск после достижения какого-то числа положительных резултатов. Но нам то нужно не просто найти подходящий документ, а выбрать самые релевантные, то есть искать нужно по индексам всех узлов anyway. Ну и опять же, вопрос расширяемости.
То есть, чистый p2p вызывает огромный траффик, использование центрального(-ых) узла накладывает ограничения на расширяемость и сильно напрягает этот самый узел.
Ещё одна идея на грани бреда - использование чего-то вроде виртуального кольца, когда каждый узел знает только своего следующего соседа и посылает пакеты ему (если сосед недоступен, он временно исключается, и пакеты посылаются следующему за ним). При этом каждый узел в дополнение к поиску по своему индексу может сразу мерджить свои результаты с предыдущими, отбирая и передавая только лучшие K. Плюс такой системы - минимизация траффика и нагрузки на каждый узел. Минус - время обработки запроса равно сумме времён прохождения каждого узла.
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-24 05:06:22.410000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: kreol
Если же брать чистый p2p, то получаем гигантский траффик. Если на каждый из n узлов поступает один запрос от пользователя в секунду, то общее количество запросов, генерируемых всеми узлами, будет равно (n - 1) * n. Если n = 200, количество запросов равно почти 40000. Это не считая ответов.
не обязательно. в децентрализованной p2p-системе вводится некоторый критерий связанности узлов, с помощью которого обработка локализуется. собственно, твоя идея насчёт "соседей" (в несколько усложнённом варианте) была реализована ещё в kazaa, из которой вырос skype - только что в твоём случае шарятся не только данные, но и расчётные мощности. локализуешь данные в семантическую сеть по интересующей тебя релевантности, а CPU time - по наиболее эффективной расчётной топологии; в таком случае запрос делегируется по первому критерию до группы, способной эффективно его обработать (либо отдать свои данные группе, которая обработает лучше)
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-24 14:05:03.683333
|
|
|
Hateman
Сообщений: 62
Оценки: 0
Присоединился: 2009-06-06 20:22:22.040000
|
quote:
Есть вариант выделить центральный узел, который и будет выполнять роль master'а.
Если имеется такой вариант, то, наверное возможно выделить несколько "центральных узлов".
А узлы объединить в группы. На каждую группу по центральному узлу.
При регистрации нового узла, он добавляется в группу, имеющую "свободные места".
Если таковых не имеется, создаётся новая группа со своим центральным узлом.
Останется решить задачу о координации центральных узлов.
Имеет ли смысл такой вариант?
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-24 18:07:47.700000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Hateman
Имеет ли смысл такой вариант?
Фактически нет. Для добавления новых центральных узлов нужна некая управляющая структура, то есть мы просто перекладываем вопрос с технической области на организационную. Другими словами, а кто будет этим заниматься? Выделить единый центральный узел не такая проблема, а вот постоянно добавлять - это уже нехорошо.
То есть это, конечно, тоже вариант, но мне бы очень его не хотелось использовать.
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-24 18:42:40.976666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Denaturat
не обязательно…
Помедленнее, я записываю (с) :)
quote:
в децентрализованной p2p-системе вводится некоторый критерий связанности узлов, с помощью которого обработка локализуется
Что значит "обработка локализуется"? То есть, ты предлагаешь по каким-то критериям делить все узлы на группы и искать только в одной группе? Единственный критерий, на который, как я понимаю, здесь можно расчитывать, - это семантическое подобие, то есть мы разбираем запрос, пытаемся понять, что человек ищет и делаем догадку, в каких узлах или в какой группе такая информация может быть, а остальные узлы сети прокатывам?
quote:
собственно, твоя идея насчёт "соседей" (в несколько усложнённом варианте) была реализована ещё в kazaa, из которой вырос skype
Эээм, из описания kazaa так и не понял, что за идея то? Выделять supernode'ы что ли?
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-24 21:36:44.426666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: kreol
Что значит "обработка локализуется"? То есть, ты предлагаешь по каким-то критериям делить все узлы на группы и искать только в одной группе?
вводишь понятие расстояния между нодами, и локализуешь их по нему. простейший вариант для расстояния - значение, пропорциональное ширине канала и latency между нодами. по какому критерию и как именно балансировать сеть - сильно зависит от конкретной системы, надо проводить анализ по существу
quote:
ORIGINAL: kreol
Единственный критерий, на который, как я понимаю, здесь можно расчитывать, - это семантическое подобие, то есть мы разбираем запрос, пытаемся понять, что человек ищет и делаем догадку, в каких узлах или в какой группе такая информация может быть, а остальные узлы сети прокатывам?
в общем - да. а чтобы догадки были точными, надо построить семантическую сеть на каталоге базы знаний
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WKJ-4P29KB6-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=938849874&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=6b11f01084d89ff6a04c589db77a3e15
http://portal.acm.org/citation.cfm?id=863976
http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4530427%2F4530428%2F04530454.pdf%3Farnumber%3D4530454&authDecision=-203
quote:
ORIGINAL: kreol
Эээм, из описания kazaa так и не понял, что за идея то? Выделять supernode'ы что ли?
хранить информацию о "соседях", и делегировать запросы через них. ни один клиент не знает всей топологии, и явно не работает со всей сетью
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-28 05:23:08.026666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
а чтобы догадки были точными, надо построить семантическую сеть на каталоге базы знаний
Насколько я понял, описанные в документах системы предполагают изначальное размещение документов по узлам в соответствии с их семантическими векторами, то есть документ попадает не в узел, а во всю сеть, а там его уже кладут куда надо. Увы, в моём случае такое не прокатит, потому что система будет строиться поверх существующих индексов в узлах, то есть не будет возможность в одном узле собрать доки по естествознанию, например, а в другом - по экономике.
Ну ладно, за некоторыми узлами можно будет закрепить хотя бы примерный вектор. Например, узел, расположенный в библиотеке народного творчества будет иметь довольно выраженный семантический вектор, но какая-нибудь общепредметная библиотека, или там книжный магазин, будут содержать тексты совершенно любого направления. Причём таких, скорее всего, будет большинство. Есть варианты выхода из такой ситуации?
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-28 12:10:56.220000
|
|
|
Hateman
Сообщений: 62
Оценки: 0
Присоединился: 2009-06-06 20:22:22.040000
|
o.O
1. Что хоть ты такое строишь, если не секрет?
2. Интернет, случаем, не является ли примером такой сети? Типа, гибридный вариант.
Только, в любом случае, полной равноправности всех узлов, достигнуть если не невозможно,
то очень сложно. Стоит ли?
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-28 16:57:18.473333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
1. Распределённую систему поиска информаци.
2. Нет, для полнотекстового поиска в Интернете используется постоянная переиндексация и сохранение индексов на серверах (например, серверах гугла).
Равноправность узлов не обязательна, главное, чтобы поиск был быстрым, эффективным, не слишком нагружал сеть и позволял безболезненно добавлять новые узлы.
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-28 17:07:40.090000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: kreol
система будет строиться поверх существующих индексов в узлах
ну смотри. пусть у тебя есть семантическая группа "естествознание", и есть n нод, в которых присутствуют документы, проиндексированные в эту группу. в таком случае есть по крайней мере два варианта: каждая из этих нод должна иметь карту всех нод, имеющих документы из этой группы (хорошо для семантически однородных нод в сети, большой словарь на нодах, хорошая производительность работы), либо каждая из этих нод должна уметь составлять запрос своим "соседям" по топологическому принципу так, чтобы запрос обощёл всю сеть и вернул в исходную ноду всю необходимую для расчёта информацию (хорошо для семантически разнородных сетей, малый словарь на нодах, низкая производительность работы для сильно топологически разнесённых сетей)
как вариант гибридного (в обоих смыслах) подхода ты можешь ввести в своей сети семантически центры, заведующие той или иной семантической группой документов; набирая статистику запросов ты можешь менять центровые группы в соответствии с их популярностью и топологическими закономерностями (если таковые имеются)
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-29 04:44:38.123333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Ок, направление мысли понял, thx. Дальше буду эксперементировать.
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-06-29 17:06:08.066666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
удачи. пиши если чего
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-07-17 19:21:04.490000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
http://en.wikipedia.org/wiki/Content_addressable_network
http://en.wikipedia.org/wiki/Kademlia
собственно, на подумать, - если сам ещё не нашёл. enjoy!
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-07-20 02:51:13.660000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Ага, про CAN уже почитал. К сожалению, пока работа идёт над базовым функционалом для одного узла. Поиграть с семантическим поиском в сети получится скорее всего где-то только к концу года. Пока пристреливаюсь.
|
|
|
|
|
RE: Как создать расширяемую распределённую систему - 2009-08-23 05:53:37.580000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
А есть что-нибудь понятное почитать про инкрементальный вариант Random Indexing для уменьшения размерности word space? А то сколько описаний, столько у меня вариантов, как это на самом деле должно быть реализовано.
upd. http://eprints.isofts.kiev.ua/141/1/%D0%9C%D0%B8%D1%81%D1%83%D0%BD%D0%BE%233.doc
Украинцы отожгли: после штук 10-ти прочитанных доков на английском было удивительно найти точное подробное описание на русском.
Второй очень неплохой док на тему: http://www.ling.su.se/DaLi/talks/VBSA_SU.pdf
|
|
|
|
|
|
