A computing system, comprising: a plurality of computing nodes, each of which comprises at least one processor (1410a, 1410n) and a memory; wherein one or more of the plurality of computing nodes is configured to implement a database service, and wherein the database service comprises a database engine head node; wherein two or more other ones of the plurality of computing nodes are configured to implement server nodes (430, 440, 450) of a distributed storage service that stores portions of database tables as respective data pages (433, 443, 453) on one or more storage devices; wherein the database engine head node is configured to: receive, from a client of the database service, a write request directed to a given data record in a database table, wherein the write request specifies a modification to be made to the given data record; generate a redo log record representing the modification to be made to the given data record; send the redo log record, but not a data page comprising the given data record, to a particular server node of the distributed storage service that stores a version of the data page comprising the given data record; wherein the particular server node of the distributed storage service is configured to: receive the redo log record from the database engine head node; write the redo log record to one or more storage devices; return, to the database engine head node, an acknowledgement that the redo log record was written; and subsequent to returning the acknowledgement: generate a current version of the data page comprising the given data record, wherein to generate the current version of the data page, the particular server node of the distributed storage service is configured to apply the received redo log record and one or more other redo log records representing modifications to the data page to a previously stored version of the data page; and write the current version of the data page to one or more storage devices. a plurality of computing nodes, each of which comprises at least one processor (1410a, 1410n) and a memory; wherein one or more of the plurality of computing nodes is configured to implement a database service, and wherein the database service comprises a database engine head node; wherein two or more other ones of the plurality of computing nodes are configured to implement server nodes (430, 440, 450) of a distributed storage service that stores portions of database tables as respective data pages (433, 443, 453) on one or more storage devices; wherein the database engine head node is configured to: receive, from a client of the database service, a write request directed to a given data record in a database table, wherein the write request specifies a modification to be made to the given data record; generate a redo log record representing the modification to be made to the given data record; send the redo log record, but not a data page comprising the given data record, to a particular server node of the distributed storage service that stores a version of the data page comprising the given data record; receive, from a client of the database service, a write request directed to a given data record in a database table, wherein the write request specifies a modification to be made to the given data record; generate a redo log record representing the modification to be made to the given data record; send the redo log record, but not a data page comprising the given data record, to a particular server node of the distributed storage service that stores a version of the data page comprising the given data record; wherein the particular server node of the distributed storage service is configured to: receive the redo log record from the database engine head node; write the redo log record to one or more storage devices; return, to the database engine head node, an acknowledgement that the redo log record was written; and subsequent to returning the acknowledgement: generate a current version of the data page comprising the given data record, wherein to generate the current version of the data page, the particular server node of the distributed storage service is configured to apply the received redo log record and one or more other redo log records representing modifications to the data page to a previously stored version of the data page; and write the current version of the data page to one or more storage devices. receive the redo log record from the database engine head node; write the redo log record to one or more storage devices; return, to the database engine head node, an acknowledgement that the redo log record was written; and subsequent to returning the acknowledgement: generate a current version of the data page comprising the given data record, wherein to generate the current version of the data page, the particular server node of the distributed storage service is configured to apply the received redo log record and one or more other redo log records representing modifications to the data page to a previously stored version of the data page; and write the current version of the data page to one or more storage devices. generate a current version of the data page comprising the given data record, wherein to generate the current version of the data page, the particular server node of the distributed storage service is configured to apply the received redo log record and one or more other redo log records representing modifications to the data page to a previously stored version of the data page; and write the current version of the data page to one or more storage devices.