Mailing-List: contact user-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@cassandra.apache.org
Received-SPF: pass (athena.apache.org: domain of jshook@gmail.com designates
 209.85.221.192 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:date:message-id:subject:from:to
         :content-type:content-transfer-encoding;
        b=Zg1TVEX3/6U2pMtn0ZwraFCRK30vWV2nFMa/tJaQBjqFcVJMe5egsRgN3kAhQ/eH9d
         1NdzCUqkgO2Nmduky89y/l1Y4aO1z+MtFUgH10yzUV3A3FlXPq8T49mxjrLCK3g/Mooh
         GcWG/TG4EKe5bwH82ghpF4GneA0zeC+y9VCo8=
MIME-Version: 1.0
In-Reply-To: <AANLkTim0agvfFBA8NzJiq6C5J04tmw9YW2eil6cCAfDy@mail.gmail.com>
References: <AANLkTim0agvfFBA8NzJiq6C5J04tmw9YW2eil6cCAfDy@mail.gmail.com>
Date: Wed, 26 May 2010 21:36:35 -0500
Message-ID: <AANLkTikxbxfmUIuzHFIZkpHnMIiEGDb57zfmI5C1D13T@mail.gmail.com>
Subject: Re: Cassandra's 2GB row limit and indexing
From: Jonathan Shook <jshook@gmail.com>
To: user@cassandra.apache.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

The example is a little confusing.
.. but ..

1) "sharding"
You can square the capacity by having a 2-level map.
 CF1->row->value->CF2->row->value
 This means finding some natural subgrouping or hash that provides a
good distribution.
2)  "hashing"
You can also use some additional key hashing to spread the rows over a
wider space:
 Find a delimiter that works for you and identify the row that owns it
by "domain" + "delimiter" + hash(domain) modulo some divisor, for
example.
3) "overflow"
You can implement some overflow logic to create overflow rows which
act like (2), but is less sparse
 while count(columns) for candidate row > some threshold, try row +
"delimiter" + subrow++
 This is much easier when you are streaming data in, as opposed to
poking the random value here and there

Just some ideas. I'd go with 2, and find a way to adjust the modulo to
minimize the row spread. 2) isn't guaranteed to provide uniformity,
but 3) isn't guaranteed to provide very good performance. Perhaps a
combination of them both? The count is readily accessible, so it may
provide for some informed choices at run time. I'm assuming your
column sizes are fairly predictable.

Has anybody else tackled this before?


On Wed, May 26, 2010 at 8:52 PM, Richard West <rich@clearchaos.com> wrote:
> Hi all,
>
> I'm currently looking at new database options for a URL shortener in orde=
r
> to scale well with increased traffic as we add new features. Cassandra se=
ems
> to be a good fit for many of our requirements, but I'm struggling a bit t=
o
> find ways of designing certain indexes in Cassandra due to its 2GB row
> limit.
>
> The easiest example of this is that I'd like to create an index by the
> domain that shortened URLs are linking to, mostly for spam control so it'=
s
> easy to grab all the links to any given domain. As far as I can tell the
> typical way to do this in Cassandra is something like: -
>
> DOMAIN =3D { //columnfamily
> =A0=A0=A0 thing.com { //row key
> =A0=A0=A0 =A0=A0=A0 timestamp: "shorturl567", //column name: value
> =A0=A0=A0 =A0=A0=A0 timestamp: "shorturl144",
> =A0=A0=A0 =A0=A0=A0 timestamp: "shorturl112",
> =A0=A0=A0 =A0=A0=A0 ...
> =A0=A0=A0 }
> =A0=A0=A0 somethingelse.com {
> =A0=A0=A0 =A0=A0=A0 timestamp: "shorturl817",
> =A0=A0=A0 =A0=A0=A0 ...
> =A0=A0=A0 }
> }
>
> The values here are keys for another columnfamily containing various data=
 on
> shortened URLs.
>
> The problem with this approach is that a popular domain (e.g. blogspot.co=
m)
> could be used in many millions of shortened URLs, so would have that many
> columns and hit the row size limit mentioned at
> http://wiki.apache.org/cassandra/CassandraLimitations.
>
> Does anyone know an effective way to design this type of one-to-many inde=
x
> around this limitation (could be something obvious I'm missing)? If not, =
are
> the changes proposed for https://issues.apache.org/jira/browse/CASSANDRA-=
16
> likely to make this type of design workable?
>
> Thanks in advance for any advice,
>
> Richard
>