Techniques for generating, storing, and using service call graphs are provided. In one technique, trace data items generated by different services are correlated to generate a service call graph. Trace data indicates when certain services are called and their respective latencies as a result of a client request. A service call graph may reflect a single trace or multiple traces over a particular period of time. A service call graph may be analyzed to inform administrators of a web site how a web application and the services it relies on are performing. A service call graph may be used to determine whether there are sufficient resources to support a projected increase in traffic to a web application. A service call graph may be used to estimate a cost of a web application. Multiple service call graphs may be compared to determine one or more root causes of a performance problem.