Patent ID: 8086820
Filing Date: 2011-12-27
Classification: G06F

Abstract:
1. An apparatus that in response to a pending input/output (I/O) operation queries a storage space for an existence of a selected copy grain of a predefined size containing previously stored data corresponding to the I/O operation, comprising a data structure stored in a computer readable memory having first and second portions, the first portion virtually mapping at least some of a predefined portion of the storage space in terms of a plurality of non-sequential entries indexing storage units that each include a plurality of copy grains, and the second portion having a plurality of entries that are indexed in relation to a value derived from an address associated with the I/O operation to locate the selected copy grain in the first portion, at least one entry of the second portion pointing to a skip list and, at least one other entry of the second portion pointing to a flat map data array, the skip list and the flap map data array each operably defining a pointer identifying a selected one of the non-sequential entries of the first portion and an offset value identifying the selected copy grain of the storage unit associated with the selected one of the non-sequential entries, and at least one other entry of the second portion operably pointing to a selected one of the non-sequential entries of the first portion directly.