Limix: Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems

We informally define the Lamport exposure of any given user $U$ as the set of computing infrastructure – i.e., every “computer $U$ didn’t even know existed” – that “can render $U$’s own computer unusable” [7]. Lamport exposure is thus meaningful only with respect to the activities of some user $U$.

Limix seeks to place a strong bound or “shield” on the Lamport exposure of any user $U$ whenever $U$ accesses data or services that are local, i.e., close to $U$ by any suitable distance metric. We may define locality based on administrative boundaries such as those of an organization or a country, or via metrics such as round-trip time (RTT). The availability of $U$’s local accesses should be unaffected by remote failures and partitions beyond Limix’s Lamport exposure shield: not just by individual server failures but also by network partitions and gray failures, or partial failures that can cascade into correlated failures and partial partitions. Gray failures have a multitude of causes including malfunctioning switches and software bugs that partially drop traffic or prevent simplex communication [4, 27, 17, 20]. Figure 2a illustrates a Lamport exposure bound shielding a user’s accesses to an object at distance $\mathrm{\Delta }$ from failures beyond a distance $ϵ\mathrm{\Delta }$, for some small factor $ϵ\ge 1$ (ideally 1, but this may be unachievable).

Strongly-consistent coordination systems (Zookeeper [22], etcd [3]) are an essential building block for large scale distributed applications. Distributed applications replicate their state in order to enhance resiliency to failures, and to decrease latency through proximity to clients. But an unsought side-effect is the need to coordinate these replicas. Hence the need for coordination services: These provide a basic set of operations – such as liveness determination, correct identification of the replicas storing a data item, lease holders, access control, accounting, etc. Because these functions need to be correct, coordination services implement consensus among the configuration replicas, ensuring strong consistency of the configuration.

Coordination systems often are not critical to application availability until failures occur. Applications routinely bypass the coordination system for configuration reads using leases [8, 24]. During partitions or failures, however, the data plane cannot bypass the configuration system, because it needs to reconfigure its data replicas. This is when the configuration system becomes critical to application availability and performance. Reconfiguration requires strongly-consistent configuration writes to agree on the new configuration. Until reconfiguration completes, the data-plane may be partially (e.g., operate in read-only mode only) or fully unavailable.

The requirements of configuration systems to be strongly consistent and available seem to conflict with the CAP theorem [15]: under partitions, a strongly-consistent (configuration) system cannot remain available (on both sides of a partition). However, Limix does not conflict with the CAP theorem when prioritizing availability of local accesses. Remote users may not be able to access remote data during partitions, but local users can, without breaking strong consistency, and in many cases as described above, local data is what interests users. For this reason, Limix collocates metadata with its data.

To decrease the risk of being affected by remote gray failures, Brooker et al. [6] suggest many smaller configuration service deployments instead of a network-wide “monolith”. Deploying several configuration services instead of a single globalized deployment is one of the principles that Limix also applies. However, as opposed to deploying disjoint cells, Limix creates overlapping, redundant configuration service deployments, organized to provide availability guarantees for any user accessing any object or service.

Recent discussions we had with globalized infrastructure customers – a large company and a non-profit organization, both international – informally confirmed to us their need for services that are globally-managed while providing availability guarantees in the face of distant failures. Applications increasingly move to globalized infrastructures such as public clouds to benefit from the elasticity properties and lower management effort. Despite the flexibility of including custom clauses in the SLA, some customers are reluctant to trust these infrastructures: Because the number of reported outages is still uncomfortably high, they fear the reputation risk. One customer suggested that a good design that guarantees availability should recommend itself before getting to the SLAs. Finally, customers would consider leveraging a service that limits Lamport exposure – one referring to this as “the holy grail” – because its guarantees are well-understood and more meaningful compared to simply limiting the “blast radius” of a failure.

We observe that many applications and services exhibit bimodal access locality. A high proportion of accesses are by users mostly in a given country or other region representing the application’s primary customer base or target audience. Other users of these same applications and services, however, tend to be globally distributed, accessing the service from anywhere (e.g., roaming employees or expats). Thus, applications must efficiently support global accessibility for global users, while prioritizing maximum availability and performance for local users representing the most critical target customers.

To test this bimodal-access hypothesis, we use the top 100 websites of five OECD countries (namely United States (US), Switzerland (CH), Spain (ES), Japan (JP) and Australia (AU)) as rough proxies for applications, and examine the access distributions they exhibit. Since these are the most visited websites in their respective countries, we conjecture that they have a strong local presence. In Figure 3, we show that these websites also have a global presence, as 17–56% (JP–AU) of the websites receive at least $50\%$ of their traffic from outside of that country. The results of our simple study does not make any assumptions about the consistency models used by the websites, but it suggests that locally-prevalent applications are indeed globally relevant too.

The goal of local availability under global management, coupled with the requirement of strong consistency for metadata, imposes key challenges on Limix’s design.

For zones to act collectively as a unified system, Limix needs to enable clients to find data that can be located anywhere, regardless of the client’s zone. However, robust and efficient item lookup is challenging. Figure 4(a) illustrates a straightforward but inadequate approach, relying on a central service to store the configuration for item lookup. This service increases the client’s exposure beyond the perimeter of the client’s and data’s common zone. The single zone may also become overloaded with requests from all zones.

Of course, this strawman could be easily made scalable by distributing the configuration service across many/all zones, using standard techniques such as consistent hashing of keys. However, consistent hashing still increases a site’s Lamport exposure beyond the zone boundaries. Consider a client requesting data without having the data location cached. To resolve the location, the client might need to query configuration service sites in zones different from the zone holding the requested data. Partitions might prevent the client from reading the data location, even though they might not isolate the client from reaching the data itself. The problem with this approach is that data and corresponding metadata are not collocated in the same zone, and hence lack fate sharing [11].

Limix thus needs to ensure that a client in a given zone can always find an item within the same zone using only resources within that zone. Efficiently collocating data and metadata in the same zone so that they have the same Lamport exposure represents the first challenge for Limix, which we address by having a distributed configuration service per zone.

As a next strawman addressing the item lookup challenge above, we could replicate all lookup pointers in all zones, as depicted in Figure 4(b). However, this strawman introduces a consistency challenge: Because all zones’ configuration services store pointers to all items, when an item is deleted or migrated, regardless of the zone where the item resided, all configuration services in all zones should be updated with the new pointer. If we required strongly consistent state for all zones’ configuration services, we would increase an item’s exposure to all zones, which is undesirable.

Limix addresses this exposure challenge as follows. Each zone’s configuration service stores strongly consistent pointers only for the items inside the zone. If an item’s configuration changes, only the configuration service in the item’s zone needs to update the item’s definitive configuration (i.e., location metadata) (see Section 3) immediately, on the critical path. Other zones’ configuration services may update their metadata lazily with eventual consistency, outside the critical path of the item reconfiguration.

With this approach, each zone has its own configuration service that stores “location hints” for where an item was last known to be located. But this strawman invites a second challenge: How do clients locate items given that configuration services might (temporarily) store outdated pointers? We distinguish two causes of outdated pointers. The first reason is item migration, when Limix updates pointers outside the critical path. Could a client be unable to find an otherwise reachable item when the item migrates? Limix addresses the challenge by temporarily storing a Permanently moved to marker at the item’s old location. On encountering this marker, a client follows it to the new location. Limix prevents long indirection paths by eventually updating all pointers, after which it deletes the marker. The client stops following pointers when it reaches the item’s authoritative zone; Limix coordination ensures there is a single authoritative zone per item (Section 4.5).

The second reason for items to be outdated is during partitions. If Limix cannot reach some zones’ configuration services, pointers will be stale. The main challenge is to ensure that clients do not return stale items because of stale pointers, which would break strong consistency. Limix clients rely on authoritative zone indicators, as explained above, to decide whether the pointers point to the most recent item version. However, there is one remaining issue when partitions heal and several migrations are in place: Pointer updates might arrive out-of-order, causing an old update to overwrite a newer one. We use versioning for pointers to avoid this situation. Every pointer update increases the pointer version and a pointer update occurs only if the update has a higher version than the existing pointer (Section 4.6). The update makes use of the compare-and-swap primitive typically offered by strongly-consistent KV stores.

The above strawman invites the question: What is the load on each zone’s configuration service? Consider updating the configuration service after an item insertion or migration. Either the destination zone could push the new item location to all zones, or the client’s zone could pull the item location on demand. Both approaches incur $O(n)$ load and communication overhead per client request for $n$ zones.

Limix instead spreads the lookup loads and limits query burden on small zones by organizing a default overlapping global zone. In our next strawman illustrated in Figure 4(c), local zones store the location only for their local items and serve lookup requests only from local sites. In contrast, the global zone serves as the backup reference point, whose globally-distributed configuration service knows any item’s location. Every zone propagates location updates to the global zone.

A client queries only its own local configuration service and the global one, without overloading other small zones. Thus, instead of $O(n)$, the overhead per update becomes $O(1)$. The global configuration service must service load from all $O(n)$ zones, but it has server capacity distributed across all $O(n)$ zones among which to share that load. Location updates propagate only eventually, off the critical path, to limit the source zone’s exposure to outer failures.

Aside from the global zone, we assumed so far that local zones are disjoint. This assumption has a significant limitation, however: it cannot support simultaneous exposure-limiting policies, which may apply by law or contractual obligation. An item located in Germany may need to be accessible by clients in Germany with Lamport exposure limited to sites within Germany, and ensure that any client in the EU can access the same item with exposure limited to the EU. Yet, with the above strawman configuration service, EU clients outside Germany must query the global configuration service, yielding global (not EU) exposure.

We address this problem by allowing local zones to overlap. All zones have a configuration service, and every zone propagates location updates to larger overlapping zones, up to the global zone. The global zone still acts as a master reference, holding pointers to all items. Update overhead increases slightly compared to the single global zone, from $O(1)$ to $O(v)$, where $v$ is the maximum overlap depth. However, this approach limits Lamport exposure to smallest zone containing both the item and the client accessing it. Location updates propagate only eventually, outside the critical path, to limit the source zone’s exposure to failures outside its borders. Figure 4(d) illustrates the final configuration service.

The placement of items may need to change, for example due to client-perceived performance and load-balancing algorithms. Or this could be caused by a policy change, e.g., a new constraint on which existing zone(s) a particular item is allowed to be placed in or migrated to. Because items involve strongly-consistent state, a challenge is that Limix must maintain strong consistency for configuration during item’s migration. Three questions arise at this point: (a) How can we ensure that the coordinator locates the latest version of an item, even during migration or partitions? (b) Given that clients could update data plane items anywhere in the system, how do we ensure another distant client, located in a different zone, finds a specific item? (c) How do we ensure item search does not degrade the exposure-limiting guarantees?

Alg. 2 depicts item migration from the item’s authoritative zone $sZone$ to the new authoritative zone $dZone$. When Limix receives a callback from the data store that an item is being migrated, it does the following: (0) Increment the item’s most recent pointer version, by definition in the item’s authoritative zone $sZone$ (lines 2-3). We use pointer compare-and-swap with versioning for the pointer updates below to avoid old pointers overwriting newer ones. (1) Update the pointer in the old zone with a forwarding reference, indicating the item is being migrated to the new zone and the old zone should no longer be considered authoritative (line 4); (2) After item migration, update the pointer in the new zone indicating migration is complete and the new zone is now authoritative, meaning that item is now usable at its new site (line 5); (3) In parallel and outside the critical item lookup path, update discovery service information in all zones for the item’s old and new location (lines 6-8); (4) Garbage collection: The item’s configuration may finally be deleted in the old zone (line 10).

The algorithm above guarantees that any client can locate any item as long as they share an unpartitioned zone, even during/after migration. After step 1, all clients following existing pointers for that item (using Alg. 1) that lead (directly or indirectly) to the former authoritative zone learn that the item is being migrated to the new zone. After step 2, when the item finishes migrating, all clients following existing pointers locate the new authoritative zone. All clients can now find the item, but possibly via a longer chain (e.g., if it moved from the UK to Italy, Spain clients may first follow the pointer to the UK, then to Italy). Lookup exposure during migration reflects the migration: The client’s exposure for accessing the item is $Z_{Spain}\cup Z_{UK}\cup Z_{Italy}$. Eventually, when all pointers in step 3 finish updating, all clients in the system can locate the item by following a single pointer. Accordingly, the exposure after migration is $Z_{Spain}\cup Z_{Italy}=Z_{SW-Europe}$. Importantly, because pointer updates happen independently and in parallel, partitions outside Europe SW cannot disrupt the client from locating the item.

It is worth outlining the tradeoff between limiting exposure and the overhead of updating metadata during item migrations. In Limix, simultaneous migrations for the same item require updating the metadata pointers in all zones that contain the item before and after each migration step. The update overhead enables Limix to limit exposure of the item lookup during migration to the smallest unpartitioned zone containing the still in-flight migrations. In contrast, an architecture that maintains local configuration services per zone and additionally a global configuration, like in the strawman in Figure 4(c), merely needs to update global zone pointers (akin to cache invalidation) and pointers of the migration zones. This reduces pointer-update overhead at the cost of global exposure during migrations.

We study the system’s scalability when the number of sites increases. We ask two questions: (1) How many zones / configuration services should a site expect to run?; and (2) How much load should a site expect when running x zones?

Figure 6 answers the first question, depicting a CDF of the expected number of zones per site. We analyzed different $N$ and $k$ parameters for a fixed network diameter $D$. The fixed overhead increases linearly per additional zone the site runs. But the dynamic load that each site serves depends on how many other sites are running the same zone, because only participating sites direct user requests to that zone.

Figure 7 depicts the expected dynamic load per site compared to the expected total number of zones in Limix. We consider a network diameter $D$ of 128 ms and each site issues 100 requests. For a set of $N$, $k$ and $D$, the expected number of zones is uniquely determined. The experiment varies $N$ and plots the expected load per site for systems with parameter $k=2$ to $k=5$. The analysis shows that, with bigger networks and more zones, the cost for each site grows with a slow logarithmic rate, which flattens for bigger $k$. We refer interested readers to the appendix for the detailed computation of the expected number of zones that a site is part of, which we used for computing the expected load per site. We conclude that Limix scales well on large wide-area systems.

Our first experiment focuses on a simple Limix deployment in which each item exists in only one local zone, in addition to the default global zone. In this scenario we consider each of the disjoint local zones to represent an administratively-defined jurisdiction, such as a country. The experiment answers the question: “What are the availability benefits and cost per Limix zone in this scenario?”

This experiment evaluates to what extent the configuration of localized data is exposed to remote gray failures. This time, however, no jurisdictions are given: we use autozoning and test Limix’s availability guarantees in comparison to Physalia. We ask the question: “If a random site runs a reconfiguration for a random item, to what extend could remote failures cause the reconfiguration to fail?”

This experiment, like the previous one, tests to what extent the configuration of localized data is exposed to remote gray failures, but on a real network and using realistic trace-based data. Because the AWS testbed has lower RTTs that are more clustered, Physalia cells are mostly between 10-30 ms RTT diameter, with a single cell up to 50 ms. Our methodology is similar to the experiment above, with the only exception that the workload of 1000 reconfiguration pairs of each experiment has a distribution of reconfiguration RTTs matching the one in trace 1 (Section 7). The workload is global, thus some interacting pairs cross the partition boundary.

Figures 10(c) and 10(d) plot the results only for the non-partitioned interactions. Our results generally mirror the ones we obtained on the cluster testbed, with Limix outperforming Physalia in almost all tested cases, and for the same reasons. There are, however, two notable differences from the previous experiment. First, Limix registers a few failures close to but above the shield. These failures correspond to some sites with a more unstable RTT than the others, whereas we depict the RTT measured at bootstrap time. However, the difference in RTT was minor, and for all the other sites we observed no violation. Second, we observe a more pronounced clustering effect of the plotted points, matching roughly our more clustered topology.

We also summarized the results for each tested workload as percentage of successes of the maximum possible availability for the non-partitioned pairs. Figure 11 shows that Limix’s success rate is close to 100% in most cases, and significantly outperforms Physalia. We conclude that Limix provides strong guarantees on a variety of testbeds and workloads.