欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標題: 分布式系統-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://m.raoushi.com/bbs/) Powered by Discuz! X3.1