Technologies are described herein for adaptively controlling the size of a write cache in a storage device based on the time required to flush the cache. Upon receiving a write command at a controller for the storage device, an estimated cache flush time for the write cache is calculated based on the write commands contained therein. If the estimated cache flush time is greater than a maximum threshold time, the size of the write cache is decreased to control the cache flush time. If the estimated cache flush time is less than a minimum threshold time, the size of the write cache is increased to enhance random write performance.