A distributed database system may implement log-structured distributed storage using a single log sequence number space. A log for a data volume may be maintained in a log-structured distributed storage system. The log may be segmented across multiple protection groups according to a partitioning of user data for the data volume. Updates to the log may be assigned a log sequence number from a log sequence number space for the data volume. A protection group may be determined for an update according to which partition of user data space the update pertains. Metadata to be included with the log record may indicate a previous log sequence number of a log record maintained at the protection group. The log record may be sent to the protection group and identified as committed based on acknowledgments received from storage nodes implementing the protection group.