Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Hi, Actually, Hazelcast gives up consistency upon network partition. This mean any implementation will experience random behavior when using MESSAGE SEQUENCE number during a partition (and this is also true for deletions). In my opinion, it does not really add guaranties compoared to Cassandra, (maybe reduce inconsistency window as operations are expected to be faster) Moreover, I don't really like the idea of adding yet an other middleware. Note : Hazelcast is a great option if we want to implement a distributed cache mechanism. I guess this is an other issue. Le 10/11/2015 13:47, Eric Charles a écrit : > Would a distributed im-memory backend such as hazelcast be an option to > start? > > http://docs.hazelcast.org/docs/3.5/manual/html/licenses.html > > On 2015-10-26 14:51, Benoit Tellier wrote: >> >> >> Le 26/10/2015 14:08, Matthieu Baechler a écrit : >>> >>> >>> On 26/10/2015 13:53, Benoit Tellier wrote: >>> >>> [...] >>> > I think we could create a Session row that map MESSAGE SEQUENCE NUMBER > to the real messages. Then, for a given session, we never remap > things, > we only add messages to this row. In case of EXPUNGE, we create a new > row that won't be used until a new session is open. Message Sequence Number are defined as mutable by the RFC. Having them being immutable look like non RFC compliant to me. I mean, the idea is nice, but client using MESSAGE SEQUENCE NUMBERS won't be designed to work this way, I think. https://tools.ietf.org/html/rfc3501#section-2.3.1.2 >>> >>> Let's quote it : >>> >>> Message sequence numbers can be reassigned during the session. For >>> example, when a message is permanently removed (expunged) from the >>> mailbox, the message sequence number for all subsequent messages is >>> decremented. The number of messages in the mailbox is also >>> decremented. Similarly, a new message can be assigned a message >>> sequence number that was once held by some other message prior to an >>> expunge. >>> >>> The only way to reassign Message sequence numbers is EXPUNGED messages. >> >> I agree on your last sentence : "The only way to reassign Message >> sequence numbers is EXPUNGED messages." >> >> The criticism was on this sentence : "In case of EXPUNGE, we create a >> new row that won't be used until a new session is open." >> >> It seems opposed to the RFC, where, from my understanding, the client >> can assume the message sequence number for all subsequent messages to be >> decremented right after his request. >> >>> > > That way, a client can't use a MESSAGE SEQUENCE NUMBER wrongly because > it always maps to a given message. With the model you suggest, I understand that a Session Row stops from being used only when a clients is disconnected. It represents his view of the correspondence on his mailbox selection moment. He use it until he is disconnected. Is this what you suggest ? >>> >>> Somehow. >>> > Do you get it ? > Hence, as it is immutable, he can not address added messages after this selection using MESSAGE SEQUENCE NUMBERS as these changes will be visible upon re-selection. Look like a problem to me... >>> >>> That's not correct : you can add messages to this view. >> >> You are right. I thought, from what you explained that message were only >> added to the future session. >> >>> Also, you have data races unless you manage APPEND and EXPUNGE operations in atomic way. This means MESSAGE SEQUENCE NUMBERS should be included in the process. This means, to have a data race free implementation, we need the mailbox manager to handle MESSAGE SEQUENCE NUMBER consistency, and not the protocol part, that did it threw the event system. Do we agree on this ? >>> >>> What race condition do you think about ? I mean, any mapping should be >>> ok, it can even be generated asynchronously as long as you assign an >>> existing mapping to a given session. >> >> I meant this. >> >> Todays implementation works in two steps : >> >> 1 : Update the database >> 2 : From the event generated from the database, update the mapping. >> >> Consider the following mapping : >> >> UID | 2 | 4 | 6 | 8 | >> - >> MSN | 1 | 2 | 3 | 4 | >> >> Bobs issue these commands, in this order : >> >> Command 1 : EXPUNGE 1 >> Command 2 : EXPUNGE 2 >> >> The expected result is : >> >> UID | 4 | 8 | >> - >> MSN | 1 | 2 | >> >> Because the client can assume that after executing command 1 mapping >> will be : >> >> UID | 4 | 6 | 8 | >> - >> MSN | 1 | 2 | 3 | >> >> Now, because the mapping update and the EXPUNGE completion are >> dissociated, mapping update might not have been done (delay in event >> delivery, a long MailboxListener preceding the SelectedMailboxImpl, >> etc... ) >> >> Hence the result might look like : >> >> UID | 6 | 8 | >> - >> MSN
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Would a distributed im-memory backend such as hazelcast be an option to start? http://docs.hazelcast.org/docs/3.5/manual/html/licenses.html On 2015-10-26 14:51, Benoit Tellier wrote: Le 26/10/2015 14:08, Matthieu Baechler a écrit : On 26/10/2015 13:53, Benoit Tellier wrote: [...] I think we could create a Session row that map MESSAGE SEQUENCE NUMBER to the real messages. Then, for a given session, we never remap things, we only add messages to this row. In case of EXPUNGE, we create a new row that won't be used until a new session is open. Message Sequence Number are defined as mutable by the RFC. Having them being immutable look like non RFC compliant to me. I mean, the idea is nice, but client using MESSAGE SEQUENCE NUMBERS won't be designed to work this way, I think. https://tools.ietf.org/html/rfc3501#section-2.3.1.2 Let's quote it : Message sequence numbers can be reassigned during the session. For example, when a message is permanently removed (expunged) from the mailbox, the message sequence number for all subsequent messages is decremented. The number of messages in the mailbox is also decremented. Similarly, a new message can be assigned a message sequence number that was once held by some other message prior to an expunge. The only way to reassign Message sequence numbers is EXPUNGED messages. I agree on your last sentence : "The only way to reassign Message sequence numbers is EXPUNGED messages." The criticism was on this sentence : "In case of EXPUNGE, we create a new row that won't be used until a new session is open." It seems opposed to the RFC, where, from my understanding, the client can assume the message sequence number for all subsequent messages to be decremented right after his request. That way, a client can't use a MESSAGE SEQUENCE NUMBER wrongly because it always maps to a given message. With the model you suggest, I understand that a Session Row stops from being used only when a clients is disconnected. It represents his view of the correspondence on his mailbox selection moment. He use it until he is disconnected. Is this what you suggest ? Somehow. Do you get it ? Hence, as it is immutable, he can not address added messages after this selection using MESSAGE SEQUENCE NUMBERS as these changes will be visible upon re-selection. Look like a problem to me... That's not correct : you can add messages to this view. You are right. I thought, from what you explained that message were only added to the future session. Also, you have data races unless you manage APPEND and EXPUNGE operations in atomic way. This means MESSAGE SEQUENCE NUMBERS should be included in the process. This means, to have a data race free implementation, we need the mailbox manager to handle MESSAGE SEQUENCE NUMBER consistency, and not the protocol part, that did it threw the event system. Do we agree on this ? What race condition do you think about ? I mean, any mapping should be ok, it can even be generated asynchronously as long as you assign an existing mapping to a given session. I meant this. Todays implementation works in two steps : 1 : Update the database 2 : From the event generated from the database, update the mapping. Consider the following mapping : UID | 2 | 4 | 6 | 8 | - MSN | 1 | 2 | 3 | 4 | Bobs issue these commands, in this order : Command 1 : EXPUNGE 1 Command 2 : EXPUNGE 2 The expected result is : UID | 4 | 8 | - MSN | 1 | 2 | Because the client can assume that after executing command 1 mapping will be : UID | 4 | 6 | 8 | - MSN | 1 | 2 | 3 | Now, because the mapping update and the EXPUNGE completion are dissociated, mapping update might not have been done (delay in event delivery, a long MailboxListener preceding the SelectedMailboxImpl, etc... ) Hence the result might look like : UID | 6 | 8 | - MSN | 1 | 2 | We have deleted the wrong message. Now, reading this : https://tools.ietf.org/html/rfc3501#section-5.5 You might argue that these two operations are ambiguous... However, we have two possible outcomes out of this commands sequence depending on the timing. This is what I call a data race. If you want, I can write an MPT test for this. A friend (Erwan Guyomarc'h), who is working on James with me, suggested an other solution. It has its problems, but I put it here as it is interesting... Suppose we have a at least one delivery distributed event system. The idea is, instead of maintaining a double index between UID and Message Sequence Number, we only store on each SelectedMailboxImpl an uid set. ADDED events is an insertion on this set EXPUNGE events is a deletion on this set Of course these operations are not CRDT. The problem comes from ADDED operation being reordered after EXPUNGED operations. ADDEDD 7 EXPUNGED 7 is not equivalent to EXPUNGED 7 ADDED 7 Now assume we have a causal order. We
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Hi Matthieu, Thanks for your reply. I think this problem might be a quite taught one. First of all, I guess you are right on why clients prefer using UID * commands. I noticed it with thunderbird. You are right about the consistency model of message queues (hence having this discussion). You are right about Option 1 a). Read might be invalidated. So if I get your point, sounds like you prefer option 2 :-) I also think this is the only viable option. I have doubts about the Cassandra implementation thought... I mean, let's imagine I have the Message Sequence Number attached to the message. Let's imagine bob deletes an e-mail. James will issue a DELETE for the message then an UPDATE for following MESSAGE SEQUENCE NUMBER. For the update, it appears atomic. But we got two instructions, hence concurrent problems. Wide rows won't protect us. The point is, to ensure Message Sequence Number stay consistent, we are compelled to have R + W > N ... Hence latencies, and unavailability on network partition either on reads or rights. Oh and we can have MESSAGE SEQUENCE NUMBER is dangerous on concurrent sessions. Imagine the following scenario : - Bob open a session and select MAILBOX - Bob deletes message with MESSAGE SEQUENCE NUMBER 1 - His mailbox is updated, and the ADDED event fired - The added event went threw the MailboxListener chain and is treated by a slow MailboxListener. Let's say indexation using LUCENE. - In the mean time, Bob deletes message with MESSAGE SEQUENCE NUMBER 2. - As the event from the first deletion is not yet fired on his session due to slow listener, we are using a wrong UID => MESSAGE SEQUENCE number, hence delete the wrong message. I definitely need to write a MPT test to highlight that. What we get from this simple example is that MESSAGE SEQUENCE NUMBER can not be dissociated from the mailbox. Seriously, I think dropping MESSAGE SEQUENCE NUMBER and returning an error on distributed implementation is our simplest walk-around on this topic... Doing overwise demands to add capabilities to the MessageManager to handle MESSAGE SEQUENCE NUMBER with really tricky code. Le 26/10/2015 10:15, Matthieu Baechler a écrit : Hi Benoit, See my comments below. On 26/10/2015 01:11, Tellier Benoit wrote: [...] Well, I have troubles to see how to make this work in a distributed system. Message systems do not offer perfect guaranties and we might get a lot of troubles in case of network partitions. Double event delivery, or no event delivery at all might arise. It is not that bad with IDLE, but can lead SelectedMailboxImpl to be inconsistent. You can actually choose between double delivery and lost messages : if you go for ACK (synchronous delivery), you can have double delivery for example, but no message lost. It introduces latency but you can be sure you won't lost any message. I guess we have several options : # Go stateless on this (note : only for distributed implementation) ## Option 1 - We can recompute the correspondence between UID and Message Sequence Number each time a message sequence number is used. It might cost compute and network resources. But no node stores specific data. We can imagine give a configuration option, that gives the choice between the two options. Depending on the implementation, we get different trade-off : Option 1 a) On a read request using Message Sequence Number, select all the data (all the message content) from the database, and select the message we want. It is consistent but highly ineffective. It's not even consistent in my opinion Note : this works for Reads, but not deletions... Option 1 b) On a read request we first fetch the mailbox to have informations about the UID to be used, and then gets the message data. But due to delay between read and write, our information can become inconsistent. Thus we can do some serious damages (eg : delete the wrong message) ## Option 2 - Store the message sequence number and update it. To do this in a consistent way, we need a CP data store with the notion of transaction and attach the Message Sequence Number directly to the Message, stored in the database. Cassandra is either CP or AP with configurable consistency and you don't always need transaction, sometimes atomicity is enough (and you have it on a single row). It works, we have ineffective queries like **UPDATE messages SET seq_number = seq_number - 1 WHERE seq_number > deleted AND mailboxId=159**. We might have to handle transaction that fails to commit. Option 2 is still dangerous on databases that lacks the notion of transaction. For example a process can crash before updating the sequence number. On Cassandra and other AP data stores, we have consistencies problems on concurrent updates of sequence number (might lead to a wrong result, and even messages having the same sequence number). Other note : adding a message requires to know the last UID used for a mailbox that
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
On 26/10/2015 10:54, Benoit Tellier wrote: [...] Seriously, I think dropping MESSAGE SEQUENCE NUMBER and returning an error on distributed implementation is our simplest walk-around on this topic... Doing overwise demands to add capabilities to the MessageManager to handle MESSAGE SEQUENCE NUMBER with really tricky code. The real problem is about deletion because addition can be managed by the atomic row trick and immutable datamodel. I think we could create a Session row that map MESSAGE SEQUENCE NUMBER to the real messages. Then, for a given session, we never remap things, we only add messages to this row. In case of EXPUNGE, we create a new row that won't be used until a new session is open. That way, a client can't use a MESSAGE SEQUENCE NUMBER wrongly because it always maps to a given message. Do you get it ? -- Matthieu Baechler - To unsubscribe, e-mail: server-dev-unsubscr...@james.apache.org For additional commands, e-mail: server-dev-h...@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Hi Benoit, See my comments below. On 26/10/2015 01:11, Tellier Benoit wrote: [...] Well, I have troubles to see how to make this work in a distributed system. Message systems do not offer perfect guaranties and we might get a lot of troubles in case of network partitions. Double event delivery, or no event delivery at all might arise. It is not that bad with IDLE, but can lead SelectedMailboxImpl to be inconsistent. You can actually choose between double delivery and lost messages : if you go for ACK (synchronous delivery), you can have double delivery for example, but no message lost. It introduces latency but you can be sure you won't lost any message. I guess we have several options : # Go stateless on this (note : only for distributed implementation) ## Option 1 - We can recompute the correspondence between UID and Message Sequence Number each time a message sequence number is used. It might cost compute and network resources. But no node stores specific data. We can imagine give a configuration option, that gives the choice between the two options. Depending on the implementation, we get different trade-off : Option 1 a) On a read request using Message Sequence Number, select all the data (all the message content) from the database, and select the message we want. It is consistent but highly ineffective. It's not even consistent in my opinion Note : this works for Reads, but not deletions... Option 1 b) On a read request we first fetch the mailbox to have informations about the UID to be used, and then gets the message data. But due to delay between read and write, our information can become inconsistent. Thus we can do some serious damages (eg : delete the wrong message) ## Option 2 - Store the message sequence number and update it. To do this in a consistent way, we need a CP data store with the notion of transaction and attach the Message Sequence Number directly to the Message, stored in the database. Cassandra is either CP or AP with configurable consistency and you don't always need transaction, sometimes atomicity is enough (and you have it on a single row). It works, we have ineffective queries like **UPDATE messages SET seq_number = seq_number - 1 WHERE seq_number > deleted AND mailboxId=159**. We might have to handle transaction that fails to commit. Option 2 is still dangerous on databases that lacks the notion of transaction. For example a process can crash before updating the sequence number. On Cassandra and other AP data stores, we have consistencies problems on concurrent updates of sequence number (might lead to a wrong result, and even messages having the same sequence number). Other note : adding a message requires to know the last UID used for a mailbox that stills correspond to an existing message. Here we have two options : store it or recompute it. In both case we have troubles without the notion of transactions. I think you can achieve what you would do with transactions based on row atomicity. There are two design tricks you can leverage : 1. model things with immutability in mind. You can create a row that contains all indices and then change the Mailbox entry to point to this new row (that gives you a commit semantic). 2. use wide rows to get atomicity on a list of things. [ ... lot of ideas ... ] I have troubles thinking about any implementation that would work : even with an IDLE channel open, how an IMAP client is supposed to handle message deletion AT ALL ? I mean, I want to delete message 12 but message 11 is deleted at the same time from another user or device : there's no way to be sure what is message 12 from the client point of view. Maybe just every single IMAP client uses UID for these reasons ? -- Matthieu Baechler - To unsubscribe, e-mail: server-dev-unsubscr...@james.apache.org For additional commands, e-mail: server-dev-h...@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Le 26/10/2015 11:08, Matthieu Baechler a écrit : On 26/10/2015 10:54, Benoit Tellier wrote: [...] Seriously, I think dropping MESSAGE SEQUENCE NUMBER and returning an error on distributed implementation is our simplest walk-around on this topic... Doing overwise demands to add capabilities to the MessageManager to handle MESSAGE SEQUENCE NUMBER with really tricky code. The real problem is about deletion because addition can be managed by the atomic row trick and immutable datamodel. We completely agree. I think we could create a Session row that map MESSAGE SEQUENCE NUMBER to the real messages. Then, for a given session, we never remap things, we only add messages to this row. In case of EXPUNGE, we create a new row that won't be used until a new session is open. Message Sequence Number are defined as mutable by the RFC. Having them being immutable look like non RFC compliant to me. I mean, the idea is nice, but client using MESSAGE SEQUENCE NUMBERS won't be designed to work this way, I think. https://tools.ietf.org/html/rfc3501#section-2.3.1.2 That way, a client can't use a MESSAGE SEQUENCE NUMBER wrongly because it always maps to a given message. With the model you suggest, I understand that a Session Row stops from being used only when a clients is disconnected. It represents his view of the correspondence on his mailbox selection moment. He use it until he is disconnected. Is this what you suggest ? Do you get it ? Hence, as it is immutable, he can not address added messages after this selection using MESSAGE SEQUENCE NUMBERS as these changes will be visible upon re-selection. Look like a problem to me... Also, you have data races unless you manage APPEND and EXPUNGE operations in atomic way. This means MESSAGE SEQUENCE NUMBERS should be included in the process. This means, to have a data race free implementation, we need the mailbox manager to handle MESSAGE SEQUENCE NUMBER consistency, and not the protocol part, that did it threw the event system. Do we agree on this ? A friend (Erwan Guyomarc'h), who is working on James with me, suggested an other solution. It has its problems, but I put it here as it is interesting... Suppose we have a at least one delivery distributed event system. The idea is, instead of maintaining a double index between UID and Message Sequence Number, we only store on each SelectedMailboxImpl an uid set. ADDED events is an insertion on this set EXPUNGE events is a deletion on this set Of course these operations are not CRDT. The problem comes from ADDED operation being reordered after EXPUNGED operations. ADDEDD 7 EXPUNGED 7 is not equivalent to EXPUNGED 7 ADDED 7 Now assume we have a causal order. We also have the certitude to see only one ADDED event per UID. If we reject EXPUNGE commands if the specified uid is absent from the SelecteMailboxImpl uid set. We might have concurrent problems, but with this we have an eventual consistent MESSAGE SEQUENCE NUMBERS <=> UID correspondance across servers. Of course with this solution the difficulty is to have causal ordering. Which means vector clocks... - To unsubscribe, e-mail: server-dev-unsubscr...@james.apache.org For additional commands, e-mail: server-dev-h...@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Le 26/10/2015 14:08, Matthieu Baechler a écrit : On 26/10/2015 13:53, Benoit Tellier wrote: [...] I think we could create a Session row that map MESSAGE SEQUENCE NUMBER to the real messages. Then, for a given session, we never remap things, we only add messages to this row. In case of EXPUNGE, we create a new row that won't be used until a new session is open. Message Sequence Number are defined as mutable by the RFC. Having them being immutable look like non RFC compliant to me. I mean, the idea is nice, but client using MESSAGE SEQUENCE NUMBERS won't be designed to work this way, I think. https://tools.ietf.org/html/rfc3501#section-2.3.1.2 Let's quote it : Message sequence numbers can be reassigned during the session. For example, when a message is permanently removed (expunged) from the mailbox, the message sequence number for all subsequent messages is decremented. The number of messages in the mailbox is also decremented. Similarly, a new message can be assigned a message sequence number that was once held by some other message prior to an expunge. The only way to reassign Message sequence numbers is EXPUNGED messages. I agree on your last sentence : "The only way to reassign Message sequence numbers is EXPUNGED messages." The criticism was on this sentence : "In case of EXPUNGE, we create a new row that won't be used until a new session is open." It seems opposed to the RFC, where, from my understanding, the client can assume the message sequence number for all subsequent messages to be decremented right after his request. That way, a client can't use a MESSAGE SEQUENCE NUMBER wrongly because it always maps to a given message. With the model you suggest, I understand that a Session Row stops from being used only when a clients is disconnected. It represents his view of the correspondence on his mailbox selection moment. He use it until he is disconnected. Is this what you suggest ? Somehow. Do you get it ? Hence, as it is immutable, he can not address added messages after this selection using MESSAGE SEQUENCE NUMBERS as these changes will be visible upon re-selection. Look like a problem to me... That's not correct : you can add messages to this view. You are right. I thought, from what you explained that message were only added to the future session. Also, you have data races unless you manage APPEND and EXPUNGE operations in atomic way. This means MESSAGE SEQUENCE NUMBERS should be included in the process. This means, to have a data race free implementation, we need the mailbox manager to handle MESSAGE SEQUENCE NUMBER consistency, and not the protocol part, that did it threw the event system. Do we agree on this ? What race condition do you think about ? I mean, any mapping should be ok, it can even be generated asynchronously as long as you assign an existing mapping to a given session. I meant this. Todays implementation works in two steps : 1 : Update the database 2 : From the event generated from the database, update the mapping. Consider the following mapping : UID | 2 | 4 | 6 | 8 | - MSN | 1 | 2 | 3 | 4 | Bobs issue these commands, in this order : Command 1 : EXPUNGE 1 Command 2 : EXPUNGE 2 The expected result is : UID | 4 | 8 | - MSN | 1 | 2 | Because the client can assume that after executing command 1 mapping will be : UID | 4 | 6 | 8 | - MSN | 1 | 2 | 3 | Now, because the mapping update and the EXPUNGE completion are dissociated, mapping update might not have been done (delay in event delivery, a long MailboxListener preceding the SelectedMailboxImpl, etc... ) Hence the result might look like : UID | 6 | 8 | - MSN | 1 | 2 | We have deleted the wrong message. Now, reading this : https://tools.ietf.org/html/rfc3501#section-5.5 You might argue that these two operations are ambiguous... However, we have two possible outcomes out of this commands sequence depending on the timing. This is what I call a data race. If you want, I can write an MPT test for this. A friend (Erwan Guyomarc'h), who is working on James with me, suggested an other solution. It has its problems, but I put it here as it is interesting... Suppose we have a at least one delivery distributed event system. The idea is, instead of maintaining a double index between UID and Message Sequence Number, we only store on each SelectedMailboxImpl an uid set. ADDED events is an insertion on this set EXPUNGE events is a deletion on this set Of course these operations are not CRDT. The problem comes from ADDED operation being reordered after EXPUNGED operations. ADDEDD 7 EXPUNGED 7 is not equivalent to EXPUNGED 7 ADDED 7 Now assume we have a causal order. We also have the certitude to see only one ADDED event per UID. If we reject EXPUNGE commands if the specified uid is absent from the SelecteMailboxImpl uid set. We might
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
On 26/10/2015 13:53, Benoit Tellier wrote: [...] I think we could create a Session row that map MESSAGE SEQUENCE NUMBER to the real messages. Then, for a given session, we never remap things, we only add messages to this row. In case of EXPUNGE, we create a new row that won't be used until a new session is open. Message Sequence Number are defined as mutable by the RFC. Having them being immutable look like non RFC compliant to me. I mean, the idea is nice, but client using MESSAGE SEQUENCE NUMBERS won't be designed to work this way, I think. https://tools.ietf.org/html/rfc3501#section-2.3.1.2 Let's quote it : Message sequence numbers can be reassigned during the session. For example, when a message is permanently removed (expunged) from the mailbox, the message sequence number for all subsequent messages is decremented. The number of messages in the mailbox is also decremented. Similarly, a new message can be assigned a message sequence number that was once held by some other message prior to an expunge. The only way to reassign Message sequence numbers is EXPUNGED messages. That way, a client can't use a MESSAGE SEQUENCE NUMBER wrongly because it always maps to a given message. With the model you suggest, I understand that a Session Row stops from being used only when a clients is disconnected. It represents his view of the correspondence on his mailbox selection moment. He use it until he is disconnected. Is this what you suggest ? Somehow. Do you get it ? Hence, as it is immutable, he can not address added messages after this selection using MESSAGE SEQUENCE NUMBERS as these changes will be visible upon re-selection. Look like a problem to me... That's not correct : you can add messages to this view. Also, you have data races unless you manage APPEND and EXPUNGE operations in atomic way. This means MESSAGE SEQUENCE NUMBERS should be included in the process. This means, to have a data race free implementation, we need the mailbox manager to handle MESSAGE SEQUENCE NUMBER consistency, and not the protocol part, that did it threw the event system. Do we agree on this ? What race condition do you think about ? I mean, any mapping should be ok, it can even be generated asynchronously as long as you assign an existing mapping to a given session. A friend (Erwan Guyomarc'h), who is working on James with me, suggested an other solution. It has its problems, but I put it here as it is interesting... Suppose we have a at least one delivery distributed event system. The idea is, instead of maintaining a double index between UID and Message Sequence Number, we only store on each SelectedMailboxImpl an uid set. ADDED events is an insertion on this set EXPUNGE events is a deletion on this set Of course these operations are not CRDT. The problem comes from ADDED operation being reordered after EXPUNGED operations. ADDEDD 7 EXPUNGED 7 is not equivalent to EXPUNGED 7 ADDED 7 Now assume we have a causal order. We also have the certitude to see only one ADDED event per UID. If we reject EXPUNGE commands if the specified uid is absent from the SelecteMailboxImpl uid set. We might have concurrent problems, but with this we have an eventual consistent MESSAGE SEQUENCE NUMBERS <=> UID correspondance across servers. Of course with this solution the difficulty is to have causal ordering. Which means vector clocks... It means creating the set for every selected mailbox : it looks like a performance killer, don't you think ? -- Matthieu Baechler - To unsubscribe, e-mail: server-dev-unsubscr...@james.apache.org For additional commands, e-mail: server-dev-h...@james.apache.org
Fwd: A distributed James server and SelectedMailboxImpl statefulness
Disclaimer : the following message is long, and might take time to read, but I think this is a topic we have to exchange on in order to have a working James in a distributed environment... = Hi every one, I am working on a distributed event system for the mailbox. The idea is to make the IDLE functionality work with an arbitrary large number of servers. To work on this feature, I had a look to the different types of MailboxListener. I found this one : SelectedMailboxImpl. SelectedMailboxImpl is stateful : it maintains (among other things) the correspondence between UIDs and Message Sequence Number ( called message index in SelectedMailbox ). When the mailbox is first selected, all the UIDs and flags for message in this mailbox are fetch and used to compute the UID for the given Message Sequence Number. The actual index is event updated using the mailbox event system. Well, I have troubles to see how to make this work in a distributed system. Message systems do not offer perfect guaranties and we might get a lot of troubles in case of network partitions. Double event delivery, or no event delivery at all might arise. It is not that bad with IDLE, but can lead SelectedMailboxImpl to be inconsistent. I guess we have several options : # Go stateless on this (note : only for distributed implementation) ## Option 1 - We can recompute the correspondence between UID and Message Sequence Number each time a message sequence number is used. It might cost compute and network resources. But no node stores specific data. We can imagine give a configuration option, that gives the choice between the two options. Depending on the implementation, we get different trade-off : Option 1 a) On a read request using Message Sequence Number, select all the data (all the message content) from the database, and select the message we want. It is consistent but highly ineffective. Note : this works for Reads, but not deletions... Option 1 b) On a read request we first fetch the mailbox to have informations about the UID to be used, and then gets the message data. But due to delay between read and write, our information can become inconsistent. Thus we can do some serious damages (eg : delete the wrong message) ## Option 2 - Store the message sequence number and update it. To do this in a consistent way, we need a CP data store with the notion of transaction and attach the Message Sequence Number directly to the Message, stored in the database. It works, we have ineffective queries like **UPDATE messages SET seq_number = seq_number - 1 WHERE seq_number > deleted AND mailboxId=159**. We might have to handle transaction that fails to commit. Option 2 is still dangerous on databases that lacks the notion of transaction. For example a process can crash before updating the sequence number. On Cassandra and other AP data stores, we have consistencies problems on concurrent updates of sequence number (might lead to a wrong result, and even messages having the same sequence number). Other note : adding a message requires to know the last UID used for a mailbox that stills correspond to an existing message. Here we have two options : store it or recompute it. In both case we have troubles without the notion of transactions. # Keep it stateful ## Option 3 : - Say that a mailbox should be handled by a single James. This can't be achieved threw load balancing. Here is a little user story that shows it : Bob and Alice uses James. Bob give the right to Alice to see and add messages to his INBOX Bob and Alice are handled by different servers. Bob is on James 1 and Alice on James 2. All there new connections will go to these server. Bob connects to his INBOX. Alice connects to Bob's INBOX. Problem. Collocating Bob and Alice ( and more generally user sharing rights) is hard but also impossible, as this graph might not be disconnected. The solution with this option might be to proxy Alice commands related to Bob INBOX selection to Bob's server. To do this, we need to know which server is in charge of Bob. A solution might be Consistent Hashing, but it is complicated to implement. Without such a thing, sharing mailboxes across users might be difficult. With this option we have other concerns : - How is our solution better than a Cyrus implementation if we have the same load balancing troubles ? - We should document how to deploy such a load balancer Obviously, with this, we do not need the distributed event system... ## Option 4 Don't care. I don't like this one. Even if inconsistent sequence numbers have a session lifetime, it can lead to critical scenarios like deleting the wrong e-mail. ## Option 5 Don't create a distributed implementation. Well, as my involvement on James project is about to make it distributed, I definitely down vote this option. # Avoid the problem ##