Редактирование: UNИX, осень 2008, 11 лекция (от 10 декабря)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 42 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

= Артём Гавриченков. Заканчивание рассказа про DNs. =

Как устроен резолвинг доменных имён?
Есть некоторый список корневых серверов (официально, 11), есть ряд доменов первого уровня, это нац. домены (ru, us, fr, tv) и домены общего назначения (com, org, name).
Далее есть второго уровня и т.п..

== Типы записей ==

Также мы успели поговорить, что во время резолвинга запрашиваем запись определённого типа (например, если по имени необходимо получить IP адрес), один из трёх типов записей: A (IPv4), AAAA (IPv6), A6 (IPv6, deprecated).
Помимо этого есть ряд других типов записей: MX (ответственный за почту домен; за счёт этого работает доменная служба гугла (Google DomainService): она обращается к серверу и смотрит на MX-запись, а она должна указывать на гугл), SRV (запись для серверов, умеет то же, что и MX, но для любого сервиса).
Помимо этого, есть записи типа CNAME и PTR.

=== Запись CNAME ===
Что такое CNAME: предположим, есть какой-то такой сервер, например, uneex.ru, и хочется разместить ftp-сервер с доменным именем ftp.uneex.ru, но второй сервер мы не хотим заводить, поэтому мы пишем CNAME и в нём указываем домен, на который надо смотреть.
Есть ещё DNAME, он для зоны.

=== Запись PTR ===

Когда маленькие пушистые зверьки с Альдебарана были маленькими и пушистыми, был '''/etc/hosts''', у которого был очень простой формат.
Очень легко командой grep искалось не только соответствие имени хосту, но и хоста имени.
На основе этого даже работала кое-какая диагностика.

В году так 1994, когда DNS работал в полную силу (так, как сейчас), получить ip из системы dns хотя бы только по адресу типа A, можно было только следующим образом: пойти на первый попавшийся хост, посмотреть у него, пойти на след. и так далее.
Понятно, что это долго.
Кто-то посчитал, что это заняло бы несколько недель.
Поэтому была придумана запись PTR.

Допустим, есть следующая схема: есть маршрутизатор, который маршрутизирует 192.x.x.x, далее есть маршрутизатор 192.168.x.x, и так далее.
Можно заметить, что деревья похожи.

Собственно, их в RFC и объединили: ввели домен arpa, там поддомен in-addr, и далее ip: таким образом адрес 192.168.1.3 будет выглядить так: доменное имя строится от листа к корню (mirror.yandex.ru), таким же образом будем передавать записи типа PTR:
    3.1.168.192.in-addr.arpa.

Таким образом очень просто получить имя хоста по имени.
Кроме того, в RFC было записано, что для любого внешнего IP должна быть запись вида PTR.
На самом деле это выполняется не всегда.

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

Ещё бывает Forward Confirmed Reverse DNS.
Вот пришёл нам пакет с некоего адреса.
По PTR получаем dns, а по A получаем ip.
Тогда это FCRDNS, если ip совпали.

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

=== Ipv4 vs IPv6 ===
Всё это хорошо, красиво и прекрасно было, пока не началось ipv4 заканчиваться.
После чего начали раздавать не большие подсети, а поменьше.
И тогда появилась сложность.
Поскольку такая ситуация: нам выдали подсети из одной подсети C, в результате DNS один, а претендуют на него двое.
После чего была придумана такая вещь: вместо записи типа PTR будет выдаваться типа CNAME, и CNAME вида:
    1.corbin1.1.168.192 (для ip 192.168.1.1).

Почему в ipv6 всё лучше: там не делегируются подсети меньше /64.
Но при этом размер гранулирования --- полубайт:
    ...a.8.0.b.c.f.ip6.arpa.

== Про Whois ==

Адреса и подсети выдаются не абы каму.
Для каждого владельца адреса существует информация о нём (или о провайдере, который его выдал динамически).
Существует сервис, который позволяет выдать эту информацию для любого заданного адреса.
Есть утилита '''whois''' и http://ripe.net.
Можно запросить информацию о владельце адреса, о его контактных данных, адресе организации и так далее.

'''whois''' может использоваться не только для получения данных об ip, но и о доменном имени.
Это работает.

= Павел. RPC =

Рассказывает, потому что напросился, а Гоша разрешил.

Рассказывать парсер будет про RPC, и ему кажется, что он знает про rpc больше, чем некоторые из нас.

В википедии написано, что RPC позволяет вызывать функции в другом адресном пространстве, но это ни о чём не говорит.

== О концепции ==

Необходимость в RPC возникает по нескольким причинам:
* Когда она возникает (в 70-х годах, когда был бум производства машин, но в распределённых системах есть компьютеры послабже и посильнее, и кусок посложнее было бы круто считать на мощной машине)
* Решение задачи разделения ресурсов: принтеры, файлы, whatever

Если вспомнить как пишется каноническое сетевое приложение с беркли-сокетами, то это достаточно рутинная операция.

На самом деле, RPC это класс технологий, стандарта RPC нет, и каждый горазд создавать их сколько угодно, и их довольно много, не все созданные вещи плохи.

== ONC-RPC ==

Open Network Communication RPC, каноничный RPC, про который есть RFC.

Как обычно, разрабатывался раньше, чем проектировался.
И делать его начали для того, чтобы реализовывать NFS.
Идея появилась в 76 году, есть RFC 707.
В заголовке RFC заложено, что главное в нём --- разделение ресурсов.
В 86 была реализация от Sun, а в 88 было RFC.
Вторая версия появилась в 95 году.

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

Как осуществляется локальный вызов: у нас есть общеизвестное место, через которое передаём параметры, и откуда получаем результат (стек, регистры, память), дальше производится пляска, в стек записываются параметры, точка возврата и так далее, всё это известно, поскольку выполняется в одном адресном пространстве.
И что делать в случае чужого адресного пространства?
Можно отображать, но это бред.
Поэтому жёстко сказано, что всё предаётся по значению.

В связи с RPC есть два RFC: 1831, который определяет транспорт, и который определяет формат данных.

Почему так много реализаций RPC: RFC, который возможно является стандартом, гибкий, не накладывающий ограничений. 
Каноническая реализация --- вызов синхронный.
RFC не говорит о том, что это нужно делать синхронно, и все современные реализации асинхронны.

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

Как это работает. Чтобы вызвать на удалённом хосте удалённую функцию, нам нужно её идентифицировать: поэтому в RPC есть три беззнаковых значения:
* номер программы
* номер функции
* номер версии

Тут интересно то, что номера не возникают из бухты-барахты, а ими заведует тот же Sun.
Если вы написали программу и хотите, чтобы все о ней знали, то нужно написать e-mail на '''rpc@sun.com''' и сказать об этом.

== rpcinfo ==
Про утилиты, которые можно непосредственно использовать: самая главная утилита --- '''rpcinfo'''.
Она позволяет обращаться к серверу, на котором есть программа, которая использует удалённый вызов процедур, и получать с него информацию.

'''rpcinfo -p''' --- полезная опция: указываем имя хоста, по этой команде клиент подключается к удалённому серверу, запрашивает множество программ, по этим программам выдаются функции которые у них есть, с версиями и именами. Обычно там можно увидеть nfs.

Каким образом мы соединяемся с удалённым сервером: понятно, что rpcinfo соединяет по какому-то порту?
По какому?
Можно договориться, что используется такой-то порт, поэтому rpc выделен порт 111, где висит portmap, который и заведует всеми rpc-шными программами, и rpc-программы регистрируются в портмапе.

= Даниил Алеексеевский. Пиринговые протоколы. =

Третья часть доклада посвящена p2p, зовут дендика Алексеевский Даниил, и он имеет к этому некое косвенное отношение.

Дендик выбрал несколько конкретных протоколов, о которых стоит рассказать больше всего.

== Что такое p2p? ==
Это общая идея, как можно располагать данные в сети.
До этого все протоколы основывались на клиент-серверной парадигме.
В какой-то момент люди посмотрели на ситуацию с HTTP и увидели, что есть клиенты, которые с него постоянно что-то спрашивают, весь трафик в итоге ходит через канал сервера и серверу приходится много платить за трафик.
Но если клиентов много, то наверняка найдётся тот, у которого данные уже есть.
В этом и основная идея.

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

p2p-сети бывают разные по своей распределённости, и дендик начнёт с классификации.

Степени распределённости бывают такие:
* Централизованная сеть. Сеть, имеющая центр. Сеть, рассчитанная на то, что есть сервер, знает обо всех клиентах и у какого что есть. И когда приходит новый клиент, он спрашивает, где есть такой-то файл;
* Промежуточная стадия;
* Полностью децентрализованная. Клиент как-то приходит в сеть, поиском по сети пытается найти, что ему нужно. Такие сети бывают построены на разных алгоритмах, но ...

== EDonkey ==

Образовалась она неизвестно когда.
Как она устроена: по большей части это неизвестно, протокол закрытый, все реализации протокола ..., есть смутное понятие сервера и клиента.
Что творится между серверами, неизвестно.
Клиенты есть двух типов: те клиенты, которые имеют возможность открывать соединения и слушать порт (High ID) и те, которые такой возм. не имеют (Low ID).
Как происходит добыча данных из edonkey: во-первых, всякий файл ищется по его хэшу.
Хэш используется md4.
Во вторых: чтобы получить файл, сервер занимается поиском, как --- неизвестно, в результате ответ ---- качай с сервера или с high id.
Опять же неизвестно, могут ли серверы ретранслировать данные.
Данные можно нарезать на куски стандартного размера --- примерно 10к, ходят с хешом, можно получать распределённо.

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

== Развитие EDonkey ==

Далее, для развития edonkey люди начали изобретать свои протоколы.
Один из них --- Kademlia.
В основе лежит DHT --- Distributed Hash Table.
В чём её суть: сначала надо договориться о таких понятиях, как ID --- имя машины, Key и Value.
Договорённость первая --- это строки какой-то длины, и важно, что Id и ключи имеют равную длину.
Мы определяем функцию, которая по двум id или по паре id-ключ умеет находить расстояние.
На этих двух предположениях строится довольно простой способ, как искать данные в сети, про которую изначально почти ничего неизвестно, есть машины, с id, каждая машина хранит списки машин для каждого бита, у которых отличие в id начинается с данного бита. Поиск строится на 4 операциях: ping (проверить, что машина жива), store и find.
Можно попросить машину сохранить кусочек данных (если мы уже знаём её ip, порт).
Поиск ведётся следующим образом: для поиска сначала надо получить ключ, потом ищем по списку в каждом из концевых кругов, и в каждом круге примерно одинаковое количество соседей и подд. дост.ю надёжные. 
Сначала ищется во внутреннем круге, находим соседа и просим найти его соседа, самых близких к данному ключу, дальше для следующего и так далее. 
Понятно, как теперь найти машину, на которой хранится заданная битовая строчка. 
Теперь понятно, как это работает.

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

Трекер умеет выполнять только одну операцию --- какие клиенты с этим файлом ещё есть.
Обычно, на трекерах реализуются разные хитрые политики: ....

Bittorrent постоянно расширяется, и недавно запихали в него такую вещь, что некие клиенты сами являются трекерами.
И при этом поиск трекеров ведётся через DHT.

= Экзамен =
17 числа будет экзамен здесь, в 6 часов.

Нужно посылать письмо на адрес george@po.cs.msu.su с темой Экзамен за два-три дня.

На uneex.ru/LecturesCMC это написано.

= Конспект Kda: =

Георгий Владимирович уехал в Петербург и попросил его заменить на лекцию.
Начинает Артем Гавриченков.
Продолжение рассказа про DNS.

Как принципиально устроено разрешение доменных имен?
Есть корневой сервер, которых 12.
Есть ряд доменов первого уровня.
Это национальные домены (ru, ...) и домены общего назначения (org, com, ...).
Запрашиваем IP.
Есть типы записей: A, AAAA, A6 (не используется).
Первое — IPv4, второе — IPv6.
Есть и другие типы записей, например, MX — почтовый сервер.
Также есть запись типа SRV, у нее специфичный формат записи.
Она умеет то же, то и MX, но для других служб типа Jabber.
Есть записи типа CNAME и PTR.

CNAME.
Допустим, есть сервер uneex.ru.
Есть желание разместить там FTP с названием ftp.uneex.ru.
Сервер тот же самый, с нагрузкой мы справимся, но доменное имя другое.
Мы создаем запись CNAME с указанием смотреть на uneex.ru.
Допустим, мы перевезли сервер в другое место с другим IP.
Тогда достаточно поменять один адрес, остальные обновятся автоматически.
Есть также DNAME, позволяющие перенаправлять доменную зону, но речь не об этом.

Основной разговор про PTR.
Когда-то давно был файл с именами хостов.
Легко командой egrep искалось не только имя — адрес, но и адрес — сеть.
Диагностика сети — получение доменного имени по адресу.
В 94 году, когда уже работал DNS, кто-то подсчитал, что чтобы получить имя по сети последовательным перебором потребовалось несколько недель, что много для диагностики сети.
Тогда была придуман PTR.
Как вообще устроен Интернет на протоколе IP?
Есть маршрутизатор, маршрутизирующий 192, затем маршрутизатор для 192.168, затем 192.168.1, и уже наш хост.
IP можно представить в виде дерева, как и DNS.
Придумали объединить эти деревья.
Домен arpa, в нем in-addr.
mirror.yandex.ru строится в виде дерева.
yandex.ru, затем ru.
Здесь аналогично строим имя, которое будет отдавать в поиск записи типа PTR.
Строим наоборот 3.1.168.192.in-addr.arpa.
Становится легко получить имя хоста по запросу такого вида.
В RFC было записано, что любому хосту, доступному из Интернет должна соответствовать запись типа PTR.
Должен быть ответ, хотя бы один.
Это не выполняется по ряду причин, хотя бы по безалаберности провайдеров.
Реально Интернет не соответствует RFC и, наверное, не будет.

Благодаря этому появилась чудесная возможность для фильтрации спама.
Появилось некоторого рода соглашение.
Пусть не любой хост имеет обратный адрес, но его должен иметь любой хост, который хочет отправлять почту.
Если нет обратного адреса, это спам с очень высокой вероятностью.
Forward Confirmed Reverse DNS.
Пришел пакет от человека с неким IP.
Делаем запрос на запись PTR, получили доменное имя, сделали запрос по доменному имени.
Если хотя бы одна доменная запись разрешается совпадающим IP адресом с исходным, считаем, что все хорошо.
Если совпадений нет, то, скорее всего, это спамер.
Если у нас есть множественное соответствие, нас устроит хотя бы одно совпадение.

Все это было хорошо, пока пространство имен IPv4 не начало заканчиваться.
Стали раздавать подсети на 4 компьютера и пр.
Допустим, в одной подсети провайдер выделил нам и еще кому-то адреса.
Но DNS-сервер один, и к нему должны иметь доступ оба.
Было написано RFC, там чудесная вещь.
Вместо того, чтобы DNS-сервер отвечал на запросы, прописали записи на каждый IP.
Нужно иметь доступ к изменению записей и нам, и другому человеку.
Вместо A выдается CNAME.
CNAME будет вида corbina.1.168.192.in-addr.arpa.
Один раз записываем и забываем как провайдер верхнего уровня.
Дальше провайдер нижнего уровня разберется сам.
Это менее красиво, куча страшных записей CNAME, все немного медленнее, но работает.

В IPv6 все намного лучше.
ip6.arpa такого иметь не будет, потому что в IPv6 запрещено делегировать подсети менее 64 бита пустоты.
Все будет красиво и хорошо, если не считать того, что в IPv6 адрес намного длиннее, но его еще и записывают по другому.
В IPv6 запись адреса идет по 4 бита.
...b.a.2.e.f.f.ip6.arpa.
Пишем не по 8 бит, а по 4.

IP-адреса и подсети выдаются не абы кому, они выдаются организациям, затем людям.
Для каждого адреса есть информация хотя бы не о нем, а о провайдере, который выдал ему адрес.
Существует сервис, позволяющий получить информацию об адресе.
В большинстве никсов существует whois.
Также существует http://ripe.net.
Можно запросить информацию о владельце, его контактных данных и пр.
Whois не только для данных об адресе, но и для получения данных о доменном имени.
Какие-то данные, хотя бы о провайдере, всегда получим.

Выступает Павел.
Рассказ о удаленном вызове процедур.
Что такое RPC?
Как написано в Википедии, четкого определения нет.
Откуда пошло RPC?
Необходимость возникла по нескольким причинам.
К моменту возникновения RPC произошел бум вычислительных способностей.
В распределенных систем есть компьютеры послабее и посильнее.
Кусок задачи, обладающий большей сложностью, хорошо считать на более мощной машине.
Другое применение — задача разделения ресурсов.
Принтеры, файлы, еще что-то.
Если мы вспомним канонические приложения с сокетами, там много работы с открытие сокетов, передачей сырых данных.
Нужно решать задачу перевода одних данных в другие.
RPC — это класс технологий.
Каждый горазд создавать такие технологии, и их очень много.
Канонический RPC — ONC (Open Network Communication).
Самое главное — он разрабатывался раньше, чем проектировался.
Архитектуры под ним не было, его просто начали делать.
Его реализовали в Sun, чтобы лучше было разрабатывать NFS.

Главная задача — разделение ресурсов.
Актуальная сейчас версия появилась в 95 году.
Чем удаленный вызов процедур отличается от локального?
В локальном вызове есть известное место, через которые мы передаем процедуре параметры и через которое получаем.
Это стек, регистры, память.
Записываются параметры, точки возврата.
Программа в одном адресном пространстве.
Что делать, если адресное пространство другое?
Можно отображать адресное пространство, но это бред.
Данные передаются по значению.
Передавать данные по указателю глупо, это не работает.

RFC 1831 определяет транспорт, что-то вроде СПД.
RFC 1832 определяет формат представления данных.
Почему так много реализаций?
RFC очень гибкий и не накладывает серьезных ограничений.
Каноническая реализация — синхронный вызов процедуры.
RFC не говорит об этом, сейчас в основном реализация асинхронная.
Допустим, мы реализуем над UDP.
Нет никаких гарантий.
Сформировали пакет, заблокировались.
Таймаут прошел, снова послали.
Ничего не произошло.
Непонятно, сколько раз была вызвана удаленная процедура.
Стандарт все же налагает ограничения на транспорт.
Одно из трех — средство сопоставления ответов с запросами.

Прикладное применение RPC.
Функции RPC обычно формируются в программах.
Чтобы вызвать удаленную функцию, ее нужно идентифицировать.
В RPC-пакете есть три целочисленных значения — номер программы, номер функции и версия.
Интересно, что номера программ возникают не с бухты-барахты, а ими заведует Sun.
Нужно написать им письмо, чтобы они дали номер.

Утилиты.
Утилита rpcinfo.
Получение информации об RPC.
Запрашивается множество программ, использующих RPC, предоставляется список программ с функциями.
Каким образом мы соединяемся с удаленным сервером?
По какому-то порту.
Можем договориться, но договориться с большим количеством людей невозможно.
Для RPC выделены порты для TCP и UDP.
На них вешается программа, регистрирующая программы.
Клиент подключается на 111 порт и запрашивает информацию.

Выступает Алексеевский Даниил.
Рассказ о p2p.
Общая идея о распространении данных в сети.
Все было основано на распространении данных по модели клиент-сервер.
Посмотрели на работу HTTP, получилось, что есть сервер, у которого все запрашивают.
Серверу придется очень много платить за трафик, а клиенту мало.
Если клиентов много, есть вероятность, что у кого-то найдется то, что нужно другим.
P2p сети бывают очень разные по степени распределенности.

С точки зрения одной из систем, степени распределенности бывают такие.
Centralized.
Есть сервер, знающий все про клиентов сети, и у какого клиента что есть.
Есть промежуточные стадии и есть полностью децентрализованные сети, когда все клиенты равны.
Нужно знать кого-либо из клиентов, чтобы подключиться.

Сеть eDonkey.
Как она устроена и с чего начиналась?
По большей части это неизвестно.
Протокол закрытый.
Протокол имеет смутное понятие сервера и смутное понятие клиента.
Что творится между серверами, неизвестно никому и никак.
Есть клиенты двух типов, а именно имеющие возможность открывать порт и слушать (HighID), а также не имеющие такой возможности (LowID).
Общая идея следующая.
Каждый файл ищется по его хэшу (MD4).
Как происходит поиск, неизвестно.
Выдастся либо сервер, либо указание качать откуда-то.
Неизвестно, есть ли элемент ретрансмиттинга данных.
В протоколе говорится, что данные можно нарезать на куски стандартного размера (10Кб), каждый передается со своим хэше, получать можно распределенно.

Некоторым неизвестность не нравилась, стали улучшать клиенты.
Стало возможным соединяться с другими клиентами, возможно, даже без участия сервера.
Это чревато, потому что нестандартизованные расширения — два экземпляра одной программы могут договариваться, и практически все.
Поиска не было в серверах изначально, а появились только с неофициальными серверами.
Некоторые клиенты стали изобретать свои протоколы.
Kademlia.
На самом деле это не протокол, а способ построения.
Используется в Kad, Overnet, BitTorrent.
Kademlia — синоним распределенной хэш-таблицы (DHT, Distributed Hash Table).

В чем суть?
Строится на красивой математике.
В начале договариваемся о компоненте ID (имя машины), ключи (Key), по которым ищем и значения (Value).
Важно, что ID машины и ключи имеют одинаковую битовую длину.
Вторая договоренность — определяем функцию нахождения расстояния между двумя числами.
Любая функция, удовлетворяющая аксиомам расстояния, удовлетворяет.
Как искать данные в сети, про которую изначально почти ничего не известно?
Для каждого бита мы храним данные про соседей, для которых различие по этому биту самое старшее.
Допустим, есть сеть, мы находимся в ней.
Мы храним серию концентрических кругов вокруг нас.
Основная операция Kademlia строится на четырех операциях.
Первая — ping, машина жива и поддерживает Kademlia.
Реально используются Store (попросить хранить) и Find (поиск, самое интересное).

Для каждой машины хранится примерно одинаковое количество соседей.
Ищем наиболее вложенный из кругов, в который входит ключ.
Ищем соседей, ближайших к искомому, получаем ответы, и т.д.
Как строится сеть?
Получение куска файла.
Компьютер приходит, имея файл.
Говорит, что по этому хэшу живет файл у него.
Мы получили хэш, идем в сеть.
Ищем машину от общего к частному.
Получаем ответ о хранении данных на машине.

Поиск по метаданным.
Имя файла разбивается на слова, каждое слово превращается в хэш, записываем ID.
Ищем, получаем список машин с данным хэшем.

BitTorrent.
Возник протокол BitTorrent.
Заходим на HTTP-сайт, который дает файл .torrent.
Общение начинается с файла .torrent.
Версии бывают не совместимы.
Файл содержит информацию о том, на какие фрагменты (какого размера) разрезан файл.
Содержит адрес трекера.
Список файлов с их размером.
Также хранится хэш для каждого кусочка (chunk).

Tracker.
Сообщает клиенту, у каких клиентов есть куски файла.
На трекерах реализуют хитрые политики — сообщать клиенту в первую очередь, где находятся наиболее редкие чанки.
Недавно ввели следующую систему.
Некоторые клиенты могут являться сами по себе трекерами.
Поиск по трекерам ведется через Kademlia.

17 числа будет экзамен здесь, в 6 часов.
Нужно посылать письмо на адрес george@po.cs.msu.su с темой Экзамен за два-три дня.
На uneex.ru/LecturesCMC это написано.
Письмо должно прийти в течение этой недели (окончательная версия).

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/UN%D0%98X%2C_%D0%BE%D1%81%D0%B5%D0%BD%D1%8C_2008%2C_11_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_10_%D0%B4%D0%B5%D0%BA%D0%B0%D0%B1%D1%80%D1%8F%29

Редактирование: UNИX, осень 2008, 11 лекция (от 10 декабря)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 153: / Строка 153: @@
 * Централизованная сеть. Сеть, имеющая центр. Сеть, рассчитанная на то, что есть сервер, знает обо всех клиентах и у какого что есть. И когда приходит новый клиент, он спрашивает, где есть такой-то файл;
 * Промежуточная стадия;
-* Полностью децентрализованная. Клиент как-то приходит в сеть, поиском по сети пытается найти, что ему нужно. Такие сети бывают построены на разных алгоритмах, но нужно знать кого-либо из клиентов, чтобы подключиться
+* Полностью децентрализованная. Клиент как-то приходит в сеть, поиском по сети пытается найти, что ему нужно. Такие сети бывают построены на разных алгоритмах, но ...
 == EDonkey ==
@@ Строка 160: / Строка 160: @@
 Как она устроена: по большей части это неизвестно, протокол закрытый, все реализации протокола ..., есть смутное понятие сервера и клиента.
 Что творится между серверами, неизвестно.
-Клиенты есть двух типов: те клиенты, которые имеют возможность открывать соединения и слушать порт (High ID) и те, которые такой возможности не имеют (Low ID).
+Клиенты есть двух типов: те клиенты, которые имеют возможность открывать соединения и слушать порт (High ID) и те, которые такой возм. не имеют (Low ID).
+Как происходит добыча данных из edonkey: во-первых, всякий файл ищется по его хэшу.
-Как происходит добыча данных из edonkey:
+Хэш используется md4.
-* всякий файл ищется по его хэшу. Хэш используется md4.
+Во вторых: чтобы получить файл, сервер занимается поиском, как --- неизвестно, в результате ответ ---- качай с сервера или с high id.
-* чтобы получить файл, сервер занимается поиском, как --- неизвестно, в результате ответ ---- качай с сервера или с high id.
 Опять же неизвестно, могут ли серверы ретранслировать данные.
 Данные можно нарезать на куски стандартного размера --- примерно 10к, ходят с хешом, можно получать распределённо.
@@ Строка 171: / Строка 170: @@
 Например, держать у себя список клиентов и обмениваться с соседями.
 В конце концов, некоторые программы могут существовать в таком режиме: получить списки клиентов и общаться только с клиентами, не трогая сервера.
 Но это опять-таки чревато и неприятно, поскольку это нестандартное расширение, по которому могут договориваться разве что два экземпляра одной программы.
 Ещё одна важная фишка: в нём каким-то образом реализован поиск на серверах, причём, судя по всему, поиска не было до первого неофициального сервера.
@@ Строка 180: / Строка 178: @@
 Один из них --- Kademlia.
 В основе лежит DHT --- Distributed Hash Table.
 В чём её суть: сначала надо договориться о таких понятиях, как ID --- имя машины, Key и Value.
 Договорённость первая --- это строки какой-то длины, и важно, что Id и ключи имеют равную длину.
 Мы определяем функцию, которая по двум id или по паре id-ключ умеет находить расстояние.
+На этих двух предположениях строится довольно простой способ, как искать данные в сети, про которую изначально почти ничего неизвестно, есть машины, с id, каждая машина хранит списки машин для каждого бита, у которых отличие в id начинается с данного бита. Поиск строится на 4 операциях: ping (проверить, что машина жива), store и find.
-На этих двух предположениях строится довольно простой способ, как искать данные в сети, про которую изначально почти ничего неизвестно, есть машины, с id, каждая машина хранит списки машин для каждого бита, у которых отличие в id начинается с данного бита.
-Поиск строится на 4 операциях:
-* ping (проверить, что машина жива)
-* store
-* find_node - искать N штук ID, самых ближних к ключу
-* find_value - то же, но заодно и искать по ключу у себя
 Можно попросить машину сохранить кусочек данных (если мы уже знаём её ip, порт).
-Поиск ведётся следующим образом: для поиска сначала надо получить ключ, потом ищем по списку в каждом из концевых кругов, и в каждом круге примерно одинаковое количество соседей и подд. дост. надёжные.
+Поиск ведётся следующим образом: для поиска сначала надо получить ключ, потом ищем по списку в каждом из концевых кругов, и в каждом круге примерно одинаковое количество соседей и подд. дост.ю надёжные.
 Сначала ищется во внутреннем круге, находим соседа и просим найти его соседа, самых близких к данному ключу, дальше для следующего и так далее.
 Понятно, как теперь найти машину, на которой хранится заданная битовая строчка.
@@ Строка 202: / Строка 190: @@
 == bit torrent ==
 Возник протокол где-то в 2001 году, строился он именно вокруг этой самой идеи.
+Он состоит из двух частей: чисто клиент-серверный протокол, у которого есть трекер, и есть клиенты, которые к нему подключены.
-Он состоит из двух частей:
-* чисто клиент-серверный протокол, у которого есть трекер
-* клиенты, которые к нему подключены
 Общение с торрентом начинается с .torrent, который содержит два поля: всякая метаинформация, например, на какие фрагменты нарезан файл, адрес трекера, поле, которое содержит метаинформацию о файлах --- список файлов и их размер, и в торренте хранится хэш каждого кусочка (чанка).