标题: 分布式系统-Distribute System-Verteilte Systeme [打印本页]
作者: wudawei    时间: 2014-12-31 01:41
标题: 分布式系统-Distribute System-Verteilte Systeme
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算法

A为需要调整时间的客户
B为UTC（协调世界时间）时间
A向B发出时间咨询
B以最快的速度返回当前时间
A计算当前的时间T = T（B）+ （t4 - t1）/ 2  

Berkeley算法 （网络内部时间同步 无外部时间来源（例如UTC））

初始状态：网络内时钟不同步


步骤1:协调者（服务器）将自己的时间发给其它所有的计算机（客户机）


步骤2：所有客户机反馈与服务器的时间差


步骤3：协调者计算整个网络的时间差中间值（-10+0+25）/ 3 = 5
协调者根据所述中间值将自己的时钟往前调5秒
并将每个客户需要调整的时间发给相应客户
相应客户根据收到的消息调整自己的时间


最终：大家皆大欢喜








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中 ab 成立则对于整个系统来说 ab 也成立；
对于一个消息m来说 send(m)receive（m）总是成立的；
对于整个系统来说 如果ab 并且 bc成立则 ac也一定成立。


弱一致性： 如果 ab 则 C(a) < C(b)
强一致性： 如果C(a) < C(b) 则 ab


实现：



用伪码实现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原则上就是换位法











文献说明：
主要来源于吕贝克大学分布式系统课程的讲义（讲师为：





欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1