A system, comprising: one or more computing devices configured to: receive, at a multi-tenant storage service configured to distribute file contents across a plurality of storage devices, a write request directed to a file, and wherein the write request indicates a write offset within the file and a write data payload; determine, based on an analysis of the write offset, the write data payload and existing metadata, that storage space is to be allocated to respond to the write request; select, based at least in part on the write offset within the file, a size of a particular stripe of storage space to be allocated for the file, wherein successive stripes of the file, corresponding to logical blocks, are mapped to a different extents at different storage devices at respective storage nodes, and wherein the size of the particular stripe is both the logical block size and the physical page size at the respective extent, and both increase as a function of the write offset within the file, such that the size of each subsequent stripe within the file is larger than a respective previous stripe within the file; identify, based at least in part on the size of the particular stripe, a storage subsystem node of the multi-tenant storage service at which at least one replica of the particular stripe is to be stored, wherein at least one replica of another stripe of the file is stored at a different storage subsystem node, and wherein the physical page size at the identified node matches the size of the particular stripe; allocate (3213, 3216) storage at the storage subsystem node for the particular stripe; and modify contents of the particular stripe in accordance with the write request; whereby the metadata is maintained at the multi-tenant storage service and stored across one or more of the plurality of storage devices as a metadata structure comprising a mapping of the different stripes of the file to physical pages of the different extents at the different storage devices of respective storage nodes and increases non-linearly with file size. receive, at a multi-tenant storage service configured to distribute file contents across a plurality of storage devices, a write request directed to a file, and wherein the write request indicates a write offset within the file and a write data payload; determine, based on an analysis of the write offset, the write data payload and existing metadata, that storage space is to be allocated to respond to the write request; select, based at least in part on the write offset within the file, a size of a particular stripe of storage space to be allocated for the file, wherein successive stripes of the file, corresponding to logical blocks, are mapped to a different extents at different storage devices at respective storage nodes, and wherein the size of the particular stripe is both the logical block size and the physical page size at the respective extent, and both increase as a function of the write offset within the file, such that the size of each subsequent stripe within the file is larger than a respective previous stripe within the file; identify, based at least in part on the size of the particular stripe, a storage subsystem node of the multi-tenant storage service at which at least one replica of the particular stripe is to be stored, wherein at least one replica of another stripe of the file is stored at a different storage subsystem node, and wherein the physical page size at the identified node matches the size of the particular stripe; allocate (3213, 3216) storage at the storage subsystem node for the particular stripe; and modify contents of the particular stripe in accordance with the write request; whereby the metadata is maintained at the multi-tenant storage service and stored across one or more of the plurality of storage devices as a metadata structure comprising a mapping of the different stripes of the file to physical pages of the different extents at the different storage devices of respective storage nodes and increases non-linearly with file size.