Invalidation in a content delivery network (CDN)

• US 9,591,047 B1
• Filed: 04/11/2016
• Issued: 03/07/2017
• Est. Priority Date: 04/11/2016
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Newton, Christopher, Wong, Fiona, Lipstone, Laurence, Crowder, William
• Primary Examiner(s): Jean, Frantz
• Application Number:
  US15/095,282
• Time in Patent Office: 330 Days
• Field of Search: 709/202, 709/216, 709/223, 709/224, 709/219, 711/113, 711/118
• US Class Current: 1/1
• CPC Class Codes: H04L 65/762 at the source reformatting of additional data in video distribution servers H04N21/2355
• CPC Class Codes: H04L 67/1004 Server selection for load balancing
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/289 Intermediate processing functionally located close to the data consumer application, e.g. in same machine, in same home or in same sub-network
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A content delivery (CD) service in a CDN maintains property invalidation information on said CD service including, for each property, a list of one or more group invalidation commands. New group invalidation commands are added by selectively merging one or more invalidation commands to form a merged invalidation command and inserting the merged invalidation command into said list, wherein the merging is based on a length of common prefix of elements in said list. A per property common prefix list is maintained for invalidation commands in each property list.

Claims

1. A computer-implemented method, operable on a device in a content delivery network (CDN), wherein said CDN delivers content on behalf of at least one content provider, and wherein the content associated with said at least one content provider comprises at least one property, said device implementing a content delivery (CD) service, the method comprising, by said service on said device:

(A) maintaining property invalidation information on said CD service, said property invalidation information comprising, for each property handled by said CD service, a list of one or more group invalidation commands;

(B) in response to receipt by said CD service of at least one new group invalidation command for a particular property, attempting to add said new group invalidation command to said property invalidation information by;

(B)(1) if a size of said list of one or more group invalidation commands for said particular property does not exceed a particular threshold, then inserting said new group invalidation command into said list;

otherwise,

(B)(2) if a size of said list of one or more group invalidation commands for said particular property exceeds a particular threshold, then (i) merging one or more invalidation commands to form a merged invalidation command, (ii) inserting said merged invalidation command into said list, and (iii) removing said one or more invalidation commands from said list, wherein said merging is based on a length of common prefix of the invalidation commands being merged.

2. The method of claim 1 further comprising:

(C) maintaining, on said CD service, a per property common prefix list for invalidation commands in each property list, and wherein said merging uses said common prefix list to determine which invalidation commands to merge.

3. The method of claim 2 wherein said per property common prefix list is sorted from smallest impact to largest impact, based on one or more impact assumptions.

4. The method of claim 2 wherein, when a new invalidation pattern is received, the new pattern is checked against the existing list of patterns and if a common prefix is found, then the common prefix is selectively added to said common prefix list.

5. The method of claim 1 wherein group invalidation commands comprise constraint patterns.

6. The method of claim 5 wherein the constraint patterns comprise glob patterns.

7. The method of claim 1 further comprising:

(D) in response to a request received at said CD service for a particular resource, if a copy of said particular resource is in a cache of said CD service, then;

(D)(1) determining, using said property invalidation information on said CD service, whether said particular resource is valid, and

(D)(2) based on said determining in (D)(1), when it is determined that said particular resource is not valid, obtaining a valid version of said particular resource and basing a response to said request on said valid version of said particular resource.

8. The method of claim 1 wherein said list of one or more group invalidation commands comprises a data structure that maintains the prefix list in a sorted order.

9. The method of claim 8 wherein the data structure that maintains the prefix list sorted from smallest impact to largest impact.

10. The method of claim 1 wherein each invalidation command in said list of one or more group invalidation commands comprises a constraint and a minimum origin version (MOV) value, and wherein said list of one or more group invalidation commands is a MOV-ordered list.

11. The method of claim 10 wherein said merging of one of more invalidation commands in (B)(2)(i), comprises determining an MOV value for the merged invalidation command based on MOV values of the one of more invalidation commands being merged.

12. The method of claim 11 wherein the MOV value for the merged invalidation command is set to a maximum of the MOV values of the one of more invalidation commands being merged.

13. The method of claim 10 wherein the constraint of the merged invalidation command was already in the list prior the merging.

14. The method of claim 13 wherein the constraint of the merged invalidation command was a constraint of one of the one of more invalidation commands being merged in (B)(2)(i).

15. An article of manufacture comprising a non-transitory computer-readable medium having program instructions stored thereon, the program instructions, operable on a computer system in a content delivery network (CDN), wherein said CDN delivers content on behalf of at least one content provider, and wherein the content associated with said at least one content provider comprises at least one property, said device implementing a content delivery (CD) service, wherein execution of the program instructions by one or more processors of said computer system causes the one or more processors to carry out the acts of:

(A) maintaining property invalidation information on said CD service, said property invalidation information comprising, for each property handled by said CD service, a list of one or more group invalidation commands;

(B) in response to receipt by said CD service of at least one new group invalidation command for a particular property, attempting to add said new group invalidation command to said property invalidation information by;

(B)(1) if a size of said list of one or more group invalidation commands for said particular property does not exceed a particular threshold, then inserting said new group invalidation command into said list;

otherwise,

(B)(2) if a size of said list of one or more group invalidation commands for said particular property exceeds a particular threshold, then (i) merging one or more invalidation commands to form a merged invalidation command, (ii) inserting said merged invalidation command into said list, and (iii) removing said one or more invalidation commands from said list, wherein said merging is based on a length of common prefix of the invalidation commands being merged.

16. A device in a content delivery network (CDN), wherein said CDN delivers content on behalf of at least one content provider, and wherein the content associated with said at least one content provider comprises at least one property, said device implementing a content delivery (CD) service, the device:

(A) maintaining property invalidation information on said CD service, said property invalidation information comprising, for each property handled by said CD service, a list of one or more group invalidation commands;

(B) in response to receipt by said CD service of at least one new group invalidation command for a particular property, attempting to add said new group invalidation command to said property invalidation information by;

(B)(1) if a size of said list of one or more group invalidation commands for said particular property does not exceed a particular threshold, then inserting said new group invalidation command into said list;

otherwise,

(B)(2) if a size of said list of one or more group invalidation commands for said particular property exceeds a particular threshold, then (i) merging one or more invalidation commands to form a merged invalidation command, (ii) inserting said merged invalidation command into said list, and (iii) removing said one or more invalidation commands from said list, wherein said merging is based on a length of common prefix of the invalidation commands being merged.