Rachid Ridouane

Cédric Gendrot

Rajesh Khatiwada

Mehri ejective fricatives: an acoustic study

Keywords: Ejective fricatives, Mehri, Modern South Arabian language

Ejective consonants are not very common crosslinguistically. Even less common is the occurrence of ejective fricatives. This infrequency is generally attributed to the incompatibility of two aerodynamic requirements: a continuing flow of air to create noise frication and an increasing intraoral air pressure to implement ejectivity. This study reports on an acoustic investigation of initial and intervocalic ejective fricatives in Mehri, a Modern South Arabian language spoken in Oman, and seeks to determine how this incompatibility is solved by the 5 subjects recorded. The analysis of different temporal and non-temporal parameters shows a high degree of variability in the way this contrast is implemented. Much of this variability is shaped by the position of the fricatives within the word.

INTRODUCTION

Ejectives occur in about 16% of the world languages (92 out of 576) [START_REF] Maddieson | Glottolized consonants[END_REF]. Ejective fricatives are more infrequently encountered; only 3.7% languages were reported to have at least one such segment. This rarity is generally attributed to aerodynamic constraints that make them acoustically instable: the continuing flow of air necessary to the production of frication is incompatible with the increasing of intraoral air pressure necessary to the production of ejectivity [START_REF] Maddieson | Why make life hard? Resolutions to problems of rare and difficult sound types[END_REF][START_REF] Shosted | Affricating ejective fricatives: The case of Tigrinya[END_REF]. This raises the question of whether these segments are real ejective fricatives, or whether they should on closer examination prove to be distinguished from their pulmonic counterparts by some other dimension. Faced with this question, Shosted and Rose [START_REF] Shosted | Affricating ejective fricatives: The case of Tigrinya[END_REF], based on acoustic data from Tigrinya, showed that ejective /s'/ was generally realized not as a fricative but as an affricate [ts']. Affrication, manifested with pre-frication closure lag, was interpreted as a general strategy used to increase intraoral air pressure. Two other strategies to solve the incompatibility of tight glottal constriction and frication have been reported. The first one, used by Yapese speakers, was to have a non-overlapping articulation by producing the ejective fricative not as a single segment but as a sequence of a pulmonic fricative followed by a glottal stop [START_REF] Shosted | Affricating ejective fricatives: The case of Tigrinya[END_REF]. The second strategy, observed in Tlingit, was to produce ejective fricatives with a much narrower constriction than was used in their pulmonic counterparts [START_REF] Maddieson | Aspects of the phonetics of Tlingit[END_REF]. This allowed for glottal closure to overlap the entire frication duration while producing high intra-oral pressure, suggesting that they were indeed ejective fricatives. This 'canonical' ejection of a fricative translated acoustically into shorter duration and a tendency for "scrapiness" or pulsing during frication noise. Similar to what has been observed in Tigrinya, Tlingit ejectives also displayed (near-)silent periods preceding frication noise. The interpretation of this silent gap differed, however. While [START_REF] Maddieson | Aspects of the phonetics of Tlingit[END_REF] interpreted it as glottal closure, [START_REF] Shosted | Affricating ejective fricatives: The case of Tigrinya[END_REF] provided some evidence that the source of this closure is oral. The phonetic implementation of ejective fricatives has been instrumentally examined in some other languages, including Amharic, Kabardian, Lowland Oaxaca Chontal, and Upper Necaxa Totonac. In a survey of the characteristics of ejective fricatives in these languages, [START_REF] Shosted | Affricating ejective fricatives: The case of Tigrinya[END_REF] showed that they acoustically displayed shorter and 'scrapy' frication noise, generally preceded and/or followed by a silent interval. From aerodynamic and articulatory perspectives, ejective fricatives were shown to display higher intraoral pressure peaks, larger tongue-palate contact and narrower constriction.

In the present study we report on an acoustic investigation of ejective fricatives in Mehri, a South Arabian Language spoken in Oman. We provide acoustic characteristics of these segments and show how native speakers solve the frication and ejectivity aerodynamic dilemma in light of what has been reported for other related and unrelated languages.

EJECTIVES IN MEHRI SYSTEM

We begin with some background information on Mehri and its consonantal system and review some of previous reports on ejective consonants in Modern South Arabian languages. Mehri is a dialect of the Modern South Arabian language, a subgroup of the Semitic branch of the Afroasiatic family. The dialect investigated in this study is spoken in the province of Dhofar in Oman by an estimated 50,000 native speakers. The consonantal system of the language is given in table 1.

In addition to voiceless and voiced stops and fricatives, the langue has ejective stops as well as a series of 4 ejective fricatives [θ', s', ɬ', š']. Like other Semitic languages, it lacks voiceless labial stop /p/ and labiodental voiced fricative /v/. Each segment in table 1 has a geminate counterpart which can be either lexically given or phonologically derived [START_REF] Watson | The Structure of Mehri[END_REF]. Ejectives were shown to pattern together with uvulars and pharyngeals as a natural class defined by the feature [+ low]. This class of segments triggers the diphtongization of following long high vowels /i:/ and /u:/ to [aj] and [aw], respectively, and the lowering of long /e:/ into /a:/ [START_REF] Watson | The Structure of Mehri[END_REF][START_REF] Bendjaballah | The phonology of 'idle glottis' consonants in the Mehri of Oman (Modern South Arabian)[END_REF]. A large amount of variability was reported in the realization of Mehri ejective segments, depending on dialectal origin, place of articulation, manner of articulation, and word position [START_REF] Watson | The Structure of Mehri[END_REF][START_REF] Lonnet | La phonologie des langues sudarabiques modernes[END_REF][START_REF] Watson | Glottalisation and neutralisation in Yemeni Arabic and Mehri: An acoustic study[END_REF][START_REF] Johnstone | The Modern South Arabian languages[END_REF][START_REF] Watson | A detective story: Emphatics in Mehri[END_REF]. This raised some debate as to whether the description of these segments as ejectives was, in fact, correct. For [START_REF] Watson | The Structure of Mehri[END_REF], for example, only /s'/ showed ejective tokens utterance-initially and -finally. Otherwise, it was realized as an emphatic or dorsopharyngealized consonant. For the other fricatives, the reported unmarked realization was emphatic. The interdental fricative was, for example, reported to be invariably pharyngealized in all environments. This has lead some researchers to argue for a gradual sound change which may switch, given the overwhelming influence of Arabic, from a contrast of ejectivity to a contrast of dorsopharyngealization [START_REF] Lonnet | La phonologie des langues sudarabiques modernes[END_REF][START_REF] Watson | A detective story: Emphatics in Mehri[END_REF]. Most of these reports on Mehri ejectives were limited to dialects spoken in Yemen. They also relied mostly on perception-based segmental transcription to capture the native speakers' productions. [START_REF] Watson | A detective story: Emphatics in Mehri[END_REF] provided a preliminary acoustic study of Yemeni Mehri ejectives, based on qualitative analysis of waveforms and spectrograms recorded from one native speaker. The only characteristic examined, however, was the presence/absence of a spike visible on the waveform, which was argued to be typical of ejectives. For our study we recorded five Omani Mehri native speakers and examined several temporal and non-temporal characteristics that might acoustically differentiate [θ', s', ɬ', š'] from their pulmonic counterparts [θ, s, ɬ, š]. More specifically, we seek to determine whether these cues signal ejectivity or some other dimension such dorsopharyngealization.

METHOD

Speakers

Five male Mehri native speakers aged from 20 to 27 (mean 22.2, SD 2.86) were recorded during a fieldwork in Salalah in southern Omani province of Dhofar. All of the participants reported being able to speak Omani Arabic and Standard Arabic, as is common for native Mehri speakers. None of them had any known history of hearing or speech disorders at the time of recordings.

Procedure

Table 1 shows the data used in this study. It consisted of 4 pairs of triliteral consonant roots contrasting each ejective fricative with its pulmonic counterpart (a larger data was recorded including filler items and items contrasting ejective stops with their nonejective counterparts). Each root was conjugated in three verbal paradigms (perf. 3ms, imperf. 3ms, subj. 3ms) and produced within a carrier sentence before them. Only the first two verbal forms were analyzed, yielding data with ejective and pulmonic fricatives in word-initial and word-medial intervocalic positions. The third verbal forms contained word-final ejectives not examined here. Target fricatives in initial position were followed by a schwa vowel. In intervocalic position, they were preceded by /i/ and followed by the long vowel /u:/ (recall that /u:/ following an ejective consonant is realized as a diphtong [aj]). One item had a vowel /a/ as a following vowel due to a lack of actual Mehri verb with the relevant structure. Each verbal root was written down in a slightly modified Arabic alphabet used to transcribe Mehri ejectives. Arabic translation of each item was also provided. For each recording, the speaker was shown the verbal root, asked to produce it with a natural speaking rate, and to maintain the same tempo throughout the session. 397 tokens were included in the statistical analysis (8

RESULTS

Presence/absence of silence

Counts of ejective fricatives with silent lags depending on word position and place of articulation are given in table 3. While no silent lags occurred during the production of pulmonic fricatives, more than 50% of the tokens with ejective fricatives display (near-)silent intervals. Word-initial ejectives (61%) are much more frequently produced with such lags than word-intervocalic ones (21%).

Intensity, center of gravity and pitch

Results for these three variables are summarized in table 5. They show that the presence or absence of ejectivity has no significant effect on F0 of the following vowels (for initial fricatives) and on F0 of the preceding vowel (for intervocalic fricatives).

Frication noise intensity varies for initial fricatives, with higher intensity for ejectives. No such differences were observed, however, in intervocalic position. Ejective fricatives were well differentiated from their pulmonic counterparts by the CoG measurement: it is significantly higher for ejectives than for their pulmonic counterparts. As expected, important differences were also observed between different places of articulation. CoG was highest for alveolars and lowest for interdentals, with alveopalatals and laterals displaying intermediate values. All pairwise comparisons of fricatives were significant at the p<.0001 level, except for the pair alveopalatal vs. lateral (p = 0.25).

Effects on vowel formants

As briefly outlined above, several authors have argued that Mehri ejective fricatives are generally realized with an emphatic or dorsopharyngealized configuration, akin to what occurs in Arabic languages. Dorsopharyngealization induces important qualitative effects on adjacent vowels, manifested by a raising of F1 -albeit generally slight -and a large drop of F2 of the adjacent vowels. The produced F1-F2 proximity was shown to be a highly reliable acoustic cue to pharyngealization in different Arabic varieties [START_REF] Obrecht | Effects of the Second Format in the Perception of Verlarization in Lebanese Arabic[END_REF][START_REF] Yeou | Pharyngealization in Arabic: Modelling, acoustic analysis, airflow and perception[END_REF]. One would expect similar acoustic effects of these consonants on neighboring vowels If Mehri ejective fricatives were pharyngealized. We measured F1 and F2 of the schwa vowel following initial fricatives and F1 and F2 of the /i/ preceding intervocalic fricatives (/u:/ was not measured because of the diphtongization that affects this vowel in the ejective context). In intervocalic position, vowel F1 is higher in the context of ejective fricatives (340.29 Hz, SD=39.09) compared to their pulmonic counterparts (310.55 Hz, SD=28.99). It is important to note, however, that the size of this difference, though significant at the p<.0001 level, is not as important as the one reported in pharyngealized consonants in Arabic [START_REF] Yeou | Pharyngealization in Arabic: Modelling, acoustic analysis, airflow and perception[END_REF]. No significant differences between ejective and pulmonic contexts were found as far as vowel F2 is concerned (p=0.22). For word-initial context, significant differences were observed both for vowel F1 and F2. Schwa vowel has a significantly higher F1 and lower F2 following ejective fricatives (F1: 455.94 Hz, SD=50.41; F2: 1200.56 Hz, SD=141.10) compared to their plain counterparts (F1: 392.07, SD=38.60; F2: 1417.49, SD=168.97). In this position, ejective fricatives display expected acoustic outcomes of a dorsopharyngealized articulation.

Temporal values

Ejectivity has no significant effect on preceding vowel duration (p=0.51). The vowel /i/ has virtually the same duration preceding an ejective fricative (87.82 ms, SD=26.29) or its pulmonic counterpart (90.26 ms, SD=28,68). Two sets of measurements were applied to fricative duration for both initial and intervocalic positions. In set1, we measured only frication duration by subtracting the duration of any silent interval. In set2 we measured the entire fricative duration including silent intervals, if any. For intervocalic position, set1 measurements yield significant differences between ejectives and their plain counterparts (p=0.005). As expected, frication noise for ejectives (87.9 ms, SD=33.03) was shorter than for their plain counterparts (105.8 ms, SD=19.19). No significant differences were observed, however, when total fricative duration was measured (107.48, SD=21.12 for ejectives, and 105.8, SD=19.19 for their plain counterparts). Absence of significant differences was also observed for initial fricatives (122.39 ms, SD=21.12 for ejectives, and 123.88 ms, SD=19.19 for their plain counterparts) as far as set2 is concerned (p=0.38). Again, as in set1 measurements for intervocalic position, the duration of frication noise is shorter in word-initial ejective fricatives than in plain fricatives at the p<.0001 level (101.94 ms, SD=27.30 for ejectives and 123.88 ms, SD=19.19 for their plain counterparts). Alveolars have the longest duration of this interval and interdentals the shortest. Alveopalatals and laterals lay in between. The mean duration of the post-frication silent interval in initial position (25.43, SD=12.04) is only slightly longer than in intervocalic position (20.63, SD=8.4). Virtually the same temporal values were obtained for pre-frication noise interval for intervocalic ejectives (24.3, SD=8.8). These durational values are closer to those reported for ejective /s'/ in Amharic [START_REF] Demolin | The search for primitives in phonology and the explanation of sound patterns: The contribution of fieldwork studies[END_REF] and Tigrinya [START_REF] Shosted | Affricating ejective fricatives: The case of Tigrinya[END_REF] than the longer lags reported for Tlingit ejectives [START_REF] Maddieson | Aspects of the phonetics of Tlingit[END_REF].

CONCLUSION AND DISCUSSION

The thread of this research was to determine how speakers implement ejectivity in fricatives given its aerodynamic incompatibility with a continuing flow of air. Results show that Mehri ejectives do display characteristics of an ejective articulation (presence of pre-and post-frication silent lags, higher C0G, shorter frication noise duration). But the way these acoustic correlates are implemented varies considerably across speakers, places of articulation and word positions. Indeed, we haven't been able to find an invariant primary acoustic correlate that systematically implements the ejective/pulmonic contrast in fricatives for the 5 speakers studied here. While fricatives do manifest pre-release silent intervals, a salient cue to ejectivity observed in different unrelated languages, this closure lag is only produced by some subjects and occurred in only 15% of the tokens, much less than the 80% reported for Tigrinya for example [START_REF] Shosted | Affricating ejective fricatives: The case of Tigrinya[END_REF]. Intervocalic ejective fricatives also displayed less post-frication lags compared to word-initial position. CoG is higher for ejectives, suggesting a narrower constriction, but no differences were found between laterals and alveopalatals. Other correlates were most notably present in word-initial position (effects on vowel formants, intensity). Dorsopharyngealization, which could be interpreted as yet another strategy to solve ejection/frication incompatibility, serves as an enhancing gesture introduced in order to increase the perceptual distance between the two phonemic categories. This enhancing gesture is unnecessary in intervocalic position, given that induced vowel diphtongization is salient enough to allow speakers recover the contrast.

fricatives * 2

 2 positions * 5 speakers * 5 repetitions -3 tokens). Three tokens were excluded from analysis because they were mispronounced (2 repetitions of [θ'əәbu:r] and one repetition of [θəәbu:r]). Different durational and non-durational values were taken from the acoustic records for each item. Nondurational values included number of fricatives with pre-and post-frication noise (near-)silent intervals, effects of ejectivity on the intensity and center of gravity (CoG) of frication noise, and effects of ejectivity on pitch and formants at the onset of following and offset of preceding vowels. Temporal measurements included preceding vowel duration, pre-release closure duration, frication noise duration, total fricative duration and post-release silence interval duration. These temporal intervals are illustrated in figure1.

Figure 1 :

 1 Figure 1: Illustration of the temporal intervals measured: V = preceding vowel duration, C = pre-frication closure interval, F = frication noise, L = post-frication glottal lag. Token [iθ'u:bəәr] "to blame".

Table 1 :

 1 The consonantal system of Mehri [cf. 6].

Table 2 :

 2 List of Mehri items Root

		Perf. 3ms	Imperf, 3ms
	/sbH/ səәbu:H	isu:bəәH	"to fix"
	/s'br/ s'əәbu:r	is'u:bəәr	"to support"
	/θbr/	θəәbu:r	iθu:bəәr	"to break"
	/θ'br/ θ'əәbu:r	iθ'u:bəәr	"to blame"
	/ɬbr/	ɬəәbu:r	iɬu:bəәr	"to measure"
	/ɬ'bl/	ɬ'əәbu:l	iɬ'u:bəәl	"to drink"
	/ʃbl/	ʃəәbla	iʃabla	"to swallow"
	/ʃ'rm/ ʃ'əәru:m	iʃ'u:rəәm	"to slap"

Table 3 :

 3 Counts of ejective fricatives with pre-frication and post-frication silent intervals, grouped by place of articulation. Symbols as in figure1. , all fricatives, including interdentals, can display (near-)silent intervals characteristics of ejectivity. Important differences among native speakers were observed, however, as shown in table 4.

		Initial	Intervocalic	Total
		L	C	L
	Alveolar	13	0	9	22/50
	Interdental	17	8	5	30/48
	Lateral	13	7	8	28/50
	Alveopalatal	17	0	5	22/50
	Total	60/98	42/100		102/198

Disregarding pre-frication silence, which couldn't be valued based on acoustic data for word-initial fricatives, no important differences in the proportion of glottal lags (L in table 3) were observed between different places of articulation (~ 22 cases). This shows that, contra to what has been reported

Table 4 :

 4 Counts of ejective fricatives with pre-frication and post-frication silence intervals for the 5 subjects, grouped by place of articulation.

		[s']	[θ']	[ɬ']	[š']	Total
	S1	0	6	2	0	8
	S2	8	7	5	5	25
	S3	10	10	10	10	40
	S4	4	6	7	5	23
	S5	0	1	3	2	6
	Total	22	30	28	22	102

Table 5 :

 5 Effect of ejectivity on F0, CoG and intensity, grouped by word position.

	Position Airstream	F0	CoG	Intensity
	Initial	Ejective	142.88 5036	57.96
		Pulmonic	137.71 4266	54.08
		P-Value	0.89	< 0,0001	0.002
	Inter.	Ejective	121.12 4721	59
		Pulmonic	120.84 3874	58.4
		P-Value	0.93	< 0.0001	0.21

ACKNOWLEDGEMENTS

This work was funded by a grant from the French Agence Nationale de la Recherche Scientifique (ANR program OmanSam) and by the Labex EFL (ANR/CGI). We would like to warmly thank the Omani participants for their help and enthusiasm during the study visit of the first author in Salalah.


Julien Meyer¹

Bernard Gautheron²

Rachid Ridouane²

Whistled Moroccan Tamazight: phonetics and phonology

Keywords: Whistled speech, Tamazight, Syllable, Schwa, Segments

This paper reports the results of a pilot phonetic study of whistled Moroccan Tamazight. Whistled speech is an ancient traditional and natural practice that consists in a phonetic emulation and transformation of the spoken signal into a simple melodic line made up of frequency and amplitude modulations of a whistled signal. It is primarily used for long distance communication. We recorded four Moroccan Tamazight speakers in the High Atlas producing this special speech register. Given its particular characteristics, namely the extensive presence of words and syllables without vowels, the opportunity Tamazight affords for the execution of whistling may be particularly challenging. We show how speakers whistle a selected set of words and sentences and discuss the preliminary results from phonetic and phonological perspectives.

INTRODUCTION

This paper addresses a special and little-known traditional language practice based on whistlingcalled whistled speech -in a language characterized by typologically unique phonetic and phonological properties -Tamazight Berber. Whistled Tamazight was recently found among shepherds of the High Atlas in Morocco, an area which greatly shades into Tashlhiyt and shares with it major phonological properties. Among these properties, the one we are interested in here concerns syllable structure. The Tamazight whistlers learn since childhood to copy any sentence of their language into a simpler whistled signal carrying key phonetic cues of the original acoustic and articulatory features. These are sufficient to guarantee high levels of intelligibility of the information encoded in the whistles. An example of a whistled word is given in Fig. 1.

Whistling is one of the multiple modes of expression for some languages. To date, all over the world, around 40 low-density and remote populations are known to have developed their local language into this special and complementary speech register which has the advantage to increase the audible range of speech and to enable dialogues when speakers are far from each others (for a review, see [START_REF] Meyer | Whistled Languages. A Worldwide Inquiry about Whistled Speech[END_REF]). It is mostly found in mountainous and densely vegetated landscapes. Whistled Spanish of La Gomera Island -locally called "El Silbo", i.e., "The Whistle" -is the most studied of them [START_REF] Classe | Phonetics of the Silbo Gomero[END_REF][START_REF] Busnel | Whistled Languages Berlin[END_REF][START_REF] Rialland | Phonological and phonetic aspects of whistled languages[END_REF][START_REF] Meyer | Acoustic strategy and typology of whistled languages; phonetic comparison and perceptual cues of whistled vowels[END_REF], and was declared a Masterpiece of the Oral and Intangible Heritage of Humanity by the UNESCO due to its historical and cultural importance for the Canary Islands. Indeed, "El Silbo" is one of the few remnants of the islands' ancient Tamazight language (Guanche) and this special whistled register has only survived by being adapted to the conqueror's language (Spanish). For historians, the discovery of a whistled tradition of speech in the High Atlas is of a great scientific interest. Indeed, besides the ancient presence and extensive cultural exchanges that the Berber populations of Africa have had with the Canarians, there is also evidence of ancient cultural exchanges with Andalucía, Greece and Bearn in the Pyrenees, three geographical locations where a whistled speech practice has been reported during the 20 th century. Moreover, ancient historians such as Elien and Herodotus made reports of the existence of whistled traditions related to language in other speaking communities of North Africa [START_REF] Meyer | Whistled Languages. A Worldwide Inquiry about Whistled Speech[END_REF].

Whistled Tamazight is also of importance for the community of researchers in phonetics and phonology. Examining how the rare phonotactic patterns of this language are transposed in such a special way will provide, we believe, some important new insights on the organization and malleability of the phonology/ phonetics system.

Whistled speech: a review

From previous research, it is known that whistled speech profoundly modifies the phonetics of standard speech by operating a reduction in the frequency domain (from the complex frequency spectrum of the voice to a simple pitch variation of whistles). During this procedure, certain phonetic details present in standard speech are lost. A major distinction in strategy is however noted for tonal versus non-tonal languages.

In most non-tonal languages (Greek, Spanish, Turkish), whistlers approximate the vocal tract articulation used in spoken form; this approach provokes a whistled adaptation of vowel and consonant qualities carried by the timbre of the voice. In Greek, Spanish and Turkish, whistled vowels are emitted at different pitch levels depending on the frequency distribution of their timbre: typically, /i/ has the highest pitch, /e/ is lower, /a/ is even lower [START_REF] Meyer | Acoustic strategy and typology of whistled languages; phonetic comparison and perceptual cues of whistled vowels[END_REF]. Consonants are represented by continuous or interrupted modulations of these vocalic frequencies [START_REF] Meyer | Whistled Languages. A Worldwide Inquiry about Whistled Speech[END_REF][START_REF] Rialland | Phonological and phonetic aspects of whistled languages[END_REF]. The description of the mechanism of bilabial whistling production has shown that a whistle frequency is always captured by either the second or third formant of the vocal tract and that a frequency jump between the two occurs when these formants are close [START_REF] Shadle | Experiments on the acoustics of whistling[END_REF]. This latter effect is most likely to occur in front vowels and in some consonant transitions [START_REF] Meyer | Whistled Languages. A Worldwide Inquiry about Whistled Speech[END_REF].

In tonal languages (see [1 and 4] for reviews), in what is called pitch-based whistling, the situation is different: whistles are not focused on emulating the timbre but instead the pitch of the voice, transposing the fundamental frequency of the vibration of the vocal folds to primarily encode the lexical tones. Therefore, in the whistled form of a tonal language, the vowel quality is completely excluded. This exclusion of timbre occurs even where the functional load of information carried by tones is lower than that carried by vowel quality.

Tamazight, which is a non-tonal language, is expected to behave like Spanish, Turkish and Greek as far as whistled syllables with full vowels are concerned (see Fig. 1). The question arises, however, concerning syllables without vowels. How are these forms transposed in whistling in the absence of a full vowel? This question has been raised and examined both for singing [START_REF] Dell | Singing in Tashlhiyt Berber, a language that allows vowe-less syllables[END_REF] and for spoken language [START_REF] Grice | The association of tones in Tashlhiyt Berber[END_REF][START_REF] Ridouane | Tashlhyt Berber[END_REF]. It was shown that forms containing neither a vowel nor a sonorant consonant may either display no peak at all or more frequently have a peak on a schwa vowel [@] occurring within the consonant string of the target form.

DATA COLLECTION

Fieldwork was organized during September 2014 in the High Atlas. Two different types of audio materials were collected at this occasion with four different traditional whistlers:

• First, a corpus was built from a list of selected isolated words that were recorded in a situation of elicitation in a room isolated from noise. Two traditional whistlers were asked to speak and whistle twice each word. One of them was also asked to over articulate the spoken form at the same pace as his whistled productions to enable the experimenters to locate where a @ would appear in this case. • Another corpus was recorded in the context of a real dialogue between two other whistlers separated by a distance of 250 meters (outdoors, mountainous and dry landscape, recording at 1 meter of the whistler who initiated the conversation semi spontaneously).

The second whistler systematically asked for repetition of each sentence for the experimenters to obtain two audio recordings of a same sentence. These corpora were double checked by two linguists, experts of whistled speech. With the help of a linguist who is both expert and fluent speaker of Tamazight, they transcribed the corpora based on visual inspection of the acoustic signals with auditory confirmation. For the present study the productions of one whistler of each corpus are examined. We first measured the frequency distribution of the three full vowels /a, i, u/. The value selected for the frequency of each whistled vowel corresponded to the maximum of amplitude of this segment. In the absence of a clear maximum, the measure was taken at the median duration of the vocalic segment. Vocalic transitional elements [@] were measured in clusters with no full vowel. Because of the over articulations of whistled speech, vowel-like modulations appeared even if they were not present in standard spoken form (for example, in voiceless clusters or clusters with homorganic consonants). Interestingly, these vocalic elements were also present in speakers' 'exaggerated' spoken repetitions of the same items, trying to pace them.

RESULTS

The vocalic system

Figure 2 presents the frequency distribution of whistled vowels and whistled vowel-like [@]. Several observations can be made from these data:

(i) the underlying vowels /i, a, u/ are whistled in intervals of frequencies that follow the same logic as in Turkish or Spanish, with /i/ statistically higher in frequency than /a/ which is also higher than /u/ (see data in (ii)).

(ii) The intervals of /i/, /a/, and /u/ are statistically different (multiple t-tests with Bonferroni correction) albeit important overlap, particularly between /a/ and /u/ (/i/ vs. /a/: [p<.0001] for AL, [p<.0001] for MO. /a/ vs. /u/: [p<.01] for AL, [p<.05] for MO). /i/ pulls the frequency to high values, /a/ is intermediate and /u/ pulls the frequencies to low values of the whistled vocalic space. (iii) The vowel-like element [@] overlaps greatly with the three other whistled vowels, suggesting that this element is not attached to a particular vowel target and transposes various timbre configurations. As such it is a phenomenon observed for the first time in whistled speech research.

(iv) The relative distribution of [@] is the same for the two whistlers whistling in different conditions (even if the whole distribution is transposed to higher frequencies for the whistler who whistles stronger to reach a greater distance).

The consonantal clusters

'Consonant-only' syllables.

Syllables made-up of underlying consonants only are present in our data. These may be of the types C (e.g. [k.ʃm] 'come in', CC (e.g. sk.su] 'couscous, a traditional Amazigh dish' or CC (e.g. [zʕ.fat] 'be angry') where the nucleus is bolded and underlined. An important constraint that regulates boundaries between syllables is the prohibition against complex onsets [START_REF] Dell | Syllables in Tashlhiyt Berber and in Moroccan Arabic[END_REF]. A consequence of this is that all prevocalic consonant clusters are heterosyllabic. That is, XCCVX forms (where X is a word boundary or any string of consonants and vowels) are systematically parsed as XC.CVX [START_REF] Ridouane | Tashlhiyt's ban of complex syllable onsets: phonetic and perceptual evidence[END_REF]. We are interested in assessing whether this heterosyllabicity is also reflected in the way whistlers delineate consonant clusters. Fig. 4 presents an illustration of the word [amksa] 'shepherd'. Here too, the form is whistled in a way that suggests that it is consciously partitioned in three parts, reflecting its underlying syllable structure (i.e. [a.mk.sa]). A more accurate transcription of what is heard when this item (and the like) is whistled or spoken in an exaggerated way should be transcribed [a.m@k.sa], making the syllable sounding more like [mak] than [mk]. This type of phonetic mapping of the abstract /CC/ representation into a [CVC] sequence changes the weight of the syllable: having a coda makes heavy.

Heavy and light syllables

Syllable weight plays an important role in the phonological system of Tamazight. Versification of song poems, for instance, can't be accounted for without making a distinction between heavy and light syllables [START_REF] Dell | Syllables in Tashlhiyt Berber and in Moroccan Arabic[END_REF][START_REF] Jouad | Mètres et rythmes de la poésie orale en berbère marocain[END_REF]. The form [ts.snt] 'you know', shown in figure 5, provides an interesting example to illustrate differences between whistled CV and CVC syllables, The form [tssnt] 'you know' is whistled in two different sentential contexts: (i) followed by a vowel, where /t/ is resyllabified as onset of the next syllable (i.e. [ta]), and (ii) followed by a consonant, with /t/ being the coda of the preceding syllable (i.e.

[snt]). As is clear from the figure, the coda /t/ is whistled with sufficient details so as to appear as an independent segment. This is not the case of onset /t/ which is represented as an interrupted modulation of the vocalic frequencies (see also figure 1). This pattern was almost always observed for internal coda consonants. Two others forms, [argaz] 'man' and [aʁbalu] "water source", are shown in figure 6.

CONCLUSION AND DISCUSSION

This study has presented results of a pilot phonetic study of whistled Tamazight. We examined how some phonological properties of this language are rendered in whistled speech, focusing more specifically on syllable structure and how it relates to the vocalic and consonantal system of the language.

As far as full vowels are concerned, we have shown that they are whistled in intervals of frequencies that follow the same pattern as was observed for other non-tonal languages (e.g. Spanish, Turkish, and Greek). Tamazight schwa elements are whistled within a much larger frequency range that greatly overlaps with the full vowels. This is probably due to the absence of a specific target for [@]; the whistled frequency levels associated to [@] depend on the locus of articulation of the neighboring consonants: coronals modulate towards high frequencies; labials, labiodentals and uvulars modulate towards low frequencies. This suggests a principle of phonetic inertia: as for vowel-like elements in spoken forms, the presence and quality of [@] results from the gestural timing configuration of the surrounding consonants [START_REF] Dell | Syllables in Tashlhiyt Berber and in Moroccan Arabic[END_REF][START_REF] Ridouane | Schwa elements in Tashlhiyt word-initial clusters[END_REF]. While in whistled Turkish, Greek or Spanish, consonant clusters resulting from two consecutive syllables concatenate the frequency shapes of each constituent by truncating them at their encounter [START_REF] Meyer | Whistled Languages. A Worldwide Inquiry about Whistled Speech[END_REF][START_REF] Meyer | Typologie et intelligibilité des langues sifflées: approche linguistique et bioacoustique[END_REF] (e.g. Greek [ksp] simplified into [kp] [START_REF] Meyer | Whistled Languages. A Worldwide Inquiry about Whistled Speech[END_REF]), Tamazight clusters are not only maintained but are over articulated making schwa elements within them highly discernable. This over articulation is not essentially different from what occurs in shouting: when consonants within a cluster display a low degree of gestural overlap and longer delay between events, a period of no constriction occurs that is overtly realized as a vowel-like element in the signal. The way Tamazight consonant clusters are whistled probably reflects the underlying syllable structure of these sequences, as shown by the fact that a form like [kʃm] is partitioned in two parts, and that differences between light and heavy syllables are quasi systematically rendered. These results are preliminary and need to be confirmed from additional data and subjects. Current and future work should therefore continue to determine to what extent, whistlers rely on abstract cognitive abilities which they possess as native speakers of a language where a single consonant or a sequence of two consonants constitute well-formed syllables.

Figure 1 :

 1 Figure 1: The Tamazight word [ud:iz] 'punch' (transcribed in the instituted Moroccan Tamazight alphabet Tifinagh).In all the figures of this paper, the spoken signal is amplified of 15 dB to be more visible and easy to compare with the whistled signal.

Figure 2 :

 2 Figure 2: Frequency distribution and standard deviation of whistled full vowels and /@/ in Tamazight for a whistler of each corpus: (A) AL whistling words in a task of indoor elicitation; (B) MO whistling sentences in a natural context of outdoor long distance dialog;

Figure 3 :

 3 Figure 3: Spoken and whistled forms of (A) [ʃm.mart] and (B) [k.ʃm] (where . indicates syllable boundary).

Fig. 3

 3 Fig. 3 presents an illustration of the verb [kʃm] produced in isolation. From a phonological point of view, this form is bisyllabic [k.ʃm], where the first consonant stands for a syllable of its own. The way this form is rendered in whistling shows that it is partitioned in two parts with a period of silence between [k] and [ʃm]. In doing so, whistlers seem to delineate parts of this form in just the same was as a clear bisyllabic form such as [izi] 'fly', which also has two parts [i] and [zi], or [uddiz] shown in Fig. 1 above. Fig. 3 also presents an illustration of the word [ʃm.maxt] 'I smelt it'. The syllable [ʃm] also stands on its own in this form but displays different acoustic characteristics from [ʃm] of [k.ʃm]. A possible explanation to these differences relates to prosodic considerations. Unlike in [ʃmmaxt], the syllable [ʃm] in [k.ʃm], because it occurs in final position and has a sonorant segment, bears the tonal event which makes it louder and longer [12, 13].

Figure 4 :

 4 Figure 4: Spoken and whistled forms of (A) [am.zil] and (B) [a.mk.sa].

Figure 5 :

 5 Figure 5: Sentence (A) [is tssnt abaxxu] 'do you know [the word] earthworm?') syllabified [is.ts.snt.ta.bax.xu] in the spoken form and (B) /is tssnt tima/ ('do you know Tima?, a proper name') syllabified [is.ts.snt.ti.ma] in the spoken form. Both sentences are interrogative marked by a rising whistled frequency at the end.

Figure 6 :

 6 Figure 6: (A)[aʁbalu], (B) [argaz] spoken/whistled forms.

ACKNOWLEDGEMENTS

The authors would like to thank R-G. Busnel and G. Pucheux for their contribution to the inquiry on whistled Tamazight. We would like to thank also Tamazight speakers/whistlers for their participation to this study. Their traditional knowledge has been a key factor making our work possible. The preparation of the fieldwork was financed by a European Eurias fellowship at the Collegium of Lyon. Fieldwork was auto-financed by Meyer and Gautheron. The phase of analysis was financed by a Marie Sklodowska Curie IIF Fellowship (project Icon-Eco-Speech). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.


Mario Macías
email: mario.macias@bsc.es

Jordi Guitart
email: jordi.guitart@bsc.es

Trust-aware Operation of Providers in Cloud Markets

Online Reputation Systems allow markets to exclude providers providers that are untrustworthy or unreliable. System failures and outages may decrease the reputation of honest providers, which would lose potential clients. For that reason, providers require trust-aware management policies aimed at retaining their reputation when unexpected failures occur. This paper proposes policies to operate cloud resources to minimise the impact of system failures in the reputation. On the one side, we discriminate clients under conflicting situations to favour those that would impact more positively the reputation of the provider. On the other side, we analyse the impact of management actions in the reputation and the revenue of the provider to select those with less impact when an actuation is required. The validity of these policies is demonstrated through experiments for various use cases.

Introduction

Cloud Computing allows clients to acquire resources (usually Virtual Machines, VMs) and size them dynamically according to their spot requirements and pay only for what they use. Our research is framed in Open Cloud Markets [START_REF] Neumann | SORMA -building an open grid market for grid resource allocation[END_REF] where both clients and providers are autonomous agents that negotiate the terms of the Quality of Service (QoS) and the pricing. After the negotiation, the terms of the contract are stored in a Service Level Agreement (SLA).

Cloud providers may not always fulfil the SLAs they agree with the clients. Online reputation systems [START_REF] Macias | Cheat-proof trust model for cloud computing markets[END_REF] allow their users to submit and retrieve information about the fulfilment rate of the SLAs for each provider. Reputation systems enforce the confidence between parties and boost the number of commercial transactions, but they are vulnerable to reputation attacks: a group of dishonest clients may report false values about the QoS that a cloud provider is actually offering [START_REF] Kerr | Smart cheaters do prosper: defeating trust and reputation systems[END_REF]. In consequence, reputation systems must also establish trust relationships between peers to avoid dishonest reports.

Reputation allows markets to exclude dishonest providers. However, spot failures or system outages may decrease the reputation of honest providers, having a double economic impact: the provider must pay penalties as agreed in the SLAs and it will lose potential clients due to the loss of reputation. For this reason, providers operating in a Cloud market require trust-aware management policies aimed at retaining their reputation when unexpected failures occur.

We propose policies to discriminate users in function of their reputation under some situations that force provider to violate SLAs, such as errors in resources allocation, or an outage that makes unavailable part of the resources in a data center, dealing with the issue raised by Xiong et al. [START_REF] Xiong | Peertrust: Supporting reputation-based trust for peer-to-peer electronic communities[END_REF] and Kerr et al. [START_REF] Kerr | Smart cheaters do prosper: defeating trust and reputation systems[END_REF], which considered the necessity of a community-context factor to incentivise peers for reporting true feedbacks.

The main contributions of this paper are: (1) introduction of policies to minimize the impact of system failures in the reputation. We discriminate clients according to their reputation to favour those with high reputation under some conflicting situations, because the reports of those clients will impact more positively the reputation of the provider; (2) evaluation of the impact of the management actions in the reputation and the revenue of the provider to select those with less impact when an actuation is required.

The rest of this paper is organised as follows: Section 2 summarizes the reputation model and describes the policies, which are evaluated in Section 3. Then, we present the conclusions and some future research.

Trust-aware SLA management

We consider a group of providers that are competing in a market to sell their resources to the potential clients. The clients are also communicated between them by means of a Peer-to-Peer network. When a client wants to buy a resource, it sends an offer to the providers to start a negotiation and agree a SLA, which is described as { -→ S , ∆t, Rev(vt)}.

-→ S are the Service Level Objectives (SLOs) that describe the QoS to be purchased by the client. ∆t is the time period when the task will be allocated. Rev(vt) is a revenue function that describes how much money the provider earns or loses after finishing a task. The Violation Time (vt) is the amount of time in which the provider has not provided the agreed QoS to the client. Let M R the Maximum Revenue, M P be the Maximum Penalty (a negative revenue), M P T the Maximum Penalty Threshold, and M RT the Maximum Revenue Threshold, we describe our revenue function as follows:

Rev(vt) = M P -M R M P T -M RT (vt -M RT ) + M R
If vt < M RT the SLA is not violated (0 violations); if vt > M P T , the SLA is completely violated (1 violations). M P T > vt > M RT is a partial violation. Please refer to Section 3 for more details about Rev(vt) and its concrete values.

Both clients and providers are entities that have a degree of trust between them as individuals. Trust relations are provided by the reputation model described in our previous work [START_REF] Macias | Cheat-proof trust model for cloud computing markets[END_REF], which demonstrated its validity to identify trustworthy providers and expel dishonest peers to protect the system against reputation attacks. In this model, a trust relation is expressed as

- → T (A, B) = ω 1 - → D(A, B) + ω 2 - → R (B); - → D(A, B) is the direct trust from A to B, which is built
based on previous experiences between A and B; -→ R (B) is the reputation trust, which is calculated by asking to other clients about their past experiences with B; ω 1 and ω 2 are used to weight each term, and may vary in each particular client. Trust values vary from 0 (no trust) to 1 (maximum trust). Trust relations are continuously updated assuming that most peers are honest and, when asked, they report their true trust toward the provider. Related work considers many incentives to peers to report honestly [START_REF] Zhang | Promoting Honesty in Electronic Marketplaces: Combining Trust Modeling and Incentive Mechanism Design[END_REF]. Our contribution is complimentary to them, since we deal with the minimization of the impact of the dishonest reports.

To select a provider, a client sends SLA templates to all the providers that match its requirements. If the providers have enough resources to handle the request, they return a price. The client then scores all the providers and chooses the provider with the highest score, which may vary depending on the client preferences. In this work, we score providers as --→ T (c x , cp y ) P rice : the client would accept sending tasks to providers to which the trust is lower if the price they establish is low enough. That would motivate providers to keep its maximum trust level and, if not possible, to lower prices. The higher QoS is provided to a client, the higher trust values he will report to the reputation system; unless the client is behaving dishonestly and reporting false values.

We propose to maximise the reputation as a key objective that will help providers to increase their revenue due to the enforcement of the trust relationship with their clients. This paper considers selective SLA violation and/or cancellation for minimizing the impact of resource failures and overloading: to prioritise trustworthy users under certain situations in which a set of SLAs that are already allocated must be violated temporarily or directly cancelled. When the monitoring system of a provider detects that there are not enough resources to fulfil the workload for all the VMs in a given node, the next process is triggered: the VMs are ordered according to a given criterion and the provider pauses the VMs on the top positions during t time. When the node can provide the QoS for the VMs that are still running, the provider stops pausing VMs. In reputation maximisation policies, the criterion to order VMs is the trustworthiness to the client that owns it. To calculate the trustworthiness to a client, the provider can join the reputation system as a normal peer, and poll several clients about several providers. If a given client is usually reporting values that are far away from the average, it will be considered unreliable.

The SLA violation algorithm is generic enough to achieve other BLOs, such as revenue maximisation [START_REF] Macias | Rule-based SLA management for revenue maximisation in cloud computing markets[END_REF]. Next section will evaluate the effectiveness of the trust maximisation policy by comparing it with the same policy for other BLOs.

We must emphasize that our policy cancels SLAs only when the provider is not able to fulfil them all. This should be infrequent, only when the violation is unavoidable, because the economic penalty is paid whatever the client trustworthiness is. The idea is at least to minimize the impact in the reputation of the provider. A bad usage of this policy could make the clients lose the confidence in the provider, thus losing profit.

To evaluate the effectiveness of our models, we have created a simulated environment [5] that is available online to facilitate replicating the experiments. The simulator reproduces the model and market negotiation steps that are described in Section 2 and the related work [START_REF] Macias | Cheat-proof trust model for cloud computing markets[END_REF]. The trustworthiness of the clients follows a folded normal distribution with mean=0.5 and standard deviation=0.2. That means that most clients have trust values near 1 and a few clients are reporting dishonestly. The values for Rev(vt) are the next: M RT = 0.05 (that means that if the agreed QoS is not provided during the 5% of the time or less, the SLA is not considered as violated); M P T = 0.3 (when the agreed QoS is not provided during the 30% of time or more, the SLA is completely violated); M R is dynamically established according to -→ S and the market status [START_REF] Macias | Rule-based SLA management for revenue maximisation in cloud computing markets[END_REF]; M P = -1.5M R (if the provider completely violates a SLA, it must pay back the 150% of the price that the client paid initially). The providers normally provide the 100% of the agreed QoS during off-peak hours and around 97% during peak hours. The workload follows a web pattern that varies in function of the hour of the day and the day of the week. The simulations rely on constant values that do not intend to reflect real market data, but to evaluate the model in terms of relative values and tendencies.

To evaluate the reputation-aware resources operation, we have simulated 5 days of a market operation with three types of providers, according to their policy for discriminating SLAs during resources overload: (1) a provider that randomly discards SLAs, used as a baseline to evaluate the system behaviour without any policy; (2) a provider that discards the SLAs that report less revenue [START_REF] Macias | Rule-based SLA management for revenue maximisation in cloud computing markets[END_REF]; and (3) a provider that discards the SLAs from the clients to which there is low trust. We introduced a global outage of the data centre at day 3 of the simulation. During the outage, the providers only have the 20% of their usual resources. The outage has been programmed to happen during a peak of workload. That means that about 80% of the allocated SLAs are to be violated during the outage.

Figure 1a shows reputation for day 2 (normal day) and day 3 (outage). Reputation is near the maximum value for all the providers at off-peak hours. During the peaks, the graph shows the effect of the increase of SLA violations in the reputation. The reputation maximisation policy keeps reputation near 1 during both peaks and off-peaks. The random policy shows that reputation decreases when no policies are applied. Although the revenue maximisation policy does not consider reputation, it indirectly keeps it between random and reputation maximisation policies: the provider tries to first pause the VMs whose SLA violation time is over M RT . In consequence, it violates less SLAs and, indirectly, the reputation of the provider is higher than the reputation of the provider that does not apply any policy.

Figure 1b shows the evolution of the spot revenue for the three providers during the outage, demonstrating that maintaining high reputation during the outage has a real impact in the revenue of the provider. However, we measured that during normal operation the revenue of the provider that maximises the reputation is slightly lower. Considering the previous observations, we have introduced a new provider that is aware of the environment (normal operation or outage) and dynamically switches the revenue/reputation maximisation policy in function of what is expected to report the highest economic profit. When the provider is operating normally it uses the revenue maximization policy; if the monitoring information shows that there is an outage in part of the resources, the provider switches to the reputation maximization policy and returns back to revenue maximization policy when the systems are again in normal operation.

Figure 2a shows that the context-aware provider maintains a reputation rate similar to the revenue-maximisation provider during normal operation and a rate similar to the reputation-maximisation provider during the outage.

The revenue of the context-aware policy is similar to the revenue maximisation policy during normal operation. Figure 2b shows the time window that comprehends an outage of the system and the subsequent recovery, demonstrating that the revenue of the context-aware policy is similar to the reputation maximisation policy during an outage.

Conclusions and future work

Under certain situations, such as errors in the estimation of resources or an outage in a cloud provider, part of the VMs that are being hosted must be paused to allow enough free resources for fulfilling the other SLAs. This paper introduces a policy to prioritize users according to their trustworthiness. This policy has a double goal: (1) to minimize the impact of the SLA violations in the reputation of the provider and, in consequence, in the revenue; and (2) incentivise users to report true validations of the providers. After analysing the policy in comparison with others, we show that providers that behave honestly and apply revenue maximisation policies, in most cases indirectly keep a good enough reputation rate and achieve higher revenue than the providers that apply reputation maximisation. The benefits of reputation maximisation in terms of revenue are noticeable under conditions that imply a high rate of SLA violations. Considering the aforementioned, we introduce a new type of provider that switches between reputation or revenue maximisation policies depending on the context. This provider achieves the best revenue in all the cases, and always keeps good-enough reputation rates.

A key issue of reputation systems is to incentivise their users to report true validations of the providers [START_REF] Macias | Cheat-proof trust model for cloud computing markets[END_REF]. The policies of this paper help solving it because clients that report true validations have high reputation to their peers. Providers that have interest on keeping high reputation will prioritize the QoS for trustworthy clients under certain situations such as peaks of demand or an outage. As a consequence, clients that want to benefit from this positive discrimination will report true validations of the providers. Since the reputation model is P2P, any provider could join a network for polling the trustworthiness of a client.

This paper validates the model by means of a simulated environment because there are no real market traces of this type of market model. In addition, we would need to fully use a large data centre during many days to generate data that is statistically representative enough. Using a simulated environment allows to solve such issues. Although the results do not reflect real information in quantitative terms, the objective of this paper is to evaluate the policies in qualitative terms: we measured that the application of a given policy can improve the trust or the revenue of a provider in a significant proportion. This paper does not consider the ethical issues of using such policies by dishonest providers for always cheating the clients with low reputation: not only dishonest clients, but also clients that recently joined the reputation network.

In future work we will improve the context-aware provider by adding statistical analysis to dynamically learn how the actions of the provider during negotiation and operation can influence the future reputation. We also plan to improve the policy for selecting the SLAs that are going to be violated. The objective is to achieve a policy that is able to ponder both reputation and revenue maximisation objectives. In addition to the improvement in the model, future work will include new policies to complement the selective violation/cancellation of SLAs. For example, to apply price discounts to the clients to which there is high trust or to use migration capabilities to redistribute VMs for decreasing the violation rate of those SLAs from trusted clients.

Fig. 1 :

 1 Fig. 1: Measurements after and before an outage

Fig. 2 :

 2 Fig. 2: Measurements for context-aware policy

Acknowledgment

This work is supported by the Ministry of Science and Technology of Spain and the European Union (FEDER funds) under contract TIN2012-34557 and by the Generalitat de Catalunya under contract 2009-SGR-980.


Kamal Hakimzadeh

Hooman Peiro Sajjad

Jim Dowling
email: jdowling@kth.se

Scaling HDFS with a Strongly Consistent Relational Model for Metadata

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Distributed le systems, such as the Hadoop Distributed File System (HDFS), have enabled the open-source Big Data revolution, by providing a highly available (HA) storage service that enables petabytes of data to be stored on commodity hardware, at relatively low cost [START_REF] Borthakur | The Hadoop Distributed File System: Architecture and Design[END_REF]. HDFS' architecture is based on earlier work on the Google Distributed File System (GFS) [START_REF] Ghemawat | The Google File System[END_REF] that decoupled metadata, stored on a single node, from block data, stored across potentially thousands of nodes. In HDFS, metadata is kept in-memory on a single NameNode server, and a system-level lock is used to implement a multiple-reader, single writer concurrency model. That is, HDFS ensures the consistency of metadata by only allowing a single client at a time to mutate its metadata. The metadata must t on the heap of a single Java virtual machine (JVM) [START_REF] Lindholm | The Java Virtual Machine Specication[END_REF] running on the NameNode.

The current implementation of HDFS does, however, support highly available metadata through an eventually consistent replication protocol, based on the Active/Standby replication pattern, but limited to having a single standby node. All read and write requests are handled by the Active node, as reads at the Standby node could return stale data. The replication protocol is based on the Active node making quorum-based updates to a recovery log, called the edit log, persistently stored on a set of journal nodes. The Standby node periodically pulls updates to the edit log and applies it to its in-memory copy of the metadata. The quorum-based replication protocol requires at least three journal nodes for high availability. Failover from the Active to the Standby can, however, take several tens of seconds, as the Standby rst has to apply the set of outstanding edit log entries and all nodes need to reach agreement on who the current Active node is. They solve the latter problem by using a Zookeeper coordination service that also needs to run on at least three nodes to provide a high availability [START_REF] Hunt | ZooKeeper: Wait-free Coordination for Internet-scale Systems[END_REF].

The challenge we address in this paper is how to migrate HDFS' metadata from highly optimized data structures stored in memory to a distributed relational database. Using a relational database to store le system metadata is not a novel idea. WinFs [START_REF] Novik | Peer-to-Peer Replication in WinFS[END_REF], a core part of the failed Windows Longhorn, was supposed to use Microsoft SQL Server to store its le system metadata, but the idea was abandoned due to poor performance. However, with the advent of New SQL systems [START_REF] Stonebraker | New Opportunities for New SQL[END_REF], we believe this is an idea whose time has now come. Recent performance improvements for distributed in-memory databases make it now feasible. Version 7.2 of MySQL Cluster, an open-source new SQL database by Oracle, supports up to 17.6 million transactional 100-byte reads/second on 8 nodes using commodity hardware over an inniband interconnect [START_REF] Stonebraker | New Opportunities for New SQL[END_REF]. In addition to this, recent work on using relational databases to store le system metadata has shown that relational databases can outperform traditional inode data structures when querying metadata [START_REF] Haryadi S Gunawi | SQCK: A Declarative File System Checker[END_REF].

Our implementation of HDFS replaces the Active-Standby and eventually consistent replication scheme for metadata with a transactional shared memory abstraction. Our prototype is implemented using MySQL Cluster [START_REF] Ronström | Recovery Principles of MySQL Cluster 5.1[END_REF]. In our model, the size of HDFS' metadata is no longer limited to the amount of memory that can be managed on the JVM of a single node [START_REF] Lindholm | The Java Virtual Machine Specication[END_REF], as metadata can now be partitioned across up to 48 nodes. By applying ne-grained pessimistic locking, our solution allows multiple compatible write operations [START_REF] Putzolu | Granularity of Locks and Degrees of Consistency in a Shared Database[END_REF] to progress simultaneously. Even though our prototype is built using MySQL Cluster, our solution can be generalized to support any transactional data store that either supports transactions with at least read-committed isolation level and row-level locking. Our concurrency model also requires implicit locking, and is motivated by Jim Gray's early work on hierarchical locking [START_REF] Putzolu | Granularity of Locks and Degrees of Consistency in a Shared Database[END_REF]. We model all HDFS metadata objects as a directed acyclic graph of resources and then with a row-level locking mechanism we dene the compatibility of metadata operations so as to isolate transactions for the fewest possible resources allowing a maximum number of concurrent operations on metadata. We show how serializable transactions are required to ensure the strong consistency of HDFS' metadata, by showing how anomalies that can arise in transaction isolation levels lower than serializable [START_REF] Berenson | A Critique of ANSI SQL Isolation Levels[END_REF] can produce inconsistencies in HDFS metadata operations. As our solution produces a high level of load on the database, we also introduce a snapshot layer (per-transaction cache) to reduce the number of roundtrips to the database.

HDFS Background and Concurrency Semantics

Distributed le systems have typically attempted to provide lesystem semantics that are as close as possible to the POSIX strong model of consistency [START_REF] Valerio | Evaluating the Price of Consistency in Distributed File Storage Services[END_REF]. However, for some operations, HDFS provides a consistency level weaker than POSIX. For example, because of the requirement to be able to process large les that are still being written, clients can read les that are opened for writing. In addition, les can be appended to, but existing blocks cannot be modied. At the le block level, HDFS can be considered to have sequential consistency semantics for read and write operations [START_REF] Valerio | Evaluating the Price of Consistency in Distributed File Storage Services[END_REF], since after a client has successfully written a block, it may not be immediately visible to other clients. However, when a le has been closed successfully, it becomes immediately visible to other clients, that is, HDFS supports linearizability [START_REF] Herlihy | Linearizability: A Correctness Condition for Concurrent Objects[END_REF] at the le read and write level.

Metadata in HDFS. Similar to POSIX le systems, HDFS represents both directories and les as inodes (INode) in metadata. Directory inodes contain a list of le inodes, and les inodes are made up a number of blocks, stored in a BlockInfo object. A block, in its turn, is replicated on a number of dierent data nodes in the system (default 3). Each replica is a Replica object in metadata. As blocks in HDFS are large, typically 64-512 MB in size, and stored on remote DataNodes, metadata is used to keep track of the state of blocks. A block being written is a PendingBlock, while a block can be under-replicated if a DataNode fails (UnderReplicatedBlock) or over-replicated (ExcessReplica) if that DataNode recovers after the block has been re-replicated. Blocks can also be in an InvalidatedBlock state. Similarly, replicas (of blocks) can be in Repli-caUnderConstruction and CorruptedReplica states. Finally, a Lease is a mutual grant for a number of les being mutated by a single client while LeasePath is an exclusive lock regarding a single le and a single client.

Tying together the NameNode and DataNodes. Filesystem operations in HDFS, such as le open/close/read/write/append, are blocking operations that are implemented internally as a sequence of metadata operations and block operations orchestrated by the client. First, the client queries or mutates metadata at the NameNode, then blocks are queried or mutated at DataNodes, and this process may repeat until the lesystem operation returns control to the client. The consistency of lesystem operations is maintained across metadata and block operations using leases stored in the NameNode. If there is a failure at the client and the client doesn't recover, any leases held by the client will eventually expire and their resources will be freed. If there is a failure in the NameNode or a DataNode during a lesystem operation, the client may be able to retry the operation to make progress or if it cannot make progress it will try to release the leases and return an error (the NameNode needs to be contactable to release leases). HDFS' Single-Writer Concurrency Model for Metadata Operations. The NameNode is the bottleneck preventing increased write scalability for HDFS applications [START_REF] Shvachko | HDFS Scalability: The limits to growth[END_REF], and this bottleneck is the result of its multiple-reader, singlewriter concurrency model [START_REF] Wang | Hadoop High Availability Through Metadata Replication[END_REF]. Firstly, metadata is not partitioned across nodes. Secondly, within the NameNode, a global read/write lock (FSNamesystem locka Java language ReentrantReadWriteLock) protects the namespace by grouping the NameNode's operations into read or write operations. The NameNode uses optimized data structures like multi-dimensional linked-lists for accessing blocks, replicas and DataNode information on which it is almost impossible to use negrained concurrency control techniques. The data structures are tightly coupled, and generally not indexed as memory access is fast and indexing would increase metadata storage requirements.

As the FSNamesystem lock is only acquired while updating metadata in memory, the lock is only held for a short duration. However, write operations also incur at least one network round-trip as they have to be persisted at a quorum of journal nodes. If writes were to hold FSNamesystem lock while waiting for the network round-trip to complete, it would introduce intolerable lock contention. So, writes release the FSNamesystem lock after applying updates in memory, while waiting for the updates to be persisted to the journal nodes. In addition to this, to improve network throughput to the journal nodes, writes are sent in batches [START_REF] Lipcon | Quorum-Journal Design[END_REF] to journal nodes. When batched writes return, the thread waiting for the write operation returns to the client. However, thread scheduling anomalies at the NameNode can result in writes returning out-of-order, thus violating linearizability of metadata. As threads don't hold the FSNamesystem lock while waiting for edits to complete, it is even possible that thread scheduling anomalies could break sequential consistency semantics by returning a client's writes out-of-order. However, metadata operations also acquire leases while holding the FSNamesystem lock, thus making individual lesystem operations linearizable.

Problem Denition

We are addressing the problem of how to migrate HDFS' metadata to a relational model, while maintaining consistency semantics at least as strong as HDFS' Na-meNode currently provides. We assume that the database supporting the relational model provides support for transactions. While metadata consistency could be ensured by requiring that transactions' execute at a serializable isolation level, distributed relational databases typically demonstrate poor throughput when serializing all updates across partitions [START_REF] Thomson | Calvin: Fast Distributed Transactions for Partitioned Database Systems[END_REF]. In HDFS, lesystem operations typically traverse the root directory, and the root inode is, therefore, a record that is frequently involved in many dierent transactions. As the root directory can only be located on one partition in a distributed database, transactions that take a lock on the root (and other popular directories) will frequently cross partitions. Thus, the root directory and popular directories become a synchronization bottleneck for transactions. A challenge is safely removing them from transactions' contention footprint, without having to give up on strong consistency for metadata. If we are to implement a consistency model at least as strong consistency as that provided for HDFS' metadata, we need transactions, and they need to support at least read-committed isolation level and row-level locks, so that we can implement stronger isolation levels when needed.

Another challenge we have is that, in the original HDFS, metadata operations, each executed in their own thread, do not read and write metadata objects in the same order. Some operations may rst access blocks and then inodes, while other operations rst access inodes and then blocks. If we encapsulate metadata operations in transactions, locking resources as we access them, cycles will be introduced resulting in deadlocks. Another problem, that is also an artifact of HDFS's NameNode design, is that many operations read objects rst, and then update them later within the same metadata operation. When these operations are naively implemented as transactions, deadlock occurs due to transactions upgrading read locks to exclusive locks.

Finally, as we are moving the metadata to remote hosts, an excessive number of roundtrips from a NameNode to the database increases the latency of lesystem operation latencies and reduces throughput. Although we cannot completely avoid network roundtrips, we should avoid redundant fetching of the same metadata object during the execution of a transaction.

Hierarchical Concurrency Model

The goal of our concurrency model is to support as a high a degree of concurrent access to HDFS' metadata as possible, while preserving freedom from deadlock and livelock. Our solution is based on modelling the lesystem hierarchy as a directed acyclic graph (DAG), and metadata operations that mutate the DAG are in a single transaction or that either commits or, in the event of partial failures in the distributed database, aborts. Aborted operations are transparently retried at NameNodes unless the error is not recoverable. Transactions pessimistically acquire locks on directory/le subtrees and le/block/replica subtrees, and these locks may be either explicit or implicit depending on the metadata operation. Explicit locking requires a transaction to take locks on all resources in the subtree. Implicit locking, on the other hand, only requires a transaction to take one explicit lock on the root of a subtree and it then implicitly acquires locks on all descendants in the subtree. There is a trade-o between overhead of taking too many locks with explicit locking over lower level of concurrency with implicit locking [START_REF] Putzolu | Granularity of Locks and Degrees of Consistency in a Shared Database[END_REF]. However, metadata operations not sharing any subtrees can be safely executed concurrently.

Building a DAG of Metadata Operations

After careful analysis of all metadata operations in the NameNode, we have classied them into three dierent categories based on the primary metadata object used to start the operation:

1. path operations, 2. block operations, 3. lease operations.

The majority of HDFS' metadata operations are path operations that take an absolute lesystem path to either a le or directory as their primary parameter. Path operations typically lock one or more inodes, and often lock block objects, lease paths and lease objects. Block operations, on the other hand, take a block identier as their primary parameter and contain no inode information. An example block operation is AddBlock : when a block has been successfully added to a DataNode, the DataNode acknowledges that the block has been added to the NameNode that then updates the block's inode. Blocks are unique to inodes, as HDFS does not support block sharing between les. Lease operations also provide a lesystem path, but it is just a subpath that is used to nd all the lease-paths for the les containing that subpath. In gure 1a, we can see how block and lease operations can mutate inodes, introducing cycles into the metadata hierarchy and, thus, deadlock.

Our solution to this problem, in gure (1b), is to break up both block operations and lease operations into two phases. In the rst phase, we start a transaction that executes only read operations, resolving the inodes used by the operations at a read committed isolation level. This transaction does not introduce deadlock. In the second phase, we start a new transaction that acquires locks in a total order, starting from the root directory. This second transaction needs to validate data acquired in the rst phase (such as inode id(s)). Now path, block and lease operations all start acquiring locks starting from the root inode.

We need to ensure that metadata operations do not take locks on inodes in a conicting order. For example, if a metadata operation operation(x, y) that take two inodes as parameters always takes a lock on the rst inode x then on the second inode y, then the concurrent execution of operation(a, b) and operation(b, a) can cause deadlock. The solution to this problem is to dene a total ordering on inodes, a total order rule, and ensure all transactions acquire locks on inodes using this global ordering. The total order follows the traversal of the le system hierarchy that depth-rst search would follow, traversing rst towards the leftmost child and terminating at the rightmost child. The rst inode is the root inode, followed by directory inodes until the leftmost child is reached, then all nodes in that directory, then going up and down the hierarchy until the last inode is reached.

More formally, we use the hierarchy of the le system to map inodes to a partially ordered set of IDs. A transaction that already holds a lock for an inode with ID m can only request a lock on an inode with ID n if n > m. This mechanism also implements implicit locking, as directory inodes always have a lower ID than all inodes in its subtree.

Our total ordering is impossible for range queries (with or without indexes), because not all databases support ordered queries. We x this issue by also taking implicit locks in such cases. As paths are parsed in a consistent order from the root to leaf inodes in the path, when we take an exclusive lock on a directory inode, we implicitly lock its subtree. This prevents concurrent access to the subtree, and thus reduces parallelism, but solves our problem. Fortunately, typical operations, such as getting blocks for a le and writing to a le do not require implicit locks at the directory level. However, we do take implicit locks at the le inode level, so when a node is writing to a le, by locking the inode, we implicitly lock all block and replica objects within that le.

Preventing Lock Upgrades

A naive implementation of our relational model would translate read and write operations on metadata in the existing NameNode to read and write operations directly on the database. However, assuming each metadata operation is encapsulated inside a single transaction, such an approach results in locks being upgraded, potentially causing deadlock. Our solution is to only acquire a lock once on each data item within a metadata operation, and we take the lock with the highest strength lock that will be required for the duration of that transaction.

Snapshotting

As we only want to acquire locks once for each data item, and we are assuming an architecture where the NameNode accesses a distributed database, it makes no sense for the NameNode to read or write the same data item more than once from the database within the context of a single transaction. For any given transaction, data items can be cached and mutated at a NameNode and only updated in the database when the transaction commits. We introduce a snapshotting mechanism for transactions that, at the beginning of each transaction, reads all the resources a transaction will need, taking locks at the highest strength that will be required. On transaction commit or abort, the resources are freed. This solution enables NameNodes to perform operations on the per-transaction cache (or snapshot) of the database state during the transaction, thus reducing the number of roundtrips required to the database. Note, this technique is not implementing snapshot isolation [START_REF] Berenson | A Critique of ANSI SQL Isolation Levels[END_REF], we actually support serializable transactions.

Algorithm 1 Snapshotting taking locks in a total order. An outline of our concurrency model for transactions, including total order locks and snapshotting, is given in algorithm 1.

Correctness Discussion

In our solution, transactions are serializable, meaning that transactions are sortable in the history of operations. Therefore, it is always true that at any moment in time, all readers get the nal and unique view of the mutated data which is strongly consistent. We ensure that transactions that contain both a read and a modify lesystem operation for the same shared metadata object should be serialized based on the serialization rule:

∀ (w i , w j ) if X wi ∩ X wj = / O then transactions of (w i , w j ) must be serialized;

∀ (r i , w j ) if X ri ∩ X wj = /
O then transactions of (r i , w j )must be serialized. First, we use the hierarchy of the le system to dene a partial ordering over inodes. Transactions follow this partial ordering when taking locks, ensuring that the circular wait condition for deadlock never holds. Similarly, the partial ordering ensures that if a transaction takes an exclusive lock on a directory inode, subsequent transactions will be prevented from accessing the directory's subtree until the lock on the directory's lock is released. Implicit locks are required for operations such as creating les, where concurrent metadata operations could return success even though only one of them actually succeeded. For operations such as deleting a directory, explicit locks on all child nodes are required.

To show that our solution is serializable, we use an anomalies-based denition of isolation levels, and then we justify why none of these anomalies happen in our solution [START_REF] Berenson | A Critique of ANSI SQL Isolation Levels[END_REF]. The list of anomalies that can arise in transactions are namely Dirty Write, Dirty Read, Fuzzy Read, Lost Update, Read Skew, Write Skew, and Phantom Reads [START_REF] Berenson | A Critique of ANSI SQL Isolation Levels[END_REF]. Assuming well-formed locking [START_REF] Berenson | A Critique of ANSI SQL Isolation Levels[END_REF], that is, we have no bugs in our locking code, then the system guarantees that it is never possible that two concurrent transactions could mutate the same data item. This prevents Dirty Reads and Write, as well as Fuzzy Reads and Read Skew . Similarly, Lost Updates only occur if we do not have well-formed locking. Similarly, Write Skew is impossible, as a reader and writer transactions require concurrent access to the same data item. Likewise for a single data item, predicates are also taken into account in our solution in the form of implicit locks. All predicates are also locked even if the metadata operation does not intend to change them directly, thus making Phantom Reads impossible. Finally, we only execute index scans when we have an implicit lock preventing the insertion of new rows that could be returned by that index scan. This means that, for example, when listing les in a directory we take an implicit lock on the directory so that no new les can be inserted in the directory while the implicit lock is held. Similarly, list all blocks for an inode only happens when we have an implicit lock on the inode.

Experiments

We used MySQL Cluster as the distributed relational database for metadata. In experiments the MySQL Cluster nodes and the NameNode run on machines each with 2 AMD 6 core CPUs (2.5 GHz clock speed, 512 KB cache size) connected with 1 GB Ethernet. The versions of our software were: MySQL Cluster 7.2.8, Java virtual machine 1.6 and ClusterJ 7.1.15a as the connector.

Capacity

Based on Shvachko in [START_REF] Shvachko | HDFS Scalability: The limits to growth[END_REF], HDFS les on average contain 1.5 blocks and, assuming a replication factor of 3, then 600 bytes of memory is required per le. Due to garbage collection eects, the upper limit on the size of the JVM heap for the NameNode is around 60GB, enabling the NameNode to store roughly 100 million les [START_REF] Shvachko | HDFS Scalability: The limits to growth[END_REF]. Existing clusters at Facebook have larger block sizes, up to 1 GB, and carefully congure and manage the JVM to scale the heap up to 100 GB, leading to larger clusters but not to signicantly more les. For our NameNode, we estimate the amount of metadata consumed per le by taking into account that each INode, BlockInfo and Replica row in database require 148, 64 and 20 bytes, respectively. Per le, our system creates 1 INode, 2 BlockInfo and 6 Replica rows, which is 396 bytes. MySQL Cluster supports up to 48 data-nodes and, in practice, each node can have up to 256GB of memory for storage. So in principle, a MySQL Cluster implementation can scale up to 12 TB in size, although the largest cluster we are aware of is only 4 TBs. If we conservatively assume that MySQL Cluster can support up to 3.072 TB for metadata, then with a replication factor of 2 for the metadata in MySQL cluster, our le system can store up to 4.1 billion les. This is a factor of 40 increase over Shvachko's estimate for HDFS from 2010. Fig. 2: Impact of snapshotting on database roundtrips ber of roundtrips to the database and consequently the overall latency for the metadata operation. We wrote an experiment to analyze a number of popular metadata operations, counting the number of roundtrips to the database that our Transaction Cache saves for each metadata operation. GET_BLK_LOC is a metadata operation that returns the addresses of the DataNodes storing a replica of a given block. MKDIR creates directories recursively. START_FILE creates INodes for all the non-existent inodes, writes the owner of the lease and creates a new lease-path entry. COMPLETE, sent by the client after having successfully written the last block of a le, removes all the under-constructionreplicas and marks the corresponding BlockInfo as complete. ADD_BLOCK adds a new BlockInfo and returns a list containing the location for its replicas.

As can be seen in gure 2, GET_BLK_LOC, START_FILE, and COMPLETE reduce the number of roundtrips to the database by 60%, 40% and 50%.

Row-level Lock in MySQL Cluster

To demonstrate the feasibility of our approach on a real database, we present a micro-benchmark on the performance of row-level locking in MySQL Cluster. In this setup, MySQL Cluster has 4 DataNodes, each running on a dierent host.

In this experiment, we vary the number of threads and the lock type taken, while we measure the total time for threads to read a set of rows of data in a pre-existing namespace. This experiment simulates the cost of a taking a lock on a parent directory and then reading the rows required to read in a le (inode, blocks, and replicas).

In the namespace structure in gure 3a, the root and a parent directory are shared between all threads while each thread is assigned just one le to read. All threads read the root directory without a lock (at read committed isolation level), but they each acquire a dierent type of lock on the parent directory. Threads that take write locks on the parent directory must be executed serially, while threads that take either a shared lock (read lock) or no lock can execute in parallel.

The results for 10,000 transactions are shown in the gure 3b. As the number of threads is increased, the time to perform 10,000 transactions decreases almost linearly for reading with shared lock until about 30 threads are run in parallel, then the time taken levels out, nally increasing slightly, starting from 50+ threads. We believe this increase is because of the extra overhead of acquiring/releasing locks at the data nodes in MySQL Cluster. For transactions that do not take any locks, the time taken decreases continually up to the 60 threads used in our experiments. However, for the write lock, we can see that the total time is halved for more than one thread but it doesn't decrease after that. This is because only one thread can acquire the write lock on the parent at a time, and the threads must wait until the lock is released before they can read the data.

System-level vs Row-level Locking

In order to compare the performance of Apache HDFS' NameNode using a system-level lock (FSNamesystem lock ) with our NameNode that uses row-level locks, we implemented a NameNode benchmark as an extension of NNThrough-putBenchmark [START_REF] Shvachko | HDFS Scalability: The limits to growth[END_REF]. In this benchmark, we measure the throughput of open and create operations on two dierent locking mechanisms with a constant 64 number of threads while increasing the number of directories (decreasing number of les per directory). The number of concurrent threads on each parent directory is a function of the number of directories. The modication we made to the NNThroughputBenchmark is that we allocated one directory per thread. The result of a create operation for 16384 (2 14 ) les is depicted in gure 4a. As the diagram shows, the throughput for creating les under a single directory is the same for both the system-level lock in Apache's HDFS and our row-level lock. This is because all 64 threads try to acquire a write lock on the same directory in the NameNode. The advantage of row-level locking is seen when we increase the number of directories. Increasing the number of directories, we see that the throughput of our NameNode with row-level locking increases while for Apache's NameNode using a system-level lock, the throughput remains almost For the open operation in gure 4b, row-level locking and system-level locking perform almost the same, since both row-level and system-level locks allow multiple read locks to be acquired simultaneously.

Related Work

Microsoft's WinFs [START_REF] Novik | Peer-to-Peer Replication in WinFS[END_REF] is an early attempt at building a distributed lesystem for a networked desktop environment with the goal of centrally managing updates to the distributed lesystem's metadata in a relational database. The database supported ecient searching and ltering of metadata. However, in contrast to our model clients mutated local copies of the lesystem and then used peerto-peer synchronization with conict resolution, resulting in a model where the metadata was eventually consistent. HDFS v1 [START_REF] Borthakur | The Hadoop Distributed File System: Architecture and Design[END_REF] follows the single metadata server model. Google's GFS [START_REF] Ghemawat | The Google File System[END_REF], HDFS v2 [START_REF] Wang | Hadoop High Availability Through Metadata Replication[END_REF] and TidyFs [START_REF] Fetterly | TidyFS: A Simple and Small Distributed File System[END_REF] have a highly available master/slave replication model for metadata, while Ceph [START_REF] Sage | Ceph: A Scalable, High-Performance Distributed File System[END_REF] and Lustre [START_REF] Schwan | Lustre: Building a File System for 1000-node Clusters[END_REF] partition metadata across distributed metadata servers. However, in contrast to HDFS, Ceph and Lustre are object-based le systems, somewhat simplifying the partitioning of metadata. Google's successor to GFS, Collosus, also partitions metadata across many machines, but the mechanisms of how they maintain consistency across partitions are not public knowledge [START_REF] Kirk | GFS: Evolution on Fast-forward[END_REF]. Similarly, MapR has built a new proprietary version of HDFS with partitioned metadata, although MapR have stated at the Hadoop Summit 2011 that the metadata is not replicated using a strongly consistent replication protocol. GFS's replication scheme is based on batching operation log updates to the local disk of the primary server and replicating them to a remote server to handle failures by reconstructing state of the le system. TidyFs [START_REF] Fetterly | TidyFS: A Simple and Small Distributed File System[END_REF] supports at URLbased les and replicates metadata using Paxos [START_REF] Lamport | The Part-Time Parliament[END_REF]. In Ceph [START_REF] Sage | Ceph: A Scalable, High-Performance Distributed File System[END_REF], the main data structure is the Directory that stores information about its child inodes. By using a two phase commit algorithm, Ceph dynamically partitions the namespace tree and evenly distributes it over a cluster of metadata servers (MDS). Lustre's general object model stores both metadata and block data in a cluster of Object Storage Devices (OSD) [START_REF] Schwan | Lustre: Building a File System for 1000-node Clusters[END_REF], so for replication Lustre relies on the promises of the underlying OSD cluster, while its Distributed Lock Manager (DLM) library assures the consistency of the le system.

It is also worth mentioning that our approach is similar to multi-version concurrency control (MVCC), in that we take a copy of the data items, however, in contrast to MVCC, we only work on a single copy of the data items and we take pessimistic locks.

Conclusion and Future Work

In this paper, we introduced a new relational model for HDFS' metadata. We also showed how to migrate metadata from highly performant and in-memory data structures in Apache's HDFS to a relational representation that guarantees strong consistency for metadata. In particular, we demonstrated that how metadata operations could be made serializable and deadlock-free using pessimisticlocking concurrency control, requiring only locking and transactions that support a read-committed isolation level. The mechanisms we introduced to ensure freedom from deadlock were the representation of a logical DAG for the metadata, specifying a global order for acquiring locks on metadata objects, preventing lock upgrades, and using of implicit locks to lock subtrees. We showed that the performance of the database underlying our system is competitive, and that our NameNode architecture can potentially scale to store 40 times more metadata than Apache's NameNode.

In future work, we will extend our system to support a multiple NameNode architecture. Certain cluster-wide NameNode tasks, such as replication management, should only be executed by a single NameNode at a time. We are also working on optimizing our schemas for representing inodes, blocks, and replicas to reduce their footprint, and to support distribution aware transactions -we want to reduce the number of partitions that transactions for common operations must cross to help improve throughput.

  HDFS' Directed Graph has cycles.

  Fig. 1: Access graph of HDFS metadata

6. 2

 2 Snapshots reduce the Number of Roundtrips to the Database Our snapshotting layer, or Transaction Cache, caches data items retrieved from the database in the local memory of the NameNode. This minimizes the num-

Fig. 3 :

 3 Fig. 3: Inuence of locking on MySQL Cluster throughput

Fig. 4 :

 4 Fig.4: Impact of the row-level lock on throughput constant. For the open operation in gure 4b, row-level locking and system-level locking perform almost the same, since both row-level and system-level locks allow multiple read locks to be acquired simultaneously.