A service provider may apply customer-selected or customer-defined auto-scaling policies to a cluster of resources (e.g., virtualized computing resource instances or storage resource instances in a MapReduce cluster). Different policies may be applied to different subsets of cluster resources (e.g., different instance groups containing nodes of different types or having different roles). Each policy may define an expression to be evaluated during execution of a distributed application, a scaling action to take if the expression evaluates true, and an amount by which capacity should be increased or decreased. The expression may be dependent on metrics emitted by the application, cluster, or resource instances by default, metrics defined by the client and emitted by the application, or metrics created through aggregation. Metric collection, aggregation and rules evaluation may be performed by a separate service or by cluster components. An API may support auto-scaling policy definition.