Fixed delay storage and its application to networked advertisement exchange

1. A device comprising:

a storage that stores a set of entries; and

a processor configured to:

receive a first key; and

insert the first key into two locations within the set of entries,

wherein the two corresponding locations are determined based on at least a first hashing function, a second hashing function, and an eviction criterion for evicting collided hashed values of the first key; and

wherein the processor is configured to:

calculate a fixed delay, based on a time stamp associated with the first key, that bounds an insertion time for operations resulting in inserting the first key, the fixed delay associated with a fixed number of steps to move keys, within the set of entries, in association with the inserting the first key;

responsive to inserting the first key in a first location, within the set of entries, of a second key and determining that the fixed number of steps have not been performed in association with the inserting the first key, move the second key to a second location, within the set of entries, of a third key;

responsive to moving the second key to the second location and determining that the fixed number of steps have not been performed in association with the inserting the first key, move the third key to a third location, within the set of entries, of a fourth key; and

responsive to (i) moving the third key to the third location, (ii) determining that the fixed number of steps have been performed in association with the inserting the first key and (iii) determining that no keys associated with the inserting the first key are expired:

evaluate a plurality of locations associated with inserting the first key, including the second location and the third location, to determine which location of the plurality of locations has a key that is closest to an expiration time of the key but is not yet expired based on an evaluation of a time stamp of each key of the plurality of locations and an expiration time for each key of the plurality of locations; and

evict the key in the determined location of the plurality of locations.

2. The device of claim 1 , wherein the evaluating the plurality of locations comprises:

evaluating a fourth location that has a fifth key that is not yet expired to determine how close the fifth key is to a fourth expiration time of the fifth key; and

evaluating a fifth location that has a sixth key that is not yet expired to determine how close the sixth key is to a fifth expiration time of the sixth key.

3. The device of claim 1 , wherein the evaluating the plurality of locations comprises:

evaluating the second location that has the second key that is not yet expired to determine how close the second key is to a second expiration time of the second key; and

evaluating the third location that has the third key that is not yet expired to determine how close the third key is to a third expiration time of the third key.

4. The device of claim 1 , wherein the first key includes a first local identifier, an entry in the set of entries includes a second local identifier and at least one private identifier, and the first key is inserted into the set of entries with a private identifier associated with the first key.

5. The device of claim 4 , wherein the first local identifier is an identifier of a client device by a first system, and the private identifier is an identifier of the client device by a second system.

6. The device of claim 5 , wherein the private identifier is stored in the second system connected to the device by a network.

7. The device of claim 6 , wherein the processor is configured to:

retrieve through the network a set of behavior stored in the second system corresponding to the private identifier; and

distribute an advertisement to the client device based on the set of behavior.

8. The device of claim 1 , wherein:

the plurality of locations associated with inserting the first key comprises all locations inspected during operations related to the inserting the first key.

9. The device of claim 1 , wherein: the eviction criterion for evicting collided hashed values of the first key is to evict an entry in a location inspected at a fixed number of step.

10. The device of claim 1 , wherein:

each entry in the set of entries has a respective associated time stamp; and

the eviction criterion for evicting collided hashed values of the first key is to evict an entry in a location that is closest to its expiration time among all locations been inspected during operations resulting in inserting the first key.

11. A method for a hashing table, comprising:

receiving, by a device, a first key;

inserting the first key, by a processor of the device, into two locations within a set of entries stored in a storage of the device,

wherein the two locations are determined by at least a first hashing function, a second hashing function, and an eviction criterion for evicting collided hashed values of the first key; and

wherein a fixed delay that is calculated based on a time stamp associated with the first key bounds an insertion time for operations related to inserting the first key, the fixed delay associated with a fixed number of steps to move keys, within the set of entries, in association with the inserting the first key;

responsive to inserting at least one key in a first location, within the set of entries, of a second key and determining that the fixed number of steps have not been performed in association with the inserting the first key, moving the second key to a second location, within the set of entries, of a third key; and

responsive to (i) moving the second key to the second location, (ii) determining that the fixed number of steps have been performed in association with the inserting the first key and (iii) determining that no keys associated with the inserting the first key are expired:

evaluating a plurality of locations associated with inserting the first key, including the second location, to determine which location of the plurality of locations has a key that is closest to an expiration time of the key but is not yet expired based on an evaluation of a time stamp of each key of the plurality of locations and an expiration time for each key of the plurality of locations; and

evicting the key in the determined location of the plurality of locations.

12. The method of claim 11 , wherein the fixed delay is associated with a fixed time interval, and the insertion time for operations related to inserting the first key is within the fixed time interval.

13. The method of claim 11 , wherein the inserting the first key comprises inserting the first key into the set of entries with a private identifier associated with the first key.

14. The method of claim 11 , wherein the first key includes a first local identifier, an entry in the set of entries includes a pair of a second local identifier and at least one private identifier, and the first key is inserted into the set of entries with a private identifier associated with the first key.

15. The method of claim 14 , wherein the first local identifier is an identifier of a client device by a first system, and the private identifier is an identifier of the client device by a second system.

16. The method of claim 15 , wherein the private identifier is stored in the second system connected to the device by a network.

17. The method of claim 16 , comprising:

retrieving, by the processor of the device and through the network, a set of behavior stored in the second system corresponding to the private identifier; and

distributing, by the processor of the device, an advertisement to the client device based on the set of behavior.

18. The method of claim 11 , wherein:

the eviction criterion for evicting collided hashed values of the first key is to evict an entry inspected during operations related to inserting the first key that is expired based on its associated time stamp.

19. The method of claim 11 , wherein: at least one entry in the set of entries comprises an identifier of a client device, the method comprising:

retrieving a set of behavior corresponding to the identifier; and

distributing an advertisement to the client device based on the set of behavior.

20. The method of claim 11 , wherein:

the plurality of locations associated with inserting the first key comprises all locations inspected during operations related to the inserting the first key.

21. A device comprising:

a storage storing a set of entries; and

a processor configured to:

receive a first key; and

insert the first key into two locations within the set of entries,

wherein the two locations are determined by at least one of a first hashing function, a second hashing function, or an eviction criterion for evicting collided hashed values of the first key; and

wherein the processor is configured to:

calculate a fixed delay, based on a time stamp associated with the first key, that bounds an insertion time for operations related to inserting the first key;

responsive to inserting at least one key in a first location, within the set of entries, of a second key and determining that a limit of the fixed delay has not been met in association with the inserting the first key, move the second key to a second location, within the set of entries, of a third key; and

responsive to (i) moving the second key to the second location, (ii) determining that the limit of the fixed delay has been met in association with the inserting the first key and (iii) determining that keys associated with the inserting the first key are not expired:

evaluate a plurality of locations associated with inserting the first key, including the second location, to determine which location of the plurality of locations has a key that is closest to an expiration time of the key but is not yet expired based on an evaluation of at least one of a time stamp of each key of the plurality of locations or an expiration time for each key of the plurality of locations; and

evict the key in the determined location of the plurality of locations.

22. The device of claim 21 , wherein the limit of the fixed delay is a fixed time interval, and the insertion time for operations related to inserting the first key is within the fixed time interval.

23. The device of claim 21 , wherein at least one entry in the set of entries comprises an identifier of a client device, the processor configured to:

retrieve a set of behavior corresponding to the identifier.

24. The device of claim 23 , wherein the processor is configured to:

distribute an advertisement to the client device based on the set of behavior.