High performance message store

• US 6,167,402 A
• Filed: 04/27/1998
• Issued: 12/26/2000
• Est. Priority Date: 04/27/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Yeager, William J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): TRINH, WILLIAM B
• Application Number:
  US09/067,537
• Time in Patent Office: 974 Days
• Field of Search: 707/10, 709/206, 709/207, 358/402
• US Class Current: 1/1
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers

Abstract

A product and method are disclosed for creating an efficient message store and delivery system is provided. A message store having an index directory, index file, and data bucket area, all of which are page based, is described. Each page corresponds to a period of time, such as a day. Each data bucket contains message data and the actual content of the message. The index file contains index file cells which store index information characterizing an associated message. The index directory contains index directory cells which store information on the location of an associated index file cell, and is thereby associated with a message. It also includes page based user folders each having user cells which reference a message, associated with a user, in the user store. A message includes a reference pointer to an associated index file cell and a reference pointer to an associated index directory cell. An index directory pointer in the user cell, an index file pointer in the index directory cell, a message pointer in the index file cell, and two pointers in the message allow the message store to reconstruct itself if necessary.

Claims

1. An Internet Message Access Protocol (IMAP) message store for storing email messages and related data comprising:

a plurality of calendar-based and page based data buckets, each data bucket being suitable for containing a plurality of messages received within a predetermined time period, thereby reducing the need to process a large body of messages;

a calendar-based and page based index file including one or more index file pages, each index file page of the index file suitable for containing a plurality of index file cells having variable length to allow for the addition of fields and index information capable under IMAP, each index file cell arranged to store index information characterizing an associated one of the messages including a message-analyzed field to indicate whether a message is in IMAP protocol, and each index file corresponding to the predetermined time period; and

a calendar-based and page based index directory including one or more index directory files, each index directory file corresponding to the predetermined time period, the index directory suitable for containing a plurality of index directory cells, each index directory cell arranged to store index directory information suitable for locating an associated index file cell, thereby being associated with the particular message associated with the index file cell;

wherein the index file and index directory allow for efficient use of IMAP indexing capabilities.

2. A message store as recited in claim 1 further comprising a plurality of calendar-based and page based user folders, each user folder being associated with a user and suitable for containing a plurality of user cells, each user cell being arranged to reference a message received within the predetermined time period associated with the user.

3. A message store as recited in claim 2 wherein each user cell includes a first index directory reference pointer to an index directory cell relating such user cell to its referenced message.

4. A message store as recited in claim 3 wherein each user cell further includes a user folder identifier indicative of which user folder contains the user cell.

5. A message store as recited in claim 3 wherein each user cell further includes an arrival time indicative of the time a referenced message arrives in the message store.

6. A message store as recited in claim 2 wherein each user folder includes a total size value indicative of the size of the message.

7. A message store as recited in claim 6 wherein each user folder further includes a next unique identifier for identifying a new user cell.

8. A message store as recited in claim 7 wherein each user folder further includes a last write date indicative of the date the most recent message referenced by the user folder was written to the message store.

9. A message store as recited in claim 6 wherein each user folder further includes a message count indicative of the number of messages referenced in the user folder.

10. A message store as recited in claim 2 wherein each user folder is categorized according to a predetermined user based criteria.

11. A message store as recited in claim 1 wherein each index directory cell includes a reference counter indicative of the number of users that are currently referencing the associated message.

12. A message store recited in claim 1 wherein each index directory cell includes a first index file reference pointer to an associated index file cell.

13. A message store as recited in claim 12 wherein the first index file reference pointer includes an index file offset indicative of a location of the index file cell in the index file and an associated index file cell size indicative of the size of the index file cell.

14. A message store as recited in claim 1 further comprising an index directory header including a cell number counter indicative of the number of index directory cells in a particular index directory page.

15. A message store as recited in claim 14 wherein the index directory header further includes a next location indicative of a location in the index directory for a new index directory cell.

16. A message store as recited in claim 15 wherein the index directory header further includes a data bucket counter indicative of the number of data buckets being used by an index directory page.

17. A message store as recited in claim 1 wherein each index file cell includes an index file cell size indicative of the size of the index file cell thereby facilitating internal consistency testing.

18. A message store as recited in claim 1 wherein each index file cell includes a message pointer to the associated message in the associated data bucket.

19. A message store as recited in claim 18 wherein the message pointer includes a data bucket identifier, identifying a data bucket containing the associated message and a data bucket offset indicative of a location of the associated message in the identified data bucket.

20. A message store as recited in claim 1 wherein each index file cell includes an associated message size.

21. A message store as recited in claim 1 wherein each index file cell includes an associated message section offset list indicative of locations of message sections in an associated data bucket.

22. A message store as recited in claim 1 wherein a message is comprised of preamble data and message data, the message data including actual data conveyed by a user.

23. A message store as recited in claim 22 wherein:

the preamble data includes a message size indicative of the size of the message; and

the preamble data includes a second index file reference pointer to an associated index file cell.

24. A message store as recited in claim 22 wherein the preamble data includes a second index directory reference pointer to an associated index directory cell.

25. A message store as recited in claim 24 further comprising:

a first index directory reference pointer in a user cell;

a first index file reference pointer in an index directory cell;

a second index file reference pointer in the message; and

a message pointer in the index file cell;

wherein such pointers in combination with the second index directory reference pointer in the preamble data enable the message store to perform internal consistency testing and reconstruct pages of the message store is required.

26. A message store as recited in claim 24 further comprising:

a first index file reference pointer in an index directory cell;

a message pointer in the index file cell; and

a second index file reference pointer in the message;

wherein such pointers in combination with the second index directory reference pointer in the preamble data form a self-contained referencing mechanism within the data buckets, index file, and index directory.

27. A message store as recited in claim 22 wherein the preamble data includes a message sender name and a recipient count, the recipient count indicative of the number of users who reference the message.

28. A method of storing an incoming message in an Internet Message Access Protocol (IMAP) message store, the method comprising:

appending the incoming message, received within a predetermined time period, thereby reducing the need to process a large body of messages, to a calendar-based and page based data bucket portion of the IMAP message store, without substantially hindering access to existing messages in the IMAP message store;

indexing the incoming message thereby creating an index file cell and index directory, wherein the index file cell is of variable length to allow for the addition of fields and index information capable under IMAP and wherein all of the indexing is done while the incoming message is appended to the calendar-based and page based data bucket and wherein the index file cell and index directory correspond to the predetermined time period; and

appending the index file cell to an index file of the IMAP message store; and

appending the index file cell to the index directory, such that the index file and index directory allow for efficient use of indexing capabilities inherent in IMAP.

29. A method as recited in claim 28 wherein the incoming message is appended to the data bucket portion of the IMAP message store without hindering access to the index file of the IMAP message store.

30. A method as recited in claim 28 wherein indexing the incoming message further includes obtaining data on the data bucket portion of the IMAP message store to be included in the index file cell corresponding to the incoming message.

31. A method as recited in claim 28 further including restricting access to an unused section of the data bucket portion of the IMAP message store while the incoming message is appended to the data bucket portion of the IMAP message store.

32. A computer-readable medium on which is embodied an IMAP message store, the message store comprised of:

a plurality of calendar-based and page based data buckets, each data bucket being suitable for containing a plurality of messages received within a predetermined time period, thereby reducing the need to process a large body of messages;

a calendar-based and page based index file including one or more index file pages, each index file page of the index file suitable for containing a plurality of index file cells having variable length to allow for the addition of fields and index information capable under IMAP, each index file cell arranged to store index information characterizing an associated one of the messages including a message-analyzed field to indicate whether a message is in IMAP protocol, and each index file corresponding to the predetermined time period; and

a calendar-based and page based index directory including one or more index directory files, each index directory file corresponding to the predetermined time period, the index directory suitable for containing a plurality of index directory cells, each index directory cell arranged to store index directory information suitable for locating an associated index file cell, thereby being associated with the particular message associated with the index file cell;

wherein the index file and index directory allow for efficient use of IMAP indexing capabilities.

33. A computer-readable medium as recited in claim 32, further comprising:

a plurality of calendar-based and page based user folders, each user folder being associated with a user and suitable for containing a plurality of user cells, each user cell being arranged to reference a message received within the predetermined time period associated with the user.

34. A computer-readable medium as recited in claim 33 wherein each user cell includes a first index directory reference pointer to an index directory cell thereby relating such user cell to its referenced message.

35. A computer-readable medium as recited in claim 34 wherein each user cell further includes a user folder identifier indicative of which user folder contains the user cell.

36. A computer-readable medium containing programming instructions for storing an incoming message in an IMAP message store, the computer-readable medium comprising computer program code devices configured to cause a computer to execute the steps of:

appending the incoming message, received within a predetermined time period, thereby reducing the need to process a large body of messages, to a calendar-based and page based data bucket portion of the IMAP message store, without substantially hindering access to existing messages in the IMAP message store;

indexing the incoming message thereby creating an index file cell and index directory, wherein the index file cell is of variable length to allow for the addition of fields and index information capable under IMAP and wherein all of the indexing is done while the incoming message is appended to the calendar-based and page based data bucket and wherein the index file cell and index directory correspond to the predetermined time period; and

appending the index file cell to an index file of the IMAP message store; and

appending the index file cell to the index directory, such that the index file and index directory allow for efficient use of indexing capabilities inherent in IMAP.

37. A computer-readable medium as recited in claim 36 further comprising computer program code devices configured to cause a computer to execute the step of restricting access to an unused section of the data bucket portion of the message store while the incoming message is appended to the data bucket portion of the message store.

38. A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause the processor to store an incoming message in a message store by performing the steps of:

appending the incoming message, received within a predetermined time period, thereby reducing the need to process a large body of messages, to a calendar-based and page based data bucket portion of the IMAP message store, without substantially hindering access to existing messages in the IMAP message store;

indexing the incoming message thereby creating an index file cell and index directory, wherein the index file cell is of variable length to allow for the addition of fields and index information capable under IMAP and wherein all of the indexing is done while the incoming message is appended to the calendar-based and page based data bucket and wherein the index file cell and index directory correspond to the predetermined time period; and

appending the index file cell to an index file of the IMAP message store; and

appending the index file cell to the index directory, such that the index file and index directory allow for efficient use of indexing capabilities inherent in IMAP.