Methods and systems for opportunistic cookie caching

• US 7,600,028 B2
• Filed: 01/10/2005
• Issued: 10/06/2009
• Est. Priority Date: 01/10/2005
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Eriksen, Bjorn Marius Aamodt
• Primary Examiner(s): Phillips; Hassan
• Assistant Examiner(s): Greene; Joseph L
• Application Number:
  US11/033,411
• Publication Number:
  US 20060156387A1
• Time in Patent Office: 1,730 Days
• Field of Search: 707/101, 707/102, 707/103, 707/104, 713/150, 709/227, 709/217, 709/203
• US Class Current: 709/227
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Caching cookies in a server includes observing cookies in document requests generated from a client and in responses from web hosts and storing them in a data structure based on certain conditions to maintain a path invariance condition. The cookies may be stored in a trie data structure. Upon certain conditions, cookies in the trie may be coalesced if they are equivalent and nodes of the trie may be collapsed. A server may retrieve cookies from the cache for use in a prefetch operation.

Claims

1. A method of utilizing cookies, comprising:

at a server,

accessing a data structure that stores cookies, wherein the data structure associates a path, a name, and a value with each cookie stored;

receiving a first cookie, the first cookie having a first path, a first name, and a first value;

not storing the first cookie in the data structure if a condition is met, and storing the first cookie in the data structure if the condition is not met;

wherein the condition is that there is a second cookie in the data structure whose associated name and value are the same as the first name and first value respectively, the path associated with the second cookie is a prefix of the first path, and there is no third cookie in the data structure

whose associated name is the same as the first name,

whose associated path is a prefix of the first path, and

for which the path associated with the second cookie is a prefix of the path associated with the third cookie.

2. The method of claim 1, further comprising removing a fourth cookie from the data structure if:

the name and value associated with the fourth cookie are the same as the first name and first value respectively;

the first path is a prefix of the path associated with the fourth cookie; and

there is no fifth cookie stored in the data structure

whose name is the same as the name associated with the fourth cookie,

whose path is a prefix of the path associated with the fourth cookie, and

for which the first path is a prefix of the path associated with the fifth cookie.

3. The method of claim 1, further comprising when the condition is met:

removing any cookie in the data structure whose associated path and name are the same as the first path and first name respectively.

4. The method of claim 3, wherein the data structure is a trie data structure in which each node corresponds to a path and each node stores cookie data for cookies, if any, whose paths match the path corresponding to the node, and further comprising when the condition is met:

identifying a first node in the data structure whose path corresponds to the first path; and

collapsing the first node, within the data structure, into a second node, if the second node is an only child of the first node and the first node no longer stores any cookie data.

5. The method of claim 1, further comprising:

identifying a document, associated with the first path for prefetching;

selecting the first cookie, if present within the data structure, and other cookies in the data structure whose associated paths are prefixes of the first path; and

prefetching the document using the selected first cookie and the selected other cookies, if any.

6. The method of claim 5, further comprising sending the document and the first cookie and the other cookies, if used to prefetch the document, to a remote computer.

7. The method of claim 5, wherein the document is identified from a referencing document.

8. A computer program product stored in one or more memory devices, comprising one or more programs configured for execution by one or more processors at a server, the one or more programs comprising instructions to:

access a data structure that stores cookies, wherein the data structure associates a path, a name, and a value with each cookie stored;

receive a first cookie, the first cookie having a first path, a first name, and a first value;

not store the first cookie in the data structure if a condition is met, and store the first cookie in the data structure if the condition is not met;

wherein the condition is that there is a second cookie in the data structure whose associated name and value are the same as the first name and first value respectively, the path associated with the second cookie is a prefix of the first path, and there is no third cookie in the data structure whose associated name is the same as the first name, whose associated path is a prefix of the first path, and for which the path associated with the second cookie is a prefix of the path associated with the third cookie.

9. The computer program product of claim 8, further comprising instructions to remove a fourth cookie from the data structure if:

the name and value associated with the fourth cookie are the same as the first name and first value respectively;

the first path is a prefix of the path associated with the fourth cookie; and

there is no fifth cookie stored in the data structure

whose name is the same as the name associated with the fourth cookie,

whose path is a prefix of the path associated with the fourth cookie, and

for which the first path is a prefix of the path associated with the fifth cookie.

10. The computer program product of claim 8, further comprising instructions that execute when the condition is met to:

remove any cookie in the data structure whose associated path and name are the same as the first path and the first name respectively.

11. The computer program product of claim 10, wherein the data structure is a trie data structure in which each node corresponds to a path and each node stores cookie data for cookies, if any, whose paths match the path corresponding to the node, and further comprising instructions that execute when the condition is met to:

identify a first node in the data structure whose path corresponds to the first path; and

collapse the first node, within the data structure, into a second node, if the second node is an only child of the first node and the first node no longer stores any cookie data.

12. The computer program product of claim 8, further comprising instructions which execute to:

identify a document, associated with the first path, for prefetching;

select the first cookie, if present within the data structure, and other cookies in the data structure whose associated paths are prefixes of the first path; and

prefetch the document using the selected first cookie and the selected other cookies, if any.

13. The computer program product of claim 12, further comprising instructions which execute to send the document and the first cookie and the other cookies, if used to prefetch the document, to a remote computer.

14. The computer program product of claim 12, wherein the instructions which execute to identify the document further comprise instructions which execute to identify the document from a referencing document.

15. A system for utilizing cookies, comprising:

a server with one or more processors and memory;

a data structure stored in the memory, wherein the data structure is configured to store a plurality of cookies, including a path, a name, and a value for each respective cookie stored; and

a data structure interface module stored in the memory, the data structure interface module executing on the one or more processors to;

receive a first cookie, the first cookie having a first path, a first name, and a first value;

not store the first cookie in the data structure if a condition is met, and store the first cookie in the data structure if the condition is not met;

wherein the condition is that there is a second cookie in the data structure whose name and value are the same as the first name and first value respectively, the path of the second cookie is a prefix of the first path, and there is no third cookie stored in the data structure

whose name is the same as the first name,

whose path is a prefix of the first path, and

for which the path of the second cookie is a prefix of the path of the third cookie.

16. The system of claim 15, wherein the data interface module further executes on the one or more processors to remove a fourth cookie from the data structure if:

the name and value associated with the fourth cookie are the same as the first name and first value respectively;

the first path is a prefix of the path associated with the fourth cookie; and

there is no fifth cookie stored in the data structure

whose name is the same as the name of the fourth cookie,

whose path is a prefix of the path of the fourth cookie, and

for which the first path is a prefix of the path of the fifth cookie.

17. The system of claim 15, wherein the data interface module further executes when the condition is met to:

remove any cookie in the data structure whose path and name are the same as the first path and first name respectively.

18. The system of claim 17, wherein the data structure is a trie data structure in which each node corresponds to a path and each node stores cookie data for cookies, if any, whose paths match the path corresponding to the node, and wherein the data interface module further executes when the condition is met to:

identify a first node in the data structure whose path is the same as the first path; and

collapse the first node, within the data structure, into a second node, if the second node is an only child of the first node and the first node no longer stores cookie data.

19. The system of claim 15, wherein the data interface module further executes to:

identify a document, associated with the first path, for prefetching;

select the first cookie, if present within the data structure, and other cookies in the data structure whose paths are prefixes of the first path; and

prefetch the document using the selected first cookie and the selected other cookies, if any.

20. The system of claim 19, wherein the data interface module further executes to send the document and the first cookie and the other cookies, if used to prefetch the document, to a remote computer.

21. The system of claim 19, wherein the data interface module further executes to identify the document from a referencing document.

22. A server system for utilizing cookies, comprising:

one or more processors, and memory storing programs executed by the one or more processors;

means for accessing a data structure that stores cookies, wherein the data structure associates a path, a name, and a value with each cookie stored;

means for receiving a first cookie, the first cookie having a first path, a first name, and a first value;

means for not storing the first cookie in the data structure if a condition is met, and means for storing the first cookie in the data structure if the condition is not met;

wherein the condition is that there is a second cookie in the data structure whose associated name and value are the same as the first name and first value respectively, the path associated with the second cookie is a prefix of the first path, and there is no third cookie in the data structure

whose associated name is the same as the first name,

whose associated path is the same as the first path, and

for which the path associated with the second cookie is a prefix of the path associated with the third cookie.