PhD Jonathan Vappou
email: jvappou@unistra.fr

Keywords: MR Thermometry, Fat referenced PRFS, MR Elastography, interventional MR, thermal ablation

Purpose: Simultaneous fat-referenced proton resonance frequency shift (FRPRFS) thermometry combined with MR Elastography (MRE) is proposed in order to continuously monitor thermal ablations for all types of soft tissues, including fatty tissues. FRPRFS thermometry makes it possible to measure temperature even in the water fraction of fat-containing tissues while enabling local field-drift correction. MRE allows measuring the mechanical properties of tissues that are related to tissue structural damage.

Methods: A gradient-echo MR sequence framework was proposed that combines the need for multiple TE acquisitions for the water-fat separation of FRPRFS, and the need for multiple MRE phase-offsets for elastogram reconstructions. Feasibility was first assessed in a fat-containing gelatin phantom undergoing moderate heating by a hot water circulation system. Subsequently, High Intensity Focused Ultrasound (HIFU) heating was conducted in porcine muscle tissue ex-vivo (N=4; 2 samples, 2 locations /sample).

Results: Both FRPRFS temperature maps and elastograms were updated every 4.1 s. In the gelatin phantom, FRPRFS was in good agreement with optical fiber thermometry (average difference 1.2±1℃). In ex-vivo HIFU experiments on muscle tissue, the shear modulus was found to decrease significantly by 34.3±7.7 % (Exp.#1-Sample#1), 17.9±10.0 % (Exp.#2-Sample#1), 55.1 ±8.7 % (Exp.#3-Sample#2), and 34.7±8.4 % (Exp.#4-Sample#2) as a result of temperature increase (Δ𝑇 = 22.5±4.2℃, 14.0±2.8℃, 14.7±3.7℃, and 14.5±3.0℃, respectively).

Conclusion:

This study demonstrated the feasibility of monitoring thermal ablations with FRPRFS Thermometry together with MRE, even in fat-containing tissues. The acquisition time is similar to non-fat referenced PRFS Thermometry combined with MRE.

INTRODUCTION

MR thermometry is commonly used to control heat deposition and to estimate tissue damage during MR-guided thermal ablations. [START_REF] Parker | Applications of NMR Imaging in Hyperthermia: An Evaluation of the Potential for Localized Tissue Heating and Noninvasive Temperature Monitoring[END_REF][START_REF] Kuroda | Non-invasive MR thermography using the water proton chemical shift[END_REF][START_REF] Quesson | Magnetic resonance temperature imaging for guidance of thermotherapy[END_REF][START_REF] Quesson | Real-time volumetric MRI thermometry of focused ultrasound ablation in vivo: a feasibility study in pig liver and kidney[END_REF] MR thermometry based on the water proton resonance frequency shift (PRFS) [START_REF] Ishihara | A precise and fast temperature mapping using water proton chemical shift[END_REF] is the most commonly used method because it offers high temperature sensitivity within the temperature range encountered during thermal ablations, and fast acquisition times in the order of a few seconds. However, fundamental limitations of PRFS thermometry need to be considered when applying this method for thermal ablation monitoring. First, PRFS temperature information provides temperature changes through the difference between the current phase and a baseline phase image. Hence, time-varying field drift and motion between successive scans can result in temperature errors, if not corrected for. Second, PRFS provides an instantaneous parameter, namely, temperature changes, which does not directly relate to tissue damage. The cumulative thermal dose (TD) represents an integration of temperature over time and has been shown to be a reliable marker of tissue damage. [START_REF] Sapareto | Thermal dose determination in cancer therapy[END_REF] However, fundamental limitations when using TD alone for monitoring thermal ablations over time need to be mentioned, such as the fact that TD thresholds are tissue-dependent [START_REF] Van Rhoon | CEM43°C thermal dose thresholds: a potential guide for magnetic resonance radiofrequency exposure levels?[END_REF] , and that TD is particularly sensitive to any uncertainty or bias due to its cumulative property. [START_REF] Vappou | MR-ARFI-based method for the quantitative measurement of tissue elasticity: application for monitoring HIFU therapy[END_REF] TD has also been shown to be poorly correlated to non-perfused volume (NPV), a reliable marker of post-ablation tissue damage, showing potential errors of MR Thermometry due to longterm heat accrual. [START_REF] Bitton | Improving thermal dose accuracy in magnetic resonance-guided focused ultrasound surgery: Long-term thermometry using a prior baseline as a reference[END_REF] Third, PRFS thermometry in fat-containing tissues may result in significant temperature errors depending on echo time, fat fraction, and extent of temperature increase because the temperature dependent electron-screening constant in fat is negligible compared to the one of water protons. [START_REF] Rieke | Echo Combination to Reduce PRF Thermometry Errors From Fat[END_REF][START_REF] Taylor | Measurement of temperature dependent changes in bone marrow using a rapid chemical shift imaging technique[END_REF] Fat-Referenced PRFS MR thermometry (FRPRFS) [START_REF] Soher | Noninvasive temperature mapping with MRI using chemical shift water-fat separation[END_REF][START_REF] Hofstetter | Fat-referenced MR thermometry in the breast and prostate using IDEAL[END_REF] using water-fat separation has been developed to tackle some of these limitations. The water-fat separation makes it possible to measure the temperature-induced PRFS from the phase of the water fraction contained in fatty tissues, and no longer from the global phase of mixed water and fat protons. Moreover, time-varying field drifts can be estimated from the phase of the fat fraction because, as previously mentioned, temperature induced changes are negligible in fat. Hence, water proton only PRFS temperature estimation can be obtained while correcting for time-varying field drifts in soft tissues, including fat-containing tissues. [START_REF] Hofstetter | Fat-referenced MR thermometry in the breast and prostate using IDEAL[END_REF] Recently, tissue elasticity has received increasing attention as a biomarker that would be complementary to temperature. Structural changes occurring during thermal ablations result in changes in tissue mechanical properties. [START_REF] Wu | Assessment of thermal tissue ablation with MR elastography[END_REF][START_REF] Mariani | Real time shear waves elastography monitoring of thermal ablation: in vivo evaluation in pig livers[END_REF][START_REF] Brosses | Temperature dependence of the shear modulus of soft tissues assessed by ultrasound[END_REF] MR Elastography (MRE) offers the possibility to measure the mechanical properties of soft tissues non-invasively. While MRE is mostly used for diagnosis, this method has also been proposed as a tool for assessing thermal damage after an ablation. [START_REF] Wu | Assessment of thermal tissue ablation with MR elastography[END_REF][START_REF] Chen | Assessment of in vivo laser ablation using MR elastography with an inertial driver[END_REF] Corbin et al. [START_REF] Corbin | Interventional MR elastography for MRI-guided percutaneous procedures[END_REF] proposed an interventional MRE protocol that allows for simultaneous PRFS temperature and elasticity monitoring at high frame rates (~0.5 Hz). More recently, Hofstetter et al. developed a novel MRE approach that relies on shear wave generation using acoustic radiation force pushes at multiple locations and composite reconstruction, allowing for elasticity mapping. This method was used successfully to assess elasticity changes following High Intensity Focused Ultrasound (HIFU) ablation. [START_REF] Hofstetter | Efficient shear wave elastography using transient acoustic radiation force excitations and MR displacement encoding[END_REF] All these studies have used conventional PRFS thermometry so that their use in fat-containing tissues may lead to significant errors in temperature estimation. The general objective of the proposed work is to extend the interventional MRE/MR Thermometry method to any type of soft tissues, including fatcontaining tissues. For this purpose, a time-efficient strategy is proposed that allows for simultaneous FRPRFS thermometry and MRE. On one hand, an iterative least square fitting algorithm (IDEAL) is used for fast and robust water-fat separation. [START_REF] Tsao | Hierarchical IDEAL: Fast, robust, and multiresolution separation of multiple chemical species from multiple echo times[END_REF][START_REF] Yu | Multiecho water-fat separation and simultaneous R2* estimation with multifrequency fat spectrum modeling[END_REF] The water and fat signal model is solved by using multiple TE datasets. On the other hand, MRE reconstructions require the acquisition of several images with varying phase-offsets between the mechanical wave and the motion sensitive gradients (MSG), in order to capture the shear wave at different propagation times. The strategy described here takes advantage of the acquisition of several phase-offsets in order to obtain the several echo times required for water-fat separation. Echo times and phase-offsets are jointly incremented to enable water-fat separation for FRPRFS thermometry along with MRE. The number of MRE phase-offsets and the number of TE used to solve the IDEAL algorithm are the same; hence, elastogram and FRPRFS temperature map are updated at the same time.

METHODS

Proposed framework

As shown in Fig. 1a, a gradient-recalled echo (GRE) MRE sequence is modified in order to obtain varying echo times for water/fat separation: each pair of images with opposite MSG is acquired at a specific TE and its corresponding MRE phase-offset. The MRE phase-offset 𝜃 corresponds to the trigger delay between the mechanical shear wave and the MSG. The acquisition scheme (Fig. 1b) consists of interleaved acquisitions with opposite MSG polarities (MSG+/-) and identical TE and phase-offset; hence, both TE and phase-offset are incremented every two images.

Image reconstruction

A 2D phase unwrapping algorithm [START_REF] Goldstein | Satellite radar interferometry: Two-dimensional phase unwrapping[END_REF] is applied to each phase image before reconstruction of elasticity and temperature maps. Different combinations of each pair of phase images acquired with opposite MSG polarities are used either for MRE elastogram reconstruction (difference) or for PRFS thermometry (average). [START_REF] Le | Feasibility of simultaneous temperature and tissue stiffness detection by MRE[END_REF] The first elastogram and temperature map are obtained once a full dataset including 4 phase-offsets / 4 TEs is obtained; subsequent ones can be reconstructed with every newly obtained pair of phase images with opposite MSG. 18

Elasticity mapping

The subtraction of each pair of phase images acquired with opposite MSG polarities offers two positive outcomes in MRE: it doubles motion-encoded phase shifts while removing the background phase.

Once 4 phase-offsets have been acquired, a temporal Fourier transform is applied to extract the fundamental MRE excitation frequency. A local frequency estimation (LFE)-based algorithm is used to estimate the local wavelength. [START_REF] Manduca | Image processing for magneticresonance elastography[END_REF] Finally, the shear modulus is calculated by 𝜇 = 𝜌(𝜆𝑓) 2 under the assumptions of linear elasticity and uniform tissue density (1000 kg/m 3 ).

Temperature mapping using the chemical shift water-fat separation

Each pair of phase images acquired with opposite MSG polarities is averaged in order to suppress the motion-dependent phase [START_REF] Le | Feasibility of simultaneous temperature and tissue stiffness detection by MRE[END_REF] , while preserving the background phase including temperature information.

The multiple TE datasets are used for temperature estimation. The measured signal can be expressed in terms of the water and fat components as follows: [1] Where 𝑆(𝑇𝐸 𝑛 ) is the complex signal of the n th echo time 𝑇𝐸 𝑛 , 𝜌 𝑤 and 𝜌 𝑓 are the complex-valued water and fat signals, 𝑓 𝑝 is the difference of spectral peaks between fat and water (-3.8, -3.4, -2.6, -1.94, -0.39, and 0.6 ppm) [START_REF] Yu | Multiecho water-fat separation and simultaneous R2* estimation with multifrequency fat spectrum modeling[END_REF] and 𝛼 𝑝 is the relative amplitude of each spectral peak (0.087, 0.694, 0.128, 0.004, 0.039, and 0.048) [START_REF] Yu | Multiecho water-fat separation and simultaneous R2* estimation with multifrequency fat spectrum modeling[END_REF] , 𝑅 2 * is the global transversal relaxation rate (𝑅 2 * = 1/𝑇 2 * ), and 𝛹 is the off-resonance precession.

The IDEAL algorithm is used to solve Eq. [1] with an iterative approach. [START_REF] Tsao | Hierarchical IDEAL: Fast, robust, and multiresolution separation of multiple chemical species from multiple echo times[END_REF][START_REF] Yu | Multiecho water-fat separation and simultaneous R2* estimation with multifrequency fat spectrum modeling[END_REF] Generally, the first step of the IDEAL processing consists in estimating the field map (𝑅 2 * decay and 𝛹) via the least square fitting error. Recently, the hierarchical IDEAL [START_REF] Tsao | Hierarchical IDEAL: Fast, robust, and multiresolution separation of multiple chemical species from multiple echo times[END_REF] method was proposed to estimate the field map by using a multiresolution technique, for improved computational efficiency. In this study, the hierarchical IDEAL is applied before heating in order to obtain a reliable estimate of the field map. Once the field map is identified, the second step consists in extracting the complex water and fat signals based on (𝑅 2 * and 𝛹) estimates. [START_REF] Tsao | Hierarchical IDEAL: Fast, robust, and multiresolution separation of multiple chemical species from multiple echo times[END_REF] Temperature changes affect the water signal 𝜌 𝑤 = 𝜌 𝑤 0 𝑒 𝑖𝜙 𝑇 , where 𝜙 𝑇 is the phase shift caused by temperature and 𝜌 𝑤 0 is the water signal in the absence of temperature change. The field map is estimated once before the ablation to extract both water and fat complex signals. This approach aims at reducing the computational complexity during the ablation by avoiding the optimization step of the IDEAL algorithm.

𝑆(𝑇𝐸 𝑛 ) = (𝜌 𝑤 + 𝜌 𝑓 ∑ 𝛼 𝑝 • 𝑒 -𝑖2𝜋𝑓 𝑝 𝑇𝐸 𝑛 𝑃 𝑝=1 ) • 𝑒 -(𝑅 2 * +𝑖2𝜋𝛹)𝑇𝐸 𝑛
This simplification is possible for two reasons. First, time-varying B0 field drifts affect both the phases of water and fat; the effect of B0 field drifts can therefore be estimated by a spatial polynomial fitting of the fat phase map in fat-containing tissues (field drift correction map), so that they are corrected for in the water phase map. Second, contrary to B0 field drifts, temperature induced R2* changes are neglected because they only affect the magnitude of both water and fat signals, and hence have no effect on temperature estimates.

Therefore, temperature changes, ∆𝑇 (℃), can be estimated from the phase of water protons, with field drift correction, using FRPRFS, following [START_REF] Hofstetter | Fat-referenced MR thermometry in the breast and prostate using IDEAL[END_REF] :

[2]
Where 𝜙 𝑤 and 𝜙 𝑤 0 are respectively the current and baseline water phase maps, 𝜙 𝐶 and 𝜙 𝐶 0 are respectively the current and baseline field drift correction maps, 𝛾 is the gyromagnetic ratio of the hydrogen nuclei, 𝐵 0 is the main magnetic field, 𝛼 is the temperature dependent water chemical shift (≈-0.01 ppm/℃), and 𝑇𝐸 is the average of the echo times used.

Experimental setup

All experiments were performed in a 1.5 T MRI (MAGNETOM Aera, Siemens Healthcare, Germany) using pneumatic MRE excitation. For monitoring during the ablation, images were transferred to a personal computer through TCP/IP connection and processed with Matlab (Mathworks, USA).

The proposed method was first demonstrated in a gel phantom experiment with hot water circulation, mimicking a thermal ablation in fatty tissues. The phantom was made of 8% gelatin in water and contained a water/fat cylindrical inclusion (2% gelatin in milk cream, 20% fat). A cylindrical plastic tube chamber connected to a water circuit was placed inside the inclusion for hot water circulation (Supporting information Figure S1). After baseline imaging for 100 s, hot water circulation was first activated between 100 s and 220 s, and a second time between 370 s and 417 s.

RESULTS

Validation experiment in a gel phantom

Ex-vivo HIFU experiments

Because of high variability across the muscle samples, changes in mechanical properties are displayed in terms of relative stiffness changes (RSC= Δµ/µ0, where µ0 is the initial stiffness). Figure 4 shows ∆𝑇, RSC, elasticity maps, and wave images measured before (100 s), after HIFU heating (250 s), and during cooling down (570 s) in one experiment. Shear modulus was found to decrease at the focal spot, as shown in the RSC maps.

ΔT and RSC were averaged within an ROI that was automatically computed as the region including all pixels exceeding 66.7% of the maximum peak temperature increase around the focal spot. Timedependent profiles of ∆𝑇 and RSC for the four samples are plotted in Fig. 5. Shear moduli were found to decrease by 34.3±7.7 % (Exp.#1), 17.9±10.0 % (Exp.#2), 58.7±3.9 % (Exp.#3), and 36.7±6.7 % (Exp.#4) as a result of moderate temperature increase of 22.5±4.2℃, 14.0±2.8℃, 14.7±3.7℃, and 14.5±3.0℃

(Exp.#1-4).

DISCUSSION

Standard MRE sequences rely on image acquisitions at a single echo time for all MRE phase-offsets.

In this study, the echo time TE is increased with each MRE phase-offset for FRPRFS thermometry. The proposed acquisition scheme keeps the acquisition time identical to previously developed combined PRFS thermometry and MRE. [START_REF] Corbin | Interventional MR elastography for MRI-guided percutaneous procedures[END_REF] Several limitations of the MRE protocol should be discussed. First of all, MRE images are acquired with varying TEs, as a consequence of the IDEAL acquisition scheme. Because of T2* signal decay, this may cause variable phase-to-noise ratio between successive MRE images. In particular, the phase-to-noise ratio of long TE acquisitions may become critical in tissues with short T2*. As in conventional MRE, this limitation can be partially overcome by increasing the MSG frequency, thus shortening the TE, at the expense of the wave-to-noise ratio. Secondly, elastograms were reconstructed using the LFE algorithm under the assumption of linear elasticity. The LFE algorithm is commonly used in clinical studies thanks to its robustness. However, LFE methods may have lower spatial resolution and higher averaging effect than other reconstruction algorithms. [START_REF] Manduca | Spatio-temporal directional filtering for improved inversion of MR elastography images[END_REF] This may lead to errors in shear modulus estimates around the focal region, especially at the onset of elasticity changes, as the region where such changes occur is very limited in size. Accuracy could be improved by increasing shear wave excitation frequency, thus improving the MRE resolution. However, increasing excitation frequency affects shear wave penetration and may result in lower wave-to-noise ratio due to increased attenuation. Despite such potential limitations, the LFE algorithm is used in this study because its processing time is well suited for the monitoring of thermal ablations.

As seen in figures 4 and 5, rib muscle elasticity was found to be particularly heterogeneous. Such variability in muscle elasticity has already been observed [START_REF] Brosses | Temperature dependence of the shear modulus of soft tissues assessed by ultrasound[END_REF] and may be related to variability in muscular fiber organization patterns. Because of such variations, results were presented in terms of relative changes of shear modulus. Similar behavior was found for the four samples tested: the shear modulus was found to decrease significantly as a consequence of moderate temperature elevation. This behavior has already been reported previously by several teams. Wu et al. reported a decrease of bovine muscle shear modulus by almost 50% up to absolute temperatures of 60 °C ex vivo, followed by significant stiffening at higher temperatures. Similar trends were reported by Sapin et al. [START_REF] Brosses | Temperature dependence of the shear modulus of soft tissues assessed by ultrasound[END_REF] and Arnal et al. [START_REF] Arnal | Monitoring of thermal therapy based on shear modulus changes: II. Shear wave imaging of thermal lesions[END_REF] in ex vivo tissue. These studies suggest that muscle tissue softening occurring at moderate temperature elevation may be due to protein structure unfolding. [START_REF] Wu | Assessment of thermal tissue ablation with MR elastography[END_REF][START_REF] Brosses | Temperature dependence of the shear modulus of soft tissues assessed by ultrasound[END_REF] Both phantom and rib tissue have relatively homogeneous water-fat distributions so that temperature-induced susceptibility changes in the fat might be slight in these experiments. [START_REF] Sprinkhuizen | Temperature-induced tissue susceptibility changes lead to significant temperature errors in PRFS-based MR thermometry during thermal interventions[END_REF][START_REF] Andriy | Correction of proton resonance frequency shift temperature maps for magnetic field disturbances using fat signal[END_REF] The FRPRFS measurement in the gel phantom experiment showed no significant difference when compared to optical fiber thermometry. Further study is needed to compensate for temperature-induced susceptibility changes in heterogeneous tissues. [START_REF] Sprinkhuizen | Temperature-induced tissue susceptibility changes lead to significant temperature errors in PRFS-based MR thermometry during thermal interventions[END_REF] Finally, combining an external MRE exciter with interventional material (HIFU or percutaneous) may be particularly challenging in terms of spatial access. Translating this setup in vivo would certainly require using interventional-specific excitation strategies such as percutaneous vibrating needles [START_REF] Corbin | Interventional MR elastography for MRI-guided percutaneous procedures[END_REF] or the acoustic radiation force. [START_REF] Hofstetter | Efficient shear wave elastography using transient acoustic radiation force excitations and MR displacement encoding[END_REF] However, this investigation falls beyond the scope of this paper, which aims at demonstrating the feasibility of performing simultaneous FRPRFS MRT and MRE with IDEAL fat/water separation.

CONCLUSIONS

In this study, a new framework was developed for FRPRFS thermometry coupled with MRE for the monitoring of thermal ablations. This protocol was validated in a gel phantom and ex vivo in porcine muscle tissue. FRPRFS thermometry coupled with MRE has similar acquisition time as regular PRFS thermometry coupled with MRE, while providing refined temperature monitoring for thermal treatments in soft tissues.

Figure 2 Fig. 3 .

 23 Figure 2 shows temperature changes ∆𝑇, elasticity changes Δµ, elasticity maps µ and wave images measured at times 40 s (resting state), 200 s (first heating), and 400 s (second heating).Temperature increase resulted in cream softening. Two ROIs (2×2 pixels) were selected at the tips of the optical fiber sensors. Time-dependent profiles of ∆𝑇 and Δµ measured in these ROIs are plotted in Fig.3. Temperature changes measured with FRPRFS thermometry were in good agreement with those of the optical fiber sensors. The mean absolute difference in ROIs 1 and 2 were 1.5±1.3 ℃ and 0.9±0.7 ℃, respectively. Over the course of the experiment, the shear modulus was found to decrease from 21.6±1.2 kPa to 10.53±0.3 kPa in ROI 1, and from 20.6±0.7 kPa to 15.4±0.7 kPa in ROI 2.

Figure 1 .

 1 Figure 1. (a) Schematic chronogram of the GRE MRE sequence for simultaneous MRE and FRPRFS thermometry. For clarity, the main elements of the GRE MRE sequence are represented in a single line (RF pulse, MSG and read out gradient). TE and MRE phase-offsets are shifted by ∆TE and ∆𝜃, respectively. (b) Summarized acquisition scheme, with 𝑛 being the number of phase-offsets and TEs. Images are acquired with alternating the polarity of MSG. Each pair of images is acquired with the same specific TE and phaseoffset.

Figure 2 .

 2 Figure 2. From left to right, temperature changes (Δ𝑇), elasticity changes (∆𝜇), elasticity maps (µ) and wave images overlaid with the magnitude image at the first TE, before (time 40 s) and during heating (times 200 s and 400 s). Localized increase in temperature result in gel softening in the inclusion.

Figure 3 .

 3 Figure 3. Time-dependent profiles of the shear modulus (a) and temperature changes ∆𝑇 (b) in ROI 1 and ROI 2 (2×2 pixels, shown in Fig. S1). Solid lines correspond to optical fiber thermometry (ROI 1 in blue, ROI 2 in red). Blue and red circles indicate measurements of the FRPRFS in ROI 1 and 2, respectively. The faded-orange regions in the graph indicate heating phases.

Figure 4 .

 4 Figure 4. From left to right, temperature changes (Δ𝑇), relative stiffness change (RSC), elasticity maps (µ), and wave images overlaid with the magnitude image at the first TE, before (time 100 s), during (time 250 s) the HIFU heating and after, during the cooling time (time 570 s) (Exp.#3). HIFU heating induces changes in the shear modulus (RSC).

Figure 5 .

 5 Figure 5. Time-dependent profiles of relative stiffness change (RSC) and temperature change ∆𝑇 in ex vivo muscle for Exp.#1 (a), #2 (b), #3 (c), and #4 (d).Mean initial elasticity value (µ0) is given in the right top corner of each graph. ROIs were defined as the region including all pixels exceeding 66.7% of the maximum peak temperature increase around the focal spot (White-dashed line in Fig.4).

Figure S2 .

 S2 Figure S2. Experimental setup and fat fraction map before HIFU heating in ex vivo muscle. White-dashed lines delineate different areas of the phantom: -1-Degassed water, -2-Pig rib tissue, -3-7% gelatin, -4-2% gelatin in milk cream, -5-HIFU transducer, -6-Pneumatic exciter. Fat fractions were measured to be 5.7±3.3 % (muscle) and 22.2±1.5 % (cream gelatin).

ACKNOWLEDGMENTS

This work was partly funded by the French state funds managed by the ANR (within the Investissements d'Avenir programme for the Labex CAMI); Grant number: ANR-11-LABX-0004. We acknowledge the use of the Fat-Water Toolbox from the ISMRM Workshop on Fat-Water Separation 2012 (http://ismrm.org/workshops/FatWater12/data.htm).

SUPPORTING INFORMATION

The two optical fiber thermometers were positioned 15 mm apart in the image plane located 5 mm away from the hot tube side. A syringe was used for the manual circulation of hot water (about 90°C). The pneumatic exciter was placed below the phantom. ROI 1 and 2 indicate the position of the tips of the two optical fibers. A fat fraction value of 20.42±1.4% was measured before heating in the cream-gelatin inclusion, using the IDEAL algorithm; this result is consistent with the fat content of the cream (20% as provided by the manufacturer) used for this experiment.


Orcun Yildiz
email: oyildiz@anl.gov

Shadi Ibrahim
email: shadi.ibrahim@inria.fr

Preserving Fairness in Shared Hadoop Cluster: A Study on the Impact of (Non-) Preemptive Approaches

Keywords: Clouds, Resource management, Data processing, Scheduling, Performance evaluation

Recently, MapReduce and its open-source implementation Hadoop have emerged as prevalent tools for big data analysis in the cloud. Fair resource allocation in-between jobs and users is an important issue, especially in multi-tenant environments such as clouds. Thus several scheduling policies have been developed to preserve fairness in multi-tenant Hadoop clusters. At the core of these schedulers, simple (non-) preemptive approaches are employed to free resources for tasks belonging to jobs with less-share. For example, Hadoop Fair Scheduler is equipped with two approaches: wait and kill. While wait may introduce a serious violation in fairness, kill may result in a huge waste of resources. Yet, recently some works have introduced new preemption approaches (e.g., pause-resume) in shared Hadoop clusters. To this end, in this work, we closely examine three approaches including wait, kill and pause-resume when Hadoop Fair Scheduler is employed for ensuring fair execution between multiple concurrent jobs. We perform extensive experiments to assess the impact of these approaches on performance and resource utilization while ensuring fairness. Our experimental results bring out the differences between these approaches and illustrate that these approaches are only sub-optimal for different workloads and cluster configurations: the efficiency of achieving fairness and the overall performance varies with the workload composition, resource availability and the cost of the adopted preemption technique.

Préserver l'équité dans un cluster Hadoop partagé : une étude de l'impact des approches (non)-préemptives Résumé : Récemment, le paradigme MapReduce et son implémentation open-source Hadoop sont devenus des outils très populaires pour l'analyse de données massives dans le Cloud. Le partage équitable des ressources entre les différentes tâches et utilisateurs est un problème important, en particulier dans les architectures multi-tenant comme le Cloud. De nombreuses stratégies d'ordonnancement ont donc été développées pour préserver l'équité dans les cluster Hadoop multi-tenant. Au coeur de ces ordonnanceurs, des approches simples et non-préemptives sont utilisées pour libérer des ressources pour des tâches appartenant à des utilisateurs en ayant eu jusque-là une part plus faible. Par exemple, Hadoop Fair Scheduler possède deux approches : "attendre" et "tuer". Si "attendre" peut causer des sérieuses ruptures d'équité, "tuer" peut aussi entraîner un important gaspillage des ressources. Cependant, certains travaux récents ont introduit des techniques préemptives (c'est-à-dire "arrêter-reprendre") dans les clusters Hadoop partagés. Dans ce travail, nous examinons précisément trois approches, incluant "attendre", "tuer" et "arrêter-reprendre", lorsque Hadoop Fair Scheduler est utilisé pour assurer une répartition équitable des ressources lors de l'exécution de plusieurs groupes de tâches concurrents.

Nous avons mené des expériences étendues pour évaluer l'impact de ces approches sur les performances et l'utilisation des ressources tout en garantissant leur partage équitable. Les résultats de nos expériences mettent en évidence les différences entre ces stratégies et montrent que chacune est sous-optimale pour une partie des workloads et des configurations : la capacité à garantir l'équité et les performances globales varient en fonction de la composition des tâches, des ressources disponibles et du coût des techniques préemptives.

Mots-clés : Clouds, organisation des ressources, calcul sur données, ordonnancement, évaluation de performances

Introduction

Data-intensive applications have been accelerating many services in different areas such as science, business, health care and finance. This has boosted the growth of the data volumes which needs to be handled efficiently. In this context, MapReduce [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF][START_REF] Jin | The mapreduce programming model and implementations[END_REF] has emerged as the prevalent paradigm for processing massive amounts of data. MapReduce is adopted in both industry and academia due to its simplicity, transparent fault tolerance and scalability. Recently, it has also been optimized to support the execution of multiple concurrent jobs belonging to multiple users [START_REF] Isard | Quincy: fair scheduling for distributed computing clusters[END_REF][START_REF] Zaharia | Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling[END_REF][START_REF] Cheriere | On the usability of shortest remaining time first policy in shared hadoop clusters[END_REF]. By analyzing the traces collected from a research cluster with 78 users [START_REF]Hadoop Workload Analysis[END_REF], we have seen that there are at least 10 jobs running concurrently at 5% of the time. Sharing MapReduce clusters leads to lower cost and better utilization of resources but it introduces new challenges such as ensuring fairness among different users and jobs. While fairness (i.e., giving each job their fair share of resources) is an important aspect in multi-tenant clusters, achieving fair execution in MapReduce clusters is not trivial. One limiting factor is the static resource management model of MapReduce clusters. A cluster consists of workers and each worker has a fixed number of slots (i.e., slots represent the capacity of a worker) which can run tasks. Depending on the available resources, duration of tasks and the number of running tasks; it might not always be possible to provide fair share of resources for different users.

To this end, several multi-tenant schedulers have been proposed to solve the problem of fairness. In this context, schedulers assign the resources in multi-tenant environments to the users depending on their specified fairness policy. For example, Quincy [START_REF] Isard | Quincy: fair scheduling for distributed computing clusters[END_REF], fair scheduler for Dryad, uses min-cost flow algorithm, while Hadoop Fair Scheduler (HFS) [START_REF] Zaharia | Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling[END_REF] uses max-min fair sharing strategy in order to operate shared MapReduce clusters towards fairness. While they apply different solutions for the fairness problem, they both employ similar approaches when the cluster status changes (e.g., new job arrives, running job(s) finishes) for ensuring fairness. Current supported approaches in MapReduce frameworks are twofold: 1) wait for running tasks until their completion, 2) kill the tasks belonging to the jobs with over-share to allocate resources for new jobs. For instance, HFS adopts wait approach by default and leaves kill approach optional to users in case fair share of some users are not met.

Kill approach is simple and efficient in deallocating the resources but it wastes the resources by destroying the on-going work of the killed tasks. On the contrary, wait approach is wastefree but it might not be efficient when cluster contains long running tasks. Besides wait and kill approaches, preemption approach (i.e., pause-resume) can be also applied to enforce the fairness1 . It is simply pausing the running tasks to make room for new tasks and resume the paused tasks where they left off when there is an available slot. In this work, we seek to provide a deep look into the different characteristics of the three different approaches (i.e., wait, kill and preemption) while enforcing fairness. To this end, we adopted the preemption approach on top of Hadoop Fair Scheduler, which was originally developed in [START_REF] Yildiz | Chronos: Failure-aware scheduling in shared hadoop clusters[END_REF]. We perform extensive experiments by using different workloads including real-life workloads from Facebook production clusters. We make the following contributions:

• A study of the fairness in multi-tenant environments with respect to the three different approaches. We find that preemptive action might be necessary in order to enforce fairness among users. Our results show that there is a serious fairness violation with wait approach in some scenarios. Specifically, we show evidence that wait approach is not able to provide equal distribution of the cluster resources, especially for the reduce slots usage due to long running reduce tasks. Similarly, Wang et al. [START_REF] Wang | Preemptive reducetask scheduling for fair and fast job completion[END_REF] also indicated the fact that long running (reduce) tasks may lead to starvation of short jobs and they introduced a technique for reduce task preemption in order to favor short jobs against long jobs.

• An analysis of the performance and resource utilization under three different approaches.

We find that fairness violation not only degrades the performance of the jobs with lessshare but also results in overall performance degradation. For resource utilization, our results show that kill approach results in noticeable resource waste (i.e., 11% resource loss in terms of slot usage) by destroying the on-going work of the killed tasks although it is able to enforce the fairness. Moreover, we observe that this introduces a performance penalty for MapReduce applications.

• An analysis of the impact of resource availability on the effectiveness of three different approaches. We discover that there is a correlation between the resource availability and the effectiveness of these approaches. In particular, we observe that wait outperforms other approaches when the cluster resources are only fully occupied for a short time and therefore slots (resources) are freed faster thus the tasks belonging to jobs with less-share wait for a small amount of time. We also find that kill and preemption approaches can be disadvantageous in low-utilized clusters. The main reason behind this is the re-execution of the killed tasks with kill approach and the introduced delay for the preempted tasks with preemption approach as described in Section 5.2.

The proposed work aims at providing a clearer understanding of the interplay between different (non-) preemptive approaches and fairness, performance and resource utilization. Moreover, it is important to mention that these approaches are applicable beyond the fairness problem. Therefore, users can benefit from our findings in different areas such as ensuring QoS requirements or improving the energy efficiency of MapReduce clusters.

The paper is organized as follows: Section 2 presents the background of our study. We discuss the three approaches: wait, kill and preemption in Section 3. Section 4 describes an overview of our methodologies, followed by the experimental results in Section 5. Finally, we conclude the paper and propose our future work in Section 6.

Background

In this section, we first provide a brief overview of Hadoop [START_REF]The Apache Hadoop Project[END_REF] and its fair scheduler, then we present the earlier works on fairness and preemption in MapReduce.

Overview of Hadoop

In Hadoop, job execution is performed with a master-slave configuration. JobTracker, Hadoop master node, schedules the tasks to the slave nodes and monitors the progress of the job execution. TaskTrackers, slave nodes, run the user defined map and reduce functions upon the task assignment by the JobTracker. Each TaskTracker has a certain number of map and reduce slots which determines the maximum number of map and reduce tasks that it can run. Communication between master and slave nodes is done through heartbeat messages. At every heartbeat, TaskTrackers send their status to the JobTracker [START_REF] Huang | Mr-scope: a real-time tracing tool for mapreduce[END_REF]. Then, JobTracker will assign map/reduce tasks depending on the capacity of the TaskTracker and also by considering the locality of the map tasks [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF][START_REF] Ibrahim | Maestro: Replica-aware map scheduling for mapreduce[END_REF] (i.e., Among the TaskTrackers with empty slots, the one with the data on it will be chosen for the map task).

Overview of Hadoop Fair Scheduler

Hadoop Fair Scheduler (HFS) [START_REF]Hadoop Fair Scheduler[END_REF] is designed for multi-tenant clusters with fairness in mind. HFS groups jobs into pools and tries to achieve fairness between these pools. Furthermore, each pool can either adopt FIFO or fair sharing as its internal scheduling policy. In FIFO scheduling, jobs are prioritized according to their submission times. Therefore, if FIFO scheduling policy is adopted, there will be only pool-based fairness. On the other hand, job-based fairness can be enforced by HFS with the adoption of fair sharing as the internal scheduling policy of the pools. In HFS, user name is the default parameter for organizing jobs among the pools. Hence, HFS creates one pool for each user in the cluster.

While enforcing fairness between different jobs/pools, HFS checks the number of running tasks for each pool. When there is a free slot, HFS allocates this slot to the pool with the fewest number of running tasks. Then, depending on the internal policy of the pool, this slot will be given to the appropriate task. Moreover, HFS defines a fair share which it calculates by max-min fair sharing algorithm [START_REF] Radunovic | A unified framework for max-min and min-max fairness with applications[END_REF]. Normally, the pools with the running tasks should have their fair share in the cluster, which is the main goal of the Fair Scheduler. However, due to the dynamic nature of the multi-tenant clusters (e.g., new users start to submit jobs, earlier jobs finish their execution), active pools might have different number of resources than their fair share. To overcome this, HFS provides a kill technique (which needs to be enabled via configuration file), that kills the most recently launched jobs from the pools with over-share to give these resources to the pools with less-share than their fair share. HFS also allows users to adjust the timeout for this comparison (i.e., whether there are pools with over-share) which is defined as fair share preemption timeout in HFS.

Fairness and preemption in MapReduce

Several research efforts have been introduced with the aim of achieving fairness in the multitenant MapReduce clusters [START_REF] Isard | Quincy: fair scheduling for distributed computing clusters[END_REF][START_REF] Wang | Preemptive reducetask scheduling for fair and fast job completion[END_REF][START_REF] Ghodsi | Choosy: Max-min fair sharing for datacenter jobs with constraints[END_REF][START_REF] Liu | Reciprocal resource fairness: Towards cooperative multiple-resource fair sharing in iaas clouds[END_REF][START_REF] Tang | Long-term resource fairness: towards economic fairness on pay-as-you-use computing systems[END_REF][START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF][START_REF] Popa | Faircloud: sharing the network in cloud computing[END_REF]. (Non-) preemptive approaches are employed at the core of each of these solutions to provide fairness while guaranteeing good performance and resource utilization. Wait approach is employed in Hadoop Fair scheduler [START_REF]Hadoop Fair Scheduler[END_REF] and ShuffleWatcher [START_REF] Ahmad | Shufflewatcher: Shuffleaware scheduling in multi-tenant mapreduce clusters[END_REF]. To compensate the performance degradation which may be caused by waiting for free resources (especially for short jobs), Hadoop Fair scheduler embraces a simple technique, called delay scheduler [START_REF] Zaharia | Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling[END_REF], to improve local execution of map tasks: when a scheduled job is not able to launch a local task, it waits for some time until it finds the chance to launch a task locally. Quincy [START_REF] Isard | Quincy: fair scheduling for distributed computing clusters[END_REF] treats scheduling as an optimization problem and uses min-cost flow algorithm to achieve the solution. It employs the kill approach to set the cluster according to the configuration in the solution. Chronos [START_REF] Yildiz | Chronos: Failure-aware scheduling in shared hadoop clusters[END_REF][START_REF] Yildiz | Enabling fast failure recovery in shared hadoop clusters: Towards failure-aware scheduling[END_REF] is a failure-aware scheduler which introduces a preemption technique in order to improve MapReduce performance under failures while ensuring fairness. Wang et al. [START_REF] Wang | Preemptive reducetask scheduling for fair and fast job completion[END_REF], leverage the fact that long running reduce tasks may lead to starvation of short jobs. Thus, they introduce a preemption technique in order to achieve fairness by favoring short jobs against long jobs. Our work is complementary to these studies, in the sense that it presents a deep and comprehensive analysis of the impact of the different approaches (including wait, kill and preemption that these works employ to achieve fairness) not only on the fairness guarantees but also on the performance of MapReduce applications and the resource utilization of MapReduce clusters; and provides a useful insight on how to select the most appropriate (non-) preemptive approach to get the best practical trade-off between fairness, performance and resource utilization. Preemption is a desirable concept in scheduling and has many different use cases, especially in the operating systems domain. In MapReduce systems, one can utilize preemption for several cases such as achieving better resource utilization or fair share of resources. For instance, to deal with the fair share of the resources, schedulers should reallocate the resources between jobs when the number of jobs changes. Since resources are normally fully utilized, fresh jobs (i.e., newly arrived jobs) are most likely to suffer by having less resources than their fair share. In this case, preemption can help releasing resources from the jobs with over-share than their fair share in order to allocate resources to these jobs.

In this work, we investigate the impact of three different approaches (i.e., wait, kill and preemption) while enforcing fairness. Currently, Hadoop Fair Scheduler supports wait and kill approaches for enforcing fairness. We also adopted the preemption approach which has been previously developed in [START_REF] Yildiz | Chronos: Failure-aware scheduling in shared hadoop clusters[END_REF] by implementing it on top of Hadoop Fair scheduler.

Kill is a simple preemption technique and it can take a fast action. To achieve fairness, it deallocates resources by killing the tasks belonging to the jobs with over-share and these resources will be allocated to the jobs with less-share. Although it simplifies the preemption mechanism, kill approach destroys the on-going work of the killed tasks. Therefore, this leads to waste of resources which can have a large impact on both application performance and resource utilization. This negative impact depends on several factors such as the current progress of killed tasks and the task type. For example, this impact will be larger if killed tasks were about to finish their execution, or vice versa. In addition, if the killed task is a reduce task, copy of the killed task has to transfer all the intermediate mapper outputs when it is launched. This in turn can further impact the MapReduce system negatively due to the extra cost of the data transfer through network, a well-known source of overhead in today's data-centers. Wait approach is the default strategy used by HFS for enforcing fairness. It simply does not take any action for allocating resources to fresh jobs and waits until currently running tasks finish their execution to give resources to the fresh jobs. While this approach can be efficient when the running tasks are short, it can introduce a serious fairness violation in the presence of long-running tasks which needs to be preempted. Besides wait and kill approaches, another strategy for enforcing fairness would be applying the preemption approach. Surprisingly, this approach is not supported by Hadoop or other MapReduce frameworks. In brief, it pauses the currently running tasks to allocate resources for new jobs and resumes them where they left off when there is an available slot. This preemption technique should be light-weight in order to be efficient. For instance, applying a naive checkpointing approach will introduce a large overhead since it requires flushing all the data associated with the preempted task to the disks.

For clarity, these three approaches (i.e., wait, kill and preemption) are displayed in Figure 1. Here, shorter task, t2, arrives later than the longer one, t1. We can see that t2 starts its execution after t1 finishes its execution. Here, waiting time of t2 is equal to the remaining time of t1 until its completion. With kill approach, we can observe that the on-going work of t1 is wasted and this leads to the longest execution time in this scenario since this wasted amount of work needs to be re-executed after the completion of t2. For the preemption case, we can see that the work has been done conserved at the moment of the preemption. After t2 finishes its execution, t1 continues its execution where it left off. Here, ∆t represents the overhead that can be caused by the preemption technique.

As we can observe from this scenario in Figure 1, the effectiveness of these three approaches depends on several factors. For example, if t2 arrives later, this will lead to increase in the amount of the wasted work with kill approach. On the other hand, this alternative scenario would reduce the waiting time of t2 with wait approach which can prevent the starvation of newly arrived jobs. For the preemption approach, its overhead (∆t) would be the main factor for its effectiveness which will depend on the implementation of the preemption technique. For instance, the overhead of the preemption technique depends on the task type in [START_REF] Yildiz | Chronos: Failure-aware scheduling in shared hadoop clusters[END_REF]. For map tasks, the overhead of the preemption is due to the waiting for the up-to-date information via new heartbeat messages in order to have a global and up-to-date view of the cluster status and it is less than 2 seconds given that the heartbeats are sent every 0.3 seconds. For reduce tasks, the overhead of the preemption is due to saving and restoring the necessary state of the task to/from the disk and also due to the waiting time during which the host (the node on which the task has been preempted) is occupied since preempted reduce tasks can only be resumed on the same node that they have been preempted.

Methodology

In this section, we describe the adoption of the three aforementioned approaches in Hadoop and the experimental environment: the platform and deployment setup.

Adoption of wait, kill and preemption approaches in Hadoop

We use the stable Hadoop version 1.2.1 in our experiments and leverage Hadoop Fair Scheduler (HFS) in assessing the impact of different approaches. HFS normally adopts wait approach as a strategy while enforcing the fairness and also provides the kill approach which is disabled by default. We further extended HFS to support the preemption approach. When HFS needs to deallocate resources from the jobs with over-share, preemption approach employs a pause and resume approach. In brief, it stores the necessary data on the local storage for preserving the state of the selected task for preemption with pause and restores back this information upon resume. It is important to note that, although we adopted these different approaches in Hadoop version 1.2.1, the same adoption can also be applied to the next generation of Hadoop, YARN [START_REF] Vavilapalli | Apache hadoop yarn: Yet another resource negotiator[END_REF]. Major difference of YARN from the Hadoop 1.x versions is that it separates the JobTracker into ResourceManager and ApplicationManager. The main motivation behind this new design Inria is to provide better fault tolerance and scalability. On the other hand, YARN adopts a similar approach for ensuring fairness as Hadoop 1.2.x versions: it is equipped with the Fair scheduling policy as Hadoop 1.2.x and employs the same approaches (i.e., wait and kill) for ensuring fairness in shared Hadoop clusters.

Platform

The experiments were carried out on the Grid'5000 [5] testbed, more specifically we employed nodes belonging to Rennes site. On Rennes site, the nodes are configured with two 12-core AMD 1.7 GHz CPUs and 48 GB of RAM. Intra-cluster communication is done through a 1 Gbps Ethernet network. Grid'5000 allows us to create an isolated environment in order to have full control over the experiments.

Experimental deployment

We configured and deployed a Hadoop cluster using 19 nodes. The Hadoop instance consists of the NameNode and the JobTracker, both deployed on a dedicated machine, leaving 18 nodes to serve as both DataNodes and TaskTrackers. The TaskTrackers were configured with 8 slots for running map tasks and 4 slots for executing reduce tasks. At the level of HDFS, we used a chunk size of 256 MB due to the large memory size in our testbed. We set a replication factor of 2 for the input and output data. We used the wordcount benchmark as a testing workload. Wordcount is a map-heavy workload with a light reduce phase, which accounts for about 70% of the jobs in Facebook clusters [START_REF] Chen | Interactive analytical processing in big data systems: A cross-industry study of mapreduce workloads[END_REF].

Experimental Results

In this section, we provide a high-level analysis of the experimental results we obtained. First, we present comprehensive evaluation of the impact of different approaches on the performance of MapReduce applications and resource utilization. We then show the impact of workload composition and resource availability on the effectiveness of the three different approaches.

Impact of different approaches on MapReduce performance and fairness

We investigate the impact of three different approaches (i.e., wait, kill and preemption) on MapReduce performance and their efficiency in ensuring fairness. We report the job execution times and cluster share for jobs in terms of map/reduce slots for comparing the performance and fairness efficiency of these approaches. First, we compare wait and preemption approaches and then compare kill and preemption approaches.

Wait vs preemption. To evaluate the effectiveness of wait and preemption approaches in achieving fair execution between different jobs, we set up two pools with fair sharing as their internal policy. Then, we submitted a sequence of wordcount jobs with two different users (i.e., different user for each pool). While the first half of the jobs (i.e., jobs in the range of 1-5) belongs to pool 1, the second half belongs to pool 2. Notably, we submitted the jobs with random inter-arrival times (Table 1) by only enforcing the jobs in pool 1 are submitted earlier compared to the jobs in pool 2. The reason behind this condition is to be able to measure how quickly resources are given to new jobs (i.e., jobs in the range of 6-10). However, we also have a real-life scenario in Section 5.2. Here, we compare these approaches in terms of application performance. Figure 2 displays the execution times for each job and also its breakdown to map and reduce phases. We can see that preemption approach achieved over two-folds performance gain for the majority of the jobs in pool 2. This clearly shows that new jobs can reach their fair share quicker with the preemption approach because they do not have to wait for earlier jobs to finish. On the other hand, we observe long running times for the reducers in pool 2 with the wait approach which resulted in a significant performance degradation for these jobs. This stems from long waiting times for the resources (reduce slots) which are already occupied by the jobs in pool 1. For the jobs in pool 1, we observe a performance loss with preemption approach, especially for the reduce phase. This is due to the fact that the (reduce) tasks belonging to the jobs with over-share in the first pool are preempted to allocate resources for new jobs in pool 2 with preemption approach. However, performance loss is much smaller compared to the performance gain it achieved. In overall, preemption approach achieved 10% performance improvement for the total execution time.

To further investigate the performance difference in the second pool, we analyzed the map and reduce slots usage by the jobs in both pools with wait and preemption approaches. For the slot usage information, we show the cluster share of both pools in Figure 3 and4. While Figure 3 displays the map slots usage, Figure 4 shows the reduce slots usage. Both approaches were able to provide equal distribution of cluster resources to the jobs in both pools for map slots usage. One might think that job 8 is under its fair share for the map resources but this stems from the fact that its demand (i.e., number of mappers in the job) is much smaller than its fair share. On the contrary to fair map slot usage under different approaches, we observed a significant difference in fair execution of the reducers. In Figure 4(a), we can clearly see the starvation of the jobs in the second pool with wait approach. This is because earlier submitted jobs in the first pool take all available reduce slots and this starvation continues until the completion of these reducers. On the other hand, reduce tasks in the second pool with preemption approach almost achieve their fair share, as shown in Figure 4(b). We also observe that these reducers only wait for a small amount of time (i.e., fair share preemption timeout) until the resources are given to them. This does not only lead to the violation of the fairness for reduce tasks with wait approach, but also contributes to a severe performance loss. We can see that while the reducers of the jobs in the second pool are completed in around 300 seconds with preemption approach, this was around 1000 seconds with wait approach. This stems from the starvation of the reducers in the second pool due to long running reducers in the first pool. Summary. Our first experiments have yielded interesting results. First, we observe that wait as the default approach of HFS may not be efficient for ensuring fairness. This showed us the importance of an early action (i.e., preemption) for fair execution of different jobs when the cluster is fully utilized. Second, preemption does not only ensure fairness but this also leads to an increase in the performance of MapReduce applications. Specifically, we noticed that the starvation of fresh reducers (reducers which belong to the later submitted jobs) is the biggest contributor to the performance loss with wait approach.

Impact of the adopted preemptive approach. In order to compare preemption and kill approaches, we employed a similar job submission schedule as in the first set of experiments by submitting a sequence of wordcount jobs (8 jobs) with random inter-arrival times and again enforcing the later submission of the jobs from the second user to have the new jobs in pool 2. This time we reduced the number of jobs in pool 1 from 5 to 3 to have new jobs (jobs in pool 2) as a majority in the cluster which allows us to highlight the impact of the preemption technique on performance and resource utilization. The input data sizes of jobs in pool 1 and pool 2 is 17 GB and 4 GB (34 and 8 map tasks), respectively. Note that, we employed smaller input sizes since we are comparing preemptive approaches in which the running time of the jobs is not a major concern as in wait approach. Figure 5 shows the total execution time and individual execution times for each job. The results show that these two approaches have similar execution times unlike the big differences in the experiments with the wait approach. This is due to the fact that both approaches take an early action for enforcing fairness between different jobs while wait approach waits until completion of the running tasks before allocating resources for new jobs. Nevertheless, preemption outperforms kill approach for the total execution time as well as the individual execution time of each job. The reason behind this is waste-free behavior of the preemption approach while preempting the tasks. In our experiment, we find out that the number of killed/preempted tasks is equal to 79 and 68 for kill and preemption approaches, respectively.

To further investigate the different behaviors of these approaches, we plot CDFs of the successful tasks for the two approaches and the running times of killed tasks with kill approach in In Figure 6(a), successful task represents the task which is completed without getting killed or preempted and here we see that two approaches have a similar trend. However, we also observe that there are more shorter successful tasks with the preemption approach. This is due to the shorter task durations of the preempted tasks after their resume in available slots. To note that, map preemption technique in our work creates a new subtask for the uncompleted key-value pairs at the time of preemption and this leads to a shorter life-time for these subtasks.

On the contrary, kill approach destroys the on-going work of the killed tasks and these tasks start their execution from scratch when there is an available slot. Moreover, Figure 6(b) illustrates the wasteful nature of the kill approach by having killed tasks with more than 70s running time that contributes to the 23% of the total execution time. What's more, we calculated the resource loss (in terms of time) with kill approach as following:

t k t k + t s (1)
where t k is the killed task duration and t s is the successful task duration. The percentage of the duration of killed tasks compared to the total time spent yielded 11% resource loss due to kill approach. Summary. We observed that the cost of the preemption approach plays an important role on both application performance and resource utilization. Interestingly, the cost of the preemption approach did not only affect the preempted tasks but also affected the performance of other jobs in the cluster.

Real-life workloads

To investigate the different characteristics of the three approaches on the real-life workloads, we ran a benchmark suite based on the workload at Facebook production clusters. For the job submission schedule, we benefited from the historical Hadoop traces at Facebook [START_REF]SWIM Workload Repository[END_REF]. We took the first 50 job submission times and ran this schedule with the wordcount benchmark. The job inter-arrival times have a mean of 56 seconds with the total submission schedule of 48 minutes.

To generate the job input sizes, we took the job input sizes (in terms of number of map tasks) at Facebook production clusters as a base. Then, we sort the jobs according to their sizes and divided them into three groups of increasing sizes. The workload composition is shown in Table 2. It is important to note that most jobs at Facebook are small. We also note that Facebook clusters are busy only for a short time [START_REF] Zaharia | Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling[END_REF]; Figure 7 shows the CDF of cluster utilization under this workload composition . Finally, we ran this workload with two different users (i.e., the jobs are distributed to two pools) under three different approaches: wait, kill and preemption. We kept the same experimental deployment as described in Section 4.3 by only adjusting reducer slots to 2 for each node due to small size of the jobs in the workload. On the contrary to the results in Section 5.1, wait approach does not lead to a noticeable fairness violation and outperforms other approaches under this workload composition. Interestingly, preemptive actions affected the overall performance negatively by resulting in 8% -10% performance degradation. We observe that job average execution time is 65.3 seconds with wait approach while this is 70.7 and 71.7 seconds with kill and preemption approaches respectively.

Performance degradation in kill and preemption approaches. To further investigate the noticeable performance degradation with the preemptive approaches, we analyzed the resource availability and its relation with the individual job execution times. To do so, we plot the cluster utilization and relative speedups (wait approach as a baseline) of the submitted jobs with respect to their submission times for kill and preemption approaches in Figure 8. Notably, we display the cluster utilization in terms of reduce slots since we only observed kill/preemption attempts for the reducers with kill and preemption approaches. We discover that kill and preemption approaches lead to performance degradation in this scenario due to their design choices. For kill approach, it destroys the on-going work of the preempted tasks, thus these tasks need to be re-executed from scratch which results in a performance degradation. On the other hand, preemption approach results in a performance degradation by introducing a delay for the preempted reduce tasks since these tasks can only be resumed on the same node that they have been preempted. In particular, we can observe this performance loss with the jobs which are submitted after the peak time of the cluster (i.e., when the cluster resources are fully utilized, as shown in circles in Figure 8) for both approaches.

Kill vs preemption. As shown in Figure 8(b), kill approach has a greater performance variability compared to preemption approach; namely, it improved the performance of some jobs better compared to the preemption approach but this also led to more serious slowdowns for other jobs in the cluster. This stems from the fact that kill is a simple preemptive action and can take a faster decision for deallocating the resources from the tasks belonging to the jobs with over-share. On the contrary, preemption approach waits for the up-to-date information via new heartbeat messages in order to have a global and up-to-date view of the cluster status and this takes up to 2 seconds. Hence, this results in a more aggressive resource allocation with kill approach. In our experiment, we find out that the number of killed/preempted tasks is equal to 74 and 59 for kill and preemption approaches, respectively. What's more, we can see the wasteful nature of kill approach in Figure 9(a) which displays the CDF of running times of the killed tasks. For preemption approach, as we indicated earlier that preempted reduce tasks can be resumed only on the same node where they have been preempted. Hence, this introduces a delay for re-launching the preempted tasks when there are no free reduce slots available on the same node as they have been preempted. We can see these delay times of the preempted tasks, the major cause of the performance degradation, in Figure 9(b). On the other hand, with wait approach newer tasks can obtain the reduce slots after waiting for a small amount of time since cluster is fully utilized only for a short time. Therefore, it does not suffer from long running reduce tasks as in the previous set of experiments. This shows us the importance of the waiting time besides the resource availability which depends on the running time of the tasks. Summary. Our second set of experiments showed us the importance of the workload composition. While wait suffered from the previous workload type and resulted in a serious fairness violation and performance degradation, it outperformed other approaches under this workload composition. Importantly, we discovered a correlation between the resource availability and the effectiveness of these approaches. We observed that kill and preemption approaches lead to performance degradation if resources are not available only for a short time. This performance degradation is mainly contributed by the re-execution of the killed tasks for kill approach and the introduced delay for the preempted tasks for preemption approach. After a deep analysis of the results with both workload types, we can say that none of these approaches is superior in all situations. Therefore, an adaptive model that can select the optimal approach for ensuring fairness can be necessary; we will investigate its feasibility in our future work.

Discussion and Future Work

Hadoop is widely used to process large volumes of data and Hadoop clusters are usually shared among multiple users and jobs in order to maximize the resource utilization. In these multitenant environments, achieving fairness is a major challenge. To meet this challenge, Hadoop is equipped with its fair scheduler, Hadoop Fair Scheduler (HFS). HFS provides two simple approaches (wait and kill) to allocate resources for tasks belonging to the jobs with less share than their fair share. In this study, we also adopted the preemption approach which was originally developed in [START_REF] Yildiz | Chronos: Failure-aware scheduling in shared hadoop clusters[END_REF] on HFS and gave a comprehensive analysis on the efficiency of these three approaches while enforcing fairness. Our findings demonstrate that these approaches are suboptimal for different job sizes and workload compositions. We confirm that wait as the default approach of HFS may not be efficient in case of long running tasks [START_REF] Zaharia | Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling[END_REF][START_REF] Wang | Preemptive reducetask scheduling for fair and fast job completion[END_REF]. In addition, we show that preemptive approaches (kill and preemption) not only help to achieve fairness but also improve the MapReduce performance. Surprisingly, these preemptive approaches did not outperform wait when cluster utilization is low and cluster consists of mostly short jobs. Hence, we claim that adaptive model that can select the optimal approach depending on the job sizes and characteristics, resource availability and workload composition is necessary. For instance, wait approach may be more efficient when the waiting time (the time until the resources will be freed for the tasks belonging to the jobs with less-share) is short. However, estimating this waiting time a priori to the job execution is not trivial since this waiting time varies according to (1) the running applications (i.e., by analyzing the traces collected from three different research clusters [START_REF]Hadoop Workload Analysis[END_REF], we observe that the execution time of map and reduce tasks varies from 2 to 84631 seconds and from 9 to 81714 seconds, respectively); and (2) the progress of the application. Hence, adaptive model which can take decisions on-the-fly can improve MapReduce performance while ensuring fairness.

We also find out that the cost of the preemption approach plays an important role on both Inria application performance and resource utilization. While kill approach is costly due to its wasteful nature by destroying the on-going work of the killed tasks, preemption approach has an overhead while preempting the reduce tasks. Moreover, we show that the implementation choices of the preemption approach determine its overhead. The preemption approach we adopted is limited for being able to resume the preempted reduce tasks only on the same node that they have been preempted. In order to achieve a better preemption technique, this limitation can be mitigated by replicating the necessary data of the preempted reduce tasks to other nodes in the cluster. However, this may lead to the unexpected overhead due to the data transfer in between nodes.

Several avenues remain open for future work. One is to expand our experimental study by using other types of widely used fair scheduling policies (e.g., Dominant Resource Fairness [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF]).

As the ultimate goal, by leveraging the knowledge gained in our work, we plan to investigate a fairness model based on these three different approaches (i.e., wait, kill and preemption), workload composition and the resource availability and use this model to adaptively select an optimal approach for ensuring fairness.

Inria 3

 3 Overview of the Three Approaches: Kill, Wait and Preemption

Figure 1 :

 1 Figure 1: Overview of the three approaches: wait, kill and preemption.

Figure 2 :

 2 Figure2: Execution times of jobs under wait and preemption approaches and its breakdown to map and reduce phases. Jobs in pool 2 experience longer reduce phases with wait approach compared to preemption approach.

Figure 3 :

 3 Figure 3: Map slots usage

Figure 4 :

 4 Figure4: Reduce slots usage. Execution time of the reducers in the second pool reduced to 300 seconds with preemption approach while it was 1000 seconds with wait approach.

Figure 5 :

 5 Figure 5: Execution times of jobs under different preemption approaches

  CDF of running times of killed tasks for the kill approach

Figure 6 :

 6 Figure 6: CDFs of running times for killed and successful tasks

Figure 7 :

 7 Figure 7: CDF of cluster utilization under the workload based on the Facebook production clusters

Figure 8 :

 8 Figure 8: Interplay between cluster utilization and job execution times with respect to two preemptive approaches: preemption and kill

  CDF of waiting times of the preempted tasks for the preemption approach

Figure 9 :

 9 Figure 9: CDFs of running times for killed and waiting times of preempted tasks

Table 1 :

 1 Job input sizes and submission schedule: We submitted the jobs with random inter-arrival times by only enforcing the jobs in pool 1 are submitted earlier compared to the jobs in pool 2. The reason behind this condition is to be able to measure how quickly resources are given to new jobs. Note that, all the jobs have 72 reducers.

		Job Number Number of map tasks Submission time
		1	190	0
		2	190	10
	Pool 1	3	190	380
		4	190	870
		5	190	880
		6	34	70
		7	34	80
	Pool 2	8	8	470
		9	16	1000
		10	16	1003

Table 2 :

 2 The workload composition based on the job sizes at Facebook traces

	Group Number of map tasks % Jobs at workload
	1		1-10			70%
	2		10-100			15%
	3		> 100			15%
		1
		0.9
		0.8
		0.7
	CDF	0.4 0.5 0.6
		0.3
		0.2
		0.1
		0
		0	20	40	60	80	100
				Utilization(%)

RR n°9384

For simplicity, hereafter preemption approach refers to the pause-resume technique which was originally developed in[START_REF] Yildiz | Chronos: Failure-aware scheduling in shared hadoop clusters[END_REF].Inria

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments

This work is supported by the ANR KerStream project (ANR-16-CE25-0014-01). Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER, and several Universities as well as other organizations (see http://www.grid5000.fr/). This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, under contract number DE-AC02-06CH11357.