Genc Tato
email: genc.tato@inria.fr

Marin Bertier
email: marin.bertier@irisa.fr

Cédric Tedeschi
email: cedric.tedeschi@inria.fr

Koala: Towards Lazy and Locality-Aware Overlays for Decentralized Clouds

Current cloud computing infrastructures and their management are highly centralized, and therefore they suffer from limitations in terms of network latency, energy consumption, and possible legal restrictions. Decentralizing the Cloud has been recently proposed as an alternative. However, the efficient management of a geographically dispersed platform brings new challenges related to service localization, network utilization and locality-awareness. We here consider a cloud topology composed of many small datacenters geographically dispersed within the backbone network.

In this paper, we present the design, development and experimental validation of Koala, a novel overlay network that specifically targets such a geographically distributed cloud platform. The three key characteristics of Koala are laziness, latencyawareness and topology-awareness.

By using application traffic, Koala maintains the overlay lazily while it takes locality into account in each routing decision. Although Koala's performance depends on application traffic, through simulation experiments we show that for a uniformly distributed traffic, Koala delivers similar routing complexity and reduced latency compared to a traditional proactive protocol, such as Chord. Additionally, we show that despite its passive maintenance, Koala can appropriately deal with churn by keeping the number of routing failures low, without significantly degrading the routing performance. Finally, we show how such an overlay adapts to a decentralized cloud composed of multiple small datacenters.

I. INTRODUCTION

Over the last decade, as a result of both industrial and academic research, cloud computing has entirely reshaped the way computing infrastructures are managed. Major industry actors such as Amazon and Microsoft are currently the main owners of the cloud infrastructure. Recently, these companies have built very large datacenters in various locations around the globe, trying to move computation closer to their clients. Still, their architecture remains primarily centralized. Centralized architectures have certain advantages, such as easy management and more optimization opportunities. Nevertheless, the distance between a centralized datacenter and its clients is often significant. This results in increased latency, higher energy consumption [START_REF] Cordero | GRaNADA: A Network-Aware and Energy-Efficient PaaS Cloud Architecture[END_REF], and is subject to legal restrictions [START_REF] Pearson | Privacy, security and trust issues arising from cloud computing[END_REF].

Various initiatives, such as the Discovery project [START_REF] Bertier | Beyond the Clouds: How Should Next Generation Utility Computing Infrastructures Be Designed[END_REF], have suggested an alternative to such a centralized architecture by bringing the Cloud even closer to its clients. They propose a fully decentralized architecture which leverages the existing Internet Service Provider (ISP) backbone network infrastructures, by introducing computing resources in Point of Presence (PoP) within the backbone. In this vision, each PoP potentially hosts a small datacenter which interacts with other small datacenters (in other PoPs) in a decentralized, peerto-peer (P2P), way in order to provide the same services as the traditional Clouds, but at a reduced cost.

A first challenge brought by decentralization is the needed functionality of service localization. In a centralized architecture, there is a single point of reference able to provide information about the status of services/resources available in the platform. In a decentralized Cloud instead, no single component has a global knowledge of the system, yet every node in the system should be able to process any query, based on a partial view of the platform. In other words, we need an overlay network to define these partial views and a routing mechanism which allows us to efficiently reach the server in charge of a specific service given a service ID.

A second challenge is the efficient network utilization. In centralized Clouds, system maintenance traffic stays generally within the datacenter and uses dedicated links so that it does not interfere with user traffic. In decentralized Clouds instead, maintenance traffic, same as user traffic, is distributed, and they both share the same communication links.

For this reason, minimizing the management traffic is essential in order to save bandwidth for the users.

A third challenge is the reduction of latency by leveraging locality, one of the main motivations of decentralized Clouds. We distinguish two kinds of locality-awareness, namely inter-PoP and intra-PoP. Inter-PoP locality-awareness means that the logical path of a message travelling between different PoPs should resemble as much as possible to the physical one. We refer to this kind of locality-awareness as latency-awareness hereafter.

Intra-PoP locality-awareness means that a message between nodes in the same PoP should not leave this PoP. We refer to this as topology-awareness hereafter.

In order to address these challenges we have recently described Koala [START_REF] Tato | Designing Overlay Networks for Decentralized Clouds[END_REF], a structured overlay network for efficient service localization which minimizes management traffic while providing locality-aware routing. While in [START_REF] Tato | Designing Overlay Networks for Decentralized Clouds[END_REF] we present the key design features of Koala, the current paper presents Koala's architecture and algorithms and their validation through a comprehensive set of simulations.

Koala nodes use the Kleinberg model [START_REF] Kleinberg | The small-world phenomenon: An algorithmic perspective[END_REF] based on logical distance (difference in node identifiers) for filling their routing 1 tables. While Kleinberg defines the ideal entries for a node's routing table, Koala nodes do not actively search for nodes matching these ideal entries, but rather fill the routing tables opportunistically, when such nodes come to their knowledge through information piggybacked in the application traffic. In other words, if no traffic is generated by the application, there is no traffic at all within the overlay. Koala's performance depends on the amount of traffic generated by applications running on top of it (for instance a cloud stack). Regarding locality-awareness, Koala focuses primarily in reducing inter-PoP latencies by making nodes select each routing hop according to a tradeoff between a latency-based and a greedy routing based on logical distance. Koala also provides a way to take the multi-PoP topology into account through integrating the information of which datacenter a node belongs to in its identifier, thus enabling intra-PoP routing when possible.

Our experiments show that despite its lazy maintenance, Koala still delivers a similar complexity to proactive protocols, while it further reduces latencies due to its latency-aware routing. Additionally, they show that passive maintenance is sufficient for repairing the overlay in case of reasonable churn. Finally, we show that Koala adapts well to a multi-datacenter environment.

The remainder of this paper is organized as follows. Section II presents Koala's related work. Section III presents the details of the protocol. Section IV presents our simulation results. Section V concludes.

II. RELATED WORK A. Structured, unstructured or hybrid?

Overlay networks are generally either structured or unstructured. Structured overlays offer efficient data retrieval mechanisms but they rely on the maintenance of a specific routing structure which can become costly to maintain as churn increases. On the other hand, unstructured overlays are designed to be resilient to churn, but this benefit comes at the cost of redundant periodic messages, and hence a very high network utilization. Additionally, unstructured overlays are not designed to support efficient unicast. Aiming at combining the best of both worlds, hybrid overlays can be found in literature. These are generally structured overlays built on top of unstructured ones. In this case the unstructured overlay is responsible for the membership management and the structured one for the efficient routing.

Structured overlays are commonly used to build distributed hash tables (DHTs). DHTs such as Chord [START_REF] Stoica | Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[END_REF], Pastry [START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF] or Kademlia [START_REF] Maymounkov | Kademlia: A Peer-to-Peer Information System Based on the XOR Metric[END_REF] focus on guaranteeing message delivery in a logarithmic number of hops. This relies on strict rules for filling routing tables. Maintaining such a rigid structure is costly, therefore other protocols introduced some flexibility into the routing table construction. The authors of Symphony [START_REF] Manku | Symphony: Distributed Hashing in a Small World[END_REF] show that the same complexity can be achieved by choosing the long links randomly, yet carefully (based on a specific probability distribution). However, in all these cases there is a background mechanism for detecting and repairing inconsistencies in the routing table. These mechanisms run either continuously or periodically, and therefore they have a high cost on network utilization.

Unstructured overlays, on the other hand, do not build their routing tables (or partial views) based on strict rules. For instance, HyParView [START_REF] Leitao | Hyparview: A membership protocol for reliable gossip-based broadcast[END_REF] selects neighbors entirely randomly, while Scamp [START_REF] Ganesh | Scamp: Peer-to-Peer Lightweight Membership Service for Large-Scale Group Communication[END_REF] and CLON [START_REF] Matos | CLON: Overlay Networks and Gossip Protocols for Cloud Environments[END_REF] use a probabilistic model for accepting new neighbors based on the number a node has currently. This simplifies the maintenance of the partial view in case of failures because nodes do not need to search for specific entries. However, for the overlay to be efficient, nodes need to continuously exchange these partial views (using gossiping). This can be done periodically, as in HyParView, or reactively, as in Scamp. Reactive gossiping happens only when nodes detect some change. CLON is an adaptation of Scamp for multi-clouds. It improves Scamp's partial view exchange by favoring nodes in the same datacenter more than those in different ones. Regarding the network utilization, unstructured overlays are expensive not only when adopting a periodic approach but also when adopting a reactive one. This is because for the overlay to be reactive, connections need to be continuously monitored.

In order to benefit from the reliability of unstructured overlays and the efficiency of unicast in structured ones, several studies focus on hybrid overlays. T-Man [START_REF] Jelasity | Third International Workshop on Engineering Self-Organising Systems (ESOA 2005)[END_REF] and Fluidify [START_REF] Resmi | Fluidify: Decentralized Overlay Deployment in a Multi-cloud World[END_REF] are examples where structured overlays are created as a result of filtering information which comes from gossiping. T-Man provides a generic interface which can be used to create structured overlays based on custom criteria. Fluidify instead, is more specific and it uses gossiping to select nodes which are physically close to improve locality-awareness. Even though these protocols combine the advantages of both types of overlays, they still suffer from the same drawbacks when it comes to network utilization.

B. The scale of laziness

As a structured overlay, Koala shares many core aspects with similar overlays, such as Chord and Symphony. However, it does not have any background mechanism for detecting and repairing the routing table. Problems are detected and repaired in a lazy way, only when routing application traffic by means of piggybacking. Piggybacking is used also in Kademlia, but only partially, to improve multiple routings between the same source and destination. The concept of using application traffic for building overlays is used also in [START_REF] Koloniari | Query workloadaware overlay construction using histograms[END_REF]. This study assumes that the application issues repeatedly similar queries, and therefore it links together nodes which collaborated in previous queries. This means that the overlay is adapted to a specific application. Koala instead, uses application traffic to optimize the overlay independently of the applications running on top of it. Relax-DHT [START_REF] Legtchenko | RelaxDHT: A Churn-Resilient Replication Strategy for Peer-to-Peer Distributed Hash Tables[END_REF] follows a lazy approach on data replication, by allowing replicas to get further from the root as the network evolves. In this way it avoids the need for a systematic rearrangement of data blocks whenever a node joins or leaves. However, this technique reduces data maintenance rather than overlay maintenance as in Koala. A concept of laziness similar to the one of Koala is introduced in [START_REF] Pastor | Locality-aware cooperation for VM scheduling in distributed clouds[END_REF], but in an entirely different context, namely the locality-aware placement of virtual machines used by a given application. Figure 1 shows an overview of the overlay families we discussed above ordered by their laziness. In this paper we do not quantitatively compare the laziness of Koala with respect to other proactive overlays as this depends on certain parameters which can vary, such as the periodicity for gossiping or for running the maintenance protocol. We rather insist on the conceptual difference and show that despite being fully lazy, Koala can perform at least as good or even better than non-lazy protocols. For our comparison, we have used Chord as a representative of structured overlays which has been shown to offer the best trade-off between bandwidth used and lookup latency [START_REF] Li | Comparing the Performance of Distributed Hash Tables Under Churn[END_REF].

C. Locality-awareness

Latency-awareness can be introduced into overlays through different mechanisms, namely (i) topology-aware overlay construction, (ii) topology-aware neighbor selection, and (iii) proximity routing [START_REF] Castro | Topology-Aware Routing in Structured Peer-to-Peer Overlay Networks[END_REF]. Topology-aware overlay construction consists in choosing logical neighbours according to their physical proximity. Fluidify [START_REF] Resmi | Fluidify: Decentralized Overlay Deployment in a Multi-cloud World[END_REF] follows this path: it updates the logical identifiers according to the identifiers of physically close nodes. A similar technique is used by Vivaldi [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF], but for placing nodes in a Cartesian space according to latencies experienced between nodes. In contrast to Fluidify, which receives latencies from an underlying gossip protocol, Vivaldi uses application traffic, and therefore is lazier.

Topology-aware neighbor selection consists in choosing the physically closest node among viable candidates. This is done only when there is some flexibility to fill a given entry of the routing table. This is why T-Chord [START_REF] Montresor | Chord on demand[END_REF] relaxes Chord's constraints for having a link at a precise distance, by allowing a range of values around this distance. Links with the lowest latency satisfying the logical constraints are selected for each entry. However, similar to Fluidify, T-Chord is based on the same gossip underlying mechanism. In Pastry [START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF] instead, nodes obtain lazily low-latency neighbors during the joining phase but then need to actively update them at a second stage.

Proximity routing consists in taking routing decisions not only according to the remaining logical distance to the destination, but also on the delay of the next hop. It is the lightest approach, since it does not require any routing table modification. This approach has been adopted by Hypeer [START_REF] Serbu | HyPeer: Structured Overlay with Flexible-Choice Routing[END_REF], which aims at introducing latency-awareness in Chord by changing the order of its hops. Its authors show that by making Chord choose the next hop based also on latency improves its overall performance. Koala also uses primarily this technique due to its lightness. Still, Koala is more flexible than Hypeer as it is not restricted by the order on hops.

III. PROTOCOL A. Model

We consider a distributed system consisting of nodes which communicate via message passing. These nodes are grouped into different physical locations called Points of Presence (PoPs) and are interconnected so that a message sent from one node can be delivered, in finite time, to any other one. We assume that the latency of a message within the same PoP is insignificant compared to the one between different PoPs. We assume that a communication channel between any two given nodes can be established and that these channels are fair-lossy, meaning that the channels can lose a finite number of messages. Nodes can join or leave (crash) at any time. The crash can be permanent or the node can recover, but then it has to re-join the system. As we aim to use Koala to interconnect nodes in different PoPs, we assume a reasonable level of churn.

B. Koala: under the hood

Similar to Chord, nodes in Koala are organized logically in a ring by assigning them a unique m-bit ID from a circular ID space, as shown in Figure 2. However, in contrast to Chord, routing in Koala is bidirectional, meaning that the logical distance d between two IDs is the smallest between the distances calculated in both directions, clockwise and counterclockwise, and it is defined as follows:

d(id 1 , id 2 ) = min(|id 1 -id 2 |, 2 m -|id 1 -id 2 |) (1)
Each node has a routing table. For each entry of the routing table, a node stores four fields: i) the logical ID, ii) the IP, iii) the latency when reaching that entry expressed in Round Trip Time (RTT) and iv) an Ideal ID (IID) field that we explain below. Routing entries can be classified in two main groups: core links and optimization links. Neighbors are nodes with predecessor or successor IDs in the identifier space. They ensure the ring structure is maintained so that every node is reachable. A node can keep multiple pairs of neighbors, for instance, 2 predecessors and 2 successors.

Long links are entries which enable shortcuts in the ring structure and affect routing significantly. In order to provide a logarithmic routing, long links need to be carefully selected at different logical distances from the node itself. In Koala we do this by using a continuous version of Kleinberg distribution which is defined as follows: p n (d) = 1/(d ln(M )). This formula defines the probability to have a long link at a distance d, where M is the maximum distance in the ring. Given that Koala is bidirectional, this distance is half of the ring, 2 m-1 . Note that this distribution favors shorter distances over long ones, enabling logarithmic routing. As we detail below, we use this probability distribution to generate the ideal distances at which our long links should be. Consecutively, we convert these distances into IDs by randomly either adding or subtracting them from the ID of the node itself. The generated IDs constitute the ideal IDs (IIDs) for our entries. Note that generating the IID fields for long links does not mean that nodes with this IID exist. We could actively search for them, but that is against the principle of laziness. Therefore, we rather wait to learn about them (or nodes with close IDs to them) in a process we describe later.

2) Optimization links: are additional links which are not necessary for the functioning of the overlay but that can optimize it further. We focus particularly on proximity links, but other kinds of links, such as random links or application links can be used as well in certain situations. Proximity links are a distinct set of nodes with which a node has communicated in the past and which have a small RTT value. They are ordered in a fixed size queue based on the RTT value. As entries with smaller latency are added, the ones with higher ones are removed. The combination of long links, which are selected based on their logical distance, and proximity links, which are based on their latency, provides a good input for our latency-based routing algorithm we explain shortly.

Random links and application links can be used to improve the diversity of entries for nodes with similar IDs and to adapt the overlay to the application, respectively. Random links are particularly useful when nodes in the same PoP share a part of their ID. Similarly, application links are handy when considering particular application patterns. In this paper we consider a uniformly distributed traffic, and therefore impact of these links is left as a future work.

The number of entries in each group is configurable. For Kleinberg distribution to provide O(log N ) routing (N being the size of the network), we need at least m long links. Therefore, for long links we choose a multiple of m such as N r ll = C ll * m. We configure the number of long links by setting the value of C ll . Although not necessary for the routing complexity, we can do the same thing with the size of the other groups of links so that it remains relative to the size of the system. Thus, C n , C pl can control the number of neighbors and proximity links, respectively.

C. Routing: greedy, latency-based, or both?

Once we have defined the routing table, we need to define a routing algorithm which determines the next hop for a message. The Kleinberg distribution of long links provides us with a logarithmic complexity in terms of number of hops if a greedy algorithm is used. Greedy routing selects the entry which reduces the most the remaining logical distance to the destination. Nevertheless, it does not consider the cost of each hop in terms of latency. As a result, even though the number of hops is reduced, the cost of the total path might still high. On the other hand, an algorithm which selects the entry with the lowest latency, without considering the logical distance, does not provide correctness and can increase drastically the number of hops. We examine an algorithm which takes into account both factors, logical distance and latency and provides a tradeoff between them. This is done by rating each potential entry as follows:

R entry = 1/(α * d(entry.ID, dest.ID) + (1 -α) * norm(entry.RT T )) [START_REF] Castro | Topology-Aware Routing in Structured Peer-to-Peer Overlay Networks[END_REF] where d(entry.ID, dest.ID) is the remaining logical distance if we choose the entry, norm() is a normalization function which converts the value of RTT into the same scale as the logical distance, and α is a coefficient which determines the weight of each of the factors. An α = 1 results in a purely greedy algorithm, and an α = 0 in a purely latency-based one. Note that the normalization function maps the minimum and maximum values for the remaining distance to those of the RTT, and derives the values in between using a linear function. The remaining distance can vary from 0, when the next step is the final destination, to d(node.ID, dest.ID) -1 if we progress just by one step. For the RTT, the maximum value can be introduced empirically (if the estimation is smaller than the real value, the consequence is the same as decreasing α. Similarly, a higher estimation is equivalent to increasing α. Algorithm 1 Routing. The details of the routing algorithm is provided by Algoritm 1. When a node receives an application message the OnRoute methods is called. If this node is the destination, the message is sent to the application, otherwise it is forwarded to the node with the highest rating in the routing table (in getNextHop). Note that in the function getRating we discard nodes for which the distance to the destination is smaller than the one of the node itself (Line 23). This provides correctness even when α = 0. Additionally, if the destination is present in the routing table, we forward directly to that entry without taking into account the latency (Line 25).

D. Joining

As shown in Algorithm 2, before joining the network a node generates its own unique m-bit ID by hashing its IP using a arbitrary-length output hash function (Line 2). Based on this ID it initializes its long links. As we explained before, for each link we generate random distances according to Kleinberg distribution and convert them into IIDs by randomly adding or substracting them from the ID of the node. Note that initially, the ID, IP and RTT fields are set to some default values (Line 9). ID df is a special value such that its distance from any other ID is infinity: d(ID df , * ) = ∞. IP df is an empty string, whereas RT T df is set to an approximate value of the average RTT in the system. After the initialization phase, the node tries to join the network by sending a "exchange routing table" request to an existing node (commonly called the bootstrap node) which IP address is known beforehand (Line 4).

Algorithm 2 Joining. This request triggers the onExchangeRT handler on the recipient node. The latter examines the received routing table, which includes all parameters passed to the ExhangeRTMsg constructor, and checks if there are neighbors or links of interest. That is, a link which ID is closer to the IID of any of the current links than the ID of the link itself. If such a link is found we update our current links as shown in method updateLinks. Since the sender just joined, the received table consists of only the sender. Assuming that the first recipient is not an immediate neighbor of the joining node, the request is forwarded to an entry in the routing table (Line 27). Forwarding will continue until a neighbor of the joining node is reached.

The neighbor will reply to the joining node by sending its routing table, its own entry details and its old neighbors (Line 24). The joining node, would look through the received entries and update its long links (generally copy them) and also find the other immediate neighbor, which was the old neighbor of the sender. Consequently, the joining node would contact it as well and receive from it its routing table which will be used to update its long links. Note that from the pseudo-code above an extra message is sent to the first discovered neighbor but that can be avoided by specifying a flag for the exchange request which distinguishes joining requests from the others. As a result of these exchanges, the joining node will find its correct position in the ring and will have a list of links by merging the routing tables of its immediate neighbors.

E. Lazy learning

As described above, a node learns from its neighbor about links of interest already during joining. However, learning does not stop there, but it continues permanently as messages are routed. Each routed message is provided with a data structure very similar to the routing table of the nodes (the msg.piggybackRT). At each step during routing, this structure is enriched with information about existing nodes. One source of this information is the path of the message. Whenever a node forwards a message, it piggybacks on it its own details as shown in Line 5 of Algorithm 1.

A second source of piggybacked information is the routing tables of nodes in the message's path. The source node which starts the routing request initializes also the piggyback structure of the message as shown in Algorithm 3. This is very similar to the initialization of the long links except that the distribution is rather uniform. This is done to improve the diversity of the information coming from the first source as this does not depend strictly on the path itself. Note that we keep the size of the piggyback structure logarithmic to the size of the network as we do with all the other structures using the C pb setting. The value of C pb is chosen based on a tradeoff between fast learning and message overhead. Algorithm 3 Learning while routing. Whenever a message is received the onReceiveMsg handler is called. Initially the receiver node will look in the piggybacked structure for links of interest and neighbors as done during routing table exchanges. At a second step, it will try to update this structure with links from its own routing table. Therefore, at each step a node receives information about the nodes present in the network and distributes also its own knowledge. These simple mechanism can be thought of as passive gossiping. Each node gossips information about the state of the network, but without periodically contacting any node solely for this purpose. As a result, the speed of learning about the network depends directly on the amount of application traffic.

F. Resilience

The extent to which a protocol is resilient to changes in the network depends on its ability to maintain the links in the routing table. However, periodic maintenance procedures are not compatible with our main principle, which is being as lazy as possible. For this reason, our protocol is not designed to support high degrees of churn. Nevertheless, we take a few inexpensive measures to support churn to some degree.

Node joining and departing are handled differently depending on whether they are neighbors or long links. In case they are neighbors, taking action immediately is much more important than when they are long links. As described before, when a node joins the network, its future neighbors are immediately notified. On the contrary, upon a node departure, its neighbors are not notified until one of them tries to contact it. At this point, it will remove it from the routing table and will exchange routing tables with the next node in its neighbors list so they become immediate neighbors. For this to work, the list of neighbors needs to be up to date. We do this by piggybacking neighbor information when messages are exchanged between neighbors. For instance, when node q sends a message to its successor s, it also reports its predecessor p. So in case q departs, s and p will exchange routing tables. This is shown in lines 7 -10 of Algorithm 1. This lazy mechanism for knowing neighbors' neighbors does not guarantee that the information will not be outdated. In case a node loses all its neighbors in a certain direction (for example, all the predecessors), it will try to search for its new neighbors by contacting a working long link in the vicinity (possibly in the direction of the lost neighbors). This is a special search because it targets nodes between the long link and the node, therefore it follows always the same direction in the ring. If no intermediate nodes are found, then the long link becomes the new neighbor.

In case a long link joins or departs, the management is more straightforward. Joining nodes which might be ideal long links for current nodes are noticed only as information gets disseminated using piggybacking. A node will realize that a long link is down only when trying to forward a message to it. In that case, it will forward the message to the link with the second highest rating according to Equation 2, and it will mark this link as down. That means that this link can be replaced with other links, even with a higher difference form the IID. In order to avoid re-adding links, we timestamp each link using a Lamport clocks [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]. When the rating of all entries in the routing table are smaller than the one of the node itself, the node declares failure to the sender of the message. This happens only in cases of extreme churn, when all the nodes in the routing table with a closer ID to the destination are down, including neighbors, which can be temporarily unavailable during the neighbor searching phase.

IV. EXPERIMENTAL VALIDATION

In order to evaluate our overlay, we have conducted various experiments using the PeerSim [START_REF] Montresor | PeerSim: A scalable P2P simulator[END_REF] simulator. For each experiment, we use the same basic setup. We assign random coordinates to each PoP on a unit 2D-coordinate system. Nodes within the same PoP have the same coordinates. We use the Waxman model [START_REF] Waxman | Routing of multipoint connections[END_REF] for creating links between these PoPs. In this model the coefficients α and β are selected in such a way that the model respects roughly the neighbor degree of Renater1 , a research ISP network in France. This model does not guarantee a connected graph at once. Therefore we recursively apply Waxman on randomly picked nodes from the connected sub-graphs until the graph is connected. The resulting topology represents our physical network. In order to simulate the IP routing in the physical network, we use Dijkstra shortest path algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], where the cost of an edge is a function of the Euclidian distance between the nodes. The cost of a physical path represents its RTT. Consequently, the RTT of a logical path in Koala is the sum of RTTs of all physical paths composing it.

In order to compare Koala with physical routing or other protocols, the simulator assigns the exact same list of tasks to all protocols. A task can be: routing a message, adding a node, or removing a node. At the end of a task, metrics such as RTT, physical and logical hops, and failures are collected and compared. Although we use PeerSim in the event-based mode, tasks are processed on a cyclic basis. At each cycle one or more tasks can be processed. Our reported results are based on the average values of a group of cycles. We show the size of this group in round brackets in the X-axis label.

We conduct four sets of experiments, presented in sections IV-A to IV-D, which focus on: Koala's scalability, latency-awareness, reliability and topology-awareness, respectively. The first three sets concentrate on Koala's inter-PoP aspects, and therefore we assume each node belongs to a different PoP, i.e. we have one node per PoP. However, in the fourth set, we focus on topology-awareness, and therefore we consider multiple nodes per PoP.

A. Number of long links and scalability

In the first experiment, we study the behavior of our overlay as the network scales up. Following a uniform traffic distribution (we plan to work with real traces in our future work), at each cycle, one node joins the network and also a Fig. 3: Latency and hops as network scales up to 100K nodes.

message is sent from a random source to a random destination. We scale up to 100K nodes and assume no node leaves the network. We run the same experiment for different numbers of long links, by varying the constant C ll . We fix α to 1, therefore routing does not take the RTT into account. As for the rest of the experiments, the number of neighbor pairs is set to 2 (C n = 2/m, 2 successors, 2 predecessors), and the piggyback list size to m (C pb = 1). In this case proximity links are not considered (C pl = 0). Figure 3 shows how latency and logical hops are affected as the network scales up (physical hops are omitted as we focus on the comparison of logical ones).

As mentioned in section III-B, N r ll = C ll * m. For N = 100K, m = 17, therefore C ll = 1, 2, 4 correspond to 17, 34 and 68 long links. Note that one point in the graph represents the average of 100 routes. In Figure 3, we observe that regardless of the number of links, both latency and hops grow logarithmically as more nodes join. It is clear that the higher the number of long links, the lower the latency and the hops. However, by doubling the number of links, we do not reduce twice the latency. Therefore, at some point, increasing further the number of long links would not provide significant benefit, while it might introduce additional latency in case of multiple attempts to connect to stale long links.

B. Lazy learning and latency-awareness

In the following experiment, we demonstrate the ability of Koala to discover the network in a lazy way, as application messages are routed. We particularly focus on the impact of the parameter α on latency and hops. We use a static network of 10K nodes, where no nodes join or leave the network. For this experiment we compare our protocol with Chord. At each cycle, both protocols are requested to route a message from the same random source to the same random destination. As in the previous experiment, we fix the number of long links by setting C ll = 2 (28 long links) and we do not consider proximity links. For Chord we use 4 successors (equal to Koala's neighbors). We repeat this experiment by varying α from 0 to 1, by adding each time 0.25. Figure 4 shows the impact of this variation on latency and number of hops.

We observe that regardless of the value of α, as more messages are routed, Koala nodes discover long links which are closer to their ideal ones, thus latency and hops decrease over time. Note that this learning is faster at the beginning. As the discovered long links comply more and more with the Kleinberg model, finding the exact ideal link does not result in significant latency improvements.

Concerning the impact of α on latency and hops, we notice that for α = 0, when the routing decisions are almost not at all based on logical distance, Koala delivers a poor performance. This is because at each hop a message is always forwarded to nearby nodes without significantly approaching the destination, which leads to many hops and as a consequence, in very high latencies. However, if we consider slightly more the logical distance (α = 0.25), we still have a relatively high number of hops, but we significantly improve the latency compared to when α = 0. On the other hand, for α = 1, when routing is based solely on logical distance, we achieve the lowest number of hops, but that does not mean the lowest latency. To improve latency, one needs to take RTT more into account by reducing α. This can be done until an equilibrium is found where reducing it more results in higher latency as the number of hops also increases. For our simulation, this equilibrium happened to be for α = 0.5, but this value depends on various factors such as network topology and traffic pattern.

In addition, we notice that for this setting Koala delivers the messages up to 32% faster than Chord. This is not only because Koala uses more long links (accountable for 65% of the gain when α = 1), but also due to its latency-awareness (accountable for the additional 35% of the gain when α = 0.5).

So far we have considered only links selected on their distance criteria, and therefore the tradeoff routing function is mainly determined by the logical distance. We continue the previous experiment by considering proximity links too. We do not change the overall number of links, instead we divide them equally between long links and proximity links. Therefore, we compare using C ll = 2 with C ll = 1 and C pl = 1. We do this for the best setting from the previous experiment, when α = 0.5 and fix this setting for the rest of the experiments.

In Figure 5 we observe that when combining long links and proximity links, the number of hops is slightly higher than when using only long links. However, as more and more proximity links are found the routes are more latency-aware and the delivery time is improved (by additional 10%).

C. Resilience to churn

Differently from proactive protocols which focus on avoiding failures by actively maintaining their routing table, Koala focuses on repairing itself once the failure has already happened. Therefore, in the next two experiments we study Koala's ability to repair itself under churn.

In the first experiment we consider a network of 5K nodes. As before, at each cycle a message is routed between a random source and a random destination. However, every 80 cycles, CHURN nodes leave the network, and the same number join. These two events do not necessarily happen in the same cycle. In all the experiments in this section we use C ll = 2 and no proximity links as we mainly focus on keeping the Kleinberg properties under churn. We analyze how Koala deals with various levels of churn by varying the number CHURN.

Figure 6 shows the effect of churn on latency (upper part) and failure rate, i.e., percentage of messages that failed to reach their destination (lower part). In the upper part of this figure we notice that, as the level of churn increases, the routing latency of successfully delivered messages increases as well, but rather gracefully. This is due to our learning techniques which help nodes to update their stale links without significantly breaking the Kleinberg distribution. Nevertheless, the same thing cannot be said for the number of failures. The lower part of Figure 6 shows that for low levels of churn (CHURN = 1 or 2), the lazy repairing is efficient enough to keep failure rate low. However, as churn levels increase (CHURN = 8), the overlay does not process enough traffic per unit of time in order to repair before other changes in the network occur. In that case the failure rate continuously grows, but note that this is an extreme level of churn.

In the next experiment we analyze the ability of Koala to repair itself in case of an abrupt failure of a whole section of the network (CHURN SEC). In this case, we consider a network of 10K nodes with no joins. At each cycle, we route as in the previous experiments, but at cycle 5K we introduce the unexpected failure. We vary the size of the failed section and show its effects on latency and failure rate in Figure 7.

As the amount of long links per node affected by this sort of failure is significantly higher than in the previous experiment, the Kleinberg distribution is initially broken, and this results in higher latencies. However, as the ring starts repairing itself and the number of nodes is reduced, the latencies are reduced as well. Nevertheless, the lower part of Figure 7 shows that the ability of Koala to repair depends on the amount of failed nodes. We can observe that the higher this amount, the longer it takes for the overlay to rebuild itself. Moreover, if this section of the network is too large (90%), Koala is not able to fully recover anymore, but this is rather unrealistic.

D. Topology-awareness

Until now we have considered only one node per PoP in order to focus on inter-PoP aspects of Koala. We now consider a topology of PoPs having multiple nodes. We examine two cases: when Koala is unaware of which nodes belong to which PoPs, and when Koala is given this information. In the first case, node IDs are generated entirely randomly, and thus nodes belonging to the same PoP might have distant IDs. In the second case instead, we assume we know whether nodes belong to the same PoP, and therefore we assign them consecutive IDs. This is done by reserving a range of IDs for each PoP, but it requires a rough estimation of the maximum number of PoPs and of nodes per PoP.

For this experiment we consider a network of 10K nodes divided in 1K PoPs (10 nodes per PoP). As in experiment IV-B, the network is static, and at each cycle a message is sent from a random source to a random destination. We use the same number of long links and proximity ones (C ll = 1, C pl = 1). We run this experiment twice, once when node IDs are assigned randomly, and once when nodes in the same PoP are assigned consecutive IDs, for both Koala and Chord.

In Figure 8 we observe that when IDs are fully random we obtain very similar results as in experiment IV-B, where we considered one node per PoP. This is because, with a high probability, nodes in the same PoP will not be in each others' routing table. Therefore, even when routing within the same PoP, the message might travel through different other PoPs before returning to the initial one. Consequently, nodes behave as if they were in different PoPs and they do not take advantage of the low intra-PoP latencies.

On the other hand, when nodes in the same PoP are assigned consecutive IDs, we notice that both Koala and Chord improve their latency. However, Koala delivers a greater improvement (≈ 28%) than Chord (≈ 16%). This difference is significant given that the lower the latencies of the messages, the more difficult it is to further improve them, and Koala already delivered better latencies than Chord. The reason why Koala exploits better this extra information is the routing tradeoff function we explained in section III-C. In Koala, a non-local message will initially travel locally within the PoP (using very cheap hops and small gains in logical distance) until it finds a good option, for which jumping outside the PoP is more convenient as the gain in logical distance justifies the higher latency. In this way, Koala makes better decisions before choosing the next PoP. On the contrary, Chord would choose to send a non-local message immediately to another PoP by trying to reduce the distance in IDs without consulting before local nodes. However, Chord's hops become smaller as the message approaches the destination, and thus Chord's final hops are also within the same PoP. Therefore, Chord also exploits the PoP topology, but to limited extent.

V. CONCLUSIONS AND FUTURE DIRECTIONS

Koala is an overlay network designed to target decentralized cloud environments. It provides efficient, locality-aware service localization while it minimizes traffic by eliminating useless overlay maintenance. When the application stops communicating, Koala stops communicating too. Our experiments show that, despite its laziness, Koala still guarantees a similar performance to other traditional protocols by providing a O(log(N )) complexity. They suggest that by finely tuning the degree of locality-awareness, we can reduce further the inter-PoP latencies. Additionally, experiments demonstrate that Koala can appropriately handle churn by lazily repairing the overlay. Finally, we show that just by assigning consecutive identifiers to nodes in the same PoP, Koala becomes intra-PoP locality-aware as well and it adapts to the decentralized cloud topology much better than Chord. In this paper we have focused on the core features of Koala which deal mainly with inter-PoP aspects. Our next step is to formalize the intra-PoP locality-awareness without the need to reserve identifier intervals for the different PoPs. We plan to split the node identifier in two parts: one part for the PoP, and another part identifying the node within the PoP, enabling a distinction between intra and inter-PoP routing policies and thus in a reduction of the ring diameter. Additionally, we intend to investigate intra-PoP collaboration for a better inter-PoP routing without introducing hierarchies. On more practical aspects, we plan to devise the integration of Koala into a decentralized OpenStack, to support decentralized messaging, as conveyed by the Discovery project [START_REF] Bertier | Beyond the Clouds: How Should Next Generation Utility Computing Infrastructures Be Designed[END_REF].

Fig. 1 :

 1 Fig. 1: Ordering overlays according to laziness.

15 Fig. 2 : 1 )

 1521 Fig.2: Logical ring in a small network (m=4), and the routing table of node 0.1) Core links: are entries which are essential for enabling efficient routing. They can be either neighbors or long links.Neighbors are nodes with predecessor or successor IDs in the identifier space. They ensure the ring structure is maintained so that every node is reachable. A node can keep multiple pairs of neighbors, for instance, 2 predecessors and 2 successors.Long links are entries which enable shortcuts in the ring structure and affect routing significantly. In order to provide a logarithmic routing, long links need to be carefully selected

Fig. 4 :

 4 Fig. 4: Impact of α on latency and hops.

Fig. 5 :

 5 Fig.5: Impact of proximity links on latency and hops.

Fig. 6 :

 6 Fig. 6: Impact of churn on latency and failure rate.

Fig. 7 :

 7 Fig. 7: Impact of a massive failure on latency and failure rate.

Fig. 8 :

 8 Fig. 8: Impact of cloud topology on Koala and Chord.

  function onJoin( ) 2: this.ID = Hash(this.IP, m) 3: this.intializeLongLinks() 4: send(this.bootNode, ExhangeRTMsg(this.RT + [this.asEntry()])) 5: function intializeLongLinks( ) 6: this.RT.longlinks ← [ ] 7: for i = 1 → C ll * m do 8: Entry(ID df ,IP df , newIID, RT T df )

		newIID ← this.getKleinbergIID()
	9:
	10:	this.RT.longlinks.add(newLL)
	11: function getKleinbergIID( )
	12: d ← round(2 RandomDouble(0,1) * (m-1) )
	13: if RandomInt() % 2 = 0 then 14: return (this.ID+d) %2 m
	15: return (this.ID-d+2 m ) %2 m
	16: function onExchangeRT(msg)
	17: oldNeighbors ← this.getImmediateNeighbors()
	18: for each entry ∈ msg.srcRT do srcRT contains parameters of ExhangeRTMsg
	19:	updateLinks(entry, this.RT.longlinks)	omitting proximity links
	20:	updateNeighbors(entry)
	21: newNeighbors ← this.getImmediateNeighbors()
	22: for each entry ∈ newNeighbors do
	23:	if entry ∈ oldNeighbors then
	24:	send(entry, ExhangeRTMsg(this.RT + [this.asEntry()] + oldNeighbors))
	25: if msg.src ∈ newNeighbors then
	26:	fwd ← this.getNextHop(msg.src)
	27:	send(fwd, msg)
	28: function getImmediateNeighbors( )
	29: return [this.RT.neighbors.succs[0], this.RT.neighbors.preds[0]]
	30: function updateLinks(newEntry, rt)
	31: for each entry ∈ rt do
	32:	if d(entry.ID, entry.IID) > d(newEntry.ID, entry.IID) then
	33:	entry.ID ← newEntry.ID
	34:	entry.IP ← newEntry.IP
	35:	entry.RTT ← newEntry.RTT

1:

newLL ←

https://www.renater.fr


Genc Tato

Marin Bertier

Etienne Rivière

Cédric Tedeschi

ShareLatex on the Edge: Evaluation of the Hybrid Core/Edge Deployment of a Microservices-based Application

Collaborative web applications benefit from good responsiveness. This can be difficult to achieve with deployments on core data centers subject to high network latencies. Hybrid deployments using a mix of core and edge resources closer to end users are a promising alternative. Many challenges are associated with hybrid deployments of applications, starting from their decomposition into components able to be replicated dynamically onto edge resources to the management and consistency of these components' state.

We report on our experience with the hybrid deployment of ShareLatex, a legacy collaborative web application. We show how its design based on the use of microservices and resource-oriented APIs allow for an efficient modular decomposition. We detail how we adapted the application configuration for a hybrid deployment with no modification to its source code. Our experiments using a fleet of emulated users show that the use of a hybrid deployment for this legacy collaborative application can decrease user-perceived application latencies for common operations at the cost of increasing them for operations involving core/edge coordination traffic.

INTRODUCTION

The demand for low-latency internet services generates great interest towards using edge resources as a complement to traditional "core" cloud resources in data centers. Edge computing resources may offer more limited capacities or reliability guarantees than core resources, but are geographically spread closer to the end users, providing smaller network latencies [START_REF] Li | Edge-Oriented Computing Paradigms: A Survey on Architecture Design and System Management[END_REF].

A great diversity of applications can benefit from hybrid core/edge deployments [START_REF] Garcia Lopez | Edge-centric Computing: Vision and Challenges[END_REF][START_REF] Shi | Edge Computing: Vision and Challenges[END_REF]. We are interested in this paper in collaborative edition environments, web-based applications that allow geographically distributed users to concurrently edit a document. Examples include SaaS applications such as Google Documents, Microsoft Word online, Nuclino and ShareLatex. User-perceived latencies are very important for these applications. Low delays between the action of a user and the visibility of its result by other users reduce the risk of conflicts and improve the global user experience.

While edge servers have been used to improve latencies by offloading localized computation or caching static content [START_REF] Wang | A Survey on Mobile Edge Networks: Convergence of Computing, Caching and Communications[END_REF], the impact of core/edge deployments for dynamic interactive applications, such as collaborative environments, is still relatively unclear [START_REF] Cho | ACACIA: Context-aware Edge Computing for Continuous Interactive Applications over Mobile Networks[END_REF], in particular for legacy, off-the-shelf applications.

The ability of a legacy collaborative application to be deployed over both core and edge resources strongly depends on its software architecture. Monolithic applications linking to a unique database are not a good fit for hybrid deployments, for the same reasons they are not easily scaled horizontally in a single datacenter. A hybrid core/edge deployment requires instead the application to have a modular architecture, in order to be able to move or clone some of its constituents from core to edge resources, based on performance, reliability and durability considerations. The design principle of microservices [START_REF] Newman | Building microservices: designing fine-grained systems[END_REF] has gained a strong momentum for building of large web applications in cloud environments. Under this model, the application is split in a collection of independent single-purpose services whose implementation is independent from that of other microservices. Each microservice may use a different solution for managing its state and be independently scaled horizontally. Interaction between services typically happen through resource-oriented HTTP APIs following REST principles [START_REF] Masse | REST API Design Rulebook: Designing Consistent RESTful Web Service Interfaces[END_REF].

Microservices-based applications naturally appear to be good candidates for hybrid core/edge deployments. For availability reasons, microservices that handle durable, long-term information should remain in the core, while other microservices can be delegated or cloned to the edge. Deciding which microservice(s) should, or should not, be deployed at the edge is not simple. User-perceived latencies are typically a result of multiple interactions between microservices, and delays between edge and core resources may accumulate and result in poorer performance than in the initial core deployment. Furthermore, while stateless microservices are easier to clone to the edge, stateful microservices require special care, as their state may need to be kept consistent across multiple copies, which can yield more costs than benefits.

Contributions. We report on our experience of porting a legacy collaborative application for a hybrid core/edge deployment, and present the lessons learnt in the process. Our target application is ShareLatex, an open-source collaborative editing tool for L A T E X documents. Our goal is to assess whether porting such an existing complex application for a hybrid deployment is feasible with appropriate configuration but without changes to its code.

Our contributions are the following. We discuss criteria for edge deployment of microservices, including aspects linked to state management and consistency, and apply these criteria to the Share-Latex application (section 3). We describe the mechanisms that support this hybrid deployment with no modification to the application source code (section 4). We detail our benchmarking toolset featuring simulated behaviors of users collectively editing L A T E X documents. We experimentally demonstrate the performance improvement in terms of user-perceived latencies for some operations on joint documents and the tradeoffs that exist for other operations due to the hybrid, multi-site resulting deployment (section 5).

RELATED WORK

An overview of the field of edge and fog computing can be found in a survey by Li et al. [START_REF] Li | Edge-Oriented Computing Paradigms: A Survey on Architecture Design and System Management[END_REF]. Our work targets the evaluation of the hybrid core/edge deployment of a legacy application. A complementary line of work proposes new programming and software engineering models for building new applications in edge/cloud environments. This includes component-based approaches such as Jolie [START_REF] Montesi | Service-Oriented Programming with Jolie[END_REF], solutions based on eventually-consistent convergent data types (CRDTs) such as LASP [START_REF] Meiklejohn | Lasp: A Language for Distributed, Eventually Consistent Computations with CRDTs[END_REF] or development frameworks for stream processing such as Steel [START_REF] Shadi | Steel: Simplified Development and Deployment of Edge-Cloud Applications[END_REF].

Fesehaye et al. [START_REF] Fesehaye | Impact of Cloudlets on Interactive Mobile Cloud Applications[END_REF] consider a deployment scenario in which an overlay of cloudlets (similar to the type of edge resources we consider in this paper) supports applications including file edition. This application is not interactive: Users download the file from its host cloudlet, edit it locally and re-upload it. The authors study the impact of document location on user-observed performance. This is complementary to the problem we consider, and we similarly highlight in our evaluation the impact of hosting part of the state of our target application on one edge resource or another.

Clinch et al. [START_REF] Clinch | How close is close enough? Understanding the role of cloudlets in supporting display appropriation by mobile users[END_REF] evaluate the impact of using cloudlets on the display appropriation of mobile applications users, which depends on the responsiveness of the application. The study considers in particular a simple interactive game and evaluates users' perception of its responsiveness for different deployment models. The authors conclude that while there are lower latencies the user perception is not significantly impacted by the use of close-by cloudlet resources.

Báguena et al. [START_REF] Báguena | Towards enabling hyper-responsive mobile apps through network edge assistance[END_REF] study the responsiveness of mobile apps under core, edge and hybrid core/edge deployments. Their model considers the limited resources and lower latency available at the edge. It proposes a split between services for hybrid placement. It does not consider however, the interaction patterns between these services and the impact they may have on the performance of the application, and it does not provide guidelines for splitting an existing application into services able to benefit from hybrid deployments.

Aderaldo et al. [START_REF] Aderaldo | Benchmark Requirements for Microservices Architecture Research[END_REF] discuss the evaluation of microservices-based applications in general, and note the lack of empirical study on the performance of these applications. Our study aims at filling this gap for the particular case of hybrid core/edge deployments. Sieve [START_REF] Thalheim | Sieve: Actionable Insights from Monitored Metrics in Distributed Systems[END_REF] also considers ShareLatex as a target application, for the problem of efficiently collecting monitoring information from microservices. The monitoring allowed by Sieve could be the basis for implementing future automated core/edge deployments policies.

BACKGROUND

We review microservices principles and define categories of stateful microservices based on their ability to be replicated to the edge. We then describe our use-case application, ShareLatex.

Microservices. Microservices [START_REF] Newman | Building microservices: designing fine-grained systems[END_REF] are an evolution of serviceoriented architectures currently very popular for building largescale cloud-based applications. They favor the use of a collection of small and feature-focused software entities over software monoliths. Microservices are advantageous for agile software development, as each service can be implemented, tested and evolved independently. Interaction between microservices typically happen through APIs following the resource-centric REST over HTTP [START_REF] Masse | REST API Design Rulebook: Designing Consistent RESTful Web Service Interfaces[END_REF].

While microservices principles where not designed specifically for edge deployments, they offer a number of advantages for this purpose. Due to the statelessness of REST, interactions between services support dynamic relocation. This feature is already leveraged for elastic scaling. In order to support hybrid core/edge deployments, it is desirable to support the creation of replicas of services to one (or several) of the edge sites. This ability primarily depends on whether the service is stateful (i.e. it maintains state across different calls) or stateless (i.e. it may maintain temporary state for an ongoing request, but no state is kept between requests). Stateless services are easily replicable. Replicated stateful services are however concerned with consistency, as simply creating a clone of their existing database to another site may lead to diverging and irreconcilable states. Fortunately, we can observe that in many cases replicating or splitting a stateful service and its database to the edge may only have a limited impact on application correctness. Identifying such services in a legacy application is actually key to deciding which can or cannot benefit from a deployment to the edge. We define four cases, illustrated by Figure 1.

μS1 d μS1-I1 d μS2 d μS2-I1 d+∆' μS2-I2 μS3 d μS3-I1 μS3-I2 d = d' ∪ d" ∧ d' ∩ d" = ∅ μS4 d μS4-I1 μS4-I2 d = d' ∪ d" ∧ d' ∩ d" ≠ ∅ d μS1-I2 d+∆'' sync a) Sync-replicable b) No-sync-replicable c) Splittable (sharded) d) Partially-splittable d' d'' d' d'' sync
• Sync-replicable services require the full current state to be available on all instances of the service in order to maintain correct application behavior. They also require that this state be kept strongly consistent across replicas. Replicating such services generally leads to poor performance/cost tradeoffs, unless they have read-mostly accesses and are able to employ a strong consistency model that allows local reads, such as sequential consistency.

• No-sync-replicable services require a copy of the full service state for a new (edge) replica, but can preserve application behavior without enforcing strong consistency with the original (core) replica.

The cost for replicating such services therefore only depends on the initial cost of copying the state from the core to the edge.

• Splittable services can provide semantically-equivalent service with only a subset of the original full service state. As partial states (shards) are disjoint between services instances, there is no need for consistency enforcement. The cost of replication in this case is the cost of splitting and outsourcing one of the shards to the edge.

• Partially-splittable services are a hybrid between sync-replicable and splittable services where only part of the state has to be shared and maintained strongly consistent between replicas. Replicating these services to the edge without falling back to the sync-replicable mode is however difficult. It typically requires modifying their implementation to redirect accesses to shared and disjoint states to different databases, or using geo-replicated databases that can leverage the partial split information [START_REF] Halalai | ZooFence: Principled Service Partitioning and Application to the ZooKeeper Coordination Service[END_REF][START_REF] Lev-Ari | Modular Composition of Coordination Services[END_REF].

The no-sync-replicable, splittable, and partially-splittable assume a preferential attachment from users to a particular site, when accessing the service for a specific resource. It is necessary to deterministically redirect calls to this specific site. When there is no modification to the application code, this redirection has to rely on externally-visible information. This constraints is often met by microservices in the form of the URI resource name in the HTTP REST calls. This strengthens their potential for edge placement.

Use case application: ShareLatex. Our goal is to study the hybrid deployment of a legacy collaborative editing application, with no modification to its source code. We target an application based on microservices. We select ShareLatex, a collaborative tool popular in Responsiveness is an important aspect for this application, as oftentimes editors can work collaboratively on the same parts of the document, and need to get updates and notifications from other users in near-real-time.

ShareLatex features 12 microservices and 2 databases, listed in Table 1. Their interactions are shown in Figure 2. We observe that the interaction is roughly centralized: the web service acts as hub for all other services and as the interface to the user (therefore playing the role of an API gateway). We also see that the web, track-changes, document-updater and real-time services are all interconnected through a Redis database, which is in charge of storing the realtime state of a document under edition (list of modifications, cursor positions, etc). This state is saved periodically in a long-term storage for documents with a call to the docstore service.

We should note that microservices principles are best practices in nature. They are not necessarily strictly and consistently enforced across entire applications. This is the case for ShareLatex. Service decoupling and state isolation are key principles in microservices, but we can observe that in this application the Redis service, acting as a container for the database of the same name, is used as a shared state for various other services. This inevitably affects the possibilities we have for replicating and deploying these services to the edge. Our goal is to study the impact of hybrid deployment for an unmodified, legacy application. We choose therefore to work with the application as it stands, and leave the evaluation of "pure microservices" applications to future work. We note that the lack of availability of such application for benchmarking has been pointed out by other authors before us [START_REF] Aderaldo | Benchmark Requirements for Microservices Architecture Research[END_REF].

HYBRID CORE/EDGE DEPLOYMENT

We seek to determine a split of the application, that is a set of replication possibilities for the microservices and a suggested placement on core and edge resources. We leverage the mapping into service categories defined in Section 3. Categories for all services are listed in

Figure 2: ShareLatex microservices architecture and their replication categories as defined in Figure 1.

Most ShareLatex microservices are splittable services. In particular, we observe that we can split their database either using the project identifier present in the REST calls URIs (services documentupdater, track-changes, docstore, filestore, chat) or by the user identifier available in the same way (services contacts, tags, spelling). Two services, web and notifications are sync-replicable as their state cannot be replicated without full synchronization. The clsi service is no-sync-replicable: replicating it with no further consistency between replicas does not impact correctness. This service handles the compilation of L A T E X sources. For performance, it maintains a cache of the project elements including images and indexes, but loosing this state only result in these being fetched again from the docstore and filestore services. All services could be potentially replicated from the core to one or more edge sites, but it arguably makes more sense for no-sync-replicable and splittable ones. There are however other non-functional aspects that must be considered for deciding on an appropriate placement. We identify three key aspects: criticality, latency-sensitivity and frequency. Critical microservices are essential for the resiliency and availability of the application. Data loss in this case must be avoided, requiring reliable hardware typically available only in the core, and this is where these services should stay. Services maintaining state but performing periodic checkpoints to another critical service can often be considered noncritical. Latency-sensitive services typically benefit highly from being replicated to the edge, especially when they can leverage the locality between users. Similarly, frequently-used services are more likely to impact user experience, and this impact pays off more compared to the cost of enabling their replication. Service replication categories suggest which services may to be deployed at the edge, and additional non-functional aspects indicate if they should be. Table 1 lists this information for all services.

We start by discussing a potentially contradicting case for the web microservice. This service has a sync-replicable state, meaning it is costly to replicate to the edge(s), but it is also latency-sensitive. Previously, we observed that it is closely coupled to other latencysensitive services. From the service interaction graph, we can deduct that these services will benefit little from being deployed at the edge if they have to interact with the core, or we would have to implement strongly consistent replication defeating our objective of not modifying the services source code. Our suggested workaround is to decouple the state from the web service and host it separately from the service implementation. We deploy the MongoDB database of web in the core. The now stateless service can be deployed at the edge and benefit from low-latency interactions with other services through the Redis service. This is not an optimal solution as database accesses are now significantly less efficient. However, it is the only one which does not require any intervention on the application.

After considering the different service attributes and the workaround, we propose the split shown in Figure 3. We keep in the core services that are critical (docstore, filestore), sync-replicable (notifications) and infrequent (tags, contacts). We deploy at the edge latency-sensitive services (web, document-updater, real-time, trackchanges) and frequent services (spelling, clsi, chat). Note that there remain instances of all services deployed to the edge in the core. These are not used by edge users but are useful for other users who connect directly to the core.

Implementing redirections. Splittable services now have instances on multiple edge sites. Each instance holds a disjoint subset of the original service state. Requests must deterministically reach the appropriate service instance. This instance can be in the core, or at one of the edge sites (not necessarily the closest to the client).

In ShareLatex, we create instances of splittable services storing the state of projects (currently edited documents). The instance storing the state for a specific project is selected at the site that is the closest to the user that creates this project. Note that we assume in this feasibility study that the location of a specific project (resource for this split service) is globally known on all core and edge sites, but remains unknown to the clients who simply connect to their closest edge site or to the core. We leave runtime service resolution and dynamic relocation for our immediate future work.

ShareLatex is an application designed for a single-site deployment. Services implementations are oblivious of any state split and do not implement the redirection of calls to instances on multiple sites. We can however implement this redirection at the level of REST calls between services, thanks to the resource-centric nature of REST and to the use of HTTP URIs for services endpoints. All user calls are intercepted by a reverse-proxy (nginx [START_REF]NGINX -Load Balancer, Web Server & Reverse Proxy[END_REF]) which redirects them to the local web service. The HTTP request to a splittable service contains a resource identifier that can be used to decide on a redirection to an edge location. Resources that are not subject to such a redirection are simply directed to the core by default. We modify the configuration of nginx to redirect calls to the correct site through a rule based on the project identifier: For any known mapping between a project identifier and some edge site, the call is redirected transparently.

EVALUATION

We evaluate the performance of the hybrid deployment of ShareLatex. We use 3 server-grade nodes from Grid'5000 [1], each with 2 Intel Xeon E5-2630 v3 CPUs and 128 GB of RAM. Our experiments do not focus on scalability or resource saturation. As a result, we use the same machines at low utilization rates for emulating core and edge sites as well as emulated users. We emulate WAN latencies between sites using the tc (traffic control) tool. We use a 50 ms roundtrip latency between the core and any edge site, and a 70 ms roundtrip latency between two edge sites. Users are considered as being close to one of the edge sites, to which they connect with a 5 ms roundtrip latency. We package the split ShareLatex application of Figure 3 and its support services (e.g. nginx and its configuration) as containers deployed using the Docker CE platform.

Emulating real users. We focus on user-visible application responsiveness. We are therefore interested in delays between actions by one user and the visibility by other users inside the actual web application running in a browser. This latency is a conjunction of multiple factors that cannot be fully modeled by measuring APIlevel latencies. We emulate a set of users using Locust [START_REF]Locust -An open source load testing tool[END_REF], a load testing tool that allows programmatically describing the behavior of users as a list of actions, under specific scenarios and occurrence frequencies. Actions are HTTP or WebSocket requests. For example, opening a project requires an HTTP call to the project URL and establishing a Websocket connection. This connection is then used to write content to the project, which is another action which has a high frequency as it is the most common interactive one. Locust simulates a number of concurrent users by executing actions and scenarios in separate pseudo-threads (greenlets). Our user behavior is similar to the one used by Sieve [START_REF] Thalheim | Sieve: Actionable Insights from Monitored Metrics in Distributed Systems[END_REF].

To measure end-to-end user-perceived application latencies, we collect timestamps for each action start by some user, and corresponding events occurring on the application interface of other users (e.g. a cursor position change and its visibility).

Centralized vs. hybrid deployment. We start by comparing perceived latencies between a centralized deployment and a hybrid deployment using a single edge site. We use 5 concurrent emulated users who open and modify the same shared projects. shows the setup. Users first share a project fully hosted in the core. This represents our baseline. Measurements for a different set of actions are taken for a period of 10 minutes. Users then switch to working with another project hosted on the edge site, and run the same measurements for another 10 minutes.

We present results for the six following common actions: writing, moving the cursor, spell checking, sending chat messages, compiling the project and displaying the history of modifications. Figure 5 shows the distribution of perceived latencies for each of them. In the first row we observe that for common actions such as writing, cursor update and spell checking, users take advantage of reduced latencies when connecting to the project when hosted on the local edge site. These actions are indeed handled in our split by services (or services shards) that are all replicated to the edge. The other three actions, present in the second row, are negatively impacted by the hybrid deployment and the hosting of the project on the edge. The main services in charge of these actions are chat, clsi (for compiling) and track-changes (for history). These services have replicas running on the edge site in the hybrid deployment, but their interactions require communication with services instances remaining in the core, which results in additional latencies. For instance, although the document is compiled at the edge, the base document is retrieved first from the docstore service, which we kept locations, with a slight increase for users connecting through one of the edge sites. This small increase highlights the low cost of the unique redirection implemented by nginx. For the "Edge" project hosted on Edge 1, latencies for these two operations are greatly reduced for local accesses (when users connect to the Edge 1 site) while accesses through the other sites is impacted, mostly due to the addition of network latencies between sites, as the redirection operation itself remains of low cost. Observed latencies are in line with the emulated network configuration: 50 ms to the core and 50 ms more from the core to Edge 1 in the first case, or 5 ms to Edge 2 and 70 ms from Edge 2 to Edge 1 in the second case. Interestingly, we can observe that the spelling operation benefits from locality for users connected to both Edge 1 and Edge 2. The reason is that the spelling service does not depend on a particular project instance or identifier: there is no need to redirect the call to a particular site if an instance of the service is deployed locally.

The second row of Figure 7 presents latencies distributions for operations that always involve interactions with services instances in the core. The cost of redirecting some of the calls to services in the core is expected to have a negative impact when accessing a project located in the edge, as we have shown in our previous experiment. We observe indeed that these 3 actions on the "Core" project have a lower latency than the same actions on the "Edge" project. Furthermore, for these three actions applied to the "Edge" project, we do not observe the better performance for users connecting to Edge 2 compared to those connecting to the core, that we could observe for the actions of the top row. The reason for this is that the additional latency of redirection paid by users connecting to the core is evened out by the use of calls to local core services that follow. Users connecting to Edge 1 have better latencies for the "Edge" project as they avoid the price of redirection for the initial call to the service, but still do not perform as well as when the project is hosted directly in the core. The calls to the chat service yields the same delays whether or not the project is hosted on the edge or core site for users connecting to Edge 1: in both cases there is a redirection to the corresponding service in the core. For other groups of users, we observe the cumulative costs of the redirections to this same service.

In general, we observe from our experiments that the hybrid core/edge deployment results in a compromise between the gain of performance of operations that involve services that can be replicated (or split) to the edge site, and the loss of performance that is observed for operations requiring interaction with services staying in the core.

CONCLUSION AND FUTURE WORK

ShareLatex is a legacy application originally designed for singlesite deployment but using a modular implementation based on microservices. We have described the lessons learnt in adapting this application configuration for a hybrid core/edge deployment. We identified that the state management and service localization are the two critical aspect for deciding on replication of a microservice to the edge, in addition to considerations on costs and reliability. These allow us to propose and evaluate a split of the application that only required changes to its configuration and runtime environment, but no modification to its source code. This was made possible, to a large extent, by the microservices-based design and the resource-oriented REST API used between these microservices and allowing redirections. Our evaluation has shown that some common operations benefit from hosting the project by services replicated to a close-by edge site, while others see a drop in performance due to the inevitable interactions with services that had to stay in the cloud for reliability and persistence reasons.

This study motivates our future work towards automated hybrid core/edge deployments. Automated deployment would require automatic service discovery and redirection at runtime with strong consistency requirements. Stateful service types from our taxonomy and additional criteria may be determined by the programmer, but runtime decisions about which service to replicate or move from one site to the other require appropriate measurements and decision-making algorithm, possibly powered by machine learning.

Figure 1 :

 1 Figure 1: Four categories of microservices based on the impact of their replication on application correctness.

Figure 3 :

 3 Figure 3: Our split and placement. Critical services in the core, latency-sensitive and frequent services at the edge.

Figure 4 :

 4 Figure 4: Centralized vs. hybrid deployment -exp. setup.

Figure 5 :

 5 Figure 5: Hybrid deployment yields lower latencies for most frequent actions (first row).

Table 1 :

 1 ShareLatex services, their categories and additional attributes: critical(Cr.), latency-sensitive(LS), Frequent(Fr.) research and teaching communities. It enables concurrent real-time modifications by various users on the same L A T E X document.Collaborators in ShareLatex are likely to come from the same location. Typical examples could be a student and her supervisors, or researchers across local institutions working on a joint paper.

	Service	Description	Category Cr. LS Fr. Service	Description	Category Cr. LS Fr.
	1. docstore	CRUD ops on tex files	Splittable ✓	✓ 8. track-changes	History of changes	Splittable		✓ ✓
	2. filestore	CRUD ops on binary files	Splittable ✓	✓ 9. real-time	Websocket server	Stateless		✓ ✓
	3. clsi	Compile project	No-sync-replicable	✓ 10. notifications	Notifications between users	Sync-replicable
	4. contacts Manage contacts Splittable	11. document-updater	Maintain consistent document state	Splittable		✓ ✓
	5. spelling	Spell checking	Splittable	✓ 12. web	User interface and service hub	Sync-replicable	✓	✓ ✓
	6. chat	Chat service	Splittable	✓ Redis (db)	DB (Pub/Sub) for dynamic data
	7. tags	Folders, tags	Splittable	MongoDB (db)	DB for internal static data

Table 1 .

 1 No service in ShareLatex is partially-splittable.

	docstore (splittable)	clsi (no-sync-replicable)	filestore
			notifications (sync-replicable)
	track changes	web (sync-replicable)	contacts spelling
	redis document updater	real-time (stateless)	tags chat

ms 50 ms Locust

Core

in the core for availability reasons. In other cases, such as sending a chat message, the added latency comes due to the web service which needs to access its remote database to check if the has the right permission to perform the task and does not cache this information. Our goal is to keep the application unmodified but implementing a fix would be relatively easy. Impact of redirections. In a second experiment, we evaluate the impact of using redirections when the project accessed by users is not managed on the site (core or edge) they are connecting to. We consider the scenario with two edge sites, Edge 1 and Edge 2, shown by Figure 6. We distinguish three user groups based on the site they connect to: Edge 1 users, Edge 2 users and users connecting directly to the core. Two separate projects are hosted on Edge 1 and in the core -we refer to them as project "Edge" and project "Core". We emulate using Locust 5 users who simultaneously access and perform actions on the same project. These 5 users are in the same location, and we alternate between the 3 groups and 2 projects for 6 possible configurations.

Figure 7 shows the distributions of user-perceived latencies for the six operations we used previously, and for the six considered configurations. Perceived latencies for updating the text or the cursor position for the "Core" project are similar for all access