Various embodiments of the invention relate to an apparatus and method for efficiently implementing out-of-order servicing of read requests originating from an input/output (I/O) interface with minimal additional storage. For example, a number of read entries may be generated from data read requests stored in a first-in-first-out in a first order. The read entries are stored in a storage device and each read entry identifies internal data reads to read data to service the data read request to which the read entry corresponds. A controller coupled to the storage structure may then submit the internal data reads a central arbiter to read data in a second order that is different than the first order. Moreover, the controller also allows the second order to include internal data reads from one read entry, before a completing servicing of another partially serviced read entry, thus providing “simultaneous” servicing of several read entries.