Architetture dei Sistemi Distribuiti · • Peer: entità con capacità simili alle altre entità...

Architetture dei Sistemi Distribuiti

Università degli Studi di Roma “Tor Vergata” Dipartimento di Ingegneria Civile e Ingegneria Informatica

Corso di Sistemi Distribuiti e Cloud Computing A.A. 2016/17

Valeria Cardellini

Architettura sw di un SD

SD: organizzazione necessaria per governarne la complessità Distinguiamo: •  Architettura software: definisce l’organizzazione logica

e l’interazione dei vari componenti software (tra loro e con l’ambiente) che costituiscono il SD

•  Architettura di sistema: istanziazione finale (realizzazione fisica) di un’architettura software –  I vari componenti del SD sono posizionati e istanziati sulle

diverse macchine che costituiscono il sistema

Valeria Cardellini - SDCC 2016/17

1

Architectural styles (patterns) for DS •  Pattern: a commonly applied solution for a class of

problems •  An architectural style is a coherent set of design decisions

concerning the architecture –  In terms of definition and usage of components and connectors

•  Component (building block) –  Modular unit with well-defined required and provided interfaces –  Fully replaceable within its environment

•  Connector –  Mechanism that mediates communication, coordination or

coordination among components •  Main architectural styles for DS

–  Layered style –  Object-based style –  Event-based style –  Data-oriented style –  Publish-subscribe style


2

Architettura a livelli •  Componenti organizzati in

livelli (layer) •  Componente a livello i invoca

componente del livello sottostante i-1

•  Comunicazione tra componenti: basata su scambio di messaggi -  Le richieste scendono lungo la

gerarchia, mentre le risposte risalgono

•  Servizi tipici offerti da un’applicazione distribuita con architettura a livelli: di interfaccia, applicativi, di storage


3

Architettura basata su oggetti •  Componente=oggetto:

incapsula una struttura dati fornendo un’API per accedere o modificare i dati –  Incapsulamento e

information hiding riducono la complessità di gestione

–  Riusabilità tra applicazioni diverse

–  Wrapping di componenti legacy

•  Comunicazione tra componenti: mediante chiamata a procedura remota (RPC) o invocazione di metodo remota (RMI)


4

Disaccoppiamento

•  Porre vincoli sui componenti che possono interagire può introdurre vincoli non necessari

•  Soluzione: far comunicare in modo indiretto mittente/i e destinatario/i tramite un intermediario –  “All problems in computer science can be solved by another

level of indirection” (David Wheeler, Titan project)

•  Disaccoppiamento (decoupling): fattore abilitante per –  ottenere maggiore flessibilità –  definire stili architetturali che possono sfruttare al meglio

distribuzione, scalabilità ed elasticità (e.g., architetture a microservice e serverless)


5

Proprietà di disaccoppiamento

•  Disaccoppiamento spaziale (space decoupling) –  I componenti non devono conoscersi (reciprocamente

o meno); sono anonimi

•  Disaccoppiamento temporale (time decoupling) –  I componenti interagenti non devono essere

compresenti (presenti insieme nello stesso instante) quando la comunicazione ha luogo

•  Disaccoppiamento di sincronia (synchronization decoupling) –  I componenti interagenti non devono aspettarsi a

vicenda e non sono soggetti a blocchi reciproci


6

Synchronous vs. asynchronous interaction


7

Synchronous interaction

Asynchronous interaction

Decoupling: pros and cons

•  Thanks to decoupling, the DS can be flexible while dealing with changes and can provide more dependable and elastic services –  Space decoupling: components can be replaced, updated,

replicated or migrated –  Time decoupling: allows to manage volatility (senders and

receivers can come and go) –  Synchronization decoupling: no blocking

•  Main disadvantage: –  Performance overhead introduced by indirection


8

Evoluzione degli stili architetturali •  Il disaccoppiamento dei componenti ha determinato

la definizione di stili architetturali alternativi, in cui i componenti comunicano in modo indiretto

Architettura orientata ai dati

Architettura publish-subscribe

Architettura basata su eventi


9

Architettura basata su eventi •  Comunicazione tra componenti:

tramite la propagazione di eventi –  Evento: cambio significativo dello

stato (es.: variazione della temperatura, apertura di una porta)

•  Componenti –  Pubblicano notifiche sugli eventi

che osservano –  Sottoscrivono eventi di cui sono

interessati a ricevere la notifica

•  Comunicazione –  Basata su scambio di messaggi –  Asincrona –  Multicast –  Anonima

•  Esempi: Java Swing •  Quale tipo di

disaccoppiamento?


10

Data-oriented architecture

storage – Data added to or removed from the

shared space – Also known as blackboard model

• API for shared space –  write, take, read and their

variants (takeIfExists, readIfExists)

–  In case of active space: also notify or push (to avoid polling)

–  Mutual exclusion to access data

•  Which type of decoupling?

How can we implement the shared space?


11

• Communication among components: through a shared data space (usually passive, but sometimes active) with persistent

• Examples: –  Linda and tuple space –  JavaSpaces, GigaSpaces XAP, TIBCO

ActiveSpaces, Fly Object Space

Architettura publish/subscribe •  I produttori generano eventi (publish) e si

disinteressano della loro consegna ai consumatori •  I consumatori si registrano come interessati ad un

evento (subscribe) e sono avvisati (notify) della sua occorrenza

•  Disaccoppiamento completo tra entità interagenti

P

Middleware publish/subscribe

P

publish

publish

Storage and management of

subscriptions

notify()

S

S

S

subscribe

subscribe() unsubscribe()

unsubscribe

notify

Publisher

Publisher

Subscriber

Subscriber

Subscriber


12

Publish/subscribe and decoupling

P

S

S

S

publish

notify notify

notify

notify()

Space decoupling

Time decoupling P S publish

P S notify() notify

Synchronization decoupling P S

publish notify notify()

t

P.T. Eugster et al., “The many faces of publish/subscribe” ACM Comput. Surv. 35(2):114-131, June 2003.






13

Publish/subscribe variations

•  Most widely used subscription schemes in publish/subscribe systems –  Topic-based (or subject based)

•  Participants can publish events and subscribe to individual topics, which are identified by keywords

•  Cons: limited expressiveness

–  Content-based •  Events are not classified according to some predefined

external criterion, but according to their actual content, e.g., meta-data associated to events

•  Consumers subscribe to events by specifying filters •  Cons: implementation challenges


14

Implementation issues of publish/subscribe •  Tasks of publish-subscribe system

–  To ensure that events are delivered efficiently to all subscribers that have filters matching the event

–  In a secure, scalable, dependable, concurrent way

•  Centralized vs. distributed implementations –  Centralized: a single node acting as an event broker that

maintains a repository of subscriptions and matches event notifications against this set of subscriptions

•  Pro: simple •  Cons: lacks resiliency and scalability

–  Distributed: network of cooperative brokers as well as peer-to-peer implementations (e.g., based on DHT or gossiping)

–  The distributed implementation of content-based schemes is complex


15

Other common architectural patterns •  Proxy

–  Aim: to support location transparency (see RPC and RMI) –  Control access to an object using another proxy object

•  The proxy is created in the local address space to represent the remote object and offers the same interface of the remote object

•  Broker –  Aim: to separate and encapsulate the details of the

communication infrastructure from its application functionality –  Enables components of a distributed application to interact

without handling remote concerns by themselves –  Locates the server for the client, hides the details of remote

communication, …

•  More than 100 design patterns for distributed computing systems! –  Source: “Pattern-Oriented Software Architecture: A Pattern

Language for Distributed Computing, Vol. 4” Valeria Cardellini - SDCC 2016/17

16

Choosing an architectural style •  No single solution: the same problem can be tackled

with many different designs and architectural styles

•  Choice depends often on extra-functional requirements: –  Costs (resource usage, development effort needed) –  Scalability and elasticity (effects of scaling work complexity

and available resources) –  Performance (e.g., execution time, response time, latency) –  Reliability –  Fault tolerance –  Maintainability (extending system with new components) –  Usability (ease of configuration and usage) –  Reusability


17

Architettura di sistema di un SD


18

•  E’ l’istanziazione a runtime dell’architettura software del SD –  Quali componenti? –  Come interagiscono i componenti? –  Dove sono posizionati i componenti?

•  Tipologie di architetture di sistema –  Architetture centralizzate –  Architetture decentralizzate –  Architetture ibride

Architetture centralizzate

•  Comunicazione tra client e server basata su scambio di messaggi e comportamento di tipo “request-reply” –  Possibile sorgente del problema di prestazioni (ad es. Web) –  Idempotenza: se la richiesta può essere ripetute più volte senza

causare danni o problemi; •  Importante in caso di comunicazioni inaffidabili: rendere

logicamente affidabile una connessione fisicamente inaffidabile ha un costo molto elevato

•  Asimmetria con il client che conosce il server e interagisce in modo sincrono e bloccante (di default)

•  Forte accoppiamento: compresenza di chi interagisce

•  E’ il modello client/server –  Il più diffuso –  Intrinsecamente distribuito –  Esempio: Web


19

Stratificazione (multi-tier)

•  E’ il classico stile architetturale a livelli applicato alle architetture centralizzate –  Livello dell’interfaccia utente

•  Gestisce l’interazione con l’utente ed aggiorna la vista dell’applicazione presentata all’utente

•  Spesso suddiviso in due livelli (livello lato client e livello di presentazione lato server)

–  Livello applicativo (logico o business) –  Livello dei dati

•  Gestisce lo spazio di memorizzazione persistente (ad es. DBMS)

•  Architettura usata in molti SD informativi, che implementano il livello dei dati mediante DB relazionali, ad oggetti o NoSQL


20

Stratificazione: esempio

•  Esempio: motore di ricerca Web


21

Architetture multilivello o multi-tier

•  Mapping tra livelli logici (layer) e livelli fisici (tier) •  Architettura ad un singolo livello (single-tier)

–  Configurazione monolitica mainframe e terminale “stupido” (no client/server!)

•  Architettura a due livelli (two-tier) –  Due livelli fisici (client e server)

•  Architettura a tre livelli (three-tier)

•  Diverse configurazioni possibili –  Determinate dalla ripartizione dei servizi di interfaccia,

applicativo e di storage nei diversi livelli


22

Two-tier configurations

fat client thin client


23

Three-tier configurations


24

Architetture multilivello (2)

•  Da 1 a N tier •  Con l’introduzione di ciascun tier

–  Migliorano flessibilità, funzionalità e possibilità di distribuzione

•  Ma aumentando il numero di livelli, possibile degrado delle prestazioni –  Aumenta il costo della comunicazione –  Più complessità, in termini di gestione ed ottimizzazione


25

Architetture multilivello (3) •  Varie architetture client-server possibili

–  In relazione all’organizzazione del servizio e dei dati •  Distribuzione verticale

–  Componenti logicamente diversi dello stesso servizio possono essere assegnati a nodi distinti

•  Sia lato server che lato client (delega parziale) –  Servizio reso tramite la cooperazione di componenti

distribuiti •  Ripartizione gerarchica (anche di autorità)

•  Distribuzione orizzontale –  Distribuzione di un singolo livello logico su molteplici nodi;

ogni componente fisico è logicamente equivalente agli altri –  Condivisione del carico, con ripartizione gestita da un load

balancer (o dispatcher) –  Esempio: Web cluster


26

Architettura di sistema


27

•  …


Architetture decentralizzate

•  … ovvero i sistemi peer-to-peer (P2P)

•  Il termine peer-to-peer si riferisce ad una classe di sistemi ed applicazioni che utilizzano risorse distribuite per eseguire una funzionalità (anche critica) in modo decentralizzato –  “P2P is a class of applications that takes advantage of

resources available at the edges of the Internet” (Clay Shirny, 2000)

•  Peer: entità con capacità simili alle altre entità nel sistema

•  Condivisione delle risorse (cicli di CPU, storage, dati) –  Offrire ed ottenere risorse dalla comunità di peer


28

Caratteristiche dei sistemi P2P •  Tutti i nodi (peer) del sistema con identiche capacità e

responsabilità (almeno in linea di principio) –  Nodi indipendenti (autonomi) e localizzati ai bordi (edge) di

Internet •  Nessun controllo centralizzato

–  Ogni peer ha funzioni di client e server e condivide risorse e servizi

•  servent = server + client –  In realtà, possono essere presenti server centralizzati o nodi con

funzionalità diverse rispetto agli altri (supernodi) •  Sistemi altamente distribuiti

–  Il numero di nodi può essere dell’ordine delle centinaia di migliaia

•  Nodi altamente dinamici ed autonomi –  Un nodo può entrare o uscire dalla rete P2P in ogni momento

•  Operazioni di ingresso/uscita (join/leave) dalla rete –  Ridondanza delle informazioni


29

Applicazioni P2P •  Distribuzione e memorizzazione di contenuti

–  Contenuti: file, video streaming, … –  Reti, protocolli e client per file sharing (“killer application” del P2P):

Gnutella, FastTrack, eDonkey, BitTorrent, Kademlia, LimeWire, eMule, iMesh, uTorrent, …

–  P2P TV (video streaming di canali TV in real time): PPLive, … –  File storage: Freenet, OceanStore, …

•  Condivisione di risorse di calcolo (elaborazione distribuita) –  Es.: SETI@home: Search for Extraterrestrial Intelligence –  Es.: Folding@home: Protein folding

•  Collaborazione e comunicazione –  Es.: Chat/IRC, Instant Messaging, XMPP

•  Telefonia –  Es.: Skype

•  Content Delivery Network –  Es.: CoralCDN

•  Piattaforme di sviluppo per applicazioni P2P –  Es:. JXTA


30

Fundamental challenges in P2P computing •  Heterogeneity in peer resources

–  Hardware heterogeneity: too many models with different architectures

–  Software heterogeneity: OS and software environment differences

–  Network heterogeneity: different network connections and protocols

•  Scalability –  System scaling related to performance and bandwidth

•  Location –  Data location, data locality, network proximity, and

interoperability •  Fault tolerance

–  Failure management and load balancing


31

Fundamental challenges in P2P computing (2) •  Performance

–  Routing efficiency, self-organization, applications •  Free-riding avoidance

–  Free-riders: peers that are selfish and unwilling to contribute anything

•  Anonymity and privacy –  Onion routing for anonymous communications

•  Trust and reputation management –  Lack of trust among peers who are strangers to each other

•  Network threats and defense against attacks •  Churn resilience

–  Peers come, leave and even fail at random Valeria Cardellini - SDCC 2016/17

32

Operazioni principali per un nodo P2P

•  Consideriamo un’applicazione di file sharing •  Un nodo del sistema P2P svolge le seguenti

operazioni di base: –  Bootstrap: è la fase di ingresso nella rete P2P

•  Soluzioni possibili: configurazione statica, cache preesistenti, nodi well-known

–  Lookup di risorse: come localizzare le risorse in una rete P2P?

–  Retrieval della risorsa localizzata

•  Focalizziamo l’attenzione sul lookup delle risorse


33

Overlay network •  Overlay network: rete virtuale che interconnette i peer

–  Basata su una rete fisica sottostante –  I nodi sono costituiti dai processi –  I collegamenti rappresentano i possibili canali di comunicazione –  Fornisce un servizio di localizzazione delle risorse –  Instradamento a livello applicativo


34

Overlay routing

•  Idea di base: –  Il sistema fa trovare il percorso per raggiungere una risorsa

•  Rispetto al routing tradizionale –  Risorsa: no indirizzo di nodo della rete, ma file, CPU

disponibile, spazio libero su disco, … •  Concentriamo l’attenzione sul routing, non

sull’interazione tra peer per recuperare una risorsa –  Il recupero avviene tipicamente con un’interazione diretta tra

peer, ad es. usando HTTP


35

Tasks of overlay network

•  Besides routing of requests to resources, an overlay network must also perform: –  Insertion of resources –  Deletion of resources –  Node addition and removal

•  How to identify resources? –  Globally Unique IDentifier (GUID), usually derived as a

secure hash (e.g., SHA-1) from some of all of the resource’s state

•  Types of overlay networks: –  Unstructured overlay networks –  Structured overlay networks


36

Unstructured overlay networks

•  Always built on random graphs –  No particular structure on the overlay network by design –  Nodes select their neighbors (more or less) randomly

•  We examine three types of random graphs –  Erdos-Renyi model –  Small-world networks –  Scale-free networks

•  Main properties of random graphs we consider –  Clustering coefficient of a vertex: number of edges between

neighbors of that vertex divided by maximum number of possible edges between them (if a vertex v has mv neighbors, at most mv(mv-1)/2)

–  Clustering coefficient of a graph: average clustering coefficient over all vertices

–  Average shortest path length: shortest path between two vertices averaged over all pairs of vertices


37

Random graphs models

•  Erdos-Renyi random graph (classical random network) –  n: number of vertices (fixed) –  p: probability that two vertices have an edge –  deg(v): vertex degree –  Probability that a vertex v has degree k

–  Vertex degree follows binomial distribution –  Mean vertex degree: (n-1)p –  Clustering coefficient: p –  Average shortest path: log(n)/log((n-1)p) –  Graph diameter: approx. log(n) –  Wrapping up:

•  Short average shortest path length and low clustering coefficient –  But low clustering not observed in many real-world networks!

•  Homogeneous network with an exponential tail


38

Random graphs models (2) •  Other models for more (but not fully!) realistic graphs

–  Some properties observed in real-world graphs (but not in Erdos-Renyi graphs):

•  High clustering coefficient •  Presence of hubs (high-degree nodes), i.e., nonhomogeneous

network

•  Watts-Strogatz random graph (small-world network) –  Properties:

•  Small average shortest path length •  High clustering coefficient, independent of the number of vertices

–  Nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops

–  Example: social networks –  Limitation: does not account for the formation of hubs


39

hub

Random graphs models (3) •  Albert-Barabasi random graph (scale-free network)

–  Vertex degree follows power law distribution P(deg(v) = k) ~ ck -γ where 2 < γ < 3

–  How do new nodes attach themselves to existing nodes? On the basis of preferential attachment

•  The more connected a node is, the more likely it is to receive new links, e.g. think about social networks connecting people!

•  There are a few hubs, but their number decreases exponentially (power law)

–  Scale-free: graph diameter ~ ln (ln n) •  Many networks are conjectured to be scale-free (Internet, Web,

social networks, power grids), but still controversial hypothesis in some cases

•  Scale-free networks are highly resilient against faulty constituents: ideal interconnect also for cloud computing


40

Unstructured overlay networks: characteristics

•  Overlay created in ad-hoc manner –  Each node joins the network following some simple, local rules –  A joining node contacts a set of neighbors

•  No overall control over the network topology or the placement of resources within the network

•  Goal: to manage nodes with highly dynamic behavior (i.e., high rates of churn)

•  Pros: insertion and deletions of nodes and resources are easily managed

•  Cons: resource location is complicated by the lack of structure –  Unpredictable performance

•  Examples: Gnutella, FastTrack, eDonkey, … Valeria Cardellini - SDCC 2016/17

41

Routing in reti non strutturate •  Classifichiamo le reti non strutturate in base al livello di

distribuzione dell’indice risorse-peer

•  Sistemi P2P centralizzati: directory centralizzata (es. Napster)

•  Sistemi P2P decentralizzati puri: directory distribuita –  Flooding, in alternativa gossiping (analizzato

successivamente) o random walk •  Sistemi P2P ibridi:

directory semi-centralizzata e flooding limitato ai supernodi


42

Sistemi P2P centralizzati •  Un nodo centralizzato (directory server) possiede il

mapping risorse-peer (index), fornendo un servizio di discovery dei peer e di ricerca delle risorse

•  Limiti –  Gestione costosa della directory centralizzata –  Collo di bottiglia costituito dal nodo centrale (scalabilità

limitata) –  Single point of failure (motivi tecnici e legali, es. Napster)

Napster serverIndex1. File location

2. List of peers

request

offering the file

peers

3. File request

4. File delivered5. Index update

Napster serverIndex


43

Sistemi P2P decentralizzati puri: flooding •  Approccio completamente distribuito per localizzare le

risorse

•  Query di lookup inviate secondo il meccanismo del flooding (inondazione) –  Ogni peer propaga (flood) la richiesta ai peer “vicini”, che a loro

volta inviano la richiesta ai loro “vicini” (escludendo il vicino da cui hanno ricevuto la richiesta)

•  Fino a che la richiesta è risolta, oppure viene raggiunto un massimo numero di peer interrogati (definito da Time To Live o TTL)

–  Ad ogni inoltro il TTL viene decrementato

–  Il TTL limita il “raggio della ricerca”, evitando che il messaggio sia propagato all’infinito

•  ID univoco assegnato alla richiesta per evitare che venga nuovamente elaborata dai nodi da cui è stato già ricevuta (presenza di cicli nei grafi)

•  Costo di lookup: O(N), con N numero di nodi della rete Valeria Cardellini - SDCC 2016/17

44

Sistemi P2P decentralizzati puri: flooding (2)

•  Alternative per l’invio della risposta alla query di lookup: –  Diretto: dal peer con risposta positiva al peer che ha

originato la richiesta –  Basato sul backward routing

•  Backward routing –  La risposta positiva viene inoltrata a ritroso lungo lo stesso

cammino seguito dalla query –  Si usa il GUID per individuare il backward path –  Quali vantaggi rispetto all’invio diretto?


45

Example of flooding


46

Problemi del flooding •  Crescita esponenziale del numero di messaggi

–  Possibilità di attacchi di tipo denial-of-service –  Nodi black-hole in caso di congestione –  Non è realistico esplorare tutta la rete

•  Costo della ricerca –  Le risposte dovrebbero avere tempi ragionevoli –  Come determinare il raggio di ampiezza del flooding (ovvero il

TTL)?

•  Non è garantito che vengano interrogati (tutti) i nodi che posseggono la risorsa

•  Traffico di query –  Messaggi senza risultato occupano comunque banda

•  Mancanza di relazione tra topologia di rete virtuale e fisica –  Quanto sono distanti i peer “vicini”?


47

Reti strutturate

•  Costruzione della rete overlay basata su algoritmi deterministici

•  Vincoli sulla topologia del grafo e sul posizionamento delle risorse sui nodi del grafo –  Organizzazione della rete secondo una topologia definita –  Esempi di topologia: anello, albero, ipercubo

•  Reti basate su Distributed Hash Table (DHT) •  Obiettivo: migliorare la localizzazione delle risorse,

minimizzando il numero di messaggi inviati •  Svantaggio: le operazioni di aggiunta o rimozione di

nodi sono più costose •  Esempi: Chord, Pastry, CAN, Kademlia, …


48

Routing in reti strutturate •  Basato su Distributed Hash Table (DHT) nella stragrande

maggioranza dei casi •  Ad ogni peer è assegnato un GUID da uno spazio di

identificatori grande; ogni peer conosce alcuni peer •  Ad ogni risorsa condivisa viene assegnato un GUID (dallo

stesso spazio di identificatori usato per i peer), definito applicando alla risorsa una funzione hash

•  Per instradare la richiesta per una risorsa verso il peer associato, occorre mappare univocamente il GUID della risorsa nel GUID di un peer in base a una metrica di distanza

−  Richiesta instradata verso il peer con GUID più “vicino” a quello della risorsa

−  Possibile copia della risorsa in ogni peer attraversato


49

Distributed Hash Table •  Astrazione distribuita della struttura dati hash table •  Una risorsa è rappresentata dalla coppia chiave-valore

(key K, value V) –  K identifica la risorsa (contenuta in V): corrisponde al GUID

•  API per l’accesso alla DHT (comune a molti sistemi basati su DHT) –  put(K, V): inserisce la risorsa (memorizza V in tutti i nodi

responsabili per la risorsa identificata da K) –  remove(K): cancella tutti i riferimenti a K e all’associato V –  V = get(K): recupera V associato a K da uno dei nodi

responsabili

Distributed hash table

Distributed application get(K) V

node node node ….

put(K, V)


50

Distributed Hash Table (2) •  Occorre mappare univocamente la chiave di una

risorsa nel GUID del nodo “più vicino” –  Identificatore a m bit (solitamente m=128 o 160)

•  Le risorse vengono mappate nello stesso spazio di indirizzamento dei nodi mediante una funzione di hash –  Ad es. funzione crittografica di hash SHA-1

•  Ogni nodo è responsabile di una parte di risorse memorizzate nella DHT –  Ad ogni nodo viene assegnata una porzione contigua dello

spazio di identificatori –  Ogni nodo memorizza informazioni relative alle risorse

mappate sulla propria porzione di identificatori

•  Ogni chiave viene mappata su almeno un nodo della rete –  Replicazione per migliorare la disponibilità


51

Difficoltà nelle DHT

•  Poiché ogni risorsa è identificata solo mediante il valore della chiave, per cercare una risorsa occorre conoscere il valore della chiave

•  E’ semplice effettuare query di ricerca di tipo exact-match, ad es. basate sul nome della risorsa

•  E’ più difficile e costoso supportare query più complesse –  Ad es. query con wildcard, range query, …


52

Reti basate su DHT •  Caratterizzate da elevata scalabilità rispetto alla

dimensione (numero di nodi) •  Diverse proposte di sistemi P2P basati su DHT

–  In cosa differisco? Nella definizione dello spazio di identificatori (e quindi la topologia della rete) e nella selezione dei peer con cui comunicare (ovvero la metrica di distanza)

–  Più di 20 protocolli ed implementazioni per reti P2P strutturate, tra cui:

•  Chord (MIT) •  Pastry (Rice Univ., Microsoft) •  Tapestry (Berkeley Univ.) •  CAN (Berkeley Univ.) •  Kademlia (NY Univ.) •  Chimera (UCSB) •  SkipNet (Washington Univ, Microsoft)


53

Chord

•  Algoritmo per il lookup in reti P2P •  I nodi e le chiavi delle risorse

sono mappati in un anello mediante una funzione di hash detta consistent hashing

•  Ogni nodo è responsabile delle chiavi poste tra sé e il nodo precedente nell’anello –  La risorsa con chiave k è mappata

nel nodo con il più piccolo identificatore id ≥ k

–  Questo nodo è detto succ(k), successore della chiave k

–  Ad es. succ(1)=1, succ(10)=12

pdos.csail.mit.edu/chord

•  Metrica di distanza: basata sulla differenza lineare tra gli identificatori


54

Consistent hashing •  A special kind of hashing

–  Both items and buckets are uniformly distributed and in the same identifier space (the same circle) using a standard hash function

•  Integral to the robustness and performance of Chord –  In case of hash table resizing (adding or removing a bucket): the

mapping of items to buckets does not significantly change •  Practical impact: nodes can join and leave the network with minimal

disruption –  All buckets get roughly same number of items: load balancing

•  Original devised by Karger et al. at MIT for distributed caching Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web

•  Some details and Java implementation www.tom-e-white.com/2007/11/consistent-hashing.html

•  Largely used: for example, Amazon Dynamo’s partitioning scheme relies on consistent hashing to distribute the load across multiple storage hosts


55

Finger table in Chord

•  Finger table (FT) –  Tabella di routing per ogni nodo –  Se FTp è la FT del nodo p, allora FTp[i] = succ(p + 2i-1) mod 2m,

1 ≤ i ≤ m •  succ(p+1), succ(p+2), succ(p+4), succ(p+8), succ(p+16), …

–  Dimensione della FT pari a m, con m = # bit GUID •  Idea della finger table

–  Ogni nodo conosce “bene” le posizioni vicine ed ha un’idea approssimata delle posizioni più lontane

100

000

101 011

010

001

110

111 Nell’esempio m=3 FT0[1]=0+20=1

FT0[2]=0+21=2

FT0[3]=0+22=4


56

Algoritmo di routing in Chord •  Come risolvere la chiave k nell’identificatore di succ(k)

a partire dal nodo p (algoritmo di routing): –  Se k è nella zona di competenza di p, la ricerca termina –  Se p < k ≤ FTp[1], p inoltra la richiesta al nodo successore –  Altrimenti, p inoltra la richiesta al nodo q con indice j in FTp

FTp[j] ≤ k < FTp[j+1]

q è il nodo più lontano da p la cui chiave viene prima della (o è uguale alla) chiave k

•  Caratteristiche –  Raggiunge velocemente le vicinanze del punto cercato, per

procedere poi con salti via via più piccoli –  Costo di lookup: O(log(N)), con N numero dei nodi


57

Esempio di routing in Chord

Il nodo 1 risolve la chiave 26

Il nodo 28 risolve la chiave 12

Nell’esempio: •  m=5 •  Quindi chiavi da 0 a 25-1


58

Ingresso e uscita di nodi in Chord •  Ogni nodo mantiene anche il puntatore al predecessore

per semplificare le operazioni di join e leave •  Al join nell’overlay network, il nodo p:

–  Contatta un nodo arbitrario a cui chiede la ricerca di succ(p+1) –  Si inserisce nell’anello –  Inizializza la sua FT chiedendo succ(p + 2i-1), 2 ≤ i ≤ m –  Aggiorna la FT del nodo che lo precede sull’anello –  Trasferisce dal suo successore su se stesso le chiavi di cui è

responsabile

•  Alla leave dall’overlay network, il nodo p: –  Trasferisce al suo successore le chiavi di cui è responsabile –  Aggiorna nel nodo che lo precede il puntatore al nodo che lo

segue sull’anello –  Aggiorna nel nodo che lo segue il puntatore al nodo che lo

precede sull’anello •  Costo di join/leave: O(log2 N)


59

Riassumendo: caratteristiche di Chord

•  Vantaggi –  Bilanciamento del carico

•  Chord distribuisce uniformemente le chiavi fra i nodi –  Scalabilità

•  Le operazioni di lookup sono efficienti: O(log(N)) –  Robustezza

•  Chord aggiorna periodicamente le finger table dei nodi per riflettere i mutamenti della rete (nodi che entrano o escono)

•  Problemi –  Manca una nozione di prossimità fisica –  Supporto costoso per ricerche senza matching esatto

•  Altre proposte di reti P2P strutturate per risolvere tali problemi


60

Pastry •  Fornisce un substrato per applicazioni P2P

–  Sviluppato da Microsoft Research e Rice University –  Alcune applicazioni: Scribe (multicast), SQUIRREL (caching

coooperativo), PAST (storage)

•  Basato su Plaxton routing –  Meccanismo per la diffusione efficiente di risorse su una rete,

pubblicato nel 1997 (precede P2P!) –  Idea di base: la risorsa A è memorizzata sul nodo con ID che

presenta il prefisso più lungo in comune con A –  Prefix matching routing: basato sul confronto tra

•  prefisso del nodo •  prefisso della risorsa

–  In realtà, Pastry usa una soluzione più complessa: ogni nodo mantiene anche un leaf set (insieme dei nodi a lui più vicini nello spazio bidirezionale degli ID)

–  Anche Tapestry e Kademlia si basano su Plaxton routing

www.freepastry.org


61

Pastry (2)

•  Come in Chord, GUID dei nodi e delle risorse sono mappati su un anello

•  Chiavi (GUID) rappresentate con d simboli da b bit ciascuno (in genere b=4)

•  Ogni nodo possiede: –  Tabella di routing –  Leaf set: L peer più vicini al nodo sull’anello in entrambe le

direzioni (L/2- e L/2+) –  Neighborhood list: M peer più vicini in base alla metrica di

distanza (non usata per il routing) •  Routing basato su longest prefix matching

–  Ad ogni passo del routing, si inoltra la ricerca verso il nodo con ID via via più vicino a quello della risorsa cercata

–  Es: **** → 8*** → 89** → 895* → 8954 •  Costo del routing: O(log2

bN)


62

Plaxton routing

•  Esempio: chiave con b=2 e d=4 → chiave di 8 bit –  Di solito chiavi molto più lunghe (128 bit)

•  Regole di composizione della tabella di routing

0212 - 2311 3121

1031 1123 - 1312 1200 1211 - 1231 - 1221 1222 1223

Tabella di routing del nodo 1220 0 1 2 3

0 1 2 3

–  Gli ID dei nodi sulla riga n-esima condividono le prime n cifre con l’ID del nodo corrente

–  La (n+1)-esima cifra degli ID sulla riga n-esima è il numero di colonna

•  Ad ogni elemento della tabella possono corrispondere più nodi •  Si sceglie il nodo più

vicino in base ad una metrica di prossimità (ad es. RTT)

⎡log2 N⎤ righe nella tabella 2b-1 elementi in ogni riga

b


63

Plaxton routing (2) •  Query di lookup inoltrata in base al meccanismo di

longest prefix matching –  Verso il nodo che condivide col nodo di destinazione almeno

una cifra in più del nodo corrente –  Se non esiste, al nodo numericamente più vicino

0212 - 2311 3121

1031 1123 - 1312 1200 1211 - 1231 - 1221 1222 1223

Routing verso 0321 Routing verso 1106 Routing verso 1201 Routing verso 1221


64

Tabella di routing del nodo 1220

Architettura di sistema


65

•  …


Hybrid architectures •  So far we have considered centralized and

decentralized architectures •  Now some examples of hybrid architectures 1.  P2P systems with super peers

2.  BitTorrent –  Once a node has identified where to download a file from, it

joins a swarm of downloaders, who in parallel get file chunks from the source but also distribute these chunks amongst each other


66

Where middleware fits •  Network/OS based distributed

system –  Communication services –  But the developer of distributed

applications has to mask the differences among the DS nodes

•  Middleware based distributed system –  Middleware provides horizontal

services to help building distributed applications

–  It also masks differences in the platform


67

Middleware: definition •  General-purpose service that sits between platforms

and applications (P. Bernstein)


68

Middleware: definition (2) •  A software layer that provides a programming

abstraction as well as masking the heterogeneity of the underlying networks, hardware, operating systems and programming languages (Coulouris & Dollimore)

•  A “middle” virtual layer between applications and the underlying platforms they run on … that provides significant transparency (R. J. Anthony)

•  Some examples of middleware: RPC, Java RMI,

CORBA, Java EE, .NET, Web Services, Enterprise Service Bus (ESB), Apache Kafka


69

Tipi di middleware

•  Varie tipologie di middleware; consideriamo una possibile classificazione non esaustiva correlata agli stili architetturali esaminati –  Piattaforme più recenti di middleware offrono soluzioni

ibride

•  Object-oriented middleware –  Evoluzione di RPC: i componenti distribuiti sono oggetti

(con identità, interfaccia, incapsulamento) –  Comunicazione tipicamente sincrona,

•  Gli oggetti comunicano tramite invocazione di metodo remoto –  Esempi: Java RMI, CORBA


70

Tipi di middleware (2) •  Message-oriented middleware (MOM)

–  Comunicazione asincrona –  Può offrire elevata flessibilità ed affidabilità –  Molte implementazioni basate su sistema a code di messaggi –  Esempi: Apache ActiveMQ, Apache Kafka, IBM WebSphere

MQ, RabbitMQ, ZeroMQ


71

Tipi di middleware (3) •  Middleware per componenti

–  Evoluzione di object-oriented middleware –  Sia comunicazione sincrona che asincrona –  I componenti vivono in contenitori (application server), che sono

in grado di gestire la configurazione e la distribuzione dei componenti e fornire ad essi funzionalità di supporto

–  Esempi: Java EE, .NET, JBoss

•  Middleware orientato ai servizi –  Enfasi sull’interoperabilità tra componenti eterogenei, sulla base

di protocolli standard aperti ed universalmente accettati –  Generalità dei meccanismi di comunicazione (sia sincroni che

asincroni) –  Flessibilità nell’organizzazione degli elementi (servizi) –  Web services, microservices –  Esempi: Apache Axis2, Apache CFX


72

Architetture e middleware •  In molti casi il middleware segue uno specifico stile

architetturale –  Ad es. architettura basata su oggetti e object-oriented

middleware –  Tale approccio architetturale al middleware offre semplicità

progettual,e ma scarsa adattabilità e flessibilità •  E’ preferibile un middleware che possa adattare

comportamento e proprietà rispetto all’applicazione specifica e all’ambiente (adaptive and reflective middleware)

•  Ancora meglio, è preferibile un sistema software in grado di adattare il proprio funzionamento rispetto a se stesso e all’ambiente è sistemi autonomici –  Richiesta per sistemi autonomici in continuo aumento

(mobile computing, fog computing, Internet of Things, …) –  Adattamento rispetto al contesto dell’utente, del dispositivo,

dell’ambiente Valeria Cardellini - SDCC 2016/17

73

Sistemi autonomici

•  Autonomic Computing: paradigma in grado di rispondere all’esigenza di gestire la crescente complessità ed eterogeneità dei sistemi IT complessi mediante adattamenti automatici

•  Ispirato dal sistema nervoso umano, in grado di controllare alcune funzioni vitali (battito cardiaco, temperatura, …) mascherandone la complessità all’uomo

•  Un sistema autonomico è in grado di: –  gestire le proprie funzionalità autonomamente (ovvero senza o

con limitato intervento umano) –  esprimendo capacità di adattamento (comportamenti reattivi e

proattivi) a dinamiche interne ed esterne, più in generale ai cambiamenti dell’ambiente


74

Obiettivi di un sistema autonomico

•  Un sistema autonomico, a fronte di determinate politiche impostate dall’amministratore, è in grado di auto-gestirsi, perseguendo come obiettivi:

•  Self-configuring •  Capacità di auto-configurarsi rispetto a cambiamenti

nell’ambiente •  Self-healing

–  Capacità di scoprire, diagnosticare e reagire a guasti (ad es. malfunzionamenti hw)

•  Self-optimizing –  Capacità di ottimizzare le proprie prestazioni

•  Self-protecting –  Capacità di proteggersi da attacchi esterni

•  Complessivamente: essere un sistema self-*

Riferimento: J.O. Kephart, D.M. Chess, The vision of Autonomic Computing, IEEE Computer, 36(1), Jan. 2003.


75

Come raggiungere gli obiettivi? •  Il sistema deve conoscere il suo stato interno (self-

awareness)…

•  e le attuali condizioni operative esterne (self-situation)

•  Il sistema deve individuare cambiamenti riguardanti il suo stato e l’ambiente circostante (self-monitoring)…

•  e di conseguenza deve adattarsi (self-adjustement)

•  Questi attributi sono i meccanismi implementativi


76

Sistemi di controllo in retroazione •  I sistemi self-* sono generalmente organizzati come

sistemi di controllo in retroazione –  Componente per la stima della metrica

•  Misura il comportamento del sistema –  Componente di analisi

•  Analizzare le misure e le confronta con dei valori di riferimento •  E’ il cuore del ciclo di controllo, poiché contiene gli algoritmi

che decidono gli eventuali adattamenti –  Meccanismi per influenzare il comportamento del sistema

Organizzazione logica di un sistema di controllo in retroazione (l’organizzazione fisica può essere molto diversa: i vari componenti possono essere distribuiti)


77

Reference architecture for autonomic systems: MAPE

•  MAPE (Monitor, Analyze, Plan, Execute) control loop


78

MAPE(-K) building blocks •  Monitor

–  Collects monitoring data from the managed resources through multiple sensors; aggregates, filters and correlates these data into symptoms that can be analyzed

•  Analyze –  Observes and analyzes situations to determine if some change needs

to be made with respect to policies and goals –  If changes are required, it passes the change request to Plan

•  Plan –  Determines which corrective actions need to be performed so to

enact a desired alteration in the managed resources •  Execute

–  Performs the necessary changes to the managed resources carrying out the actions determined by Plan through effectors

•  Knowledge –  Data used by the autonomic system are stored as shared knowledge


79

Example 1: Provisioning of cloud resources •  Autonomic provisioning of virtual machines in cloud

systems based on MAPE reference framework –  Plan phase: find the optimal number of virtual machines so to

satisfy application response time when the request load changes

System components Mapping system component on SaaS and IaaS providers

Source: E. Casalicchio, L. Silvestri, “Mechanisms for SLA provisioning in cloud-based service providers”, Computer Networks, 2013.


80

Example 2: Service selection •  QoS-driven self-adaptation of SOA applications

–  Plan phase: select the set of concrete services to be used in the composition, and (possibly) the coordination pattern for multiple functionally equivalent services

Source: V. Cardellini, E. Casalicchio, V. Grassi, S. Iannucci, F. Lo Presti, R. Mirandola, "MOSES: a framework for QoS driven runtime adaptation of service-oriented systems", IEEE Trans. Soft. Eng 2012

Vale

ria C

arde

llini

- S

DC

C 2

016/

17

81

Example 3: Two-level cloud controller

Application controller

Cloud Controller

Cloud Platform

Application 1

Application controller

Application nSLA 1 SLA n

Application 1

VM VM

Application n

VM VM

Monitor

Decision

Actuator

Monitor

Decision

Actuator

….

….

….

….

•  Automatic resource management based on two levels of controllers, one for the service provider and one for the application –  Application controllers and cloud controllers work in concert

Source: D. Marinescu, “Cloud Computing: Theory and Practice”, Morgan Kaufmann, 2013. Valeria Cardellini - SDCC 2016/17

82

Architetture dei Sistemi Distribuiti · • Peer: entità con capacità simili alle altre entità...

Documents

Transcript of Architetture dei Sistemi Distribuiti · • Peer: entità con capacità simili alle altre entità...