Redundancy and majority voting in a key-value data storage system using content addressable memory
A memory system includes a memory device comprising a content addressable memory (CAM) block storing a plurality of stored search keys. The memory system further includes a processing device that receives an input search key and identifies, from the plurality of stored search keys in the CAM block, multiple redundant copies of a stored search key that match the input search key. The processing device further determining whether a number of the multiple redundant copies of the stored search key that match the input search key satisfies a threshold criterion. Responsive to the number of the multiple redundant copies of the stored search key that match the input search key satisfying the threshold criterion, the processing device determines a match result for the input search key.
1 . A system comprising:
a memory device comprising a content addressable memory (CAM) block storing a plurality of stored search keys; and
a processing device, operatively coupled with the memory device, to perform operations comprising:
identifying, from the plurality of stored search keys in the CAM block, multiple redundant copies of a stored search key that match an input search key;
incrementing a counter to a value based on a number of the multiple redundant copies of the stored search key that match the input search key; and
responsive to determining that the value of the counter is greater than or equal to a threshold value, determining that the input search key is found in the CAM block.
2 . The system of claim 1 , wherein the CAM block comprises an array of memory cells organized into a plurality of strings, each string storing one of the plurality of stored search keys and comprising a plurality of memory cells connected in series between a precharged match line and a page buffer, wherein each of the plurality of memory cells is connected to one of a plurality of search lines, wherein the input search key comprises a first sequence of bits, and wherein the processing device is to perform operations further comprising:
generating a search pattern based on the first sequence of bits, the search pattern comprising a first set of voltage signals representing the first sequence of bits and a second set of voltage signals representing a second sequence of bits comprising an inverse of the first sequence of bits; and
providing the search pattern as an input to the plurality of search lines of the CAM block, wherein the search pattern to cause at least one string of the plurality of strings storing the one of the plurality of stored search keys that matches the input search key to be conductive and provide a signal to the page buffer in response to the input search key matching the one of the plurality of stored search keys stored on the at least one string, the signal resulting from the precharged match line discharging, and the page buffer storing data based on the signal.
3 . The system of claim 1 , wherein the multiple redundant copies of the stored search key are stored in different sub-blocks of the CAM block, wherein the different sub-blocks are associated with a common page buffer.
4 . The system of claim 1 , wherein the multiple redundant copies of the stored search key are stored in a same sub-block of the CAM block.
5 . The system of claim 1 , wherein each of the multiple redundant copies of the stored search key has an associated respective match location in the CAM block, and wherein the processing device is to perform operations further comprising:
responsive to determining that the input search key is found in the CAM block, determining, using at least one of the associated respective match locations, a corresponding value location in a value data block; and
retrieving, from the value location in the value data block, data representing a value associated with the input search key.
6 . The system of claim 5 , wherein the memory device comprises a negative and (NAND) type flash memory device, and wherein the associated respective match locations in the CAM block comprise memory addresses of respective strings on the NAND type flash memory device.
7 . The system of claim 5 , further comprising:
a lookup table comprising a plurality of entries, wherein each entry of the plurality of entries associates the associated respective match locations from the CAM block with a value location in the value data block where data representing a value corresponding to the multiple redundant copies of the stored search key from the CAM block is stored.
8 . The system of claim 7 , wherein determining the corresponding value location in the value data block comprises identifying an entry of the plurality of entries in the lookup table corresponding to the associated respective match locations.
9 . The system of claim 1 , wherein the input search key is received from a host system, and wherein the processing device is to perform operations further comprising: providing data representing a value associated with the input search key to the host system.
10 . A method comprising:
identifying, from a plurality of stored search keys in a content addressable memory (CAM) block of a memory device, multiple redundant copies of a stored search key that match an input search key;
incrementing a counter to a value based on a number of the multiple redundant copies of the stored search key that match the input search key; and
responsive to determining that the value of the counter is greater than or equal to a threshold value, determining that the input search key is found in the CAM block.
11 . The method of claim 10 , wherein the multiple redundant copies of the stored search key are stored in different sub-blocks of the CAM block, wherein the different sub-blocks are associated with a common page buffer.
12 . The method of claim 10 , wherein the multiple redundant copies of the stored search key are stored in a same sub-block of the CAM block.
13 . The method of claim 10 , wherein each of the multiple redundant copies of the stored search key has an associated respective match location in the CAM block, the method further comprising:
responsive to determining that the input search key is found in the CAM block, determining, using at least one of the associated respective match locations, a corresponding value location in a value data block; and
retrieving, from the value location in the value data block, data representing a value associated with the input search key.
14 . The method of claim 13 , wherein the memory device comprises a negative and (NAND) type flash memory device, and wherein the associated respective match locations in the CAM block comprise memory addresses of respective strings on the NAND type flash memory device.
15 . A non-transitory machine readable storage medium storing instructions that, when executed by a processing device, cause the processing device to perform operations comprising:
identifying, from a plurality of stored search keys in a content addressable memory (CAM) block of a memory device, multiple redundant copies of a stored search key that match an input search key;
incrementing a counter to a value based on a number of the multiple redundant copies of the stored search key that match the input search key; and
responsive to determining that the value of the counter is greater than or equal to a threshold value, determining that the input search key is found in the CAM block.
16 . The non-transitory machine readable storage medium of claim 15 , wherein the multiple redundant copies of the stored search key are stored in different sub-blocks of the CAM block, wherein the different sub-blocks are associated with a common page buffer.
17 . The non-transitory machine readable storage medium of claim 15 , wherein the multiple redundant copies of the stored search key are stored in a same sub-block of the CAM block.
18 . The non-transitory machine readable storage medium of claim 15 , wherein each of the multiple redundant copies of the stored search key has an associated respective match location in the CAM block, and wherein the instructions to cause the processing device to perform operations further comprising:
responsive to determining that the input search key is found in the CAM block, determining, using at least one of the associated respective match locations, a corresponding value location in a value data block; and
retrieving, from the value location in the value data block, data representing a value associated with the input search key.
19 . The non-transitory machine readable storage medium of claim 18 , wherein the memory device comprises a negative and (NAND) type flash memory device, and wherein the associated respective match locations in the CAM block comprise memory addresses of respective strings on the NAND type flash memory device.
20 . The non-transitory machine readable storage medium of claim 15 , wherein the input search key is received from a host system, and wherein the instructions to cause the processing device to perform operations further comprising:
providing data representing a value associated with the input search key to the host system.