Systems and methods are described herein for synthesizing traces from logs of a distributed computing system. A trace represents a single transaction, such as handling of a user request, on the distributed computing system. The transaction can include multiple underlying operations on the distributed computing system, which are represented as spans within the trace and may be hierarchically arranged within the trace. In instances where a distributed computing system does not provide for tracing natively, a trace can be synthesized from log entries of the distributed computing system. A streaming data processing system can ingest a data stream including log entries, and identify within the data stream those log entries relating to a given transaction. The streaming data processing system can further identify log entries that demark the beginnings and endings of operations for that transaction, and can utilize the identified log entries to build a trace for the transaction.