  Understanding the performance of data-parallel workloads when
resource-constrained has significant practical importance but unfortunately has
received only limited attention. This paper identifies, quantifies and
demonstrates memory elasticity, an intrinsic property of data-parallel tasks.
Memory elasticity allows tasks to run with significantly less memory that they
would ideally want while only paying a moderate performance penalty. For
example, we find that given as little as 10% of ideal memory, PageRank and
NutchIndexing Hadoop reducers become only 1.2x/1.75x and 1.08x slower. We show
that memory elasticity is prevalent in the Hadoop, Spark, Tez and Flink
frameworks. We also show that memory elasticity is predictable in nature by
building simple models for Hadoop and extending them to Tez and Spark.
  To demonstrate the potential benefits of leveraging memory elasticity, this
paper further explores its application to cluster scheduling. In this setting,
we observe that the resource vs. time trade-off enabled by memory elasticity
becomes a task queuing time vs task runtime trade-off. Tasks may complete
faster when scheduled with less memory because their waiting time is reduced.
We show that a scheduler can turn this task-level trade-off into improved job
completion time and cluster-wide memory utilization. We have integrated memory
elasticity into Apache YARN. We show gains of up to 60% in average job
completion time on a 50-node Hadoop cluster. Extensive simulations show similar
improvements over a large number of scenarios.
