|
|
1. Einführung und Motivation 导论以及动机分布式系统的定义：
A distributed system is a collection of independent computers that appears to its users as a single coherent system.
分布式系统是一种使许多独立电脑的协作在用户看来好像是在一台电脑上运作的一样的计算机系统。
最主要的两个角度：单个电脑成员的独立性和整个系统分布的透明性。
为什么要采用分布式系统?（优点）
Kommunikationsverbund
Uebertragung von Daten (Nachrichten) an verschiedene, raeumlich getrennte Orte
数据（消息）转送到不同的空间上分隔的地点 （EMAIL）
Informationsverbund
Verbreiten von Information an interessierte Personen
传播信息到感兴趣的人（WWW, Twitter）
Datenverbund
Speicherung von Daten an verschiedenen Stellen
将数据保存在不同地点——>更高的可用性、安全性等 （例如银行的数据库通常在不同地点有多份备份以避免因灾难而不能提供服务）
Lastverbund
Aufteilung stoweise anfallender Lasten auf verschiedene Rechner
将拥堵式积累的负荷分到不同的计算机上 （例如多个服务器可以防止爆发性的用户访问）
Leistungsverbund
Aufteilung von Anfragen in Teilaufgaben
将请求分成子任务 （可以更快的获得回复）
Wartungsverbund
Zentrale Stoerungserkennung und –behebung
中心式的故障得以识别和消除（尤其是系统的单点）
Funktionsverbund
Verteilung spezieller Aufgaben auf spezielle Rechener
将任务分配给不同的专用计算机 （例如图像处理等）
分布式系统所希望的性质包括： Offenheit 开发性，Nebenlaeufigkeit 并行性，Skalierbarkeit 可扩展性，Sicherheit 安全性，Fehlertoleranz 容错性，Transparenz 透明性。
其中透明性尤其重要。透明性可以有很多不同的角度来说明。但总的来说透明性就是让用户感觉不到自己是在一个分布式系统中工作。而透明性的种类包括：
1.Zugriff 存取：
Zugriff auf die Ressource erfolgt immer auf die gleiche Art und Weise (lokal oder entfernt)
资源的存取总是采用同样的方式和方法（本地或远程）
2. Ort 地点：
Verbirgt, wo sich eine Ressource befindet. Zugriff ueber Namen, die keine Ortsinformationen enthalten.
隐藏资源在何处。通过不包含地址信息的名字来实现存取。
3. Migration 迁移
Verschieben von Ressourcen ist fuer Benutzer und Anwendungen transparent.
资源的移动对于用户和应用来说是透明的。也就是说如果所要读取的数据实际上的位置已经发生了变化, 但用户却不知道。
4. Relokation 再定位
Verbirgt, dass eine Ressource an einen anderen Ort verschoben werden kann, waehrend sie genutzt wird.
5. Replikation 复制
Verbirgt, dass eine Ressource repliziert ist
隐藏资源是复制品。
6. Nebenlaeufigkeit 并发性
Verbirgt, dass eine Ressource von mehreren konkurrierenden Benutzern gleichzeitig genutzt werden kann.
隐藏资源可以同时被多个相互竞争的用户使用。
7. Fehler 错误
Verbirgt den Ausfall und die Wiederherstellung einer Ressource
隐藏某个资源的出错以及恢复。（例如某台服务器出错时由其它服务器接管从而让用户感觉不到曾经有出过故障。）
2. Protokolle und Schichtenmodelle 协议以及分层模型
服务和协议的区别：服务是在同一个程序的相邻两层之间进行的，而协议则是在同一层的不同程序（个体）间进行的。
因为通过网络的通讯时常出现问题，所以将复杂任务分解成很多层简单的层次，每一层都使用比它更底层的服务。
Protokoll --- Nachrichten + Verhaltensregeln（Zustandsautomat） 协议是消息加行为规则（有状态自动机）。
Schichtenbildung 分层:
-Aufteilung von Systemen in kleinere, weniger komplexe Teilsysteme 将系统分割成更小更简单的子系统
-Modularisierung / Austauschbarkeit 模块化 / 可更换性
-Prinzip zur Strukturierung verteilter Systeme 分布式系统的构建的原则
-Austausch von Nachrichten mit Instanzen auf gleicher Schicht 在同一层上的个体间的消息交换
-Nutzt zur Erbringung Dienste vertikal benachbarter Schichten 在垂直上相邻的层次间标准服务的使用
图1：ISO/OSI和TCP/IP两个标准的比较
这个图我想学过计算机网络的人都会很熟悉吧。可惜的是以前学的时候就没记住过。这次好了，还是的接着背。
ISO/OSI：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。
TCP/IP：网络接口层、网络互联层、传输层和应用层。
ISO/OSI vs TCP/IP:
ISO/OSI起源于电信网络的需求，其模型的分层更严格，并且要求子网提供无错和稳定的面向连接的服务。
Auf Bedürfnisse von Telekommunikationsfirmen zugeschnitten 按照电信公司的需求分层
Entworfen von formalen Standardisierungsgremien 由正式的标准委员会起草
Zeitaufwndiger Prozess mit oftmals komplexen Resultaten 费时的过程带来复杂效果
而TCP/IP从一开始就起始于计算机网络的世界从其子网固有的就不稳定。错误-及流控制都是上层即应用层的任务。
Hat entsprechend geeignete Programmierschnittstellen. 有相对应的合适的程序接口。
Implementierungen meist frei zugnglich. 程序的实现通常是自由接入的。
Groer Verbreitung und Verbesserungen in kurzen Zeitintervallen 在短时间内分布很广并且提升很大。
ISO/OSI到目前为止还是概念性的模型，而TCP/IP则是实际上的标准。
3. Nachrichtenrepraesentation 消息代理
问题：
1. Byte-Order (Host-/Network)
图2：（字节序）大端序和小端序的对比图
2.Groesse der Datentypen 数据类型的大小
在不同的系统和程序语言中数据类型的大小也是不同的。例如C语言中的unsigned int类型在PC是64位，在jennic是32位，而在MSP430则是16位。
3. Alignment 校准
在存储器中数据类型是“对齐”（aligned）记录的。比如某 CPU存取字的尺寸是4字节（每字节是8比特）。而某个数据是14字节的话就需要在读取之前进行一些处理，CPU才能进行工作。这往往是通过在上一个数据的尾部或者下一个数据的头部增加一些无意义的比特来实现的。
Serialisierungsverfahren 序列化的方法
-ASCII-basiert
-RFC 1014 (XDR)
-Abstract Syntax Notation One (ASN.1, DER)
-Extensible Markup Language (XML, XML Schema)
-JavaScript Object Notation (JSON)
-Objektserialisierung (Java,...)
XML
XML Schema示例
合法的XML文件示例
JSON：
{} 对象
： 名字和值的配对
， 名字-值对之间的分隔
JSON示例图
Kriterien zur Auswahl von Serialisierungstechnologien 选择序列化技术的标准
Gre der serialisierten Daten (Payloadgre“, Latenz)
Maschinen- und Menschenlesbarkeit
Validierbarkeit
Rechenaufwand
Komplexitt der Toolchain
Erweiterbarkeit (z.B. einzelne Felder hinzufügen)
Versionierung
Verbreitung (Standards, De-facto Standards)
Programmiersprachenunabhngigkeit
Verfügbarkeit für Programmiersprachen und Zielplattformen
Trennung von Nachrichten (Framing) 消息的分离 （框架）
出发点：
Sender schickt Nachrichten in Form eines Bytestroms 发送者发送以字节流的方式发送消息
Empfaenger liest Bytes aus Strom 接受者从流中读取出字节
由此产生的问题是：如何分出前后的消息？（即什么时候消息已经完整接收了？什么时候开始下个新的消息）
Framing: Verfahren zur Trennung 成帧：分段的方法
Rahmen markiert Anfang (und Ende) einer Nachricht 框架标识了一个消息的开始(和结束)
Framing ist bei Streams notwendig 成帧在字节流中的必须的
Namenskonventionen 命名规则
从下往上：
Frame : 帧
Datagram: 数据包
Segement : 段
Stream : 流
Message : 消息
-Nagle's Algorithm
在网络通讯中常常一次通讯的包里所要传送的信息（Body）远比实现通讯的附加（Header）要小的多。所以在实时性要求不高的时候累积到一定数量的信息（Body）之后再发送一个包的方式来提高效率。这就是Nagle's算法的思路。
4. Realisierung von Netzwerkdiensten 网络服务的实现
Sockets
5. Kommunikationsmechanismen 通信机制
基于消息的通讯
中间件的概念
RPC Remote Procedure Call 远程过程调用
分布式对象系统
Web Service
– A Web service is a software system designed to support interoperable machine-to-machine interaction over a network
Message Exchange Patterns (MEPs)
Verfügbare MEPs
– Input-Output Operation:
Request Response (Return-Wert oder Fault)
– Input-Only Operation:
Nur Request, keine Response (auch keine Faults)
– Output-Input Operations (Solicit Response):
Sendet Nachricht und erwartet eine bestimmte Antwort
– Output-Only Operations:
Nur “Response” Genutzt für Notifications
SOAP
Envelope enthlt SOAP-Header und SOAP-Body
– Header: Metadaten zur Behandlung der SOAP-Nachricht und Interpretation des Body
– Body: Serialisierter Nachrichteninhalt (z.B. RPC Request oder Response)
Web Service Definition Language (WSDL)
Beschreibungssprache zur Definition von Web Services
Abstrakter Teil
– Datentypen (XML Schema)
– Nachrichten (Referenziert Datentypen)
– PortType (Schnittstelle des Dienstes)
Referenziert Nachrichten
Menge von Operationen (Input, Output, Fault-Nachrichten)
Konkreter Teil
– Binding (Transportprotokoll und SOAP-Binding)
z.B. SOAP über HTTP mit document/literal
– Service (Konkrete Erreichbarkeit)
Definiert verschiedene Ports“
Port: Referenziert Binding, spezifiziert konkrete Adresse (z.B. Port 80)
REST Representational State Transfer
keine Technologie sonder eine Architekturkonzept
Statuslosigkeit
-Keine Client-spezifischen Daten auf dem Server
-Gleichzeitiger lesender Zugriff verschiedener Clients auf die gleiche Ressource führen zu Reprsentationen mit gleichem Status
-Alle notwendige Information ist in der Anfrage enthalten
Idempotenz
Mehrere gleiche Anfragen führen zum gleichen Folgestatus der Ressource wie eine einzige Anfrage
Beispiel: einzahlen(100)--nicht idenpotenz vs. setzeKontostand(100) -- idenpotenz
REST mit HTTP: HTTP-Methoden
Create, Read, Update, Delete
6. Adressen, Namen und Verzeichnisdienste 地址, 名字以及目录服务
Adressen 地址
包含地理信息，通常是用于寻址和选择路径的一串数字（例如IP地址 192.168.1.1）。适合机器阅读。
Namen 名字
用于区分的符号，通常是不包含地理信息的字符串（例如网站名www.google.com）。方便人的阅读和记忆。
Identifier 标识符
地址和名字的合称。 尤其是URI包括了URL和URN。
Adressen in VS
分布式系统中的地址
因为用名字比较易读好记，而且资源可以很方便的移动位置或者复制备份，所以对于用户来说基本上都以采用名字为主。
而名字是可以有结构和文法的。这就是所谓的命名空间（namespace）。
名字的结构分成两种：扁平式和分层式。
扁平式的实现很简单，适合小规模（例如Sun RPC/ONC RPC Portmapper）。
Sun RPC/ONC RPC Portmapper： Sun RPC在端口111；服务在此用自己的端口号进行注册；客户利用IP找到服务器并询问所需服务的端口号。
分层式的相对复杂一些（例如DNS和LDAP）。
DNS（Domain Name System）域名系统。曾经热极一时的抢注域名其实就是抢这东西里面的一个名字。
DNS结构示例图
如图所示DNS的结构类似于一棵倒置的树：根是空的/；然后是最上层域名（如com / de / cn）等；再就是下一层的域名（通常是公司或者机构名，例如uni-luebeck）；接下来会有一些子域名（通常对应子机构，例如ITM学院）。
解析一个域名的过程通常是这样的：
由客户发起查询（通常是用户在浏览器地址栏输入网址，如mail.google.com）；
浏览器自动调整所输入的网址（通常是在结尾处增加一个“.”）；
浏览器发给DNS服务器（Nameserver）一个查询报文 “ query mail.google.com ”；
DNS服务器首先检查自身缓存，如果存在记录则直接返回结果，如果记录老化或不存在，则向根域名(root zone)服务器发送查询报文"query mail.google.com"，根域名服务器返回 .com 域的权威域名服务器地址；
DNS服务器向 .com 域的权威域名服务器发送查询报文"query mail.google.org"，得到 .google.com 域的权威域名服务器地址
DNS服务器向 .google.com 域的权威域名服务器发送查询报文"query mail.google.org"，得到主机 zh 的A记录，存入自身缓存并返回给客户端。
不过域名的解析方式有两种：Iterative（重复）和 Rekursiv （递归）。上面所介绍的是重复，而递归则不需要重复使用命令来查询而是不断递归到最底层的mail的主机地址再返回。
目录服务
有的时候用户并不知道自己要的资源的名字，而只知道其特性。例如某个人想找披萨店，可是并不知道确切的某家店的名字。这个时候他就会去看黄页。在网络世界里也有类似的目录服务。例如在做搜索引擎优化的时候就会需要将自己的网页登记到雅虎的目录中以提高自己的分数。
接下来要介绍的是LDAP(Lightweight Directory Access Protocal)
LDAP-Server LDAP服务器
Verzeichnisdienst, der über LDAP angesprochen wird；Speichert Menge von Entries
提供LDAP目录服务；保存有大量的条目
LDAP Entry LDAP条目
Enthlt Menge von Attributen; Kann wieder Entries enthalten; Eindeutig identifizierbar über Distinguishd Name
包括大量的属性；条目下可以再包括条目；通过DN（区别名）来唯一识别
LDAP-Namensraum LDAP命名空间
Baumfrmig organisiert；Voll qualifizierte Namen werden von unten nach oben gelesen
树状的组织；完整的名字是从下往上读的(如下图中uid=pfisterer, ou=people, dc=itm, dc=uniluebeck.de, dc=de)
Relative Distinguished Name ( Relative DN)
Linker Teil: uid=pfisterer
Base Distinguished Name (Base DN)
DN ohne RDN: ou=people, dc=itm, dc=uniluebeck.de, dc=de
LDAP示例图
7. Synchronisation 同步
Cristian算法
NTP(Network Time Protocol) 网络时间协议
网络上的计算机被分成很多层
最上层为原子钟
当前层的计算机的时间和其上一层的计算机同步
时间同步的极限：
问题：不同的电脑上的时钟不可能完美同步，而有的时候我们又需要判断两件事情发生的先后顺序
解决思路：逻辑时间
Happened-Before
In computer science, the happened-before relation (denoted:  ) is a relation between the result of two events, such that if one event should happen before another event, the result must reflect that even if those events are in reality executed out of order (usually to optimize program flow).
Lamports happened-before关系的说明：
如果在某个处理器P中 a b 成立则对于整个系统来说 a b 也成立；
对于一个消息m来说 send(m) receive（m）总是成立的；
对于整个系统来说 如果a b 并且 b c成立则 a c也一定成立。
弱一致性： 如果 a b 则 C(a) < C(b)
强一致性： 如果C(a) < C(b) 则 a b
实现：
用伪码实现Happened before
在三个处理器上采用happened before的效果图
Vektoruhren (Lamport的扩展)
Vektoruhren的示意图
那如何比较呢？ 
次序的定义（比较方法）
Gegenseitiger Ausschluss （共有消除/ mutual exclusion）
如何解决多个处理器操作同一个数据导致数据可能不一致的情况？
1. Zentralisierter Algorithmus --> einfach implementieren aber single-point
2. Verteilter Algorithmus (ohne Koordinator) --> komplex, langsam und wenige Robust
3. Token-Ring-Algorithmus --> korrekt und fair aber Verlust eines Tokens ist schwer zu erkennnen
Global State
Consistent und Inconsistent Cut
Frontier
Ein Cut ist dann konsistent, wenn
– er für jedes Ereignis, das er enthlt, auch alle Ereignisse enthlt,
– die zu diesem Ereignis in der Happened-Before-Relation (s. Zeit in verteilten Systemen) stehen:
e ∈ C , f → e f ∈ C
Lamport/Chandy-Algorithmus
Auswahlalgorithmen
Zweck von Auswahlalgorithmen : Einen Prozess unter vielen gleichartigen bestimmen, der eine besondere Rolle übernimmt
Bully-Algorithmus
Ring-Algorithmus
Prozesse sind logisch als Ring organisiert
– Jeder Prozess besitzt einen Vorgnger und einen Nachfolger
– Entsprechend aufsteigender Prozessnummern
Prozess stellt fest, dass der Koordinator ausgefallen ist
– Sendet ELECTION-Nachricht auf den Ring
– In diese trgt er sich als ersten ein
– Jeder weitere aktive Prozess fügt sich selbst in die Liste ein
Nachricht trifft wieder beim Initiator ein
– Er wandelt diese in eine KOORDINATOR-Nachricht um
– Diese enthlt den neuen Koordinator und die aktiven Mitglieder
8. Replikation und Konsistenz 拷贝以及坚固性
优点：性能、容错以及可用性 （拷贝的坚固性非常重要）
问题：1.很多拷贝 2. 强地理分布 3. 经常性的写入操作 于是陷入进退两难的困境（Dilemma）中，一边要提高性能和可扩展性，一边必要的措施又降低性能。
解决方案：唯一的解决方案就是降低坚固性的要求（非严格坚固性）。
在数据存储器和读写数据的处理器间的协议：
以数据为中心的坚固性模型 – Sicht des Datenspeichers, geeignet für parallele Schreibzugriffe
Strikte Konsistenz (Daten-zentriert) : Jedes Read liefert Wert der letzten Write-Operation
Sequentielle Konsistenz : Etwas schwcheres Modell, aber implementierbar
– Es greifen mehrere nebenlufige Prozesse auf Daten zu
– Jede gültige Kombination von Read- und Write-Operationen ist akzeptabel, solange alle Prozesse dieselbe Folge sehen
– Zeit spielt keine Rolle
Kausale Konsistenz : Schwcheres Modell als die sequentielle Konsistenz
- mit Kausalitt (mit read operation)
- ohne Kausalitt
以客户为中心的坚固性模型
– Sicht des Client mit weniger starken Annahmen
– Insbesondere keine gleichzeitigen Updates
Monotones Lesen (Client-zentriert)
Wenn ein Prozess den Wert einer Variable x liest, dann wird jede weitere Read-Operation denselben oder einen neueren Wert von
x liefern
Monotones Schreiben
Oft wichtig, dass Schreiboperationen in der richtigen Reihenfolge an alle Dateispeicher weitergeleitet werden
Eine Schreiboperation eines Prozesses auf ein Datenelement x wird abgeschlossen, bevor eine folgende Schreiboperation
auf x durch denselben Prozess erfolgen kann
Platzierung der Replikate
Unterscheidung drei verschiedener Arten von Kopien
– Permanente Replikate --> Meist nur sehr wenige Replikate
– Server-initiierte Replikate --> Meist in der (Netz-)Gegend, in der der Bedarf auftritt (Kurzfristig initiiert bei hohem Bedarf )
– Client-initiierte Replikate --> Meist als (Client-)Cache bezeichnet
Propagierung von Updates
Spontane Idee : Server, dessen Replikat gendert wurde, propagiert neuen Wert an alle anderen
Pull oder Push?
Push --> Typisch, wenn ein hoher Grad an Konsistenz erforderlich ist
Protokolle zur Konsistenzerhaltung
– Primary-based Protocols (Write-Operationen gehen immer an dieselbe Kopie)
Local-Write-Protokolle
Remote-Write-Protokolle
– Replicated-Write Protocols (Write-Operationen gehen an beliebige Kopien)
9. Fehlertoleranz 容错性
“Verlaesslich”可靠
10. verteilte Transaktionen 分布式交易
11. Sicherheit 安全性
Security Services (Sicherheitsdienste) :
Confidentiality (Vertraulichkeit) 机密性
Authenticity (Authentizitaet) 验证
Integrity (Integritaet) 完整性
Non-Repudiation (Nicht-Anfechtbarkeit) 无争议/可验证
Access Control (Zugriffskontrolle) 存取控制
Availability (Verfuegbarkeit) 可用性
Communication Model 通讯模型
Data Flow Deviations (数据流偏差)
Interruption 被中断
Message is destroyed or corrupted
Attacks availability
Interception 被窃听
Resource is accessed by a unauthorized third
Attacks confidentiality
Modification 被修改
A resource is (a) accessed and (b) modified by a unauthorized third
Attacks integrity and confidentiality
Fabrication 被伪造
A forged resource is smuggled into the system
Attacks authenticity
Attacker Model (攻击模式):
Passive Attacks(被动攻击):
Publication of message content (公开消息内容) 例如wikiLeaks (维基解密)
Traffic analysis （交通分析）通过分析谁和谁之间有密切联系来侦测被分析主体的关系
Active Attacks（主动攻击）:
Denial-of-Service / DoS （拒绝服务）故意抑制资源的使用、攻击资源的可用性。例如攻击竞争对手的网站让其不能为正常用户提供服务。
Spoofing (欺骗) 伪造用户ID等。通常和其它手段联用。
Replay （回放）窃听消息并随后重发以达到恶意效果。
Message modification （消息修改） 修改消息内容。例如修改拦截到的银行转账的银行账号。
密码学基础：
Einordnung der Kryptograhie （密码学分类）：
秘密通信分为两类：一类是加密，包括替换法（Substitution）和换位法(Transposition)；另一类是掩藏。
替换法:
Caesar-Verschluesselung 凯撒加密法 例如将每个字母都向后移动3位。有25种密钥。
Einfache Substitution 简单替换法 每个字母随机的被另外一个字母替代。有26！种密钥。
Homophone Substitution 同音字替换法 部分明文分配多个密文符号
换位法：
Einfaches Verfahren 简易方法 按照横列方式以五个为一组写下并以纵列方式重组
Bigramm-Substitution 双置换发 不再是每个字而是每两个字进行置换
Polyalphabetische Subsitution 多字母置换 置换规律依照其的位置。
Konfusion und Diffusion 混乱和扩散
Konfusion 原则上就是替换法
Diffusion原则上就是换位法
文献说明：
主要来源于吕贝克大学分布式系统课程的讲义（讲师为：
|
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
