The embodiments described herein provide a system and method for efficiently storing small, random modifications or changes to data on one or more storage devices, such as disks, of storage servers coupled to a host computer in a network environment. Illustratively, the data is stored in a region of a byte-addressable, persistent memory of the host computer and is replicated (i.e., copied) as changed data of the region on the disks at the granularity at which it was modified, e.g., at the byte-addressable granularity. To that end, each storage server employs a data structure (e.g., a Fibonacci array) that is configured to efficiently accumulate the small, random data changes into one or more large blocks of changed data for storage on the disks in a manner that realizes the streaming bandwidth of the disk.