Sawzall (programming language)

<h2 id="motivation">Motivation</h2>
<p>Google's server logs are stored as large collections of records (<a href="/facts/Protocol_Buffers/4Pj3zymo">Protocol Buffers</a>) that are partitioned over many disks within <a href="/facts/Google_File_System/mDeBYrAb">GFS</a>. In order to perform calculations involving the logs, engineers can write <a href="/facts/MapReduce/KbfxJ5vV">MapReduce</a> programs in C++ or Java. MapReduce programs need to be compiled and may be more verbose than necessary, so writing a program to analyze the logs can be time-consuming. To make it easier to write quick scripts, <a href="/facts/Rob_Pike/K5R9UoSH">Rob Pike</a> et al. developed the Sawzall language. A Sawzall script runs within the Map phase of a MapReduce and "emits" values to tables. Then the Reduce phase (which the script writer does not have to be concerned about) aggregates the tables from multiple runs into a single set of tables.
</p><p>Currently, only the language runtime (which runs a Sawzall script once over a single input) has been open-sourced; the supporting program built on MapReduce has not been released.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="features">Features</h2>
<p>Some interesting features include:
</p>
<ul><li>A Sawzall script has a single input (a log record) and can output only by emitting to tables. The script can have no other side-effects.</li>
<li>A script can define any number of output tables. Table types include:
<ul><li>collection saves every value emitted</li>
<li>sum saves the sum of every emitted value</li>
<li>maximum(n) saves only the highest n values on a given weight.</li></ul></li>
<li>In addition, there are several statistical table types that give inexact results. The higher the parameter n, the more accurate the estimates are.
<ul><li>sample(n) gives a random sample of n values from all the emitted values</li>
<li>quantile(n) calculates a cumulative probability distribution of the given numbers.</li>
<li>top(n) gives n values that are probably the most frequent of the emitted values.</li>
<li>unique(n) estimates the number of unique values emitted.</li></ul></li></ul>
<p>Sawzall's design favors efficiency and engine simplicity over power:
</p>
<ul><li>Sawzall is statically typed, and the engine compiles the script to <a href="/facts/X86/Kypq5fgu">x86</a> before running it.</li>
<li>Sawzall supports the <a href="/facts/Compound_data_type/RBBfE1FY">compound data types</a> lists, maps, and structs. However, there are no references or pointers. All assignments and function arguments create copies. This means that <a href="/facts/Recursive_data_structure/fzBvEl6A">recursive data structures</a> and cycles are impossible.</li>
<li>Like C, functions can modify <a href="/facts/Global_variable/XWF9zC08">global variables</a> and <a href="/facts/Local_variable/q8sIjyhx">local variables</a> but are not closures.</li></ul>
<h2 id="sawzall-code">Sawzall code</h2>
<p>This complete Sawzall program will read the input and produce three results: the number of records, the sum of the values,
and the sum of the squares of the values.
</p>
count: table sum of int;
total: table sum of float;
sum_of_squares: table sum of float;
x: float = input;
emit count <- 1;
emit total <- x;
emit sum_of_squares <- x * x;

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Pig_(programming_tool)/y3JVRF1k">Pig</a> – similar tool and language for use with <a href="/facts/Apache_Hadoop/oUS1G2R7">Apache Hadoop</a></li>
<li><a href="/facts/Sawmill_(software)/gGFJrUrv">Sawmill (software)</a></li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>S. Ghemawat, H. Gobioff, S.-T. Leung, The Google file system, in: 19th ACM Symposium on Operating Systems Principles, Proceedings, 17 ACM Press, 2003, pp. 29–43.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://code.google.com/archive/p/szl/">Google Code Archive - Long-term storage for Google Code Project Hosting.</a></li>
<li><a href="https://web.archive.org/web/20110604204310/http://www.soe.ucsc.edu/classes/cmps253/Spring07/notes/mapreduce.pdf">MapReduce</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Rob Pike, Sean Dorward, Robert Griesemer, Sean Quinlan. Interpreting the Data: Parallel Analysis with Sawzall <a href="http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/sv//archive/sawzall-sciprog.pdf" target="_blank">http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/sv//archive/sawzall-sciprog.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Sawzall's open source project at Google Code. <a href="https://code.google.com/p/szl/" target="_blank">https://code.google.com/p/szl/</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Discussion on which parts of Sawzall are open-source. <a href="https://groups.google.com/group/szl-users/browse_thread/thread/c0d90423d0fc27bd" target="_blank">https://groups.google.com/group/szl-users/browse_thread/thread/c0d90423d0fc27bd</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>"Replacing Sawzall". 2015-12-04. Retrieved 2018-06-18. <a href="http://www.unofficialgoogledatascience.com/2015/12/replacing-sawzall-case-study-in-domain.html" target="_blank">http://www.unofficialgoogledatascience.com/2015/12/replacing-sawzall-case-study-in-domain.html</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Discussion on which parts of Sawzall are open-source. <a href="https://groups.google.com/group/szl-users/browse_thread/thread/c0d90423d0fc27bd" target="_blank">https://groups.google.com/group/szl-users/browse_thread/thread/c0d90423d0fc27bd</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Sawzall (programming language) open-in-new

Sawzall (programming language)