Multi-tiered fleet management cache

• US 9,576,254 B2
• Filed: 02/08/2008
• Issued: 02/21/2017
• Est. Priority Date: 03/01/2007
• Status: Active Grant

• Current Assignee: Zipcar Incorporated (Avis Budget Group Incorporated)
• Original Assignee: Zipcar Incorporated (Avis Budget Group Incorporated)
• Inventors: McGuire, Gregory J., Wolfe, Jonathan E.
• Primary Examiner(s): Vetter, Daniel
• Application Number:
  US12/028,477
• Publication Number:
  US 20080228533A1
• Time in Patent Office: 3,301 Days
• Field of Search: 705 5- 9, 701/207, 701/208, 701/213, 340988-996
• US Class Current: 1/1
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: G06F 8/454 Consistency cache consistency protocols in hierarchically structured memory systems G06F12/0815
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 30/0625 Directed, with specific intent or strategy
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles

Abstract

A method of providing reservation status relating to a group of objects includes providing a database for containing (i) availability data describing availability of at least one of the group of objects, and (ii) reservation data describing allocation of at least one of the group of objects. The availability data and the reservation data are stored in sparse form. The method further includes extracting, from the database, availability data and reservation data corresponding to a predetermined period of time, and combining the extracted availability data and reservation data to form windowed data in a dense format. The method also includes receiving the windowed data and providing the windowed data in a bit-vector view, and sampling the windowed data in the bit-vector view to produce sampled data. The sampled data provides the reservation status as a static view of the windowed data in the bit-vector view.

Claims

1. A system for providing reservation status relating to a plurality of objects, comprising:

a database, implemented on a first computing system, the database constructed and arranged to contain (i) operational status data describing whether each particular object of said plurality of objects is functionally capable of performing a task, and (ii) reservation data describing availability of each particular object of the plurality of objects for a reservation by a pre-authorized user, wherein the reservation data comprises information regarding whether each particular object of the plurality of objects is allocated to another pre-authorized user for a particular time period;

a first caching level module, implemented on the first computing system, configured to create a first cache of dense windowed data by (i) receiving, from the database, operational status data and reservation data from a window of time, and (ii) converting the received operational status data and reservation data to form windowed data denser than the received operation status data and reservation data;

a second caching level module, implemented on the first computing system, configured to create a second cache of compact data by storing the dense windowed data in the first cache in a simple set data structure; and

a third caching level module, implemented on the first computing system, configured to create one or more third caches by copying the second cache, wherein said one or more third caches are provided to one or more application computing systems separate from the first computing system, such that a copy of cached windowed data is stored on the second computer system for access by an end user computing device without access to the first computer system;

wherein the first cache is updated whenever the data in the database changes;

further wherein the first computing system both (i) updates the one or more third caches on said one or more application computing systems following a change to the first cache, and (ii) receives, from the one or more application computing systems, polls for changes in the database that affect the corresponding third caches, thereby minimizing the time the third caches, second cache and the first cache are different.

2. The system of claim 1, wherein the plurality of objects is a fleet of automobiles.

3. The system of claim 1, wherein the operational status data comprises binary information specifying, for each of the at least one of the plurality of objects, that either (i) the object is functionally capable of performing a task, or (ii) the object is not functionally capable of performing the task.

4. The system of claim 1, comprising a receiver module configured for receiving current operational status data from at least one of the plurality of objects, and for updating the database with the current operational status data.

5. The system of claim 1, wherein the state between the third caches, the second cache, the first cache, and the data contained in the database is maintained at or near real time.

6. The system of claim 1, wherein the third caching level module provides a third cache to each of one or more application servers running application server software.

7. The system of claim 6, wherein the application server software maintains consistency between the third caches on each of the one or more application servers and the second cache by using a distributed invalidation function to inform the one or more application servers and the first computing system of impending changes to a third cache.

8. The system of claim 6, wherein the application server software maintains consistency between the third caches on the one or more application servers by polling a journal table that records changes to the first cache, and using the recorded changes to update the second cache and third caches.

9. The apparatus of claim 1, wherein the data is the second cache is stored as bit-vector data configured to exploit bit-level parallelism.

10. A computer implemented method of providing reservation status relating to a plurality of objects, comprising:

extracting, by a first computer system, from a database, availability data and reservation data corresponding to a predetermined period of time, wherein the database contains (i) operational status data describing whether each particular object of said plurality of objections is functionally capable of performing a task, and (ii) reservation data describing availability of each particular object of the plurality of objects for a reservation by a pre-authorized user, wherein the reservation data comprises information regarding whether each particular object of the plurality of objects is allocated to another pre-authorized user for a particular time period;

combining, by the first computer system, the extracted operational status data and reservation data to create a first cache of dense windowed data denser than the extracted operational status data and reservation data;

creating a second cache of compact by storing the dense windowed data in the first cache in a simple set data structure;

creating a third cache by copying the second cache to a second computer system, such that the third cache is stored on the second computer system for access by an end user computing device without access to the first computer system; and

updating, by the first computer system, the first cache whenever the data in the database changes;

wherein the first computer system both (i) updates the third cache following a change to the first cache, and (ii) receives, from the second computer system, polls for changes in the database that affects the third cache, thereby minimizing the time the third cache, second cache, and first cache are different.

11. The method of claim 10, comprising receiving current operational status data from at least one of the plurality of objects, and updating the database with the current operational status data.

12. The method of claim 10, wherein the second computer system comprises an application server, wherein conformity between the first cache and third cache on the application server are maintained at or near real time.

13. The method of claim 10, wherein there are two or more second computer systems each comprising an application server.

14. The method of claim 13, comprising the step of maintaining consistency between the third caches on the two or more application servers using a distributed invalidation function to inform the two or more application servers of impending changes to the third caches.

15. The method of claim 13, comprising the step of maintaining consistency between the third caches on the two or more application servers by polling a journal table that records changes to the first cache, and using the recorded changes to update the second cache and third caches.

16. The method of claim 10, wherein the data is the second cache is stored as bit-vector data configured to exploit bit-level parallelism.

17. The method of claim 10, wherein the plurality of objects is a fleet of automobiles.