Electronic mail system with methodology providing distributed message store

• US 7,117,246 B2
• Filed: 12/12/2000
• Issued: 10/03/2006
• Est. Priority Date: 02/22/2000
• Status: Active Grant

• Current Assignee: Proofpoint Incorporated
• Original Assignee: Sendmail Incorporated (Proofpoint Incorporated)
• Inventors: Larson, James Stephen, Christenson, Nikolai Paul, Fritchie, Scott Ernest Lystig
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Assistant Examiner(s): LEZAK, ARRIENNE M
• Application Number:
  US09/735,130
• Publication Number:
  US 20020112008A1
• Time in Patent Office: 2,121 Days
• Field of Search: 709201-253, 707 1- 10, 707100-1041, 707200-206, 714 1- 57, 714/100, 715/752
• US Class Current: 709/206
• CPC Class Codes: H04L 51/23 Reliability checks, e.g. acknowledgments or fault reporting
• CPC Class Codes: H04L 51/42 Mailbox-related aspects, e.g. synchronisation of mailboxes

Abstract

An electronic mail system with a methodology providing distributed message storage and processing is described. In particular, this methodology breaks up how the individual components of message data are stored. Message data itself is broken up into two parts: a metadata (mutable) portion, and an immutable portion. The metadata portion represents that part of the message data that may change over time. This includes message status flags (e.g., the IMAP “message deleted” flag) and the message'"'"'s position within a particular message folder, among other information. The immutable portion, which comprises the bulk of electronic mail data (namely, the message itself), once stored is never edited. Immutable data is written f+1 times on as many unique servers, to tolerate f number of server failures using Lampson'"'"'s stable storage algorithm. The metadata portion is stored 2f+1 times on as many unique servers to tolerate f number of server failures using quorum voting. Once the message has been stored once, instead of being copied, its location is passed around by reference. The system utilizes a two-tier architecture. One tier consists of servers which store message metadata and immutable data, the Data Servers, and servers that operating upon those data, the Access Servers. Message store integrity is maintained in the event of server failure and as the set of Data Servers changes. In the latter case, I/O and storage workloads are dynamically redistributed across Data Servers in an efficient way.

Claims

1. In an electronic mail (e-mail) system, a methodology for storing e-mail messages in a distributed manner across a plurality of data servers in order to tolerate f number of faults in a manner that allows the system to provide continuous operation, the method comprising:

for each e-mail message to be stored, dividing the message into a mutable portion and an immutable portion, said mutable portion comprising that portion of the message data which is subject to change after the message has been stored, said immutable portion comprising that portion of the message which is not subject to change after the message has been stored; and

storing the message in a distributed manner by;

redundantly storing the immutable portion of the message as immutable message data, f+1 times among selected ones of said data servers, in order to tolerate f number of failures in a manner that allows the system to provide continuous operation; and

redundantly storing the mutable portion of the message as mutable message data, 2f+1 tines among selected ones of said data servers, in order to tolerate f number failures in a manner that allows the system to provide continuous operation, said mutable portion including a mutable pointer indicating where the immutable message data is stored.

2. The method of claim 1, wherein said mutable portion includes message header information.

3. The method of claim 1, wherein said mutable portion includes status information for the message.

4. The method of claim 1, wherein said immutable portion comprises static message data for the message.

5. The method of claim 1, wherein said immutable portion comprises a message body.

6. The method of claim 4, wherein said immutable portion is stored using large block Input/Output (I/O) storage technique.

7. The method of claim 1, further comprising:

in case of a fault, restoring the message from stored copies of said mutable and immutable portions.

8. A computer-readable medium having processor-executable instructions for performing the method of claim 1.

9. A downloadable set of processor-executable instructions for performing the method of claim 1.

10. An improved method for storing messages in an electronic mail (e-mail) system that processes e-mail messages in order to support fault-tolerant operation in a manner that allows the system to provide continuous operation, the method comprising:

for a given e-mail message, identifying a first portion of the message that may be edited after the message has been stored and a second portion that may not be edited after the message has been stored;

redundantly storing the first portion of the message at least f+1 times among individual machines, to tolerate f number of failures in a manner that allows the system to provide continuous operation; and

redundantly storing the second portion of the message at least 2f+1 times among individual machines, to tolerate said f number of failures in a manner that allows the system to provide continuous operation.

11. The method of claim 10, wherein said first portion of the message that may be edited after the message has been stored is identified as a mutable portion.

12. The method of claim 11, wherein said mutable portion includes status flags for the message.

13. The method of claim 11, wherein said mutable portion is stored as metadata for the message.

14. The method of claim 11, wherein said mutable portion represents any part of the message that may be edited after the message has been stored.

15. The method of claim 10, wherein the second portion comprises an immutable portion of the message.

16. The method of claim 15, wherein said immutable portion represents any part of the message that will not be edited after the message has been stored.

17. The method of claim 15, wherein said immutable portion comprises most of the message'"'"'s data.

18. The method of claim 15, wherein the message stores its message content in a message body, and wherein said immutable portion stores the message'"'"'s message body.

19. The method of claim 11, further comprising:

using a pointer for identifying an immutable portion that has been stored separately from the message.

20. The method of claim 10, further comprising:

in the presence of a fault, restoring the message.

21. The method of claim 20, wherein said restoring step includes:

restoring the message by retrieving a copy of the first portion.

22. The method of claim 20, wherein said restoring step includes:

restoring the message by retrieving a copy of the second portion.

23. The method of claim 20, wherein said restoring step includes:

retrieving multiple copies of the second portion; and

based on said multiple copies, deriving a correct copy of the second portion based on a consensus of said multiple copies of the second portion.

24. The method of claim 23, wherein said deriving step includes:

subjecting said multiple copies to quorum voting for deriving the correct copy.

25. The method of claim 10, wherein said second portion is stored using large-block Input/Output (I/O).

26. The method of claim 10, wherein f equals 1, and wherein said first portion is stored twice and said second portion is stored three times.

27. The method of claim 10, wherein actual processing of the message for e-mail delivery occurs via reference.

28. The method of claim 10, wherein said second portion comprises message metadata having a size that is independent of the message'"'"'s size.

29. A computer-readable medium having processor-executable instructions for performing the method of claim 10.

30. A downloadable set of processor-executable instructions for performing the method of claim 10.

31. A two-tier e-mail system comprising:

a first tier comprising a plurality of access servers for communicating with clients over the Internet via standard protocols, wherein said first tier is connected directly to the Internet;

a second tier comprising a plurality of data servers for storing e-mail messages redundantly, wherein said second tier is shielded from direct connection to the Internet so as to prevent malicious packets from reaching the data servers from the Internet wherein said data servers spread storage of replicated copies of e-mail message data across all data servers to protect against failures that cause loss of a particular data server, and wherein said access servers communicate with said data servers over a data network and manage redundant storage of objects across the data servers; and

program logic for instructing the data servers to store e-mail messages redundantly in order to provide fault-tolerant operation in a manner that allows the system to provide continuous operation, wherein, in order to tolerate f number of failures, each e-mail message is divided into an immutable portion stored at least f+1 times among selected ones of said data servers and a mutable portion stored at least 2f+1 times among selected ones of said data servers.

32. The system of claim 31, wherein said standard protocols include selected ones of POP, SMTP, and LMAP.

33. The system of claim 31, wherein said access servers include at least one network interface on the Internet.

34. The system of claim 31, wherein said data network comprises a redundant data network.

35. The system of claim 34, wherein said data network includes a Gigabit Ethernet network.

36. The system of claim 31, wherein said access servers run programs providing e-mail services to clients on the Internet.

37. The system of claim 31, further comprising a separate command server responsible for administrative tasks.

38. The system of claim 37, wherein said command server is not necessary for operation of the system.

39. The system of claim 31, wherein an immutable portion for a given e-mail message is associated with a corresponding mutable portion via a pointer.

40. The system of claim 31, further comprising:

program logic for restoring messages from redundantly-stored copies of said immutable and mutable portions.