You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by jc...@apache.org on 2010/01/09 19:23:16 UTC
svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Author: jchris
Date: Sat Jan 9 18:23:16 2010
New Revision: 897509
URL: http://svn.apache.org/viewvc?rev=897509&view=rev
Log:
make sequential uuids the default
Modified:
couchdb/trunk/etc/couchdb/default.ini.tpl.in
Modified: couchdb/trunk/etc/couchdb/default.ini.tpl.in
URL: http://svn.apache.org/viewvc/couchdb/trunk/etc/couchdb/default.ini.tpl.in?rev=897509&r1=897508&r2=897509&view=diff
==============================================================================
--- couchdb/trunk/etc/couchdb/default.ini.tpl.in (original)
+++ couchdb/trunk/etc/couchdb/default.ini.tpl.in Sat Jan 9 18:23:16 2010
@@ -99,7 +99,7 @@
; random prefix is regenerated and the process starts over.
; utc_random - Time since Jan 1, 1970 UTC with microseconds
; First 14 characters are the time in hex. Last 18 are random.
-algorithm = random
+algorithm = sequential
[stats]
; rate is in milliseconds
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Paul Davis <pa...@gmail.com>.
On Mon, Jan 11, 2010 at 10:51 PM, Roger Binns <ro...@rogerbinns.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Robert Newson wrote:
>> Unless I misread you, you are implying that _id is stored increasingly
>> less inefficiently in the .couch file as its length increases? I don't
>> think, unless you've really dug into the disk structure, that this
>> assertions will hold.
>
> I don't have enough data sets (or math background) to work out the exact
> relationship. At the simplest level adding one byte to the _id length
> results in more than num_documents*1 bytes increase in file size. It at
> least doubles since the _id is also stored in a btree node. And in my tests
> it appears to be more than double but I don't see an exact formula since it
> presumably depends on other factors as well such as the "more
> nodes/turnover" you mention.
>
> At the simplest level when using a non-trivial number of documents with
> CouchDB it is a bad idea to use long ids. Shorter ones result in a lot less
> disk space being consumed and hence more I/O, longer replication times etc.
> I assume the _id keys are also included in views so again each byte in _id
> length is used a multiple of times.
>
> Roger
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iEYEARECAAYFAktL8bwACgkQmOOfHg372QRnRwCfYyKmrxkNgvT7uCMzDA8a9E7c
> +HIAnjnFUYNeB36jztdtDS//8ldMAwqS
> =BaLY
> -----END PGP SIGNATURE-----
>
>
I reckon that a longer _id is going to result in greater than linear
storage requirement. There's a function class I can't remember that's
roughly related to this. Its quite tied into other things like
randomness and other bits so its hard to say for certain in math terms
what the exact effects would be.
Paul Davis
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Roger Binns <ro...@rogerbinns.com>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Robert Newson wrote:
> Unless I misread you, you are implying that _id is stored increasingly
> less inefficiently in the .couch file as its length increases? I don't
> think, unless you've really dug into the disk structure, that this
> assertions will hold.
I don't have enough data sets (or math background) to work out the exact
relationship. At the simplest level adding one byte to the _id length
results in more than num_documents*1 bytes increase in file size. It at
least doubles since the _id is also stored in a btree node. And in my tests
it appears to be more than double but I don't see an exact formula since it
presumably depends on other factors as well such as the "more
nodes/turnover" you mention.
At the simplest level when using a non-trivial number of documents with
CouchDB it is a bad idea to use long ids. Shorter ones result in a lot less
disk space being consumed and hence more I/O, longer replication times etc.
I assume the _id keys are also included in views so again each byte in _id
length is used a multiple of times.
Roger
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEARECAAYFAktL8bwACgkQmOOfHg372QRnRwCfYyKmrxkNgvT7uCMzDA8a9E7c
+HIAnjnFUYNeB36jztdtDS//8ldMAwqS
=BaLY
-----END PGP SIGNATURE-----
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Damien Katz <da...@apache.org>.
Your analysis is correct. Just to clarify, the btrees are *mostly* self balancing, but it omits the 2 expensive rotations on btree rebalancing, which are used when removing keys from the tree. It is possible for btrees to become unbalanced, but a simple compaction does fix it. However, it needs to recompute the reductions, and for views that means recalling out to JS. For database compaction, the reductions are very cheap CPU wise, so it's not a big there. But if the btrees were fully balanced, then there no need to recompute reductions during compaction, just copy the nodes and their existing reduction values.
-Damien
On Jan 12, 2010, at 4:49 AM, Robert Dionne wrote:
> I don't think so, perhaps I misspoke. What I meant was the comment, "a balancing condition", implied that it was balanced and was merely missing a particular case. It's not balanced in the textbook sense of having an order n that determines lower and upper bounds on the number of nodes at each level.
>
> The amount of branching is determined by a "chunkify" function that write out chunks of a constant size and so will depend on the key size of kv nodes and the reductions for the kp nodes.
>
> So when deletions occur it will be unbalanced in the sense that compaction results in a different b-tree which requires the reductions to be computed again. I believe the intent of #224 is that if the b-tree is balanced in the text book sense that compaction can just be a copy of the nodes.
>
> I haven't looked at this in some time, and it requires a very detailed analysis to see if it might in fact be improved, particularly with respect to views. I'd love to hear Damien's or Jan's or Paul's opinion on this. When I looked at this last summer I noted there been considerable research in trees used in databases in recent years.
>
>
>
>
> On Jan 12, 2010, at 4:02 AM, Brian Candler wrote:
>
>> On Mon, Jan 11, 2010 at 07:58:10AM -0500, Robert Dionne wrote:
>>> jira-224 makes an odd claim that it misses "a balancing condition", it
>>> doesn't balance at all so I'm not sure what this means.
>>
>> If it's not balanced at all, does that mean there are degenerate cases which
>> could end up with having to do a linear search through the nodes?
>>
>> .
>> ||||
>> \
>> ||||
>> \
>> ||||
>> \
>> ||||
>>
>> Could inserting with strictly sequential ids cause that condition to occur?
>> (As would be the case with utc_random)
>
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Paul Davis <pa...@gmail.com>.
Bob's description is exactly my understanding as well. Though I think
we came to the same conclusion together on IRC if memory serves, so
this may just be a confirmation that we can both remember a
conversation from a few months ago.
Pau
On Tue, Jan 12, 2010 at 7:49 AM, Robert Dionne
<di...@dionne-associates.com> wrote:
> I don't think so, perhaps I misspoke. What I meant was the comment, "a balancing condition", implied that it was balanced and was merely missing a particular case. It's not balanced in the textbook sense of having an order n that determines lower and upper bounds on the number of nodes at each level.
>
> The amount of branching is determined by a "chunkify" function that write out chunks of a constant size and so will depend on the key size of kv nodes and the reductions for the kp nodes.
>
> So when deletions occur it will be unbalanced in the sense that compaction results in a different b-tree which requires the reductions to be computed again. I believe the intent of #224 is that if the b-tree is balanced in the text book sense that compaction can just be a copy of the nodes.
>
> I haven't looked at this in some time, and it requires a very detailed analysis to see if it might in fact be improved, particularly with respect to views. I'd love to hear Damien's or Jan's or Paul's opinion on this. When I looked at this last summer I noted there been considerable research in trees used in databases in recent years.
>
>
>
>
> On Jan 12, 2010, at 4:02 AM, Brian Candler wrote:
>
>> On Mon, Jan 11, 2010 at 07:58:10AM -0500, Robert Dionne wrote:
>>> jira-224 makes an odd claim that it misses "a balancing condition", it
>>> doesn't balance at all so I'm not sure what this means.
>>
>> If it's not balanced at all, does that mean there are degenerate cases which
>> could end up with having to do a linear search through the nodes?
>>
>> .
>> ||||
>> \
>> ||||
>> \
>> ||||
>> \
>> ||||
>>
>> Could inserting with strictly sequential ids cause that condition to occur?
>> (As would be the case with utc_random)
>
>
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Robert Dionne <di...@dionne-associates.com>.
I don't think so, perhaps I misspoke. What I meant was the comment, "a balancing condition", implied that it was balanced and was merely missing a particular case. It's not balanced in the textbook sense of having an order n that determines lower and upper bounds on the number of nodes at each level.
The amount of branching is determined by a "chunkify" function that write out chunks of a constant size and so will depend on the key size of kv nodes and the reductions for the kp nodes.
So when deletions occur it will be unbalanced in the sense that compaction results in a different b-tree which requires the reductions to be computed again. I believe the intent of #224 is that if the b-tree is balanced in the text book sense that compaction can just be a copy of the nodes.
I haven't looked at this in some time, and it requires a very detailed analysis to see if it might in fact be improved, particularly with respect to views. I'd love to hear Damien's or Jan's or Paul's opinion on this. When I looked at this last summer I noted there been considerable research in trees used in databases in recent years.
On Jan 12, 2010, at 4:02 AM, Brian Candler wrote:
> On Mon, Jan 11, 2010 at 07:58:10AM -0500, Robert Dionne wrote:
>> jira-224 makes an odd claim that it misses "a balancing condition", it
>> doesn't balance at all so I'm not sure what this means.
>
> If it's not balanced at all, does that mean there are degenerate cases which
> could end up with having to do a linear search through the nodes?
>
> .
> ||||
> \
> ||||
> \
> ||||
> \
> ||||
>
> Could inserting with strictly sequential ids cause that condition to occur?
> (As would be the case with utc_random)
Re: svn commit: r897509 -
/couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Brian Candler <B....@pobox.com>.
On Mon, Jan 11, 2010 at 07:58:10AM -0500, Robert Dionne wrote:
> jira-224 makes an odd claim that it misses "a balancing condition", it
> doesn't balance at all so I'm not sure what this means.
If it's not balanced at all, does that mean there are degenerate cases which
could end up with having to do a linear search through the nodes?
.
||||
\
||||
\
||||
\
||||
Could inserting with strictly sequential ids cause that condition to occur?
(As would be the case with utc_random)
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Paul Davis <pa...@gmail.com>.
> Well I wouldn't characterize random UUID's as a bug, but yes they
> happen to exacerbate the worse side of the b~tree performance. Though
> I don't think that speed alone is reason enough to change the default.
^C
:%s/exacerbate/demonstrate/
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Damien Katz <da...@apache.org>.
On Jan 11, 2010, at 11:21 AM, Paul Davis wrote:
>> My experience is that from time to time someone has a support request
>> where the symptom is "CouchDB is so slow as to be unusable" and the
>> answer is "set sequential uuids" and they are happen and CouchDB
>> "works" again.
>>
>> Support requests are like cockroaches, for everyone you see there 100
>> others you don't. This math means the default random uuids is one of
>> the bigger bugs CouchDB ships with, and the switch to sequential is
>> one of the smallest patches with the biggest positive impacts we could
>> make.
>
> Well I wouldn't characterize random UUID's as a bug, but yes they
> happen to exacerbate the worse side of the b~tree performance. Though
> I don't think that speed alone is reason enough to change the default.
>
>> The downsides to sequential uuids are these (unless I've missed one).
>>
>> Info leakage - the sequential uuids could give big brother an idea who
>> created a given document.
>>
>> Gives the wrong idea - people will do stupid things like use the _id
>> in lieu of a timestamp or the local_seq for ordering.
>>
>> Could be better - there's maybe an even better uuid algorithm we could discover.
>>
>> I think the first case is important, but the others aren't that
>> compelling. Is there anything I'm missing?
>
> My biggest concern is that it gives a relative ordering and proximity
> information to documents created on a given node (and can spread
> between DB's). And its a non-obvious leakage so that people may not
> realize that they're leaking such information. It may seem like an
> abstract concern but I think its real enough to force users to make
> that decision.
I was the one who asked Chris to make the change. The current ids are the worst case for btree insert performance, slowing and bloating both doc inserts and view indexing
I don't see leakage as a problem. I don't think we've ever claimed as a feature that our generated id are somehow secure against someone figuring out when and where something might have been created, and I don't know of anyone relying on it.
But I agree we should add to the documentation how ids are generated its implications. If someone wants crypto random ids, they can configure it.
-Damien
>
> The sequential algorithm isn't time based, so its misuse doesn't
> really play into effect nearly as much as if we were going to try the
> utc_random algorithm.
>
> HTH,
> Paul Davis
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Paul Davis <pa...@gmail.com>.
> My experience is that from time to time someone has a support request
> where the symptom is "CouchDB is so slow as to be unusable" and the
> answer is "set sequential uuids" and they are happen and CouchDB
> "works" again.
>
> Support requests are like cockroaches, for everyone you see there 100
> others you don't. This math means the default random uuids is one of
> the bigger bugs CouchDB ships with, and the switch to sequential is
> one of the smallest patches with the biggest positive impacts we could
> make.
Well I wouldn't characterize random UUID's as a bug, but yes they
happen to exacerbate the worse side of the b~tree performance. Though
I don't think that speed alone is reason enough to change the default.
> The downsides to sequential uuids are these (unless I've missed one).
>
> Info leakage - the sequential uuids could give big brother an idea who
> created a given document.
>
> Gives the wrong idea - people will do stupid things like use the _id
> in lieu of a timestamp or the local_seq for ordering.
>
> Could be better - there's maybe an even better uuid algorithm we could discover.
>
> I think the first case is important, but the others aren't that
> compelling. Is there anything I'm missing?
My biggest concern is that it gives a relative ordering and proximity
information to documents created on a given node (and can spread
between DB's). And its a non-obvious leakage so that people may not
realize that they're leaking such information. It may seem like an
abstract concern but I think its real enough to force users to make
that decision.
The sequential algorithm isn't time based, so its misuse doesn't
really play into effect nearly as much as if we were going to try the
utc_random algorithm.
HTH,
Paul Davis
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Chris Anderson <jc...@apache.org>.
On Mon, Jan 11, 2010 at 4:58 AM, Robert Dionne
<di...@dionne-associates.com> wrote:
> I suspect the assertion that key size matters is valid, though to what extent I'm not sure. There is an open ticket to improve the b-tree (#224).
>
> I spent some time last summer reviewing couch_btree. It's quite elegant in that its passes inserts/deletes/lookups down through the recursion at the same time. However it's not balanced, technically (per definitions in Knuth) it's not a b-tree, it has no order. The number of nodes written at each level is determined by the number to write and a constant, called chunk size.
>
> jira-224 makes an odd claim that it misses "a balancing condition", it doesn't balance at all so I'm not sure what this means. #224 asserts that if it were balanced compaction would go much faster as it would remove the need to recompute reductions, which are stored with internal nodes and computed as the tree is constructed from the leaves up.
>
> I assumed that balancing is less important due to the append only nature. Ironically what makes the implementation quite elegant also makes balancing non-trivial. The delete case in particular is hard because one wants to do splitting of nodes opportunistically on the way down the recursion to minimize disk access.
>
> The change to use a sequentially increasing random ids improves locality a lot, especially in bulk inserts, but I would be -1 on changing the default.
>
> Best,
>
> Bob
>
>
>
>
> On Jan 11, 2010, at 4:39 AM, Robert Newson wrote:
>
>> Roger,
>>
>> Unless I misread you, you are implying that _id is stored increasingly
>> less inefficiently in the .couch file as its length increases? I don't
>> think, unless you've really dug into the disk structure, that this
>> assertions will hold. A better measure is the number of btree nodes on
>> disk for the different kinds of _id. I would expect to see more nodes
>> (and a higher rate of 'turnover') for large random ids than equally as
>> large sequential ids. Large random ids versus short sequential ids
>> should show a larger difference but for two unrelated reasons.
>>
>> B.
>>
>> On Mon, Jan 11, 2010 at 9:33 AM, Robert Newson <ro...@gmail.com> wrote:
>>> I should point out that the sequential algorithm in couchdb is
>>> carefully constructed so that generated ids won't clash, even in a
>>> distributed system. You might have assumed that the sequential ids
>>> were 1, 2, 3, 4, ... and so on, but they are not.
>>>
>>> The sequential ids are the same length as the random ids (16 bytes).
>>> The first 13 bytes stay the same for around 8000 generated ids and is
>>> then rerandomized. The ids with the same prefix have suffixes in
>>> strictly increasing numeric order. This characteristic (that a new id
>>> is numerically close to the previous id) is what helps with insertion
>>> speed and general b-tree performance.
>>>
>>> Before changing the default I think it would be worth getting numbers
>>> from a suitably fair benchmark, I would still advocate random as the
>>> default until that is done.
>>>
My experience is that from time to time someone has a support request
where the symptom is "CouchDB is so slow as to be unusable" and the
answer is "set sequential uuids" and they are happen and CouchDB
"works" again.
Support requests are like cockroaches, for everyone you see there 100
others you don't. This math means the default random uuids is one of
the bigger bugs CouchDB ships with, and the switch to sequential is
one of the smallest patches with the biggest positive impacts we could
make.
The downsides to sequential uuids are these (unless I've missed one).
Info leakage - the sequential uuids could give big brother an idea who
created a given document.
Gives the wrong idea - people will do stupid things like use the _id
in lieu of a timestamp or the local_seq for ordering.
Could be better - there's maybe an even better uuid algorithm we could discover.
I think the first case is important, but the others aren't that
compelling. Is there anything I'm missing?
Chris
>>> B.
>>>
>>> On Mon, Jan 11, 2010 at 12:51 AM, Chris Anderson <jc...@apache.org> wrote:
>>>> On Sun, Jan 10, 2010 at 4:24 PM, Roger Binns <ro...@rogerbinns.com> wrote:
>>>>> -----BEGIN PGP SIGNED MESSAGE-----
>>>>> Hash: SHA1
>>>>>
>>>>> Chris Anderson wrote:
>>>>>> I'm not feeling super-strong about this. However, making the default
>>>>>> sequential seems like it will preempt a lot of the problems people
>>>>>> tend to show up asking about.
>>>>>
>>>>
>>>> If we think that speed and size are more important than randomness, we
>>>> should continue to refine uuid generators.
>>>>
>>>> Roger, if you can make a short sequential that'd be neat.
>>>>
>>>>> There are several issues conflated together:
>>>>>
>>>>> - - When doing inserts, sorted ids are faster
>>>>>
>>>>> - - The resulting size of the db file is the size of the docs plus a multiple
>>>>> of the _id size (and probably an exponential of the size)
>>>>>
>>>>> - - Sequential ids give small _id
>>>>>
>>>>> - - Random ids give large _id
>>>>>
>>>>> - - Sequentials will clash between different dbs (consider replication,
>>>>> multiple instances etc). They'll also lead people to rely on this
>>>>> functionality as though it was like a SQL primary key
>>>>>
>>>>> - - Random ids won't clash and better illustrate how CouchDB really works
>>>>>
>>>>>> I think the info-leakage argument is overblown
>>>>>
>>>>> It does make URLs easy to guess like many ecommerce sites that didn't
>>>>> validate when showing you an invoice - you added one to the numeric id in
>>>>> the URL and got to see someone elses.
>>>>>
>>>>> I would far prefer the size of the db file and the size of the _id link
>>>>> being addressed. Because the _id size can cause the db file to get so big,
>>>>> I/O etc is a lot slower mainly because there is just so much more file to
>>>>> deal with! (In my original posting I had a db go from 21GB to 4GB by
>>>>> reducings ids from 16 bytes to 4 bytes.)
>>>>>
>>>>> Roger
>>>>>
>>>>> -----BEGIN PGP SIGNATURE-----
>>>>> Version: GnuPG v1.4.9 (GNU/Linux)
>>>>> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>>>>>
>>>>> iEYEARECAAYFAktKb8AACgkQmOOfHg372QRb0ACfRWu1TUOs3twwmOGgAUOwhLfx
>>>>> FJkAoKgnkWnPayPtPqMfk3/AxOj2xaMx
>>>>> =V7Zq
>>>>> -----END PGP SIGNATURE-----
>>>>>
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Chris Anderson
>>>> http://jchrisa.net
>>>> http://couch.io
>>>>
>>>
>
>
--
Chris Anderson
http://jchrisa.net
http://couch.io
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Robert Dionne <di...@dionne-associates.com>.
I suspect the assertion that key size matters is valid, though to what extent I'm not sure. There is an open ticket to improve the b-tree (#224).
I spent some time last summer reviewing couch_btree. It's quite elegant in that its passes inserts/deletes/lookups down through the recursion at the same time. However it's not balanced, technically (per definitions in Knuth) it's not a b-tree, it has no order. The number of nodes written at each level is determined by the number to write and a constant, called chunk size.
jira-224 makes an odd claim that it misses "a balancing condition", it doesn't balance at all so I'm not sure what this means. #224 asserts that if it were balanced compaction would go much faster as it would remove the need to recompute reductions, which are stored with internal nodes and computed as the tree is constructed from the leaves up.
I assumed that balancing is less important due to the append only nature. Ironically what makes the implementation quite elegant also makes balancing non-trivial. The delete case in particular is hard because one wants to do splitting of nodes opportunistically on the way down the recursion to minimize disk access.
The change to use a sequentially increasing random ids improves locality a lot, especially in bulk inserts, but I would be -1 on changing the default.
Best,
Bob
On Jan 11, 2010, at 4:39 AM, Robert Newson wrote:
> Roger,
>
> Unless I misread you, you are implying that _id is stored increasingly
> less inefficiently in the .couch file as its length increases? I don't
> think, unless you've really dug into the disk structure, that this
> assertions will hold. A better measure is the number of btree nodes on
> disk for the different kinds of _id. I would expect to see more nodes
> (and a higher rate of 'turnover') for large random ids than equally as
> large sequential ids. Large random ids versus short sequential ids
> should show a larger difference but for two unrelated reasons.
>
> B.
>
> On Mon, Jan 11, 2010 at 9:33 AM, Robert Newson <ro...@gmail.com> wrote:
>> I should point out that the sequential algorithm in couchdb is
>> carefully constructed so that generated ids won't clash, even in a
>> distributed system. You might have assumed that the sequential ids
>> were 1, 2, 3, 4, ... and so on, but they are not.
>>
>> The sequential ids are the same length as the random ids (16 bytes).
>> The first 13 bytes stay the same for around 8000 generated ids and is
>> then rerandomized. The ids with the same prefix have suffixes in
>> strictly increasing numeric order. This characteristic (that a new id
>> is numerically close to the previous id) is what helps with insertion
>> speed and general b-tree performance.
>>
>> Before changing the default I think it would be worth getting numbers
>> from a suitably fair benchmark, I would still advocate random as the
>> default until that is done.
>>
>> B.
>>
>> On Mon, Jan 11, 2010 at 12:51 AM, Chris Anderson <jc...@apache.org> wrote:
>>> On Sun, Jan 10, 2010 at 4:24 PM, Roger Binns <ro...@rogerbinns.com> wrote:
>>>> -----BEGIN PGP SIGNED MESSAGE-----
>>>> Hash: SHA1
>>>>
>>>> Chris Anderson wrote:
>>>>> I'm not feeling super-strong about this. However, making the default
>>>>> sequential seems like it will preempt a lot of the problems people
>>>>> tend to show up asking about.
>>>>
>>>
>>> If we think that speed and size are more important than randomness, we
>>> should continue to refine uuid generators.
>>>
>>> Roger, if you can make a short sequential that'd be neat.
>>>
>>>> There are several issues conflated together:
>>>>
>>>> - - When doing inserts, sorted ids are faster
>>>>
>>>> - - The resulting size of the db file is the size of the docs plus a multiple
>>>> of the _id size (and probably an exponential of the size)
>>>>
>>>> - - Sequential ids give small _id
>>>>
>>>> - - Random ids give large _id
>>>>
>>>> - - Sequentials will clash between different dbs (consider replication,
>>>> multiple instances etc). They'll also lead people to rely on this
>>>> functionality as though it was like a SQL primary key
>>>>
>>>> - - Random ids won't clash and better illustrate how CouchDB really works
>>>>
>>>>> I think the info-leakage argument is overblown
>>>>
>>>> It does make URLs easy to guess like many ecommerce sites that didn't
>>>> validate when showing you an invoice - you added one to the numeric id in
>>>> the URL and got to see someone elses.
>>>>
>>>> I would far prefer the size of the db file and the size of the _id link
>>>> being addressed. Because the _id size can cause the db file to get so big,
>>>> I/O etc is a lot slower mainly because there is just so much more file to
>>>> deal with! (In my original posting I had a db go from 21GB to 4GB by
>>>> reducings ids from 16 bytes to 4 bytes.)
>>>>
>>>> Roger
>>>>
>>>> -----BEGIN PGP SIGNATURE-----
>>>> Version: GnuPG v1.4.9 (GNU/Linux)
>>>> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>>>>
>>>> iEYEARECAAYFAktKb8AACgkQmOOfHg372QRb0ACfRWu1TUOs3twwmOGgAUOwhLfx
>>>> FJkAoKgnkWnPayPtPqMfk3/AxOj2xaMx
>>>> =V7Zq
>>>> -----END PGP SIGNATURE-----
>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> Chris Anderson
>>> http://jchrisa.net
>>> http://couch.io
>>>
>>
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Robert Newson <ro...@gmail.com>.
Roger,
Unless I misread you, you are implying that _id is stored increasingly
less inefficiently in the .couch file as its length increases? I don't
think, unless you've really dug into the disk structure, that this
assertions will hold. A better measure is the number of btree nodes on
disk for the different kinds of _id. I would expect to see more nodes
(and a higher rate of 'turnover') for large random ids than equally as
large sequential ids. Large random ids versus short sequential ids
should show a larger difference but for two unrelated reasons.
B.
On Mon, Jan 11, 2010 at 9:33 AM, Robert Newson <ro...@gmail.com> wrote:
> I should point out that the sequential algorithm in couchdb is
> carefully constructed so that generated ids won't clash, even in a
> distributed system. You might have assumed that the sequential ids
> were 1, 2, 3, 4, ... and so on, but they are not.
>
> The sequential ids are the same length as the random ids (16 bytes).
> The first 13 bytes stay the same for around 8000 generated ids and is
> then rerandomized. The ids with the same prefix have suffixes in
> strictly increasing numeric order. This characteristic (that a new id
> is numerically close to the previous id) is what helps with insertion
> speed and general b-tree performance.
>
> Before changing the default I think it would be worth getting numbers
> from a suitably fair benchmark, I would still advocate random as the
> default until that is done.
>
> B.
>
> On Mon, Jan 11, 2010 at 12:51 AM, Chris Anderson <jc...@apache.org> wrote:
>> On Sun, Jan 10, 2010 at 4:24 PM, Roger Binns <ro...@rogerbinns.com> wrote:
>>> -----BEGIN PGP SIGNED MESSAGE-----
>>> Hash: SHA1
>>>
>>> Chris Anderson wrote:
>>>> I'm not feeling super-strong about this. However, making the default
>>>> sequential seems like it will preempt a lot of the problems people
>>>> tend to show up asking about.
>>>
>>
>> If we think that speed and size are more important than randomness, we
>> should continue to refine uuid generators.
>>
>> Roger, if you can make a short sequential that'd be neat.
>>
>>> There are several issues conflated together:
>>>
>>> - - When doing inserts, sorted ids are faster
>>>
>>> - - The resulting size of the db file is the size of the docs plus a multiple
>>> of the _id size (and probably an exponential of the size)
>>>
>>> - - Sequential ids give small _id
>>>
>>> - - Random ids give large _id
>>>
>>> - - Sequentials will clash between different dbs (consider replication,
>>> multiple instances etc). They'll also lead people to rely on this
>>> functionality as though it was like a SQL primary key
>>>
>>> - - Random ids won't clash and better illustrate how CouchDB really works
>>>
>>>> I think the info-leakage argument is overblown
>>>
>>> It does make URLs easy to guess like many ecommerce sites that didn't
>>> validate when showing you an invoice - you added one to the numeric id in
>>> the URL and got to see someone elses.
>>>
>>> I would far prefer the size of the db file and the size of the _id link
>>> being addressed. Because the _id size can cause the db file to get so big,
>>> I/O etc is a lot slower mainly because there is just so much more file to
>>> deal with! (In my original posting I had a db go from 21GB to 4GB by
>>> reducings ids from 16 bytes to 4 bytes.)
>>>
>>> Roger
>>>
>>> -----BEGIN PGP SIGNATURE-----
>>> Version: GnuPG v1.4.9 (GNU/Linux)
>>> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>>>
>>> iEYEARECAAYFAktKb8AACgkQmOOfHg372QRb0ACfRWu1TUOs3twwmOGgAUOwhLfx
>>> FJkAoKgnkWnPayPtPqMfk3/AxOj2xaMx
>>> =V7Zq
>>> -----END PGP SIGNATURE-----
>>>
>>>
>>
>>
>>
>> --
>> Chris Anderson
>> http://jchrisa.net
>> http://couch.io
>>
>
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Robert Newson <ro...@gmail.com>.
I should point out that the sequential algorithm in couchdb is
carefully constructed so that generated ids won't clash, even in a
distributed system. You might have assumed that the sequential ids
were 1, 2, 3, 4, ... and so on, but they are not.
The sequential ids are the same length as the random ids (16 bytes).
The first 13 bytes stay the same for around 8000 generated ids and is
then rerandomized. The ids with the same prefix have suffixes in
strictly increasing numeric order. This characteristic (that a new id
is numerically close to the previous id) is what helps with insertion
speed and general b-tree performance.
Before changing the default I think it would be worth getting numbers
from a suitably fair benchmark, I would still advocate random as the
default until that is done.
B.
On Mon, Jan 11, 2010 at 12:51 AM, Chris Anderson <jc...@apache.org> wrote:
> On Sun, Jan 10, 2010 at 4:24 PM, Roger Binns <ro...@rogerbinns.com> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Chris Anderson wrote:
>>> I'm not feeling super-strong about this. However, making the default
>>> sequential seems like it will preempt a lot of the problems people
>>> tend to show up asking about.
>>
>
> If we think that speed and size are more important than randomness, we
> should continue to refine uuid generators.
>
> Roger, if you can make a short sequential that'd be neat.
>
>> There are several issues conflated together:
>>
>> - - When doing inserts, sorted ids are faster
>>
>> - - The resulting size of the db file is the size of the docs plus a multiple
>> of the _id size (and probably an exponential of the size)
>>
>> - - Sequential ids give small _id
>>
>> - - Random ids give large _id
>>
>> - - Sequentials will clash between different dbs (consider replication,
>> multiple instances etc). They'll also lead people to rely on this
>> functionality as though it was like a SQL primary key
>>
>> - - Random ids won't clash and better illustrate how CouchDB really works
>>
>>> I think the info-leakage argument is overblown
>>
>> It does make URLs easy to guess like many ecommerce sites that didn't
>> validate when showing you an invoice - you added one to the numeric id in
>> the URL and got to see someone elses.
>>
>> I would far prefer the size of the db file and the size of the _id link
>> being addressed. Because the _id size can cause the db file to get so big,
>> I/O etc is a lot slower mainly because there is just so much more file to
>> deal with! (In my original posting I had a db go from 21GB to 4GB by
>> reducings ids from 16 bytes to 4 bytes.)
>>
>> Roger
>>
>> -----BEGIN PGP SIGNATURE-----
>> Version: GnuPG v1.4.9 (GNU/Linux)
>> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>>
>> iEYEARECAAYFAktKb8AACgkQmOOfHg372QRb0ACfRWu1TUOs3twwmOGgAUOwhLfx
>> FJkAoKgnkWnPayPtPqMfk3/AxOj2xaMx
>> =V7Zq
>> -----END PGP SIGNATURE-----
>>
>>
>
>
>
> --
> Chris Anderson
> http://jchrisa.net
> http://couch.io
>
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Chris Anderson <jc...@apache.org>.
On Sun, Jan 10, 2010 at 4:24 PM, Roger Binns <ro...@rogerbinns.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Chris Anderson wrote:
>> I'm not feeling super-strong about this. However, making the default
>> sequential seems like it will preempt a lot of the problems people
>> tend to show up asking about.
>
If we think that speed and size are more important than randomness, we
should continue to refine uuid generators.
Roger, if you can make a short sequential that'd be neat.
> There are several issues conflated together:
>
> - - When doing inserts, sorted ids are faster
>
> - - The resulting size of the db file is the size of the docs plus a multiple
> of the _id size (and probably an exponential of the size)
>
> - - Sequential ids give small _id
>
> - - Random ids give large _id
>
> - - Sequentials will clash between different dbs (consider replication,
> multiple instances etc). They'll also lead people to rely on this
> functionality as though it was like a SQL primary key
>
> - - Random ids won't clash and better illustrate how CouchDB really works
>
>> I think the info-leakage argument is overblown
>
> It does make URLs easy to guess like many ecommerce sites that didn't
> validate when showing you an invoice - you added one to the numeric id in
> the URL and got to see someone elses.
>
> I would far prefer the size of the db file and the size of the _id link
> being addressed. Because the _id size can cause the db file to get so big,
> I/O etc is a lot slower mainly because there is just so much more file to
> deal with! (In my original posting I had a db go from 21GB to 4GB by
> reducings ids from 16 bytes to 4 bytes.)
>
> Roger
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iEYEARECAAYFAktKb8AACgkQmOOfHg372QRb0ACfRWu1TUOs3twwmOGgAUOwhLfx
> FJkAoKgnkWnPayPtPqMfk3/AxOj2xaMx
> =V7Zq
> -----END PGP SIGNATURE-----
>
>
--
Chris Anderson
http://jchrisa.net
http://couch.io
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Roger Binns <ro...@rogerbinns.com>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Chris Anderson wrote:
> I'm not feeling super-strong about this. However, making the default
> sequential seems like it will preempt a lot of the problems people
> tend to show up asking about.
There are several issues conflated together:
- - When doing inserts, sorted ids are faster
- - The resulting size of the db file is the size of the docs plus a multiple
of the _id size (and probably an exponential of the size)
- - Sequential ids give small _id
- - Random ids give large _id
- - Sequentials will clash between different dbs (consider replication,
multiple instances etc). They'll also lead people to rely on this
functionality as though it was like a SQL primary key
- - Random ids won't clash and better illustrate how CouchDB really works
> I think the info-leakage argument is overblown
It does make URLs easy to guess like many ecommerce sites that didn't
validate when showing you an invoice - you added one to the numeric id in
the URL and got to see someone elses.
I would far prefer the size of the db file and the size of the _id link
being addressed. Because the _id size can cause the db file to get so big,
I/O etc is a lot slower mainly because there is just so much more file to
deal with! (In my original posting I had a db go from 21GB to 4GB by
reducings ids from 16 bytes to 4 bytes.)
Roger
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEARECAAYFAktKb8AACgkQmOOfHg372QRb0ACfRWu1TUOs3twwmOGgAUOwhLfx
FJkAoKgnkWnPayPtPqMfk3/AxOj2xaMx
=V7Zq
-----END PGP SIGNATURE-----
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Chris Anderson <jc...@apache.org>.
On Sun, Jan 10, 2010 at 8:25 AM, Paul Davis <pa...@gmail.com> wrote:
> Was there a discussion I missed somewhere on making sequential uuid's
> the default algorithm? We decided against it when applying the patch
> from COUCHDB-465 [1] and I still hesitate to use anything other than
> completely random as the default. With the sequential algorithm we're
> leaking doc creation times in a non-obvious manner.
>
The discussion was in this thread:
http://mail-archives.apache.org/mod_mbox/couchdb-dev/201001.mbox/%3Ce282921e1001071104r78cd3fb3off29b13a24c86e95@mail.gmail.com%3E
I'm not feeling super-strong about this. However, making the default
sequential seems like it will preempt a lot of the problems people
tend to show up asking about. If even power users are running into the
issue before reconfiguring for faster uuids, then no amount of
documentation will help the people out there who are never gonna touch
any sort of config.
I think the info-leakage argument is overblown (I'm glad its easy to
config to fix this when it's important) -- with random uuids Couch can
become so slow as to be unusable, for some cases, with the sequential
ones you have to push a lot harder to get it into the red.
> I'd rather just see a wiki page on something like "Configuring CouchDB
> for improved performance" that went over any config settings to speed
> things up with relevant explanations for each. This could also cover
> batch inserts with the logic behind the changes.
>
> Paul Davis
>
> [1] https://issues.apache.org/jira/browse/COUCHDB-465
>
> On Sat, Jan 9, 2010 at 1:23 PM, <jc...@apache.org> wrote:
>> Author: jchris
>> Date: Sat Jan 9 18:23:16 2010
>> New Revision: 897509
>>
>> URL: http://svn.apache.org/viewvc?rev=897509&view=rev
>> Log:
>> make sequential uuids the default
>>
>> Modified:
>> couchdb/trunk/etc/couchdb/default.ini.tpl.in
>>
>> Modified: couchdb/trunk/etc/couchdb/default.ini.tpl.in
>> URL: http://svn.apache.org/viewvc/couchdb/trunk/etc/couchdb/default.ini.tpl.in?rev=897509&r1=897508&r2=897509&view=diff
>> ==============================================================================
>> --- couchdb/trunk/etc/couchdb/default.ini.tpl.in (original)
>> +++ couchdb/trunk/etc/couchdb/default.ini.tpl.in Sat Jan 9 18:23:16 2010
>> @@ -99,7 +99,7 @@
>> ; random prefix is regenerated and the process starts over.
>> ; utc_random - Time since Jan 1, 1970 UTC with microseconds
>> ; First 14 characters are the time in hex. Last 18 are random.
>> -algorithm = random
>> +algorithm = sequential
>>
>> [stats]
>> ; rate is in milliseconds
>>
>>
>>
>
--
Chris Anderson
http://jchrisa.net
http://couch.io
Re: svn commit: r897509 - /couchdb/trunk/etc/couchdb/default.ini.tpl.in
Posted by Paul Davis <pa...@gmail.com>.
Was there a discussion I missed somewhere on making sequential uuid's
the default algorithm? We decided against it when applying the patch
from COUCHDB-465 [1] and I still hesitate to use anything other than
completely random as the default. With the sequential algorithm we're
leaking doc creation times in a non-obvious manner.
I'd rather just see a wiki page on something like "Configuring CouchDB
for improved performance" that went over any config settings to speed
things up with relevant explanations for each. This could also cover
batch inserts with the logic behind the changes.
Paul Davis
[1] https://issues.apache.org/jira/browse/COUCHDB-465
On Sat, Jan 9, 2010 at 1:23 PM, <jc...@apache.org> wrote:
> Author: jchris
> Date: Sat Jan 9 18:23:16 2010
> New Revision: 897509
>
> URL: http://svn.apache.org/viewvc?rev=897509&view=rev
> Log:
> make sequential uuids the default
>
> Modified:
> couchdb/trunk/etc/couchdb/default.ini.tpl.in
>
> Modified: couchdb/trunk/etc/couchdb/default.ini.tpl.in
> URL: http://svn.apache.org/viewvc/couchdb/trunk/etc/couchdb/default.ini.tpl.in?rev=897509&r1=897508&r2=897509&view=diff
> ==============================================================================
> --- couchdb/trunk/etc/couchdb/default.ini.tpl.in (original)
> +++ couchdb/trunk/etc/couchdb/default.ini.tpl.in Sat Jan 9 18:23:16 2010
> @@ -99,7 +99,7 @@
> ; random prefix is regenerated and the process starts over.
> ; utc_random - Time since Jan 1, 1970 UTC with microseconds
> ; First 14 characters are the time in hex. Last 18 are random.
> -algorithm = random
> +algorithm = sequential
>
> [stats]
> ; rate is in milliseconds
>
>
>