Таненбаум Э. Распределенные системы. Принципы и парадигмы
Подождите немного. Документ загружается.
DISTRIBUTED
SYSTEMS
PRINCIPLES AND PARADIGMS
Andrew S. Tanenbaum,
Maarten van Steen
Prentice Hall PTR
Upper Saddle
River,
New Jersey 07458
www.phptr.com
НЛРССИНП COmPUTER SCIENCE
Э. ТАНЕНБАУМ,
М. ван
СТЕЕН
РАСПРЕДЕЛЕННЫЕ
СИСТЕМЫ
ПРИНЦИПЫ и ПАРАДИГМЫ
1:^ППТЕР
®
Москва • Санкт-Петербург • Нижний Новгород • Воронеж
Ростов-на-Дону • Екатеринбург • Самара
Киев - Харьков - Минск
2003
ББК 32.973.202
УДК 681.324
Т18
Т18 Распределенные системы. Принципы и парадигмы / Э. Таненбаум,
М. ван Стеен. — СПб.: Питер, 2003. — 877 с: ил. — (Серия «Классика computer
science»).
ISBN 5-272-00053-6
Эта книга является фундаментальным курсом
по
распределенным системам.
В ней
детально
описаны принципы, концепции
и
технологии этих систем: связь, процессы, синхронизация,
целостность
и
репликация, защита
от
сбоев
и
безопасность. Особое внимание
в
книге уделено World
Wide
Web,
развитие которой
и
послужило толчком
к
резкому повышению интереса
к
распре-
деленным системам. Как это характерно для всех книг Э.Таненбаума, последовательное
и
детальное
изложение теории сопровождается примерами реально действующих систем.
Книга предназначена прежде всего студентам
и
преподавателям,
но,
безусловно, будет полезна
и специалистам данной области.
ББК 32.973.202
УДК 681.324
Информация, содержащаяся
в
данной книге, получена
из
источников, рассматриваемых издательством
как
надежные.
Тем не
менее, имея
в
виду возможные человеческие
или
технические ошибки, издательство
не
может гарантировать абсолютную
точ-
ность
и
полноту приводимых сведений
и не
несет ответственности
за
возможные ошибки, связанные
с
использованием книги.
© 2002
by
Prentice-Hall,
Inc.
ISBN 0-13-088893-1 (англ.)
©
Перевод
на
русский язык, ЗАО Издательский дом «Питер», 2003
ISBN 5-272-00053-6
©
Издание на русском языке, оформление, ЗАО Издательский дом «Питер», 2003
Краткое содержание
Об авторах 14
Предисловие 16
Руководство по использованию книги 18
Глава 1. Введение 22
Глава 2. Связь 81
Глава 3. Процессы 164
Глава 4. Именование 214
Глава 5. Синхронизация 274
Глава 6. Непротиворечивость и репликация 328
Глава 7. Отказоустойчивость 403
Глава 8. Защита 458
Глава 9. Распределенные системы объектов 539
Глава 10. Распределенные файловые системы 623
Глава
11.
Распределенные системы документов 699
Глава 12. Распределенные системы согласования 752
Глава 13. Библиография 790
Список терминов 833
Алфавитный указатель 855
Содержание
Об авторах 14
Предисловие 16
От издательства 17
Руководство по использованию книги 18
Курсы для студентов старших курсов и дипломников 18
Семинары для профессионалов 19
Первый день 20
Второй день 20
Самостоятельное изучение 20
Глава 1. Введение 22
1.1.
Определение распределенной системы 23
1.2. Задачи 25
1.2.1.
Соединение пользователей с ресурсами 25
1.2.2.
Прозрачность 26
1.2.3.
Открытость 30
1.2.4.
Масштабируемость 31
1.3. Концепции аппаратных решений 38
1.3.1.
Мультипроцессоры 40
1.3.2.
Гомогенные мультикомпьютерные системы 42
1.3.3.
Гетерогенные мультикомпьютерные системы 44
1.4. Концепции программных решений 45
1.4.1.
Распределенные операционные системы 46
1.4.2.
Сетевые операционные системы 57
1.4.3.
Программное обеспечение промежуточного уровня 60
1.5. Модель клиент-сервер 67
1.5.1.
Клиенты и серверы 67
1.5.2.
Разделение приложений по уровням 72
1.5.3.
Варианты архитектуры клиент-сервер 75
1.6. Итоги 78
Вопросы и задания 79
Глава 2. Связь 81
2.1.
Уровни протоколов 82
2.1.1.
Низкоуровневые протоколы 85
2.1.2.
Транспортные протоколы 87
2.1.3. Протоколы верхнего уровня 90
2.2.
Удаленный вызов процедур ' 93
2.2.1.
Базовые операции RPC 94
2.2.2.
Передача параметров 98
2.2.3. Расширенные модели RPC 103
2.2.4. Пример - DCE RPC 106
2.3.
Обращение к удаленным объектам 111
2.3.1.
Распределенные объекты 112
2.3.2.
Привязка клиента к объекту 114
2.3.3. Статическое и динамическое удаленное обраш^ение к методам 117
2.3.4. Передача параметров 118
Содержание
2.3.5. Пример
1
-—удаленные объекты DCE 120
2.3.6. Пример 2 —Java RMI 122
2.4.
Связь посредством сообщений 126
2.4.1.
Сохранность и синхронность во взаимодействиях 126
2.4.2.
Нерезидентная связь на основе сообщений 131
2.4.3. Сохранная связь на основе сообщений 136
2.4.4. Пример — IBM MQSeries 143
2.5. Связь на основе потоков данных 148
2.5.1.
Поддержка непрерывных сред 148
2.5.2.
Потоки данных и качество обслуживания 151
2.5.3. Синхронизация потоков данных 156
2.6.
Итоги 159
Вопросы и задания 160
Глава 3. Процессы 164
3.1.
Потоки выполнения 165
3.1.1.
Знакомство с потоками выполнения 165
3.1.2. Потоки выполнения в распределенных системах 171
3.2. Клиенты 175
3.2.1.
Пользовательские интерфейсы 175
3.2.2. Клиентское программное обеспечение, обеспечивающее прозрачность
распределения 178
3.3. Серверы 179
3.3.1.
Общие вопросы разработки 179
3.3.2. Серверы объектов 183
3.4. Перенос кода 189
3.4.1.
Подходы к переносу кода 189
3.4.2. Переноси локальные ресурсы 194
3.4.3. Перенос кода в гетерогенных системах 197
3.4.4. Пример —
D'Agent
199
3.5. Программные агенты 204
3.5.1.
Программные агенты в распределенных системах 205
3.5.2. Технология агентов 207
3.6. Итоги 210
Вопросы и задания 212
Глава 4. Именование 214
4.1.
Именованные сущности 215
4.1.1.
Имена, идентификаторы и адреса 215
4.1.2.
Разрешение имен 220
4.1.3.
Реализация пространств имен 225
4.1.4.
Пример —система доменных имен 232
4.1.5.
Пример —Х.500 237
4.2.
Размещение мобильных сущностей 241
4.2.1.
Именование и локализация сущностей 241
4.2.2.
Простые решения 244
4.2.3.
Подходы на основе базовой точки 247
4.2.4.
Иерархические подходы 249
4.3.
Удаление сущностей, на которые нет ссылок 256
4.3.1.
Проблема объектов, на которые нет ссылок 257
4.3.2.
Подсчет ссылок 258
4.3.3.
Организация списка ссылок 263
4.3.4.
Идентификация сущностей, на которые нет ссылок 264
8 Содержание
4.4.
Итоги 270
Вопросы и задания 271
Глава 5. Синхронизация 274
5.1.
Синхронизация часов 275
5.1.1.
Физические часы 276
5.1.2. Алгоритмы синхронизации часов 280
5.1.3. Использование синхронизированных часов 284
5.2. Логические часы 285
5.2.1.
Отметки времени Лампорта 286
5.2.2. Векторные отметки времени 290
5.3. Глобальное состояние 292
5.4. Алгоритмы голосования 296
5.4.1.
Алгоритм забияки 296
5.4.2. Кольцевой алгоритм 298
5.5. Взаимное исключение 299
5.5.1.
Централизованный алгоритм 299
5.5.2. Распределенный алгоритм 300
5.5.3. Алгоритм маркерного кольца 303
5.5.4. Сравнение трех алгоритмов 304
5.6. Распределенные транзакции 305
5.6.1.
Модель транзакций 306
5.6.2. Классификация транзакций 309
5.6.3. Реализация 312
5.6.4. Управление параллельным выполнением транзакций 315
5.7. Итоги 324
Вопросы и задания 325
Глава 6. Непротиворечивость и репликация 328
6.1.
Обзор 329
6.1.1.
Доводы в пользу репликации 329
6.1.2. Репликация объектов 331
6.1.3. Репликация как метод масштабирования 333
6.2. Модели непротиворечивости, ориентированные
на
данные 335
6.2.1.
Строгая непротиворечивость 336
6.2.2. Линеаризуемость и последовательная непротиворечивость 338
6.2.3. Причинная непротиворечивость 343
6.2.4. Непротиворечивость FIFO 344
6.2.5. Слабая непротиворечивость 346
6.2.6. Свободная непротиворечивость 348
6.2.7. Поэлементная непротиворечивость 351
6.2.8. Сравнение моделей непротиворечивости 353
6.3. Модели непротиворечивости, ориентированные на клиента 355
6.3.1.
Потенциальная непротиворечивость 356
6.3.2. Монотонное чтение 358
6.3.3. Монотонная запись 359
6.3.4. Чтение собственных записей 361
6.3.5. Запись за чтением 362
6.3.6. Реализация 363
6.4. Протоколы распределения 365
6.4.1.
Размещение реплик 366
6.4.2. Распространение обновлений 370
6.4.3. Эпидемические протоколы 374
Содержание
6.5. Протоколы непротиворечивости 377
6.5.1.
Протоколы на базе первичной копии 378
6.5.2. Протоколы реплицируемой записи 382
6.5.3. Протоколы согласования кэшей 386
6.6. Примеры 388
6.6.1.
Огса 388
6.6.2. Слабая причинно непротиворечивая репликация 394
6.7. Итоги 399
Вопросы и задания 400
Глава 7. Отказоустойчивость 403
7.1.
Понятие отказоустойчивости 404
7.1.1.
Основные концепции 404
7.1.2. Модели отказов 406
7.1.3. Маскирование ошибок при помощи избыточности 408
7.2. Отказоустойчивость процессов 410
7.2.1.
Вопросы разработки 410
7.2.2. Маскировка ошибок и репликация 413
7.2.3. Соглашения в системах с ошибками 414
7.3. Надежная связь клиент-сервер 417
7.3.1.
Сквозная передача 418
7.3.2. Семантика RPC при наличии ошибок 418
7.4. Надежная групповая рассылка 424
7.4.1.
Базовые схемы надежной групповой рассылки 424
7.4.2. Масштабируемость надежной групповой рассылки 426
7.4.3. Атомарная групповая рассылка 430
7.5. Распределенное подтверждение 437
7.5.1.
Двухфазное подтверждение 437
7.5.2. Трехфазное подтверждение 442
7.6. Восстановление 445
7.6.1.
Основные понятия 445
7.6.2. Создание контрольных точек 448
7.6.3. Протоколирование сообщений 452
7.7. Итоги 455
Вопросы и задания 456
Глава 8. Защита 458
8.1,
Общие вопросы защиты 459
8.1.1.
Угрозы, правила и механизмы 459
8.1.2. Вопросы разработки 465
8.1.3. Криптография 470
8.2. Защищенные каналы 478
8.2.1.
Аутентификация 478
8.2.2. Целостность и конфиденциальность сообщений 486
8.2.3. Защищенное групповое взаимодействие 490
З.З.Контрольдоступа 493
8.3.1.
Общие вопросы контроля доступа 493
8.3.2. Брандмауэры 497
8.3.3. Защита мобильного кода 499
8.4. Управление защитой 506
8.4.1.
Управление ключами 507
1 о Содержание
8.4.2. Управление защищенными группами 511
8.4.3. Управление авторизацией 512
8.5. Пример —Kerberos 518
8.6. Пример —SESAME 520
8.6.1.
Компоненты системы SESAME 521
8.6.2. Сертификаты атрибутов привилегий 523
8.7. Пример —электронные платежные системы 525
8.7.1.
Электронные платежные системы 525
8.7.2. Защита в электронных платежных системах 527
8.7.3. Примеры протоколов 531
8.8. Итоги 535
Вопросы и задания 537
Глава 9. Распределенные системы объектов 539
9.1.C0RBA
540
9.1.1.
Обзор 541
9.1.2.
Связь 547
9.1.3.
Процессы 554
9.1.4.
Именование 560
9.1.5.
Синхронизация 564
9.1.6.
Кэширование и репликация 565
9.1.7.
Отказоустойчивость 567
9.1.8.
Защита 569
9.2.DCOM
572
9.2.1.
Обзор 572
9.2.2.
Связь 578
9.2.3.
Процессы 581
9.2.4.
Именование 584
9.2.5.
Синхронизация 588
9.2.6.
Репликация 588
9.2.7.
Отказоустойчивость 588
9.2.8.
Защита 589
9.3.
Globe 592
9.3.1.
Обзор 592
9.3.2.
Связь 600
9.3.3.
Процессы 602
9.3.4.
Именование 604
9.3.5.
Синхронизация 607
9.3.6.
Репликация 607
9.3.7.
Отказоустойчивость 611
9.3.8.
Защита 611
9.4. Сравнение систем CORBA, DOOM и Globe 613
9.4.1.
Философия 613
9.4.2. Связь 615
9.4.3. Процессы 615
9.4.4. Именование 616
9.4.5. Синхронизация 617
9.4.6. Кэширование и репликация 617
9.4.7. Отказоустойчивость 618
9.4.8. Защита 618
9.5. Итоги 620
Вопросы и задания 621