How to reliably achieve unique constraints with Cassandra?

Showing 1-20 of 20 messages
How to reliably achieve unique constraints with Cassandra? Drew Kutcharian 1/6/12 10:03 AM
Hi Everyone,

What's the best way to reliably have unique constraints like functionality with Cassandra? I have the following (which I think should be very common) use case.

User CF
Row Key: user email
Columns: userId: UUID, etc...

UserAttribute1 CF:
Row Key: userId (which is the uuid that's mapped to user email)
Columns: ...

UserAttribute2 CF:
Row Key: userId (which is the uuid that's mapped to user email)
Columns: ...

The issue is we need to guarantee that no two people register with the same email address. In addition, without locking, potentially a malicious user can "hijack" another user's account by registering using the user's email address.

I know that this can be done using a lock manager such as ZooKeeper or HazelCast, but the issue with using either of them is that if ZooKeeper or HazelCast is down, then you can't be sure about the reliability of the lock. So this potentially, in the very rare instance where the lock manager is down and two users are registering with the same email, can cause major issues.

In addition, I know this can be done with other tools such as Redis (use Redis for this use case, and Cassandra for everything else), but I'm interested in hearing if anyone has solved this issue using Cassandra only.

Thanks,

Drew

Re: How to reliably achieve unique constraints with Cassandra? Mohit Anchlia 1/6/12 10:38 AM
On Fri, Jan 6, 2012 at 10:03 AM, Drew Kutcharian <dr...@venarc.com> wrote:
> Hi Everyone,
>
> What's the best way to reliably have unique constraints like functionality with Cassandra? I have the following (which I think should be very common) use case.
>
> User CF
> Row Key: user email
> Columns: userId: UUID, etc...
>
> UserAttribute1 CF:
> Row Key: userId (which is the uuid that's mapped to user email)
> Columns: ...
>
> UserAttribute2 CF:
> Row Key: userId (which is the uuid that's mapped to user email)
> Columns: ...
>
> The issue is we need to guarantee that no two people register with the same email address. In addition, without locking, potentially a malicious user can "hijack" another user's account by registering using the user's email address.

It could be as simple as reading before writing to make sure that
email doesn't exist. But I think you are looking at how to handle 2
concurrent requests for same email? Only way I can think of is:

1) Create new CF say tracker
2) write email and time uuid to CF tracker
3) read from CF tracker
4) if you find a row other than yours then wait and read again from
tracker after few ms
5) read from USER CF
6) write if no rows in USER CF
7) delete from tracker

Please note you might have to modify this logic a little bit, but this
should give you some ideas of how to approach this problem without
locking.

Regarding hijacking accounts, can you elaborate little more?


>
> I know that this can be done using a lock manager such as ZooKeeper or HazelCast, but the issue with using either of them is that if ZooKeeper or HazelCast is down, then you can't be sure about the reliability of the lock. So this potentially, in the very rare instance where the lock manager is down and two users are registering with the same email, can cause major issues.
>
> In addition, I know this can be done with other tools such as Redis (use Redis for this use case, and Cassandra for everything else), but I'm interested in hearing if anyone has solved this issue using Cassandra only.
>
> Thanks,
>
> Drew

Re: How to reliably achieve unique constraints with Cassandra? Drew Kutcharian 1/6/12 11:01 AM
Yes, my issue is with handling concurrent requests. I'm not sure how your logic will work with eventual consistency. I'm going to have the same issue in the "tracker" CF too, no?
Re: How to reliably achieve unique constraints with Cassandra? Mohit Anchlia 1/6/12 11:03 AM
I don't think if you read and write with QUORUM
Re: How to reliably achieve unique constraints with Cassandra? Bryce Allen 1/6/12 12:42 PM
On Fri, 6 Jan 2012 10:38:17 -0800
Mohit Anchlia <mohita...@gmail.com> wrote:
> It could be as simple as reading before writing to make sure that
> email doesn't exist. But I think you are looking at how to handle 2
> concurrent requests for same email? Only way I can think of is:
>
> 1) Create new CF say tracker
> 2) write email and time uuid to CF tracker
> 3) read from CF tracker
> 4) if you find a row other than yours then wait and read again from
> tracker after few ms
> 5) read from USER CF
> 6) write if no rows in USER CF
> 7) delete from tracker
>
> Please note you might have to modify this logic a little bit, but this
> should give you some ideas of how to approach this problem without
> locking.

Distributed locking is pretty subtle; I haven't seen a correct solution
that uses just Cassandra, even with QUORUM read/write. I suspect it's
not possible.

With the above proposal, in step 4 two processes could both have
inserted an entry in the tracker before either gets a chance to check,
so you need a way to order the requests. I don't think the timestamp
works for ordering, because it's set by the client (even the internal
timestamp is set by the client), and will likely be different from
when the data is actually committed and available to read by other
clients.

For example:

* At time 0ms, client 1 starts insert of us...@example.org
* At time 1ms, client 2 also starts insert for us...@example.org
* At time 2ms, client 2 data is committed
* At time 3ms, client 2 reads tracker and sees that it's the only one,
  so enters the critical section
* At time 4ms, client 1 data is committed
* At time 5ms, client 2 reads tracker, and sees that is not the only
  one, but since it has the lowest timestamp (0ms vs 1ms), it enters
  the critical section.

I don't think Cassandra counters work for ordering either.

This approach is similar to the Zookeeper lock recipe:
http://zookeeper.apache.org/doc/current/recipes.html#sc_recipes_Locks
but zookeeper has sequence nodes, which provide a consistent way of
ordering the requests. Zookeeper also avoids the busy waiting.

I'd be happy to be proven wrong. But even if it is possible, if it
involves a lot of complexity and busy waiting it's probably not worth
it. There's a reason people are using Zookeeper with Cassandra.

-Bryce

Re: How to reliably achieve unique constraints with Cassandra? Bryce Allen 1/6/12 12:48 PM
On Fri, 6 Jan 2012 10:03:38 -0800
Drew Kutcharian <dr...@venarc.com> wrote:
> I know that this can be done using a lock manager such as ZooKeeper
> or HazelCast, but the issue with using either of them is that if
> ZooKeeper or HazelCast is down, then you can't be sure about the
> reliability of the lock. So this potentially, in the very rare
> instance where the lock manager is down and two users are registering
> with the same email, can cause major issues.

For most applications, if the lock managers is down, you don't acquire
the lock, so you don't enter the critical section. Rather than allowing
inconsistency, you become unavailable (at least to writes that require
a lock).

-Bryce

Re: How to reliably achieve unique constraints with Cassandra? Jeremiah Jordan 1/6/12 12:53 PM
Correct, any kind of locking in Cassandra requires clocks that are in
sync, and requires you to wait "possible clock out of sync time" before
reading to check if you got the lock, to prevent the issue you describe
below.

There was a pretty detailed discussion of locking with only Cassandra a
month or so back on this list.

-Jeremiah

Re: How to reliably achieve unique constraints with Cassandra? Jeremiah Jordan 1/6/12 1:02 PM
Since a Zookeeper cluster is a quorum based system similar to Cassandra,
it only goes down when n/2 nodes go down.  And the same way you have to
stop writing to Cassandra if N/2 nodes are down (if using QUoRUM), your
App will have to wait for the Zookeeper cluster to come online again
before it can proceed.
Re: How to reliably achieve unique constraints with Cassandra? Bryce Allen 1/6/12 1:16 PM
Re: How to reliably achieve unique constraints with Cassandra? Mohit Anchlia 1/6/12 1:33 PM
This looks like right way to do it. But remember this still doesn't
gurantee if your clocks drifts way too much. But it's trade-off with
having to manage one additional component or use something internal to
C*. It would be good to see similar functionality implemented in C* so
that clients don't have to deal with it explicitly.
Re: How to reliably achieve unique constraints with Cassandra? Drew Kutcharian 1/6/12 1:36 PM
Bryce,

I'm not sure about ZooKeeper, but I know if you have a partition between HazelCast nodes, than the nodes can acquire the same lock independently in each divided partition. How does ZooKeeper handle this situation?

-- Drew

Re: How to reliably achieve unique constraints with Cassandra? Bryce Allen 1/6/12 1:41 PM
I don't think it's just clock drift. There is also the period of time
between when the client selects a timestamp, and when the data ends up
committed to cassandra. That drift seems harder to control, when the
nodes and/or clients are under load.

I agree that it would be nice to have something like this in Cassandra
core, but from the JIRA tickets it looks like this has been tried
before, and for various reasons was not added. It's definitely
non-trivial to get right.

On Fri, 6 Jan 2012 13:33:02 -0800

Re: How to reliably achieve unique constraints with Cassandra? Mohit Anchlia 1/6/12 1:55 PM
On Fri, Jan 6, 2012 at 1:41 PM, Bryce Allen <bal...@ci.uchicago.edu> wrote:
> I don't think it's just clock drift. There is also the period of time
> between when the client selects a timestamp, and when the data ends up
> committed to cassandra. That drift seems harder to control, when the
> nodes and/or clients are under load.

As suggested you control that by sleeping before reading. You are
worried about the edge case but this should work well for the use case
posted by original poster. For eg: How many people will try to create
account with the same email at the same time that will have issue
where none of the safety checks would work?

Your use case might be different and probably no tolerance whatsoever.
In that case C* probably is not the right thing to use anycase.

Re: How to reliably achieve unique constraints with Cassandra? Jeremiah Jordan 1/6/12 2:08 PM
By using quorum.  One of the partitions will may be able to acquire
locks, the other one won't...
Re: How to reliably achieve unique constraints with Cassandra? Bryce Allen 1/6/12 2:11 PM
That's a good question, and I'm not sure - I'm fairly new to both ZK
and Cassandra. I found this wiki page:
http://wiki.apache.org/hadoop/ZooKeeper/FailureScenarios
and I think the lock recipe still works, even if a stale read happens.
Assuming that wiki page is correct.

There is still subtlety to locking with ZK though, see (Locks based
on ephemeral nodes) from the zk mailing list in October:
http://mail-archives.apache.org/mod_mbox/zookeeper-user/201110.mbox/thread?0

-Bryce

On Fri, 6 Jan 2012 13:36:52 -0800


Drew Kutcharian <dr...@venarc.com> wrote:
> Bryce,
>
> I'm not sure about ZooKeeper, but I know if you have a partition
> between HazelCast nodes, than the nodes can acquire the same lock
> independently in each divided partition. How does ZooKeeper handle
> this situation?
>
> -- Drew
>
>
> On Jan 6, 2012, at 12:48 PM, Bryce Allen wrote:
>
> > On Fri, 6 Jan 2012 10:03:38 -0800
> > Drew Kutcharian <dr...@venarc.com> wrote:
> >> I know that this can be done using a lock manager such as ZooKeeper
> >> or HazelCast, but the issue with using either of them is that if
> >> ZooKeeper or HazelCast is down, then you can't be sure about the
> >> reliability of the lock. So this potentially, in the very rare
> >> instance where the lock manager is down and two users are
> >> registering with the same email, can cause major issues.
> >
> > For most applications, if the lock managers is down, you don't
> > acquire the lock, so you don't enter the critical section. Rather
> > than allowing inconsistency, you become unavailable (at least to
> > writes that require a lock).
> >
> > -Bryce
>

Re: How to reliably achieve unique constraints with Cassandra? Drew Kutcharian 1/6/12 2:35 PM
Thanks everyone for the replies. Seems like there is no easy way to handle this. It's very surprising that no one seems to have solved such a common use case.

-- Drew

Re: How to reliably achieve unique constraints with Cassandra? Narendra Sharma 1/6/12 2:46 PM
>>>It's very surprising that no one seems to have solved such a common use case.
I would say people have solved it using RIGHT tools for the task.

--
Narendra Sharma
Re: How to reliably achieve unique constraints with Cassandra? Drew Kutcharian 1/6/12 4:00 PM
So what are the common RIGHT solutions/tools for this?
Re: How to reliably achieve unique constraints with Cassandra? Narendra Sharma 1/6/12 10:43 PM
Instead of trying to solve the generic problem of uniqueness, I would focus on the specific problem. 

For eg lets consider your usecase of user registration with email address as key. You can do following:
1. Create CF (Users) where row key is UUID and has user info specific columns.
2. Whenever user registers create a row in this CF with user status flag as waiting for confirmation.
3. Send email to the user's email address with link that contains the UUID (or encrypted UUID)
4. When user clicks on the link, use the UUID (or decrypted UUID) to lookup user
5. If the user exists with given UUID and status as waiting for confirmation then update the status  and create a entry in another CF (EmailUUIDIndex) representing email address to UUID mapping.
6. For authentication you can lookup in the index to get UUID and proceed.
7. If a malicious user registers with someone else's email id then he will never be able to confirm and will never have an entry in EmailUUIDIndex. As a additional check if the entry for email id exists in EmailUUIDIndex then the request for registration can be rejected right away.

Make sense?

-Naren
Re: How to reliably achieve unique constraints with Cassandra? Drew Kutcharian 1/6/12 11:15 PM
It makes great sense. You're a genius!!