Partially ordered queue for efficient processing of assets

• US 8,051,433 B1
• Filed: 11/18/2005
• Issued: 11/01/2011
• Est. Priority Date: 09/20/2005
• Status: Active Grant

• Current Assignee: Savi Technology Incorporated
• Original Assignee: Savi Technology Incorporated
• Inventors: Alcock, Andrew Edward Savige, Gill, Andrew, Chinowutthichai, Ronnachai
• Primary Examiner(s): Ho, Andy
• Assistant Examiner(s): Seye, Abdou
• Application Number:
  US11/283,226
• Time in Patent Office: 2,174 Days
• Field of Search: 719/320, 709/224
• US Class Current: 719/320
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A system and method provides efficient message processing of assets. The system and method places all messages in a queue as they are received from an information feed and groups the messages according to the entities with which they are associated. The messages within each group are sorted according to the time the message was generated by the information feed, and then are processed in the order in which they were generated.

Claims

1. A method for efficient message processing in an asset management system, comprising:

using a computer including a processor and a memory to perform steps comprising;

receiving messages from an information feed, each message associated with a tracking device coupled with an asset tracked by the asset management system;

entering the messages into a queue stored in the memory;

sorting the received messages into partial order groups of messages in which each partial order group includes messages associated with a group of related assets and related data records corresponding to the related assets, wherein sorting the received messages into partial order groups of messages further comprises;

determining a plurality of assets associated with a received message,

determining a subset of a plurality of individual queues associated with the plurality of assets,

preventing additional messages from entering the subset of individual queues,

merging the subset of individual queues to create a partial order group queue, and

directing the received message to the partial order group queue; and

for each partial order group, processing the sorted messages in an order generated by the information feed, wherein there is at most a single message from the partial order group accessing the related data records corresponding to the related assets at any time.

2. The method of claim 1, wherein the information feed includes data from one or more tag reader devices.

3. The method of claim 1, wherein the information feed includes data from multiple locations.

4. The method of claim 1, wherein each message from the information feed includes a state identifier and the state identifier indicates a business state of a tracking device associated with at least one of the messages.

5. The method of claim 1, wherein the messages are selected from the group consisting of state update messages and state-independent messages.

6. The method of claim 1, wherein the received messages are state-independent messages that can be processed in any order.

7. The method of claim 1, wherein the queue is a standard FIFO queue.

8. The method of claim 1, wherein sorting the messages into groups sorts the messages by business entities with which the messages are associated.

9. The method of claim 1, wherein processing the sorted messages associated with a group of related assets comprises:

evaluating a message predicate for a message from the sorted messages;

halting processing and delivery of the message if the message predicate evaluates to false; and

continuing processing and delivery of the message if the message predicate evaluates to true.

10. The method of claim 9, wherein the message predicate is an expression that reduces to a Boolean value.

11. The method of claim 10, further comprising continuing processing and delivery of the message if no message predicate exists.

12. The method of claim 1, wherein processing the sorted messages in an order generated by the information feed further comprises:

determining a pre-state of a tracking device associated with a message selected from the sorted messages;

retrieving a last stored state of the tracking device;

determining whether the pre-state and the last stored state match;

responsive to a determination that the pre-state and last stored state match, processing the message; and

responsive to a determination that the pre-state and last stored state do not match, returning the message to a queue for the each partial order group.

13. The method of claim 12, further comprising:

applying a predicate to the message reflecting the last stored state;

determining whether the message is a state-changing message; and

responsive to a determination that the message is a state-changing message, reevaluating predicates on a subset of messages.

14. The method of claim 1, wherein the group of related assets includes assets contained in physical proximity of each other.

15. An apparatus for efficient message processing in an asset management system, the apparatus comprising:

a processor and a memory, the processor configured to execute instructions stored as modules in the memory, the modules comprising;

a receiving module for receiving messages from an information feed, each message associated with a tracking device coupled with an asset tracked by the asset management system;

a message queue for temporarily sorting the received messages into partial order groups of messages in which each partial order group includes messages associated with a group of related assets and related data records corresponding to the related assets, wherein sorting the received messages into partial order groups of messages further comprises;

determining a plurality of assets associated with a received message,

determining a subset of a plurality of individual queues associated with the plurality of assets,

preventing additional messages from entering the subset of individual queues,

merging the subset of individual queues to create a partial order group queue, and

directing the received message to the partial order group queue, and the message queue coupled to the receiving module; and

a message delivery module for processing the sorted messages in an order generated by the information feed, wherein there is at most a single message from a partial order group accessing the related data records corresponding to the related assets at any time, the message delivery module coupled to the message queue.

16. The apparatus of claim 15, wherein the message queue is a FIFO queue.

17. The apparatus of claim 15, wherein the apparatus further comprises a non-volatile storage device for storing state information and data.

18. The apparatus of claim 15, further comprising a process module communicatively coupled to the message queue and the message delivery queue, the process module for:

evaluating a message predicate associated with each message in the sorted messages;

halting processing and delivery of the message if the message predicate evaluates to false; and

continuing processing and delivery of the message if the message predicate evaluates to true.

19. A system for efficient message processing in an asset management system, the system comprising:

a front-end server, including a processor and a memory, for posting multi-threaded messages received from an information feed, each message associated with a tracking device coupled with an asset tracked by the asset management system;

a partial order message queue for receiving messages and sorting the messages into partial order groups of messages in which each partial order group includes messages associated with a group of related assets and related data records corresponding to the related assets, wherein sorting the received messages into partial order groups of messages further comprises;

determining a plurality of assets associated with a received message,

determining a subset of a plurality of individual queues associated with the plurality of assets,

preventing additional messages from entering the subset of individual queues,

merging the subset of individual queues to create a partial order group queue, and

directing the received message to the partial order group queue; and

a dispatcher for dispatching messages for processing from each of the partial order groups in an order generated by the information feed, wherein there is at most a single message from the partial order group accessing the related data records corresponding to the related assets at any time.

20. The system of claim 19, further comprising a data store communicatively coupled to the partial order message queue, for storing data associated with tracked assets.

21. The system of claim 19, further comprising a client communicatively coupled to the front-end server, for sending messages to the partial order message queue.

22. The system of claim 19, further comprising a server communicatively coupled to the dispatcher, for receiving messages from the partial order message queue.