Processing and storing data using a hash table data structure
Key data is processed using a hash table data structure. Control data storage locations have a write-availability indicated by a first write-availability state indicating that the location is available to be written to, and a second write-availability state indicating that the location is not available to be written to. A temporary label value is stored in a selected control data storage location to render the selected location and a corresponding key data storage location inactive for read-out. The write-availability of the control data storage location is changed to the second write-availability state in association with the storage of the processed label value in the selected location. A read-out label value is obtained and the temporary label value stored in the selected control data storage location is over-written with the obtained read-out label value, to render the selected control data storage location and corresponding key data storage location active for read-out.
1. A method of processing key data representative of a key using a hash table data structure, wherein the hash table data structure comprises a plurality of control data storage locations corresponding to a plurality of key data storage locations, wherein each of the plurality of control data storage locations has a write-availability indicated by a first write-availability state which indicates that the control data storage location is available to be written to, and a second write-availability state, which indicates that the control data storage location is not available to be written to, the method comprising:
receiving the key data;
applying a hash function to at least part of the key data to determine a hash value;
based on the determined hash value, determining a temporary label value, wherein the temporary label value has at least one bit which is different from a read-out label value usable to identify a key data storage location based on the key;
selecting a control data storage location of the plurality of control data storage locations having the first write-availability state;
storing the temporary label value in the selected control data storage location to render both the selected control data storage location and a corresponding key data storage location inactive for read-out, wherein the write-availability of the selected control data storage location is caused to be changed to the second write-availability state in response to the storage of the temporary label value in the selected control data storage location;
writing the key data to the key data storage location corresponding to the selected control data storage location;
performing a predetermined operation on the temporary label value stored in the selected control data storage location to determine a new read-out label value; and
overwriting the temporary label value stored in the selected control data storage location with the new read-out label value to render both the selected control data storage location and corresponding key data storage location active for read-out; wherein the determination of the new read-out label value and overwriting the temporary label value are performed atomically.
2. The method according to claim 1 , wherein:
the temporary label value is determined from the hash value; and
the hash value comprises a first section and second section and the hash table data structure comprises a plurality of buckets, each comprising a plurality of control data storage locations and a corresponding plurality of key data storage locations, the method further comprising:
using the first section of the hash value to select a bucket of the plurality of buckets in which the selected control data storage location is to be found; and
using the second section of the hash value is to determine the temporary label value.
3. The method according to claim 2 , further comprising determining the temporary label value by:
determining the read-out label value from the hash value; and
performing a reversible operation on at least part of read-out label value.
4. The method according to claim 3 , wherein the reversible operation comprises an XOR operation.
5. The method according to claim 1 , wherein the new read-out label value is determined by performing an inverse-of-a-reversible operation on at least part of the temporary label value.
6. The method according to claim 5 , wherein the inverse-of-a-reversible operation comprises an XOR operation.
7. The method according to claim 1 , wherein storing the temporary label value in the selected control data storage location comprises a compare and swap (CAS) instruction.
8. The method according to claim 7 , wherein storing the temporary label value in the selected control data storage location is performed by a first thread and one or more other threads are capable of writing to the hash table data structure while the temporary label value is stored in the selected control data storage location.
9. The method according to claim 1 , wherein the key data includes a key-value pair.
10. The method according to claim 1 , further comprising:
processing a data packet using the key data.
11. The method according to claim 1 , further comprising:
receiving a key;
identifying a control data storage location on the basis of the received key; and
reading out key data from a key data storage location corresponding to the identified control data storage location.
12. The method according to claim 11 , further comprising:
retrieving data to control one or more operations to be performed on a received data packet from the hash table data structure, wherein:
the key data which has been read out from the key data storage location comprises a MAC address; and
processing the received data packet using the key data which has been read out comprises transmitting the data packet using the MAC address.
13. The method according to claim 12 , further comprising:
comparing at least part of the key data which has been read out with the received key; and
determining whether the identified control data storage location and corresponding key data storage location are active for read-out on the basis of the comparing.
14. A computer system comprising:
one or more processors; and
a memory storing:
key data which represents a key,
a hash table data structure comprising a plurality of control data storage locations corresponding to a plurality of key data storage locations, wherein each of the plurality of control data storage locations has a write-availability indicated by a first write-availability state, which indicates that the control data storage location is available to be written to, and a second write-availability state, which indicates that the control data storage location is not available to be written to,
a hash function,
a hash value,
a temporary label value,
a predetermined operation, and
a read-out label value;
the memory communicatively coupled with the one or more processors, the memory having computer-readable instructions stored thereupon that, when executed by the one or more processors, cause the system to perform operations comprising:
receiving the key data;
applying a hash function to at least part of the key data to determine a hash value;
based on the determined hash value, determining a temporary label value, wherein the temporary label value has at least one bit which is different from a read-out label value usable to identify a key data storage location based on the key;
selecting a control data storage location of the plurality of control data storage locations having the first write-availability state;
storing the temporary label value in the selected control data storage location to render both the selected control data storage location and a corresponding key data storage location inactive for read-out, wherein the write-availability of the selected control data storage location is caused to be changed to the second write-availability state in response to the storage of the temporary label value in the selected control data storage location;
writing the key data to the key data storage location corresponding to the selected control data storage location;
performing a predetermined operation on the temporary label value stored in the selected control data storage location to determine a new read-out label value; and
overwriting the temporary label value stored in the selected control data storage location with the new read-out label value to render both the selected control data storage location and corresponding key data storage location active for read-out; wherein the determination of the new read-out label value and overwriting the temporary label value are performed atomically.
15. The computer system according to claim 14 , wherein:
the temporary label value is determined from the hash value; and
the hash value comprises a first section and second section and the hash table data structure comprises a plurality of buckets, each comprising a plurality of control data storage locations and a corresponding plurality of key data storage locations, the memory further comprising computer-readable instructions stored thereupon that, when executed by the one or more processors, cause the system to perform operations comprising:
using the first section of the hash value to select a bucket of the plurality of buckets in which the selected control data storage location is to be found; and
using the second section of the hash value is to determine the temporary label value.
16. The computer system according to claim 15 , the memory further comprising computer-readable instructions stored thereupon that, when executed by the one or more processors, cause the system to perform operations comprising further comprising determining the temporary label value by:
determining the read-out label value from the hash value; and
performing a reversible operation on at least part of read-out label value.
17. The computer system according to claim 16 , wherein the reversible operation comprises an XOR operation.
18. The computer system according to claim 14 , wherein the new read-out label value is determined by performing an inverse-of-a-reversible operation on at least part of the temporary label value.
19. The computer system according to claim 18 , wherein the inverse-of-a-reversible operation comprises an XOR operation.
20. A non-transitory computer program comprising a set of instructions, which, when executed by a computer system, cause the computer system to perform operations for processing key data representative of a key using a hash table data structure, wherein the hash table data structure comprises a plurality of control data storage locations corresponding to a plurality of key data storage locations, wherein each of the plurality of control data storage locations has a write-availability indicated by a first write-availability state which indicates that the control data storage location is available to be written to, and a second write-availability state, which indicates that the control data storage location is not available to be written to, the operations comprising:
receiving the key data;
applying a hash function to at least part of the key data to determine a hash value;
based on the determined hash value, determining a temporary label value, wherein the temporary label value has at least one bit which is different from a read-out label value usable to identify a key data storage location based on the key;
selecting a control data storage location of the plurality of control data storage locations having the first write-availability state;
storing the temporary label value in the selected control data storage location to render both the selected control data storage location and a corresponding key data storage location inactive for read-out, wherein the write-availability of the selected control data storage location is caused to be changed to the second write-availability state in response to the storage of the temporary label value in the selected control data storage location;
writing the key data to the key data storage location corresponding to the selected control data storage location;
performing a predetermined operation on the temporary label value stored in the selected control data storage location to determine a new read-out label value; and
overwriting the temporary label value stored in the selected control data storage location with the new read-out label value to render both the selected control data storage location and corresponding key data storage location active for read-out; wherein the determination of the new read-out label value and overwriting the temporary label value are performed atomically.