Distributed Software Engineering Middleware for Reconfigurable Systems Gianpaolo Cugola Dipartimento di Elettronica e Informazione Politecnico di Milano, Italy [email protected] http://www.elet.polimi.it/~cugola joint work with Gian Pietro Picco, Paolo Costa, Davide Frey, Matteo Migliavacca, and Amy Murphy Politecnico di Milano Outline Sources of reconfiguration Publish-subscribe middleware (Jedi) – Managing reconfigurations in distributed publish-subscribe middleware – Reducing event loss during reconfigurations by using epidemic algorithms State-based, peer-to-peer middleware (PeerWare) – A model combining state based and reactive communication – A middleware which adopts such model Future work IS-MANET kick-off meeting 2 Politecnico di Milano Sources of reconfiguration Modern distributed applications must be able to operate in dynamic environments At the network level, dynamicity comes from: – Organizational changes in companies, which results in changes in the company network • New departments, merging among companies, … – Mobile computing • Nomadic users, base-station, and ad-hoc scenarios – Peer-to-peer networking • Peers come and go during the application lifetime Building reconfigurable systems is a challenge for software engineering IS-MANET kick-off meeting 3 Politecnico di Milano Middleware for reconfigurable systems - 1 To efficiently build reconfigurable applications developers need new middleware – Applications must be able to reconfigure themselves... – ... and cannot rely on common notions like the address of remote components Standard C/S middleware, like RMI and CORBA, present several drawbacks – Being based on a strong coupling among clients and servers... – ... which reduces the possibility of dynamically changing the configuration of the application to cope with changes in connectivity – Even if some services have been added to the above mentioned middleware to try to overcome these problems IS-MANET kick-off meeting 4 Politecnico di Milano Middleware for reconfigurable systems - 2 In the last years, different middleware have shown their benefit in a dynamic environment – Publish-Subscribe middleware – State-based, Linda like, middleware The SE group at Politecnico di Milano has gained a good experience with both – Jedi: A publish-subscribe middleware for large scale applications – Lime: A state-based middleware based on the Linda paradigm, explicitly conceived for mobile computing Recently we got even further by extending Jedi and developing PeerWare, a new state-based, p2p middleware IS-MANET kick-off meeting 5 Politecnico di Milano Publish-Subscribe Middleware Communication is based on asynchronous event notifications, published by clients Clients subscribe to event classes by issuing a subscription Client components are attached to an event dispatcher, responsible for dispatching events to subscribers Publish-subscribe middleware varies in terms of: – Event format & subscription language – Architecture Dispatcher Temperature > 20 oC Temperature = 25 oC C IS-MANET kick-off meeting C C 6 Politecnico di Milano Subscription Language The expressivity of the subscription language allows to distinguish between: – Subject-based • The set of subjects is determined a priori • Analogous to multicast – Content-based • Subscriptions contain expressions (event patterns) that allow clients to filter events based on their content • The pattern set is determined by client subscriptions • A single event may match multiple subscriptions IS-MANET kick-off meeting 7 Politecnico di Milano Architecture of the event dispatcher Most publish-subscribe middleware adopt a centralized event dispatcher To improve scalability and performance, most advanced publish-subscribe middleware offer a distributed event dispatcher – Where a set of interconnected dispatching servers cooperate to distribute events Distributed publish-subscribe middleware differ in the way such dispatching servers are connected ad in the way subscriptions are propagated IS-MANET kick-off meeting 8 Politecnico di Milano Subscription Forwarding Every dispatcher propagates subscriptions to the others – Subscriptions are never sent twice through the same link Events follow the routes laid by subscriptions IS-MANET kick-off meeting 9 Politecnico di Milano Reconfiguration To operate in dynamic environments, distributed publishsubscribe middleware must provide mechanisms to reconfigure the event dispatching network – No publish-subscribe system to date deals with this kind of reconfiguration Supporting reconfiguration implies solving three problems: – How to reconstruct the overlay network • Open issue… to be solved in is-manet – How rearrange the subscription information • Content-based makes the problem very different from existing subjectbased solutions, inspired by multicast – How to minimize event loss during reconfiguration • Epidemic algorithms We considered the three problems as orthogonal IS-MANET kick-off meeting 10 Politecnico di Milano Removing a link A B D C The graph is partitioned in two Unsubscriptions are propagates along the two subgraphs, starting at the broken link IS-MANET kick-off meeting 11 Politecnico di Milano Adding a link A B D C The two subgraphs are merged back into one Subscriptions are propagated across the new link IS-MANET kick-off meeting 12 Politecnico di Milano Drawbacks A B D C In the case of a link substitution, the ordering of operations affects the efficiency of the reconfiguration All the subscriptions in the left subtree are removed, but the blue ones are reinserted immediately after IS-MANET kick-off meeting 13 Politecnico di Milano Understanding Propagation A subscription is propagated following the unique route up to the closest splitter, if it exists; to the whole tree, otherwise – A splitter is either a subscriber or a dispatcher whose routing table has two or more entries for the given subscription A B D IS-MANET kick-off C meeting Adding a subscription is usually cheap The more splitters, the shorter the path a subscription must follow 14 Politecnico di Milano The Idea To appear in Int. Conf. on Distributed Computing Systems (ICDCS03) The idea is to perform unsubscriptions first, and subscriptions after – This way, the network is kept dense of subscriptions, and the impact of reconfiguration is reduced Unsubscriptions are managed through a timer, which is set when a link breakage is detected Other optimizations are provided, e.g., for the case where a dispatcher belongs to a broken link and a new link The idea is very simple but: – It is based on a thorough understanding of the dispatching strategy – It provides significant improvements IS-MANET kick-off meeting 15 Politecnico di Milano Simulations: Event Delivery Goal: understand whether the algorithm converges, even under a barrage of reconfigurations non-overlapping IS-MANET kick-off meeting overlapping 16 Politecnico di Milano Simulations: Overhead Reduction Better performance with a sparse graph The impact of misrouted events is relevant IS-MANET kick-off meeting 17 Politecnico di Milano Reducing event loss during reconfiguration We need a mechanism to reduce event loss during reconfiguration – It should be scalable, light, and resilient to reconfigurations The idea: why not try to apply epidemic (gossip) algorithms to recover lost messages? Epidemic algorithms: – Each process periodically communicates its view of the system state to a random subset of the other processes – Information propagates “epidemically” up to a stable state IS-MANET kick-off meeting 18 Politecnico di Milano Gossip & reconfigurable publishsubscribe middleware Content-based routing introduces new problems Issues to solve – How to route gossip messages? • Content-based routing schema do not have any notion of “group” – How to detect event loss? • Simple numbering schemas are not enough Different approaches – Push – Pattern-based pull – Source-based pull Same approaches can be used to recover event lost during reconfigurations or because of channel failures IS-MANET kick-off meeting 19 Politecnico di Milano Simulations Overlapping reconfigurations IS-MANET kick-off meeting 20 Politecnico di Milano Simulations Unreliable channels IS-MANET kick-off meeting 21 Politecnico di Milano Simulations Delivery rate vs. size IS-MANET kick-off meeting 22 Politecnico di Milano Simulations Overhead (gossipMsgs/events) IS-MANET kick-off meeting 23 Politecnico di Milano PeerWare: Some facts and an idea Some facts – Sometimes it is necessary to have state based communication... – ... other times messages are the best form of communication – As demonstrated by applications like gnutella, peer-to-peer architectures perfectly fit the needs of flexibility and reconfigurability of several classes of distributed applications The idea – Merge in a single, integrated model the two forms of communication • A model that could be implemented by a scalable middleware – Develop a peer to peer middleware that adopts this model IS-MANET kick-off meeting 24 Politecnico di Milano PeerWare: The general model Based on the notion of global virtual data structure – Each mobile unit carries a piece of a global data structure, e.g., a subtree, a subset, a submatrix, … – When connectivity is available, the portion of the global data structure available to the unit is larger, and determined by the other connected units Middleware carries the burden of maintaining the illusion of local access to a global data structure Wide (and largely unexplored) range of design choices – Rules for breaking/merging the data structure, proactive vs. reactive primitives, definition of connectivity, … IS-MANET kick-off meeting 25 Politecnico di Milano PeerWare: The specific model PeerWare maintains a gvds organized as a graph of nodes and documents – Each node may be part of zero or one “parent” nodes – Each document may belong to one or more nodes Each component connected to PeerWare contributes the gvds with a set of connected nodes and documents The gvds managed by PeerWare is built by “merging” these documents and nodes IS-MANET kick-off meeting 26 Politecnico di Milano PeerWare: Engagement Nodes with the same identifier (i.e., path) are merged together n1 d3 n2 d2 d6 n7 n3 n1 n2 n3 n4 d1 n8 n10 n9 d8 d7 d2 Component 2 d1@c2 n1 n4 d5 n5 d6 n7 n3 d1@c1 n2 n6 d4 d5 n6 Component 1 d3 n5 d1 d4 n8 n9 d8 n10 d7 dds IS-MANET kick-off meeting 27 Politecnico di Milano PeerWare: Primitives PeerWare provides primitives to: – Join and leave the system – Manipulate the local repository of each component • i.e., the set of nodes and documents held by each component – Query the distributed data structure – Register subscriptions to events occurring on data items – Publish event notifications for events related to data items IS-MANET kick-off meeting 28 Politecnico di Milano PeerWare: Global primitives Item[] execute(NodeFilter, DataFilter, Action, Callback, Mode) – The query is distributed to the set of hosts holding at least one node matching NodeFilter – Locally, the set M of items that belong to these nodes and match the DataFilter is determined – M is passed (locally) to the user-provided Action that manipulates it (e.g., by filtering out part of their content) – The set of items returned by the action is given back to the caller • Through the Callback if the asynchronous mode is specified • As a single array of data if the synchronous mode is specified IS-MANET kick-off meeting 29 Politecnico di Milano PeerWare: Global primitives SubscriptionID subscribe(NodeFilter, DataFilter, EventFilter, Callback) – – – – Events matching NodeFilter,... ... occurring on a data item matching DataFilter,... ... and belonging to a node matching NodeFilter... ... are returned to the caller through the specified Callback IS-MANET kick-off meeting 30 Politecnico di Milano PeerWare: Global primitives <Item[],SubscriptionID> executeAndSubscribe( NodeFilter, DataFilter, EventFilter, Action, Callback, Mode) – Equivalent to an execute atomically followed (on each single host) by a subscribe – It allows programmers to “hook” upon some data and provide “strong consistency” on the content of that data • Through event notifications that inform the caller of any further change on that data IS-MANET kick-off meeting 31 Politecnico di Milano PeerWare: Different scenarios Peer to peer with base stations Fixed backbone of PeerWare servers Dynamic fringe of mobile or disconnected nodes IS-MANET kick-off meeting 32 Politecnico di Milano PeerWare: Different scenarios “Strongly” peer to peer Mobile hosts connects in an adhoc network Querying and publishing/subscribing proceed as before IS-MANET kick-off meeting 33 Politecnico di Milano PeerWare: The prototype Current prototype is oriented to enterprise networks – Base station scenario Provides limited mechanisms to reconfigure the overlay network of peers – Only leaf nodes may join and leave at run-time IS-MANET kick-off meeting 34 Politecnico di Milano PeerWare: Conclusions PeerWare brings together the best of two worlds... – It is possible to mix together message-based and state-based communication • In a single model (with nodes acting as a unique mechanism to limit the scope of queries and subscriptions) – It does not suffer of the scalability problems of Linda-like middleware • Access to the distributed data structure is not atomic • Events combined with the executeAndSubscribe primitive provide great expressive power ... in a peer to peer architecture Applicability – Within the EU project MOTION PeerWare has been used to develop a collaborative application in an enterprise scenario IS-MANET kick-off meeting 35 Politecnico di Milano Future work Publish-subscribe middleware – Find some mechanisms to maintain the overlay network – Generalize the approaches to other architectures (generic graphs) – Introduce these mechanisms in Jedi PeerWare – “Port” the mechanisms above to PeerWare to support more dynamic scenarios – Validate the middleware by using it in different environments IS-MANET kick-off meeting 36