Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim(s) 1-4 and 6-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wang, US Patent 9,760,493, in view of McGlaughlin et al., US PGPub 2019/0303283, further in view of Jayasena, US PGPub 2021/0182262, further in view of Jung et al., US PGPub 2019/0196956.
With respect to claim 1, Wang teaches storage device comprising:
a nonvolatile memory (col. 3, lines 2-8, the flash cache); and
a controller configured to insert, into a hot list, a portion of a logical address received from a host, manage a hot hash table storing a position at which the logical address is inserted into the hot list (col. 4, lines 15-27, the hot queue comprising the hot list, the hot queue adding an entry with the LBA, then the hash table is updated with an entry including the LBA and a pointer to the location in the hot queue where the LBA is stored),
search the hot hash table for the position, at which the logical address is inserted into the hot list, by using the hot index, determine an attribute of data corresponding to the logical address based on the search result, and store attribute information indicating the attribute of the data (col. 4, lines 29-41, where the hash table is searched, and if the entry is in the hot queue, the reference bit associated with the storage location of hot queue in which the LBA is stored is set to 1, which is the attribute of the claim).
manage a candidate hash table, that stores at least one position at which at least one logical address is inserted into the candidate list (col. 3, lines 19-33, the ghost queue corresponds to the candidate list, the ghost queue storing LBAs recently evicted. Note that Wang uses one hash table for the hot hash table and the candidate hash table. This is addressed below).
Wang fails to teach that the hot list is a FIFO.
McGlaughlin teaches:
a hot list in a first-in first-out scheme (par. 38).
Wang teaches the use of one hash table for the hot list and candidate list, and therefore does not teaching managing a candidate hash table, separate from the hot hash table. McGlaughlin is also silent on this feature. Jayasena teaches:
use a hot hash function to obtain a hot index corresponding to the position (par. 51 and fig. 6, using the hash function for the frequently accessed bucket set to identify candidate buckets, and the value corresponding to the key)
manage a candidate hash table, separate from the hot hash table and with a candidate hash function different from the hot hash function (pars. 51-52 and fig. 6, using the hash function for the infrequently accessed bucket set to identify candidate buckets), and therefore the combination of Wang and Jayasena teaches to manage a candidate hash table, separate from the hot hash table and with a candidate hash function different from the hot hash function, that stores at least one position at which at least one logical address is inserted into a candidate list.
Wang, Mclaughlin, and Jayasena fail to teach the hot list is a double connection link structure. Jung teaches:
wherein the controller is further configured to store the logical address in the hot list in a double connection list structure in which nodes of the hot list are bidirectionally connected (par. 78, the double linked list 321 used to detect hot addresses. Par. 40 discloses that the hot addresses are logical addresses)
It would have been obvious to one of ordinary skill in the art, having the teachings of Wang and McGlaughlin before him before the earliest effective filing date, to modify the memory management device of Wang with the memory management device of McGlaughlin, as the hot list of McGlaughlin allows wear leveling, which mitigates neighbor disturbance in memory, as taught by McGlaughlin in par. 34. Further, it would have been obvious, also having the teachings of Jayasena before him before the earliest effective filing date, to modify the memory management device of Wang and McGlaughlin with the memory management device of Jayasena, as having separate frequently accessed and infrequently accessed bucket sets with respective hash functions provides performance optimization over the prior art of a large hash table with uniformly distributed data elements across buckets, as taught by Jayasena in pars. 4 and 60. Further, it would have been obvious, also having the teachings of Jung before him before the earliest effective filing date, to modify the memory management device of Wang, McGlaughlin and Jayasena with the memory management device of Jung, as the double linked hot list of Jung allows system resources may be used more efficiently while maintaining the hot address detection rate high enough, as taught by Jung in par. 206.
With respect to claim 2, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 1, wherein the controller is further configured to obtain the hot index by converting the logical address through the hot hash function, search for the position, at which the logical address is inserted into the hot list, in a region of the hot hash table corresponding to the hot index, and determine data corresponding to the logical address as hot data if the position, at which the logical address is inserted into the hot list, is retrieved (col. 4, lines 9-41, where the hash table is searched and retrieved from the hot queue).
With respect to claim 3, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 1, wherein the controller is further configured to, when the position, at which the logical address is inserted into the hot list, is retrieved, remove the logical address from the hot list and re-insert the logical address into the hot list (col. 5, lines 34-53 and fig. 7, where the location is in the hash table, and in the hot queue, and at step 726, the cached data location is updated at the hit location of the hot queue).
With respect to claim 4, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 3, wherein the controller is further configured to, when the position, at which the logical address is inserted into the hot list, is retrieved, obtain the hot index by converting the logical address through a hot hash function, remove a value stored in a region of the hot hash table corresponding to the hot index, and store a position, at which the logical address is re-inserted into the hot list, in the region of the hot hash table corresponding to the hot index list (col. 5, lines 34-53 and fig. 7, where the location is searched in the hash table to retrieve and index, the location is found in the hot queue, and at step 726, the cached data location is updated at the hit location of the hot queue).
With respect to claim 6, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 1, wherein the controller is further configured to, when the logical address is not retrieved from the hot list, search for a position, at which the logical address is inserted into the candidate list, in the candidate hash table by using the logical address, determine an attribute of data corresponding to the logical address, and store attribute information indicating the attribute of the data (col. 4, lines 29-55 and fig. 3, where if the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated).
With respect to claim 7, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 1, wherein the controller is further configured to obtain a candidate index by converting the logical address through the candidate hash function, search for the position, at which the logical address is inserted into the candidate list, in a region of the candidate hash table corresponding to the candidate index, determine the data corresponding to the logical address as warm data when the position, at which the logical address is inserted into the candidate list, is retrieved, and determine the data corresponding to the logical address as cold data when the position, at which the logical address is inserted into candidate list, is not retrieved (col. 4, lines 29-55 and fig. 3, where the hash table is searched, the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated).
With respect to claim 8, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 6, wherein the controller is further configured to, when the position, at which the logical address is inserted into the candidate list, is retrieved, remove the logical address from the candidate list, insert the logical address into the hot list, and change, to hot, the attribute of the data corresponding to the logical address (col. 4, lines 29-55 and fig. 3, where if the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated, with the hot queue storing the warm data, with an attribute indicating hot).
With respect to claim 9, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 8, wherein the controller is further configured to obtain a candidate index by converting the logical address through the candidate hash function, remove a value stored in a region of the candidate hash table corresponding to the candidate index, obtain the hot index by converting the logical address through the hot hash function, and store the position, at which the logical address is inserted into the hot list, in a region of the hot hash table corresponding to the hot index (col. 4, lines 29-55 and fig. 3, where the hash table is searched, the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated, with the index derived from the hash table).
With respect to claim 10, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 6, wherein the controller is further configured to, when the position, at which the logical address is inserted into the candidate list, is not retrieved, insert the logical address into the candidate list and change, to warm, the attribute of the data corresponding to the logical address (col. 4, lines 29-55 and fig. 3, where if the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated, with the hot queue storing the warm data, with an attribute indicating hot).
With respect to claim 11, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 10, wherein the controller is further configured to obtain a candidate index by converting the logical address through the candidate hash function and store the position, at which the logical address is inserted into the candidate list, in a region of the candidate hash table corresponding to the candidate index (col. 4, lines 29-55 and fig. 3, where if the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated).
With respect to claim 12, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 1, wherein the controller is further configured to store the logical address in the candidate list (col. 3, lines 19-33 and fig. 2, where the hash table is connected to both the hot queue and the ghost queue).
Jung teaches the candidate list is a double connection list structure in which nodes of the candidate list are bidirectionally connected (par. 78, the double linked list 321 is a double linked list, and would be substituted for the ghost queue of Wang)
With respect to claim 13, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the storage device of claim 1, wherein the controller is further configured to store the logical address in the candidate list in a first-in first-out scheme (col. 3, lines 63-66, the ghost queue is configured as first-in first-out buffer, which stores LBAs, as previously discussed).
With respect to claim 14, Wang teaches an operating method of a storage device comprising a nonvolatile memory and a controller, the operating method comprising:
receiving a logical address from a host under control of the controller (col. 3, lines 7-15, the LBA is received from the hypervisor);
searching a hot hash table for the hot index corresponding to a position, at which the logical address is inserted into a hot list, by using the hot index under control of the controller (col. 4, lines 29-41, where the hash table is searched);
determining an attribute of data corresponding to the logical address based on the search result under control of the controller; (col. 4, lines 29-41, where the hash table is searched, and if the entry is in the hot queue, the reference bit associated with the storage location of hot queue in which the LBA is stored is set to 1, which is the attribute of the claim).
searching, under control of the controller, a candidate hash table for a position, at which the logical address is inserted into a candidate list when the position, at which the logical address is inserted into the hot list, is not retrieved (col. 4, lines 29-55 and fig. 3, where the hash table is searched, the LBA is in the ghost queue. Note that Wang uses one hash table for the hot hash table and the candidate hash table. This is addressed below); and
storing attribute information indicating the attribute of the data under control of the controller (col. 4, lines 29-41, where the hash table is searched, and if the entry is in the hot queue, the reference bit associated with the storage location of hot queue in which the LBA is stored is set to 1, which is the attribute of the claim).
Wang fails to teach that the hot list is a FIFO.
McGlaughlin teaches a hot list in a first-in first-out scheme (par. 38).
Wang teaches the use of one hash table for the hot list and candidate list, and therefore does not teaching managing a candidate hash table, separate from the hot hash table. McGlaughlin is also silent on this feature. Jayasena teaches:
using a hot hash function to obtain a hot index (par. 51 and fig. 6, using the hash function for the frequently accessed bucket set to find candidate buckets, and find the value corresponding to the key)
searching, under control of the controller, a candidate hash table, separate from the hot hash table and with a candidate hash function different from the hot hash function (pars. 51-52 and fig. 6, using the hash function for the infrequently accessed bucket set to find candidate buckets), and therefore the combination of Wang and Jayasena teaches searching, under control of the controller, a candidate hash table, separate from the hot hash table and with a candidate hash function different from the hot hash function, for a position, at which the logical address is inserted into the hot list, is not retrieved.
Wang, Mclaughlin, and Jayasena fail to teach the hot list is a double connection link structure. Jung teaches:
wherein the hot list has a double connection list structure in which nodes of the hot list are bidirectionally connected (par. 78, the double linked list 321 used to detect hot addresses. Par. 40 discloses that the hot addresses are logical addresses)
It would have been obvious to one of ordinary skill in the art, having the teachings of Wang and McGlaughlin before him before the earliest effective filing date, to modify the memory management device of Wang with the memory management device of McGlaughlin, as the hot list of McGlaughlin allows wear leveling, which mitigates neighbor disturbance in memory, as taught by McGlaughlin in par. 34. Further, it would have been obvious, also having the teachings of Jayesena before him before the earliest effective filing date, to modify the memory management device of Wang and McGlaughlin with the memory management device of Jayasena, as having separate frequently accessed and infrequently accessed bucket sets with respective hash functions provides performance optimization over the prior art of a large hash table with uniformly distributed data elements across buckets, as taught by Jayasena in pars. 4 and 60. Further, it would have been obvious, also having the teachings of Jung before him before the earliest effective filing date, to modify the memory management device of Wang, McGlaughlin and Jayasena with the memory management device of Jung, as the double linked hot list of Jung allows system resources may be used more efficiently while maintaining the hot address detection rate high enough, as taught by Jung in par. 206.
With respect to claim 15, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the operating method of claim 14, wherein the determining the attribute of the data corresponding to the logical address comprises determining, under control of the controller, the data corresponding to the logical address as hot data if the position, at which the logical address is inserted into the hot list, is retrieved (col. 4, lines 9-41, where the hash table is searched and retrieved from the hot queue).
With respect to claim 16, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the operating method of claim 14, further comprising: removing, under control of the controller, the logical address from the hot list when the position, at which the logical address is inserted into the hot list, is retrieved; and re-inserting the logical address into the hot list under control of the controller (col. 4, lines 9-41, where the hash table is searched and retrieved from the hot queue).
With respect to claim 17, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the operating method of claim 14, wherein the determining the attribute of the data corresponding to the logical address comprises: determining, under control of the controller, the data corresponding to the logical address as warm data when a position, at which the logical address is inserted into the candidate list, is retrieved address; and determining, under control of the controller, the data corresponding to the logical address as cold data when the position, at which the logical address is inserted into the candidate list, is not retrieved (col. 4, lines 29-55 and fig. 3, where the hash table is searched, the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated).
With respect to claim 18, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the operating method of claim 17, further comprising: removing, under control of the controller, the logical address from the candidate list when the position, at which the logical address is inserted into the candidate list, is retrieved; inserting the logical address into the hot list under control of the controller; and changing, to hot, the attribute of the data corresponding to the logical address under control of the controller (col. 4, lines 29-55 and fig. 3, where if the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated, with the hot queue storing the warm data, with an attribute indicating hot).
With respect to claim 19, Wang, Mclaughlin, and Jayasena teach all limitations of the parent claim. Wang further teaches the operating method of claim 17, further comprising: inserting, under control of the controller, the logical address into the candidate list when the position, at which the logical address is inserted into the candidate list, is not retrieved; and changing, to warm, the attribute of the data corresponding to the logical address under control of the controller (col. 4, lines 29-55 and fig. 3, where if the LBA is in the ghost queue, and at step 330 the hot and ghost queues are updated, with the hot queue storing the warm data, with an attribute indicating hot).
With respect to claim 20, Wang teaches a storage system comprising:
a storage device including a nonvolatile memory and a controller configured to manage a hot list, a hot hash table, a candidate list, and a candidate hash table (col. 3, lines 2-25 and fig. 1, the flash cache corresponding to the nonvolatile memory, the hot queue corresponding to the hot list, the hash table corresponding to the hot hash table, and the ghost queue corresponding to the candidate list. Note that Wang uses one hash table for the hot hash table and the candidate hash table. This is addressed below); and
a host configured to transmit a logical address to the storage device (col. 4, lines 6-11, the hypervisor issues a read IO with an LBA),
search the hot hash table for the hot index corresponding to a position, at which the logical address is inserted into the hot list, by using the hot index, determine an attribute of data corresponding to the logical address based on the search result, and store attribute information indicating the attribute of the data (col. 4, lines 29-55, and fig. 3 where the hash table is searched, and if the entry is in the hot queue, the reference bit associated with the storage location of hot queue in which the LBA is stored is set to 1, which is the attribute of the claim),
manage the candidate hash table storing a position at which the logical address is inserted into the candidate list (col. 4, lines 29-55 and fig. 3, where the hash table is searched, the LBA is in the ghost queue. Note that Wang uses one hash table for the hot hash table and the candidate hash table. This is addressed below).
Wang fails to teach that the hot list is a FIFO.
McGlaughlin teaches a hot list in a first-in first-out scheme (par. 38).
Wang and McGlaughlin fail to teach a separate candidate list and a candidate hash table.
Jayasena teaches:
a candidate hash table separate from the hot hash table (pars. 51-52 and fig. 6, using a hash for the infrequently accessed bucket set to find candidate buckets, and a separate hash for the frequently accessed bucket set)
use a hot hash function to obtain a hot index (par. 51 and fig. 6, using the hash function for the frequently accessed bucket set to find candidate buckets, and find the value corresponding to the key)
manage the candidate hash table with a hash function different from the hot hash function (pars. 51-52 and fig. 6, using the hash function for the infrequently accessed bucket set to find candidate buckets), and therefore the combination of Wang, which teaches managing a hash table storing a position at which the logical address is inserted into the candidate list, and Jayasena, which teaches a candidate hash table separate from the hot hash table, teach to manage the candidate hash table with a candidate hash function storing a position at which the logical address is inserted into the candidate list,
Wang, Mclaughlin, and Jayasena fail to teach the hot list is a double connection link structure. Jung teaches:
store the logical address in the hot list in a double connection list structure in which nodes of the hot list are bidirectionally connected (par. 78, the double linked list 321 used to detect hot addresses. Par. 40 discloses that the hot addresses are logical addresses)
It would have been obvious to one of ordinary skill in the art, having the teachings of Wang and McGlaughlin before him before the earliest effective filing date, to modify the memory management device of Wang with the memory management device of McGlaughlin, as the hot list of McGlaughlin allows wear leveling, which mitigates neighbor disturbance in memory, as taught by McGlaughlin in par. 34. Further, it would have been obvious, also having the teachings of Jayasena before him before the earliest effective filing date, to modify the memory management device of Wang and McGlaughlin with the memory management device of Jayasena, as having separate frequently accessed and infrequently accessed bucket sets with respective hash functions provides performance optimization over the prior art of a large hash table with uniformly distributed data elements across buckets, as taught by Jayasena in pars. 4 and 60. Further, it would have been obvious, also having the teachings of Jung before him before the earliest effective filing date, to modify the memory management device of Wang, McGlaughlin and Jayasena with the memory management device of Jung, as the double linked hot list of Jung allows system resources may be used more efficiently while maintaining the hot address detection rate high enough, as taught by Jung in par. 206.
Response to Arguments
Applicant's arguments filed 09/26/2025 have been fully considered but they are not persuasive. Applicant’s arguments are directed towards the amended limitation in claims 1, 14, and 20, “a candidate hash function different from the hot hash function,” as that feature is not taught by the Wang, McGlaughlin, Davis or Jung references. These arguments are moot, as the new Jayasena reference has been supplied to teach this limitation, as disclosed in pars. 51-52, and detailed in the rejection above.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RYAN DARE whose telephone number is (571)272-4069. The examiner can normally be reached M-F 9:00-5:00.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Kenneth Lo can be reached at 571-272-9774. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/RYAN DARE/Examiner, Art Unit 2136