incubator-couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Adam Kocoloski <adam.kocolo...@gmail.com>
Subject Re: Even more fine-grained ETag support when querying views?
Date Thu, 15 Sep 2011 21:01:45 GMT
It's a decent idea, though it would cause unnecessary cache invalidations in the case of document
updates that do not end up changing the emitted KVs for the document.

On Thursday, September 15, 2011 at 10:51 AM, sleepnova wrote:

> How about max update sequence of current view range?
> 
> 2011/9/13 Robert Newson <rnewson@apache.org (mailto:rnewson@apache.org)>
> 
> > CRC32 should be good enough but there are better hash algorithms out
> > there (not completely sure they're commutative though). Will update.
> > 
> > On 13 September 2011 14:09, Paul Davis <paul.joseph.davis@gmail.com (mailto:paul.joseph.davis@gmail.com)>
> > wrote:
> > > Yeah, that's the basic idea. I walked through the idea of using
> > > something more familiar like SHA's or what not, but unless someone
> > > knows how to combine SHA hash states commutatively then I think that
> > > idea is shot because it'd cause a stampeding herd effect after
> > > compaction.
> > > 
> > > On Tue, Sep 13, 2011 at 8:46 AM, Robert Newson <rnewson@apache.org (mailto:rnewson@apache.org)>
> > wrote:
> > > > My joke about bloom filters was apparently misunderstood but the
> > > > notion above, which sounds a lot like a Merkle tree, seems lucid to
> > > > me.
> > > > 
> > > > As for the strong vs. weak ETag variants, I think views need strong
> > > > ETags in all cases, given the declared semantics for them in 13.3.3
> > > > 
> > > > B.
> > > > 
> > > > On 12 September 2011 23:28, Paul Davis <paul.joseph.davis@gmail.com
(mailto:paul.joseph.davis@gmail.com)>
> > wrote:
> > > > > In general the idea is intriguing. Using a combining hash would allow
> > > > > you to get a specific hash value for a given range. Unfortunately,
> > > > > bloom filters are not a good solution here because they require an
a
> > > > > priori guess of the number of keys that are going to be stored. On
the
> > > > > other hand, CRC32 appears to be combinable.There are a couple issues
> > > > > though. The first of which is whether this is a strong enough hash
to
> > > > > use for an ETag. There are two types of ETags with slightly different
> > > > > semantics, so we'd have to figure out what we can do and where this
> > > > > falls on that spectrum. Secondly, computing the range ETag would
> > > > > require the equivalent of a reduce=false view call in addition to
> > > > > streaming the output if validation matched which has performance
> > > > > implications as well.
> > > > > 
> > > > > On Mon, Sep 12, 2011 at 6:50 PM, Alon Keren <alon.keren@gmail.com
(mailto:alon.keren@gmail.com)>
> > wrote:
> > > > > > Disclosure: I don't know much about e-tags, CouchDB internals
(or
> > bloom
> > > > > > filters).
> > > > > > 
> > > > > > How about maintaining an e-tag for each sub-tree in the view,
similar
> > to the
> > > > > > way (I think) reduce works?
> > > > > > When a row gets updated, its e-tag would be recalculated, and
then its
> > > > > > parent's e-tag would be recalculated, and so on. The e-tag of
an
> > internal
> > > > > > node could be the hash of all its children's hashes.
> > > > > > The actual e-tag that a view-query receives: the e-tag of the
common
> > > > > > ancestor of all involved rows.
> > > > > > 
> > > > > > The next time you query the same keys, you would supply the
e-tag
> > you've
> > > > > > just received.
> > > > > > 
> > > > > >  Alon
> > > > > > 
> > > > > > 
> > > > > > On 10 September 2011 16:41, Andreas Lind Petersen <
> > > > > > andreaslindpetersen@gmail.com (mailto:andreaslindpetersen@gmail.com)>
wrote:
> > > > > > 
> > > > > > > Hi!
> > > > > > > 
> > > > > > > Background: I'm working on a web app that uses a single
CouchDB
> > database
> > > > > > > for
> > > > > > > storing data belong to 400000+ users. Each user has an
average of
> > about 40
> > > > > > > documents that need to be fetched in one go when the frontend
is
> > launched.
> > > > > > > I
> > > > > > > have accomplished this by querying a simple view with ?key=ownerID
> > (with a
> > > > > > > fallback to /_alldocs?startkey=<ownerID>_...&endkey=<ownerID>~
if the
> > view
> > > > > > > isn't built). Since the data for each user rarely changes,
there's a
> > > > > > > potential to save resources by supporting conditional GET
with
> > > > > > > If-None-Match, which would amount having the web app backend
copy the
> > > > > > > CouchDB-generated ETag into the response sent to the browser.
> > > > > > > 
> > > > > > > However, I just learned that CouchDB only maintains a single
ETag for
> > the
> > > > > > > entire view, so every time one of my users changes something,
the
> > ETag for
> > > > > > > everyone else's query result also changes. This makes conditional
> > GETs
> > > > > > > useless with this usage pattern.
> > > > > > > 
> > > > > > > I asked about this on #couchdb and had a brief talk with
rnewson, who
> > was
> > > > > > > sympathetic to the idea. Unfortunately we weren't able
to come up
> > with an
> > > > > > > idea that didn't involve traversing all docs in the result
just for
> > > > > > > computing the ETag (my suggestion was a hash of the _revs
of all docs
> > > > > > > contributing to the result). That would be a bad default,
but might
> > still
> > > > > > > work as an opt-in thing per request, eg. slowetag=true.
> > > > > > > 
> > > > > > > Newson said I should try raising the discussion here in
case someone
> > else
> > > > > > > had an idea for a cheaper way to calculate a good ETag.
So what does
> > > > > > > everyone else think about this? Is my use case too rare,
or would it
> > be
> > > > > > > worthwhile to implement it?
> > > > > > > 
> > > > > > > Best regards,
> > > > > > > Andreas Lind Petersen (papandreou)
> > > > > > > 
> > > > > > > Here's our chat transcript:
> > > > > > > 
> > > > > > > [11:46] <papandreou> Does anyone know if there are
plans for issuing
> > even
> > > > > > > more granular etags for view lookups? When you only look
up a small
> > range
> > > > > > > or
> > > > > > > a specific key it would be really great if the ETag only
changed when
> > that
> > > > > > > subset changes rather than the entire view.
> > > > > > > [11:47] <papandreou> In the application I'm working
on I'll hardly
> > ever be
> > > > > > > able to get a 304 response because of this.
> > > > > > > [...]
> > > > > > > [13:51] <+rnewson> papandreou: unlikely.
> > > > > > > [13:52] <papandreou> rnewson: So the best thing I
can do is to fetch
> > the
> > > > > > > data and compute a better etag myself? (My use case is
a backend for
> > a web
> > > > > > > app)
> > > > > > > [13:53] <+rnewson> papandreou: You might be able
to set ETag in a
> > list
> > > > > > > function? If you can't, I'll gladly change CouchDB so you
can.
> > > > > > > [13:54] <papandreou> rnewson: I thought about that,
too, but that
> > would
> > > > > > > cause a big overhead for every request, right?
> > > > > > > [13:55] <papandreou> rnewson: (Last time I tried
views were slooow)
> > > > > > > [13:55] <papandreou> I mean lists
> > > > > > > [13:55] <+rnewson> papandreou: slower, yes, because
couch needs to
> > evaluate
> > > > > > > the javascript in an external process.
> > > > > > > [13:55] <+rnewson> how will you calculate the fine-grained
ETag?
> > > > > > > [13:56] <+rnewson> Also we did recently make it slightly
finer,
> > before it
> > > > > > > was view group scope and now it's the view itself (I think)
> > > > > > > [13:56] <papandreou> rnewson: Maybe something like
a hash of the
> > _revs of
> > > > > > > all the documents contributing to the result?
> > > > > > > [13:56] <+rnewson> hm, that makes no sense actually.
but we did
> > refine it
> > > > > > > recently.
> > > > > > > [13:57] <+rnewson> papandreou: that doesn't sound
cheap at all, and
> > it
> > > > > > > would
> > > > > > > need to be cheaper than doing the view query itself to
make sense.
> > > > > > > [13:58] <papandreou> rnewson: There's still the bandwidth
thing
> > > > > > > [13:58] <+rnewson> oh, you're working with restricted
bandwidth
> > and/or have
> > > > > > > huge view responses?
> > > > > > > [13:59] <papandreou> rnewson: And it would be really
nice to have
> > something
> > > > > > > like this completely handled by the database instead of
inventing a
> > bunch
> > > > > > > of
> > > > > > > workarounds.
> > > > > > > [14:01] <+rnewson> If there's a correct and efficient
algorithm for
> > doing
> > > > > > > it, I'm sure it would be applied.
> > > > > > > [14:02] <papandreou> rnewson: I guess it depends
on the use case. If
> > the
> > > > > > > database is rarely updated I suppose the current tradeoff
is better.
> > > > > > > [14:03] <+rnewson> I'm sure the only reason we have
ETags at the
> > current
> > > > > > > granularity is because it's very quick to calculate. A
finer-grain
> > would be
> > > > > > > committed if a viable approach was proposed.
> > > > > > > [14:04] <papandreou> rnewson: I have a huge database
with data
> > belonging to
> > > > > > > 400000+ different users, and I'm using a view to enable
a
> > lookup-by-owner
> > > > > > > thing. But every time a single piece of data is inserted,
the ETag
> > for the
> > > > > > > view changes
> > > > > > > [14:04] == case_ [~
> > case@AMontsouris-651-1-123-169.w83-202.abo.wanadoo.fr (mailto:case@AMontsouris-651-1-123-169.w83-202.abo.wanadoo.fr)]
> > > > > > > has quit [Read error: Connection reset by peer]
> > > > > > > [14:04] <+rnewson> yes, I've completely understood
the problem you
> > stated
> > > > > > > earlier.
> > > > > > > [14:05] <+rnewson> I can't think of a way to improve
this right now
> > but I
> > > > > > > would spend the time to implement it if you had one.
> > > > > > > [14:06] <papandreou> rnewson: So right now the code
path that sends a
> > 304
> > > > > > > only needs to look at a single piece of metadata for the
view to make
> > its
> > > > > > > decision? That'll be hard to beat :)
> > > > > > > [14:07] <+rnewson> doesn't need to beat it, it just
needs to be fast.
> > > > > > > [14:07] <+rnewson> but I don't see any current possible
solutions,
> > let
> > > > > > > alone
> > > > > > > fast ones.
> > > > > > > [14:07] <papandreou> rnewson: Well, thanks anyway
for considering my
> > > > > > > suggestion. I'll let you know of I get an idea :)
> > > > > > > [14:08] <+rnewson> and it is now per-view and not
per-viewgroup. so
> > it's
> > > > > > > what I said first before I thought it was silly
> > > > > > > [14:08] <+benoitc> query + last seq returned maybe
....
> > > > > > > [14:08] <+rnewson> but obviously a change could affect
one view in a
> > group
> > > > > > > but not others
> > > > > > > [14:09] <papandreou> benoitc: The query is already
sort of included
> > since
> > > > > > > it's in the url.
> > > > > > > [14:09] <+rnewson> benoitc: ?
> > > > > > > [14:10] <+benoitc> i was meaning last committed seq,but
it won't
> > change
> > > > > > > anything ...
> > > > > > > [14:10] <papandreou> benoitc: I guess you'd also
need to make sure
> > that the
> > > > > > > ETag changes if a document is deleted?
> > > > > > > [14:10] <papandreou> ah
> > > > > > > [14:10] <+rnewson> benoitc: we already use the update_seq
of the
> > #view,
> > > > > > > which is finer-grained that db's last committed seq
> > > > > > > [14:11] <+benoitc> rnewson: commited seq in the view
group but anyway
> > it
> > > > > > > won't work
> > > > > > > [14:12] <+rnewson> benoitc: right, that would be
the pre-1.1.0
> > behavior, I
> > > > > > > think.
> > > > > > > [14:12] <+rnewson> which is coarser
> > > > > > > [14:12] <+rnewson> we simply don't record the info
that papandreou's
> > > > > > > suggestion would need to work.
> > > > > > > [14:12] <+benoitc> papandreou: easier solution would
be to request
> > each
> > > > > > > time
> > > > > > > on on stale view
> > > > > > > [14:13] <papandreou> rnewson: Another reason why
my suggestion sucks
> > is
> > > > > > > that
> > > > > > > it would require two traversals of the range, right? I'm
guessing it
> > starts
> > > > > > > streaming as soon as it has found the first doc now?
> > > > > > > [14:13] <+benoitc> and update after, think it would
work. except if
> > you
> > > > > > > want
> > > > > > > something strict
> > > > > > > [14:13] <+rnewson> papandreou: yes, we stream the
results as we read
> > them,
> > > > > > > we don't buffer.
> > > > > > > [14:14] <papandreou> benoitc: Hmm, so the theory
is that stale=ok
> > would
> > > > > > > increase the percentage of 304 responses?
> > > > > > > [14:14] <papandreou> rnewson: Right, yes, then it
would take a
> > serious hit.
> > > > > > > [14:14] <+rnewson> papandreou: but we could add an
option that reads
> > the
> > > > > > > thing, builds an etag, and then streams the result. it
would be
> > slower, but
> > > > > > > for the times that we can send 304 we'd save bandwidth.
It sounds a
> > bit too
> > > > > > > niche to me, but you could raise it on user@
> > > > > > > [14:15] == Frippe [~Frippe@unaffiliated/frippe] has quit
[Ping
> > timeout:
> > > > > > > 240
> > > > > > > seconds]
> > > > > > > [14:15] <papandreou> rnewson: Would be awesome to
have that as a
> > > > > > > configuration option
> > > > > > > [14:15] <+rnewson> papandreou: the view would not
change, so neither
> > would
> > > > > > > the ETag (with stale=ok)
> > > > > > > [14:15] <+rnewson> papandreou: I think it would be
a runtime option
> > > > > > > ?slow_etag=true
> > > > > > > [14:15] <papandreou> rnewson: That would also be
fine
> > > > > > > [14:16] <+rnewson> a better solution would not require
two passes,
> > though.
> > > > > > > [14:16] <+benoitc> papandreou: i would use stale=ok,
then query the
> > view
> > > > > > > async, save new etag & ...
> > > > > > > [14:16] <papandreou> rnewson: I really don't think
it's that niche
> > :). But
> > > > > > > maybe ETag-nerds are rarer than I think, hehe
> > > > > > > [14:16] <+benoitc> rnewson: that could encourage
pretty dangerous
> > things
> > > > > > > [14:16] <+rnewson> benoitc: ?
> > > > > > > [14:17] <+benoitc> rnewson: cpu intensives tasks
eacht time the call
> > is
> > > > > > > done,
> > > > > > > [14:17] <+benoitc> rather than encouraging something
async
> > > > > > > [14:18] <+benoitc> rahh I hate osx, it introduce
be bad unicode chars
> > in
> > > > > > > vim
> > > > > > > :@
> > > > > > > [14:23] == Frippe_ has changed nick to Frippe
> > > > > > > [14:23] <papandreou> benoitc: I'm not sure exactly
how that would
> > work? I'm
> > > > > > > working on the backend for a web app, so the requests will
be coming
> > from
> > > > > > > multiple machines
> > > > > > > [14:24] <+benoitc> papandreou: call with stale==ok
and have a process
> > > > > > > asking
> > > > > > > your deb for refresh from time to time
> > > > > > > [14:24] <+benoitc> s/deb/view
> > > > > > > [14:25] <+rnewson> benoitc: not sure I follow. doubling
the number of
> > view
> > > > > > > requests to achieve a finer etag is an ok solution, but
shouldn't be
> > the
> > > > > > > default, but I do think we'd need a better solution than
that.
> > > > > > > [14:25] <+rnewson> benoitc: and you might be forgetting
all the md5
> > > > > > > verification we do all the time.
> > > > > > > [14:27] <+benoitc> rnewson: you don't need to call
each views though
> > > > > > > [14:27] <+benoitc> I don't see the arg about last
one
> > > > > > > [14:27] <papandreou> benoitc: Ah, ok, I understand
now. Won't work
> > very
> > > > > > > well
> > > > > > > for me, though, the web app is a single page thing that
only asks for
> > this
> > > > > > > particular chunk of data once per session, so the ETag
will probably
> > have
> > > > > > > changed anyway unless we accept day-old data.
> > > > > > > [14:27] <+benoitc> anyway enotime to discuss about
that , i'm on
> > > > > > > anotherthing
> > > > > > > [14:32] <papandreou> rnewson: But next step would
be for me to raise
> > the
> > > > > > > issue on the user mailing list?
> > > > > > > [14:33] <+rnewson> papandreou: on reflection, it's
more a dev@thing, but
> > > > > > > yes.
> > > > > > > [14:33] <+rnewson> post the suggestion about calculating
an etag over
> > the
> > > > > > > results and then streaming them, with the caveat that a
better
> > solution
> > > > > > > should be found.
> > > > > > > [14:34] <papandreou> rnewson: Ok, I will, thanks
:). Btw. do you
> > think
> > > > > > > there's a chance that this will be easier for key=... queries
than
> > > > > > > arbitrary
> > > > > > > startkey=...&endkey=... ones?
> > > > > > > [14:35] <+rnewson> papandreou: yes. for key= we could
use a bloom
> > filter.
> > > > > > > [14:38] <papandreou> rnewson: Man, I've got some
reading up to do :).
> > > > > > > Thanks! So dev@ it is?
> > > > > > > [14:39] <+rnewson> papandreou: yes.
> > > > > > > [14:40] <+rnewson> papandreou: 'bloom filter' is
just how we handwave
> > > > > > > solutions these days, it just sounds vaguely plausible
to for the
> > keys=
> > > > > > > variant
> > > > > > > [14:40] <+rnewson> but doesn't make sense at all
for startkey/endkey
> > > > > > > [14:40] <+jan____> haha, I'm sitting in an ""HTTP
Architecture"
> > session,
> > > > > > > and
> > > > > > > all the two speakers do is tell the audience how CouchDB
gets it all
> > right.
> > > > > > > [14:41] <+rnewson> at base, we'd want some cheap
way to invalidate a
> > range
> > > > > > > of keys in memory.
> > > > > > > [14:49] <+jan____> the answer must include bloom
filters.
> 
> 
> 
> -- 
> - sleepnova



Mime
View raw message