L'ordinamento dipende da alcuni dettagli di implementazione e funzionalità aggiuntive nel runtime di Google. Vedi la sezione 4.2:
We guarantee that within a given partition, the intermediate
key/value pairs are processed in increasing key order. This ordering
guarantee makes it easy to generate a sorted output file per
partition, which is useful when the output file format needs to
support efficient random access lookups by key, or users of the output
find it convenient to have the data sorted.
Il sistema consente anche uno schema di partizionamento arbitrario (menzionato nella sezione 4.1). Il sistema di ordinamento utilizza questo schema:
The partitioning function uses the initial bytes of the key to
segregate it into one of R pieces.
Quindi, quando la funzione Reduce viene eseguita su ogni partizione, non ci sono modifiche ai dati, ma l'output è garantito nell'ordine corretto (presumibilmente non c'è nulla di speciale nell'implementazione di questo - è solo un semplice tipo locale di qualche tipo ).
Una volta che hai le partizioni ordinate, tutto ciò che devi fare è concatenarle nell'ordine dei byte iniziali che sono stati usati per creare le partizioni e hai un elenco completamente ordinato.
(Sto prendendo una "chiave di ordinamento" per essere un riassunto del valore che è stato progettato in modo tale che quando le chiavi sono ordinate i valori sono anche nell'ordine corretto, almeno in una approssimazione ragionevole. Semplicemente troncando il primo le lettere di una stringa sarebbero sufficienti per creare una chiave di ordinamento grezza)