You are viewing a plain text version of this content. The canonical link for it is here.
Posted to server-dev@james.apache.org by Benoit Tellier <be...@orange.fr> on 2015/10/26 01:11:07 UTC
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
## Option 6
On distributed implementation, partly implement IMAP and refuse requests
based on sequence numbers. Seems stupid, but this is the only
implementation that works safely with Cassandra that comes to my mind...
# Option 7
If you have other ideas...
Re: Fwd: A distributed James server and SelectedMailboxImpl
statefulness
Posted by Benoit Tellier <be...@minet.net>.
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 | 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 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 ?
>>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: server-dev-unsubscribe@james.apache.org
>> For additional commands, e-mail: server-dev-help@james.apache.org
>>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: server-dev-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Posted by Eric Charles <er...@apache.org>.
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 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 ?
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: server-dev-unsubscribe@james.apache.org
> For additional commands, e-mail: server-dev-help@james.apache.org
>
--
Eric Charles http://datalayer.io
---------------------------------------------------------------------
To unsubscribe, e-mail: server-dev-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl
statefulness
Posted by Benoit Tellier <be...@minet.net>.
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 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 ?
>
---------------------------------------------------------------------
To unsubscribe, e-mail: server-dev-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Posted by Matthieu Baechler <mb...@linagora.com>.
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-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl
statefulness
Posted by Benoit Tellier <be...@minet.net>.
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-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Posted by Matthieu Baechler <mb...@linagora.com>.
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-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl
statefulness
Posted by Benoit Tellier <be...@minet.net>.
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 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 ?
>
---------------------------------------------------------------------
To unsubscribe, e-mail: server-dev-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org
Re: Fwd: A distributed James server and SelectedMailboxImpl statefulness
Posted by Matthieu Baechler <mb...@linagora.com>.
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-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org
Fwd: A distributed James server and SelectedMailboxImpl statefulness
Posted by Tellier Benoit <bt...@apache.org>.
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
## Option 6
On distributed implementation, partly implement IMAP and refuse requests
based on sequence numbers. Seems stupid, but this is the only
implementation that works safely with Cassandra that comes to my mind...
# Option 7
If you have other ideas...