Architetture dei Sistemi Distribuiti · • Architettura software: definisce l’organizzazione...

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. 2018/19

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 2018/19

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 connects components among each other,

mediating communication, coordination or coordination among components

–  Example: facilities for (remote) procedure call, messaging, or streaming


2

Main architectural styles for DS

•  Layered style

•  Object-based style

•  RESTful style

•  Event-based style

•  Data-oriented style

•  Publish/subscribe style


3

Layered style •  Componenti organizzati in

livelli (layer) •  Componente del livello i

invoca componente del livello i-1

•  Comunicazione tra componenti: basata su scambio di messaggi -  Le richieste scendono, le

risposte risalgono

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


4

Layered style

•  Different layered organizations


5

Application layering

•  Traditional three-layered view –  Application-interface layer contains units for interfacing

to users or external applications –  Processing layer contains the functions of an application,

i.e., without specific data –  Data layer contains the data that a client wants to

manipulate through the application components

•  This layering is found in many distributed information systems, using traditional database technology (i.e., RDBMS) and accompanying applications


6

Application layering: example

•  A simple Web search engine


7

Object-based style •  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)


8

RESTful style •  View the DS as a collection of resources, individually

managed by components •  Representational State Transfer (REST): proposed

by Roy Fielding, one of the authors of HTTP/1.1 •  Resources may be added, removed, retrieved, and

modified by (remote) applications (HTTP methods) •  Resources are identified through a single naming

scheme (URI) •  Components expose a uniform interface •  Messages sent to or from a component are fully self-

described •  Interactions are stateless

–  State must be transferred from clients to servers


9

REST operations •  Basic operations

–  Use HTTP methods: GET, PUT, POST and DELETE


10

Example: REST API in AWS S3

•  S3: Cloud storage service offered by AWS •  Objects (i.e., files) are placed into buckets (i.e.,

directories) –  Buckets cannot be placed into buckets –  Operations on ObjectName in bucket BucketName require

the following identifier: http://BucketName.s3.amazonaws.com/ObjectName

•  All operations are carried out by sending HTTP requests: –  Create a bucket/object: PUT, along with the URI –  Listing objects: GET on a bucket name –  Reading an object: GET on a full URI!


11

REST API in AWS S3

GET /examplebucket/puppy.jpg HTTP/1.1!Host: s3.dualstack.us-west-2.amazonaws.com!Date: Mon, 11 Apr 2016 12:00:00 GMT!x-amz-date: Mon, 11 Apr 2016 12:00:00 GMT!Authorization: authorization string!!PUT /ObjectName HTTP/1.1!Host: BucketName.s3.amazonaws.com!Date: date!Authorization: authorization string !


12

Disaccoppiamento

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

•  Soluzione: far comunicare in modo indiretto mittente/i e destinatario/i tramite un intermediario

•  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)


13

“All problems in computer science can be solved by another level of indirection”

(David Wheeler, Titan project)

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


14

Synchronous vs. asynchronous interaction


15

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


16

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


17

Event-based style •  Comunicazione tra componenti:

tramite propagazione di eventi –  Evento: cambio significativo dello

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

•  Componenti –  Sottoscrivono eventi di cui sono

interessati a ricevere la notifica –  Ricevono notifiche sugli eventi

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

•  Esempi: Java Swing •  Quale tipo di

disaccoppiamento?


18

Data-oriented style

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?


19

• 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

Example: Linda tuple space

•  Data is contained in ordered sequences of typed fields (tuples)

•  Tuples are stored in a persistent, global shared space (tuple space)

•  Three simple operations: –  in(t): remove a tuple matching template t!–  rd(t): return copy of a tuple matching template t!–  out(t): write tuple t to the tuple space

•  Some details –  Calling out(t) twice in a row, leads to storing two copies of

tuple t: a tuple space is modeled as a multiset –  Both in and rd are blocking operations: the caller will be

blocked until a matching tuple is found, or has become available


20

Example: Linda tuple space


21

Publish/subscribe style •  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


22

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.






23

Publish/subscribe variants

•  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


24

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


25

Other common architectural styles •  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 2018/19

26

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


27

Architettura di sistema di un SD


28

•  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 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


29

Architetture multi-tier

•  Mapping tra livelli logici (layer) e livelli fisici (tier)

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

•  Architettura a tre livelli (three-tier) -  Tre livelli fisici

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

applicativo e di storage nei diversi livelli fisici


30

Two-tier organizations

fat client thin client


31

Three-tier organizations


32

Architetture multi-tier (2)

•  Da 2 a N tier •  Con l’introduzione di ciascun livello fisico

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

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


33

Architetture multi-tier (3) •  Distribuzione verticale

–  Componenti logicamente diversi sono assegnati a nodi distinti

•  Sia lato server che lato client

•  Distribuzione orizzontale –  Distribuzione di un singolo livello logico su molteplici nodi –  Condivisione del carico tra molteplici nodi, con ripartizione

gestita da un load balancer (o dispatcher) –  Esempio: Web cluster


34

Architetture decentralizzate

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

•  Peer-to-peer: 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


35

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 –  Possono anche essere presenti 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


36

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


37

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


38

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 2018/19

39

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


40

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


41

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


42

Tasks of overlay network

•  Besides routing of requests to resources, an overlay network must also perform: –  Insert and delete resources –  Add and remove nodes –  Identify resources and nodes

•  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

•  How to manage resources and nodes? –  Depends on the overlay network type:

•  Unstructured overlay networks •  Structured overlay networks


43

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


44

Random graphs models: Erdos-Renyi

•  Erdos-Renyi random graph: classical random network –  n: number of vertices (fixed) –  p: probability that two vertices have an edge –  deg(v): vertex degree –  Vertex degree follows binomial distribution

•  Probability that a vertex v has degree k

–  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:

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

•  Homogeneous network with an exponential tail


45

Random graphs models: Watts-Strogatz •  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

–  Most 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


46

Random graphs models: Albert-Barabasi •  Albert-Barabasi random graph: scale-free network

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

•  Power law: the frequency of an event varies as a power of some attribute of that event –  Example: number of cities having a certain population size,

allocation of wealth among individuals –  Property: scale invariance –  Some special types of power law

•  Pareto law: “80% of effects come from 20% of causes” •  Zipsf’s law: word frequency


47

-  Power law probability distributions are also heavy-tailed •  The tail of the distributions contains

a great deal of probability (i.e., heavier tail than the exponential distribution)

Power-law (α) and exponential distributions (λ) See http://bit.ly/2hXOc48

hub

Random graphs models: Albert-Barabasi (2) •  Albert-Barabasi random graph:

–  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


48

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 2018/19

49

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

distribuzione dell’indice risorse-peer

•  Reti non strutturate centralizzate: directory centralizzata (es. Napster)

•  Reti non strutturate decentralizzate pure: directory distribuita –  Flooding, in alternativa gossiping (analizzato

successivamente) o random walk •  Reti non strutturate ibride:

directory semi-centralizzata e flooding limitato ai supernodi


50

Reti centralizzate •  Un nodo centralizzato (directory server) è

responsabile del 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


51

Reti decentralizzate pure: 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 2018/19

52

Reti decentralizzate pure: 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?


53

Example of flooding


54

Flooding: problemi •  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”?


55

Reti overlay strutturate

•  Rete overlay costruita seguendo 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, …


56

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 ad essa 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 caching della risorsa nei peer attraversati


57

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)


58

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à


59

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, …


60

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)


61

Chord

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

sono mappati in un anello mediante la 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

https://github.com/sit/dht/wiki

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


62

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”, STOC 1997.

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

•  Largely used: e.g., Amazon Dynamo’s partitioning scheme relies on consistent hashing to distribute the load across multiple storage nodes


63

Finger table in Chord

•  Finger table (FT) –  Tabella di routing per ogni nodo –  Dimensione della FT pari a m, con m = # bit GUID –  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), …

•  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


64

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


65

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


66

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)


67

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


68

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 avente ID con

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

http://www.freepastry.org


69

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) •  Routing basato su longest prefix matching

•  Costo del routing: O(log2bN)

•  Ogni nodo s possiede: –  Tabella di routing –  Leaf set: L peer più vicini al nodo

sull’anello in entrambe le direzioni (L/2- e L/2+)


70

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

Looking for resource d46a1c from node 65a1fc

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 nel leaf set in base ad una metrica di prossimità (ad es. RTT)

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

b


71

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


72

Tabella di routing del nodo 1220

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


73

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


74

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

and applications (P. Bernstein)


75

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


76

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


77

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


78

Tipi di middleware (3) •  Middleware per componenti

–  Evoluzione di object-oriented middleware –  Comunicazione sia sincrona sia 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 (realizzazione di SOA), microservices (evoluzione

di SOA) –  Esempi: Apache Axis2, Apache CFX, WSO2


79

Middleware e stile architetturale

•  In molti casi il middleware segue uno specifico stile architetturale –  Es.: stile architetturale basato su oggetti e middleware

object-oriented –  Tale approccio architetturale al middleware offre semplicità

progettuale –  Ma scarsa adattabilità e flessibilità

•  E’ preferibile un middleware che possa adattare comportamento e proprietà rispetto all’applicazione specifica e all’ambiente (reflective or modifiable middleware)

•  C’è una soluzione migliore?


80

•  E’ preferibile avere un sistema software in grado di adattare il proprio funzionamento a run-time rispetto a se stesso e all’ambiente è sistemi software self-adaptive (o autonomici) –  Adattamento rispetto a: contesto dell’utente, del dispositivo,

dell’ambiente –  Applicazioni di sistemi autonomici in nuovi contesti

•  Fog computing •  Mobile edge computing •  Internet of Things •  Sistemi cyber-fisici


81

Sistemi software self-adaptive

“Intelligence is the ability to adapt to changes” Stephen Hawking

Autonomic computing •  Autonomic computing: paradigma in grado di rispondere

all’esigenza di gestire la complessità ed eterogeneità dei sistemi IT complessi mediante adattamenti automatici –  Ispirato dal sistema nervoso autonomico umano, in grado di

controllare alcune funzioni vitali (battito cardiaco, temperatura, …) mascherandone la complessità all’uomo

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

con limitato, intervento umano) –  esprimendo capacità di adattamento a dinamiche interne ed

esterne, più in generale ai cambiamenti dell’ambiente –  capacità di adattamento reattiva o proattiva

•  Reattiva: in reazione ad eventi già accaduti (e.g., aumento del numero di risorse in reazione all’incremento del carico di lavoro)

•  Proattiva: predizione, in modo da pianificare in anticipo le azioni di adattamento (e.g., aumento del numero di risorse in previsione dell’incremento del carico di lavoro)


82

Obiettivi di un sistema self-adaptive

•  Un sistema self-adaptive, 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: è un sistema self-*

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


83

Come raggiungere gli obiettivi di un sistema self-*?

•  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


84

Model of self-adaptive software system


85

You are already familiar with this model

•  The control-theory perspective of self- adaptive systems


86

Reference architecture for self-adaptive systems: MAPE

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


87

MAPE(-K) building blocks (or phases) •  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


88

Plan phase of MAPE

•  Perhaps the most challenging and studied phase of the MAPE loop

•  A variety of methodologies and techniques can be used to plan the proper adaptation –  Optimization theory –  Heuristics –  Machine learning, including reinforcement learning –  Control theory –  Queueing theory –  …

•  Example: elastic provisioning of Cloud resources (e.g., virtual machines)


89

Also other acronyms, but same story •  Adaptation loop also called CADA (Collect,

Analyze, Decide, Act) or OODA (Observe, Orient, Decide, Act) –  OODA developed in the military sector


90

Examples of self-adaptive systems

•  We analyze some examples of self-adaptive systems

•  Common ground –  Applications facing unpredictable workloads or unexpected

failures –  Adaptation goal: satisfy some QoS requirement (e.g.,

application response time, application availability of their combination) avoiding SLA violations


91

Example 1: AWS Auto Scaling •  AWS service to launch or terminate EC2 virtual

machine (VM) instances automatically based on user-defined policies, schedules, and health checks –  All the MAPE phases

•  A scaling plan tells Auto Scaling when and how to scale –  Threshold-based scaling policy –  Example: scale-out by adding 1 new instance when the

average CPU utilization > 70% for 5 minutes


92

•  Simple and intuitive policy but: -  No adaptation goal based on Cloud

application metrics

-  Setting the threshold depends on the application and requires to understand the workload trend

https://aws.amazon.com/autoscaling/

Example 2: Provisioning of cloud resources •  Autonomic provisioning of virtual machines (VMs) in

cloud systems –  Plan: find the optimal number of VMs so to satisfy application

response time when the request load changes by means of integer programming

System components How to map the system components on SaaS and IaaS providers

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


93

Example 3: Elasticity in cloud applications

•  High-level view of elastic Cloud software –  Analyze and Plan: use fuzzy logic to deal with uncertainty in

specifying elasticity rules


94

Source: P Jamshid, “Autonomic resource provisioning for cloud-based software”, Proc. SEAMS 2014. .

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

–  Plan: select the optimal set of concrete services (and their coordination) by means of linear programming optimization

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

018/

19

95

Example 5: Two-level controllers

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 2018/19

96

How to control adaptation in a decentralized fashion?

•  Alternatives for designing the control architecture of a self-adaptive system: –  Centralized MAPE, i.e., all MAPE components on

the same node: does not scale well in geo-distributed environments

–  Decentralized MAPE: many patterns, each one with pros and cons

•  No clear winner, it depends on the system and application characteristics and requirements

97 Valeria Cardellini - SDCC 2018/19

How to decentralize the adaptation control?

D. Weyns et al., “On patterns for decentralized control in self-adaptive systems. In Software Engineering for Self-Adaptive Systems II, 2013.


98

•  Some architectural patterns for decentralized MAPE

How to decentralize the adaptation control? •  First design choice:

–  Hierarchical vs. flat –  Hierarchical: easier but higher risk of bottlenecks in the hierarchy

top levels –  Flat: more difficult to coordinate, but can scale better

•  Hierarchical patterns: multiple MAPE loops organized in a hierarchy, where a higher-level control loop manages subordinated control loops; possible patterns: -  Master-worker -  Regional -  Hierarchical control

•  Flat patterns: multiple MAPE loops cooperate as peers; possible patterns: –  Coordinated control –  Information sharing


99

Hierarchical MAPE: master-worker pattern


100

M EM E ...

Master

Worker 1 Worker N

A P

•  Decentralize M and E on Workers, keep A and P centralized on Master

•  Pro: global view on Master that can achieve global adaptation goals

•  Cons: communication overhead and risk of bottleneck and SPF on Master

Hierarchical MAPE: regional pattern


101

P

M EA M EA

P

M EA

•  Multiple and loosely coupled regions, each having a two-level hierarchical structure

•  Pro: regions can be under different ownership or administrations

•  Con: achieving global goals is more complex

Hierarchical MAPE: hierarchical control pattern


102

M EA P

M EA P M EA P

•  Multiple control loops which can work at different time scales and with separation of concerns

•  Pro: the top-level MAPE can achieve global goals

•  Con: can be difficult to identify the different levels of control, depends on the controlled application or system type

Flat MAPE: coordinated control pattern


103

M EA P M EA P

M EA P M EA P

•  Multiple control loops, each one in charge of controlling some part of the system but coordinated through interaction

•  Pro: better scalability

•  Con: more difficult to take joint adaptation decisions

Flat MAPE: information sharing pattern


104

M EA P M EA P

M EA P M EA P

•  Special case of previous one: interaction only among M •  Pro: better scalability

•  Con: lack of planning coordination, conflicting or sub-optimal adaptation actions can be enacted

Date post:	19-Feb-2019
Category:	Documents
Upload:	trantu
View:	222 times
Download:	0 times

Architetture dei Sistemi Distribuiti · • Architettura software: definisce l’organizzazione...

Documents