Trua: Efficient Task Replication for Flexible User-defined Availability in Scientific Grids

The first model focuses on running a single copy of a task on a pilot. It aims to quantify a task’s failure probability based on a pilot lifetime PDF. Without losing any generality, we assume that a task is going to start its execution at time $t_{0}$. This also implies a pilot which carries the task is alive at time $t_{0}$. The failure rate of the task, as expressed in Equation 1, is defined as the probability of failure during the next $\Delta t$ time units.

where $s$ represents the time that the task fails to continue to run.

We use $p(t)$ to represent the runtime PDF of the pilot job and $f_{i}$ to represent the failure rate of the task $T_{i}$, then the above equation can be further represented as follows:

Litke’s model then decides to use replication to protect a task from failures. The term replica is used to denote an identical copy of a task. By producing task replicas, the failure probability for a task can be significantly lowered. We assume that $m_{i}$ replicas - denoted by $T_{ik}$, $k=1,...,m_{i}$ - of a task $T_{i}$ are produced and placed in the grid. The new failure rate for task $T_{i}$ becomes:

The above equation corresponds to the probability of the event “all replicas fail (the original task is also considered as a replica).” The number of replicas created depends on the failure probabilities of replicas and the desired availability level from the application. We denote $\lambda$ as the desired availability. Thus, for each task, a sufficient number of replicas should satisfy the condition:

where $\lambda\in(0,1)$.

A loss of a single replica should not be considered as a failure because other replicas might survive to the end. We consider a task successfully finishes when any of the replicas finish in the end.

From the OSG perspective, for any user-submitted task, there are two parameters attached to it: target availability $\lambda$ and lease period $\Delta t$. A lease period is the estimated runtime for a task to run on a pilot. If the required lease period is larger than the assigned pilot’s lifetime, the task cannot finish before the pilot terminates and therefore the task will fail. The OSG needs to look at the pilot pool and select a set of pilots so that their cumulative availability is greater than the target availability. More importantly, if we sort all pilots by their failure rates and select pilots from the most reliable one, Litke’s model can guarantee that we use the minimum redundancy to replicate a task for any given availability [14]. In this paper, we evaluate both the random selection and the sorted selection and use Random and Sorted to represent two selections respectively.

Figure 1 shows the lifetime PDF on 102-day dataset. Unlike Litke’s assumption that the lifetime PDF follows a Weibull distribution, the actual PDF follows a bimodal Johnson distribution. In our previous work [9], we divided pilot termination into two categories: expected termination and unexpected termination and use two Johnson distributions to fit two PDFs. In order to understand the difference between expected and unexpected terminations, we need to introduce some background knowledge. In the OSG, there are two important parameters pertaining to pilot lifetime - retire time and kill time. Retire time is considered as a “soft deadline” for a pilot and kill time is considered as a “hard deadline”. After passing the retire time, a pilot is still able to run its carried task until the task is finished. If a carried task cannot be finished before its carrier pilot reaches the kill time, the pilot will be intermediately killed by the system resulting in task failure. Retire time and kill time are configurable in the OSG, they can be adjusted based on different workloads. During the time period we collected the data, all pilots’ retire time and kill time had been configured around 38 hours and 40 hours. In Figure 1, all pilots whose lifetime were less than the retire time were terminated due to unexpected failures such as preemptions and network disconnections; the rest of pilots whose lifetime greater than the retire time were terminated due to normal pilot life cycle.

As described in our previous work [9], preemptions are apt to happen in an early stage. In Figure 1, most of the pilots whose lifetimes are less than 10 hours are terminated due to preemptions. Preemptions are dominant in unexpected terminations and leave other unexpected failure types (network disconnections, idle shutdown and so on) negligible. We also call this region as the preempting stage. After the preempting stage, a pilot enters a stable stage where pilots have less chance to be terminated. The stable stage lasts until the retire time is reached and from the moment a pilot enters the retiring stage.

We applied Litke’s failure model to the lifetime PDF and tested on three lease periods - 60, 240, 420 minutes. Figure 2 shows three failure rate curves generated from Figure 1. The failure rate curves demonstrate three stages in a pilot life cycle: in the preempting stage, a pilot faces high failure rate; as a pilot survives preemptions, it goes into the stable stage and its failure rate keeps decreasing as the age increases; however, when a pilot approaches the retire time, the failure rate starts sharply increasing.

According to Litke’s replication model, a task can produce a large number of replicas if the selected pilots have high failure rates, which results in wasting resources. On a failure rate curve, left region before retire time is more attractive to our design. We call such a truncated region as a bathtub curve and Figure 3 conceptually summarizes a bathtub curve pertaining to the OSG pilots.

We tested Litke’s model on our 102-day pilot dataset. Since scanning the whole dataset takes too long, we sampled our dataset every 100 minutes. At each sample, we listed all available pilots and calculated their ages. With Litke’s failure model, we can estimate each pilot’s failure rate. After getting all failure rates, we run Litke’s replication model. We conducted two algorithms on selecting pilots: random selection and sorted selection. Both selections accumulate multiple pilots until their overall failure rate reaches above a target availability. The difference is that random selection randomly picks pilots and sorted selection always starts selecting from the most reliable one.

Figure 4 shows the overall failure rates on different combinations of target availability levels and lease periods. Each combination is represented by a pair ($a(n)$, $t(n)$) where $a(n)$ represents the availability levels (0.90, 0.95, 0.99) and $t(n)$ represents the lease periods (60, 240, 420 minutes). As shown in the figures, only the test of (0.90, 60) which is represented by ($a_{1}$, $t_{1}$) meets the target availability. For the test of (0.95, 60) which is represented by ($a_{2}$, $t_{1}$), random selection meets the target availability; however, sorted selection fails to keep the failure rate under 0.05. In general, the model gets closer to the target availability at a shorter lease period (60 minutes). As the lease period becomes larger, the model becomes more inaccurate to select reliable pilots.

Figure 5 shows the average number of replicas that are selected for a task. As the sorted algorithm always selects the most reliable pilots, it uses the minimum redundancy. Interestingly, if we look at both Figure 5 and Figure 4, the tests of (0.90, 240), (0.95, 420), (0.99, 60) and (0.99, 240) show that sorted selection uses less redundancy to achieve higher availability compared with random selection. This implies sorting failure rate indeed helps to improve task availability. Unfortunately, neither of the two algorithms can meet the target availability levels.

The Weibull distribution in Litke’s assumption generates a monotonically increasing failure rate curve. However, a bimodal Johnson distribution generates a non-monotonical curve. As two red x-points show in Figure 2, two pilots who run into different ages can have an equal failure rate. In such a case, one pilot is still in its early stage and the other is in the retiring stage. A user might prefer to select the first pilot because as it continues to run, its failure rate will decrease. On the other hand, the second pilot’s failure rate will sharply increase. For this reason, the model might not be able to select a set of the most reliable pilots.

Incidents such as power loss or network disconnection can cause a large number of failures resulting in a sudden rise in pilot terminations. We call such unexpected pilot terminations as anomalies. To demonstrate anomalies in the OSG, we select the first 18 days in the 102-day pilot dataset where a large number of pilot failures occurred due to network disconnection. Figure 6a shows the lifetime PDF of the 18-day data. A red circle indicates a large spike in the lifetime PDF that is about 7 hours to 8 hours. We extract all pilots with a lifetime between 7 and 8 hours and examine their pilot start time and end time. Figure 6c and 6d show start time distribution of those pilots. Figure 6e and 6f show end-time distribution of those pilots. These figures show a large number of pilots start and end around 370 and 380 hours. After adopting the pilot classifier described in our previous work [9]. It turns out a large number of network disconnections happened in the OSG. Figure 6b shows that we detected a sudden rise of network failures in our pilot dataset.

Another factor that makes the model difficult to select the most reliable pilots is the variance in the lifetime PDF caused by non-anomalous preemptions in the OSG. In our previous work, we found that over 40% of pilots encountered preemptions. Most of those preemptions happened on a regular basis and bring the randomness in pilot lifetime PDF overall time ranges. In addition, the OSG usually disassembles a large job into multiple tasks in order to execute them in parallel. As a result, the OSG has to create a bunch of pilots around the same time to carry those tasks if there are not enough pilots available in the pilot pool. These newly created pilots have the same start time and therefore will have the same end time if preemptions happened to these pilots. We call this effect as lifetime locality. In Litke’s model with failure rate being sorted, these pilots are highly likely to be selected together because they have similar age and therefore similar failure rate. This pilot behavior has been discussed in more detail in our previous work [9], in this paper we will propose new pilot selection algorithms in Section VI to specifically tackle this effect.

In order to detect failure anomalies, we adopt the RRCF algorithm [22]. We put the pilots that are characterized as network failures in a time stream. The anomaly detector acts on the time stream. The output from the anomaly detector is also a data stream containing anomaly scores produced by RRCF algorithm. Potential anomalies identified by RRCF have a higher anomaly score than data that the algorithm considers non-anomalous. RRCF generates the anomaly score based on how different the new data is compared to the recent past. If the anomaly score is above a certain threshold, the detector considers the recently terminated pilots are anomalous. Figure 8b shows the lifetime PDF after removing anomalies.

The anomalous failures can easily exceed the limits of any reasonable replication scheme, so we should not replicate tasks when an anomaly appears. Instead, the OSG should halt scheduling tasks to any infected cluster sites until the incidents get resolved. Therefore, we select another input parameter in our anomaly detector which defines a halting period after detecting an anomaly. Figure 8b shows the new pilot lifetime PDF after we applied RRCF with a threshold score set to 250 and a halting period set to 15 minutes.

Although the anomaly detector can filter out anomalous preemptions, most of the preemptions in the OSG are non-anomalous. In order to overcome these failures, we introduce a concept - valley. Figure 9 shows three valleys in a bathtub curve. A valley is defined by a target availability (failure rate is (1 - availability)). A smaller valley covers a shorter lifetime range. Therefore, the number of pilots that exist in a smaller valley is less than the number of pilots in a larger valley. More importantly, all those pilots that exist in a smaller valley are always a subset of the pilots that exist in a larger valley. With the definition of the valley, let us look at why we want to determine valleys in a bathtub curve.

There are several challenges in practically adopting the idea of using valleys to our system.

We use our data collected from the OSG over 102 days. We split them into three time frames, each of which contains   80,000 pilots. We apply the anomaly detector with the parameters - score: 250, delay: 60 minutes - to the three time frames.

Figure 10 shows the PDF fitting curves on the three time frames. As seen in the figure, the three time frames follow the same shape. Although anomalies unpredictably happen over time, once we group enough number of pilots, the pilot lifetime PDF is relatively stationary to some degree. This observation confirms the feasibility of using historical pilot information to estimate the ongoing pilot failure rate. We do not run a sensitivity analysis on the size of historical pilots that are eligible to estimate the pilot lifetime PDF. More investigations might be necessary to identify the minimum time window or the size of pilots.

We use a statistical approach to generate failure curves given a set of pilots. The procedure works as follows.

After characterizing the valleys of different availability levels, we propose two algorithms to select pilots from those valleys: valley selection and spread selection. We will also use Valley and Spread in this paper to represent these two algorithms. Algorithm 1 shows the procedures of two algorithms. The difference between these two algorithms is that valley selection uses random_select_n_pilots which randomly select $r$ pilots out of all available pilot within a valley; spread selection uses spread_select_n_pilots shown in Algorithm 2 which tries to evenly distribute the selected pilots over their minimum and maximum start times. The motivation behind spread selection is to mitigate the effect coming from lifetime locality.

Both algorithms start from the most reliable valley in which only the minimum number of pilots need to be selected. The algorithms gradually move to a larger valley and try to select more pilots if the preceding smaller valley is not able to select enough pilots. The algorithms return a set of pilots when there is a valley that can select enough pilots that match the valley’s redundancy level.

Table I shows the valleys for nine combinations of availability levels (0.90, 0.95, 0.99) and lease periods (60, 240, 420 minutes). All valleys are determined based on 102-day pilot data. R represents how many replicas a task needs to be replicated on a certain valley. v(n) represents a valley range that corresponds to a redundancy level. For example, let us look at the pair of the availability of 0.95 and the lease of 420 minutes. There is no valley region that can achieve the target availability of 0.95 by selecting one pilot. Therefore, v1 is labeled as N/A. If we further look at v2, it indicates a valley range between 1800 and 1950 minutes, which means by selecting any two pilots whose ages are between 1800 and 1950 minutes, the cumulative failure rate of the selected pilots is expected to be below 0.05 (the target availability is 0.95). In Table I, we omit v11 in which none of the availability-lease-pairs have a valid valley.

Figure 12 shows failure rates of different pairs of target availability and lease period. As shown in the figure, Random and Sorted show the results of the same algorithms described in Section III. Our model, shown as Valley and Spread, can meet all target availability levels. Interestingly, as a revised algorithm of Valley, Spread shows lower failure rates than Valley. This proves that evenly distributing start time of selected pilots is an effective technique to overcome the variance in the pilot lifetime PDF.

Figure 13 shows the redundancy costs of different availability levels and lease periods. Unsurprisingly, the Sorted algorithm uses the minimum number of replicas. Compared with Random, Valley and Spread can use less redundancy to achieve higher availability in some test cases especially with low target availability and short lease period - (0.90, 60), (0.90, 240), (0.90, 420) and (0.95, 60).

Figure 13 also suggests that we should always spread out the pilots based on their start time because it improves availability without introducing any redundancy overheads.

Figure 14 shows the pilot utilization of different selection algorithms. In general, Random and Sorted algorithms have a larger candidate pool compared with Valley and Spread algorithms. Random and Sorted are able to select all available pilots; however, Valley and Spread cannot select any pilots if available pilots are not within any pre-defined valleys. Thus the first two algorithms have higher system utilization than the latter two. As shown in Table I, if all pilots are close to the end of the retire time ($>$ 2100 minutes) and not enough pilots are in the valleys at a certain time point, the scheduler should not choose any pilots. As a result, these tasks should be held by the scheduler until there are more eligible pilots in the valleys later. We call such a mechanism as delay scheduling.

As shown in Table I, a task might have to be replicated by a large number of times in certain situations. For example, given a target availability of 0.99 and a lease period of 420. The last valley that is able to cover all pilot lifetime from 0 to 2060 needs to select 12 pilots in the valley. Such an aggressive replication scheme can quickly exhaust the resources in the system. To overcome the workload burden, we propose an algorithm - delay scheduling which is able to control the upper bound of redundancy for a task. The idea is that we can define an upper bound for the largest valley in which the maximum number of replicas to replicate a task is acceptable. The scheduler stops moving to a larger valley after the maximum allowed valley fails to select enough pilots. The system has to hold the tasks in the batch queue until there are enough pilots available in the upper-bounded valley. For example, if the system put redundancy limit to 6, all valleys after v6 in Table I are cut off. Let us take the pair of the availability of 0.99 and the lease period of 420 as an example. If there are not enough pilots that exist between 1400 and 1950 minutes, the scheduler postpones scheduling any task until it can find 6 pilots with that valley.

We tested the redundancy limit of 6, 5, 4. Only the larger target availability gets affected by the redundancy limit because the smaller availability does not exceed the limit. Thus, we only show the pairs of (0.99, 60), (0.99, 240) and (0.99, 420) in Figure 15. As shown in Figure 15a, all three pairs achieve the target availability of 0.99. The lease of 420 minutes reaches almost zero failure rate on the redundancy limit 5 and 4 because it uses valleys up to [1850, 1950] minutes. In such a small pilot age range, most of the pilots are highly reliable. Figure 15b shows that the redundancy keeps below the limit as expected.

Despite successfully keeping redundancy within a certain limit, delay scheduling can lower the system utilization. Let us look at the lease of 420 minutes. The scheduler only allows the pilots whose ages are in [1850, 1950]. Compared to the whole lifetime range [0, 2100], only a small portion of pilots are able to be selected. Figure 15c shows the system utilization on redundancy limits. As seen in the figure, only 14.5% of pilots can go to the candidate pool. If we allow all valleys shown in Table I to be used in selection, 73.5% of pilots are able to be selected in the system.