You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Jaakko Laine (JIRA)" <ji...@apache.org> on 2009/12/09 15:49:18 UTC
[jira] Created: (CASSANDRA-617) gossiper scalability
gossiper scalability
--------------------
Key: CASSANDRA-617
URL: https://issues.apache.org/jira/browse/CASSANDRA-617
Project: Cassandra
Issue Type: Improvement
Components: Core
Affects Versions: 0.5
Reporter: Jaakko Laine
Fix For: 0.5
Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-617) gossiper scalability
Posted by "Jaakko Laine (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12790142#action_12790142 ]
Jaakko Laine commented on CASSANDRA-617:
----------------------------------------
Does somebody have a good suggestion for compression algorithm/implementation? I tested LZF from Voldemort and java.util.zip. Zip compresses gossip data roughly on 4~5:1 ratio (or 2~3:1 for smaller messages). LZF seems to be unsuitable for this kind of data, as compression ratio was only about 40-60%. This was a very quick test, so I might have done something wrong, though.
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.5
> Reporter: Jaakko Laine
> Fix For: 0.5
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (CASSANDRA-617) gossiper scalability
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis resolved CASSANDRA-617.
--------------------------------------
Resolution: Not A Problem
Fix Version/s: (was: 0.6)
Assignee: (was: Jaakko Laine)
CASSANDRA-705 moved gossip into TCP.
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Jaakko Laine
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-617) gossiper scalability
Posted by "Jaakko Laine (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jaakko Laine updated CASSANDRA-617:
-----------------------------------
Attachment: spread_90.png
spread_50.png
averages.png
I've run some simulated gossiper tests and there are some issues with Gossiper scalability:
(1) Overall capacity to spread state information:
Due to gossiper packet size, at most 117 gossip digest messages fit into one GossipDigestSynMessage. This means that if there are more than 117 nodes, at one round only a subset of all digests (endpoint states) can be gossiped. This can cause starvation as some nodes' state information has to potentially queue for long time before getting a chance to spread (for example if there are 234 nodes, there's only 50% chance for state information to spread at each stage). Due to this, the time it takes for one state information to reach all nodes, grows logarithmically only to 117 nodes. Growth rate after this seems to be linearish (it is not exponential as randomness and multiple paths between any two nodes dampen the effect of worsening max_digest_size / all_endpoints_size ratio). Attached chart (averages.png) shows average amount of rounds it takes for a piece of gossip to reach given percentage of nodes. As can be seen, after cluster size exceeds 117 nodes, the curves take a sharp turn upwards.
As can also be seen, when cluster size grows, 98% curve stays considerably lower than 100%. When there are only a few nodes without certain piece of gossip, max_digest_size / all_endpoints_size ratio plays bigger role and it is more difficult for certain state information to reach the last nodes.
Attached there are also spread_100.png, spread_90.png and spread_50.png charts. These show minimum, maximum and average time to reach 100%, 90% and 50% of the nodes respectively. Samples per one stage (number of nodes) were only 12 gossips, so there is some room for error, but should give some indication as to how the gossiper behaves in larger clusters.
(2) Ability of Ack message to spread endpoint state information
(a) Size of GossipDigestAckMessage is similarly restricted, so the amount of gossip digests and endpoint states it can carry is also limited. In the simulation, once cluster size reaches about 80-90 nodes, not all endpoint states can be included in Ack message. This means that on top of delays caused by Syn message limitations, also Ack message capacity will cause delays in endpoint state propagation.
(b) Another related issue is how GossipDigestAckMessage size is divided between digests and endpoint states. Currently all digests are included first, and then, if there is room, as many endpoint states will be included as will fit. In the simulation this was not a problem, but it might happen that digests take so much room that not many endpoint states can be included.
(3) New nodes entering a large cluster
(a) When a new node enters a ring, it will first gossip to a seed and let it know that it has joined the cluster. However, the way SYN/ACK/ACK2 exchange works, the seed will not volunteer information about any other nodes it knows about. Only when a seed randomly chooses this node to gossip to, the new node will know (through the arriving Syn message) about other nodes. In a large cluster, this chance might be very small (less than a percent), so the node might need to wait for considerable time before getting knowledge of other nodes.
(b) Another related issue is endpoint state size. There are currently four "move" application states, which make the whole endpoint state rather big. During normal operation these states are of course delivered as deltas, but when a new node enters the ring, full state needs to be delivered. Only 9-10 of these states fit to one Ack message, so it will take some time before all data is delivered in a big cluster.
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.5
> Reporter: Jaakko Laine
> Fix For: 0.5
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-617) gossiper scalability
Posted by "Jaakko Laine (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12788466#action_12788466 ]
Jaakko Laine commented on CASSANDRA-617:
----------------------------------------
> Wouldn't it be worth making gossip state names an enum? This would (a) make it harder to screw things up with name collisions, and (b) make name part of gossip load almost negligible.
Yeah, I was also thinking about making the names shorter (or enum), but this is only part of the problem. Since we have four different move states, we also have the token in the gossiper four times (three of which are obsolete at any time). Biggest impact in reducing total amount of data in the gossiper would be to reduce the amount of move states to one, but this discussion has not yet reached a conclusion (#572).
> Compress the messages which are being sent. I have seen 5:1 compression is achievable. So if you send 117 per the JIRA this is automatically 500+.
Compression sounds good, but needs to be investigated how much it would actually help in this case. Gossip digest is IP:generation:version, so it should compress quite well. Big part of ApplicationState payload is random data (token), however, so it will not compress so well. Squeezing many digests into one Syn message might not help as much as it seems on paper, as Ack might not be able to keep up the pace (even now it starts to drop data sooner than Syn). Now of course during normal operation Ack mainly carries gossip digests and "empty" EPStates (only heartbeat), so APState compress ratio might not be a problem at all.
> move to TCP and compress and send all digests.
Wouldn't like to do this lightly, but let's keep it in mind. It would need rather big cluster before TCP overhead is worth paying for.
> if we can get to ~500 with compression and the simpler fixes
Yeah, I agree there is no need to rush, so let's do the simple stuff now and see when/if we need more complex stuff later.
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.5
> Reporter: Jaakko Laine
> Fix For: 0.5
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-617) gossiper scalability
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-617:
-------------------------------------
Fix Version/s: (was: 0.5)
0.9
Assignee: Jaakko Laine
Affects Version/s: (was: 0.5)
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Jaakko Laine
> Assignee: Jaakko Laine
> Fix For: 0.9
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-617) gossiper scalability
Posted by "Jaakko Laine (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12788115#action_12788115 ]
Jaakko Laine commented on CASSANDRA-617:
----------------------------------------
As for the fixes...
(1) I think the easiest way would be to give Gossiper a chance to send multiple Syn messages per round. If it cannot send "enough" (enough being certain threshold percentage) digests compared to how many endpoints there are in all, it could send multiple Syn messages to the same host. Gossiper messages are independent of each other, so they can be handled separately. The downside would be that there is potentially quite a number of endpoint states to handle per one round. However, since current way is for all nodes to know about all other nodes, this will put a cap to scalability at some point in any case. (No idea at what point, though).
(2a) Depends on (1). If we can send multiple messages per round, then this one goes away.
(2b) Multiple messages will also solve this. However, if we stick to one message per round, we might consider guaranteeing certain chunk of packet for both purposes.
(3a) When handling Syn message with only one digest (the sending node), include random endpoint state information in the reply as much as there is room. This way a new node does not need to wait for syn message from the seed to start gathering information about other nodes.
(3b) Might not be a big issue, but in order to squeeze more endpoint states to gossip messages, perhaps it would be good idea to reduce the number of "move" states from four separate states to one. This would decrease the total amount of data in Gossiper "cloud" potentially by tens of percents. Would speed up the process of new node gathering node info.
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.5
> Reporter: Jaakko Laine
> Fix For: 0.5
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-617) gossiper scalability
Posted by "Jaakko Laine (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jaakko Laine updated CASSANDRA-617:
-----------------------------------
Attachment: spread_100.png
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.5
> Reporter: Jaakko Laine
> Fix For: 0.5
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-617) gossiper scalability
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12790168#action_12790168 ]
Jonathan Ellis commented on CASSANDRA-617:
------------------------------------------
since we're only compressing a small amount of data relatively infrequently, zip seems fine to me
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.5
> Reporter: Jaakko Laine
> Fix For: 0.5
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-617) gossiper scalability
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12788135#action_12788135 ]
Jonathan Ellis commented on CASSANDRA-617:
------------------------------------------
Wouldn't it be worth making gossip state names an enum? This would (a) make it harder to screw things up with name collisions, and (b) make name part of gossip load almost negligible.
Avinash also suggested:
* Compress the messages which are being sent. I have seen 5:1 compression is achievable. So if you send 117 per the JIRA this is automatically 500+.
* If and if absolutely necessary move to TCP and compress and send all digests. Then all the problems go away.
IMO [jbellis again] if we can get to ~500 with compression and the simpler fixes (your Syn fix, move state optimization, enum names) then that gives us a long time before any current user of Cassandra needs to worry about the complexity of adding multiple messages per round (or the even bigger change of moving to TCP).
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.5
> Reporter: Jaakko Laine
> Fix For: 0.5
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-617) gossiper scalability
Posted by "Avinash Lakshman (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12789810#action_12789810 ]
Avinash Lakshman commented on CASSANDRA-617:
--------------------------------------------
The heartbeats which are predominantly what take up Gossip state and hence compression really helps out here. TCP overhead is actually negligible and we can still restrict the size of the Gossip packet to be around 8K and then compress. But TCP suggestion was mainly for clusters perhaps in excess of 1000 nodes. The reason I brought that up was because if we do it we can forget about it once and for all :).
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.5
> Reporter: Jaakko Laine
> Fix For: 0.5
>
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-617) gossiper scalability
Posted by "Jaakko Laine (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-617?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12803088#action_12803088 ]
Jaakko Laine commented on CASSANDRA-617:
----------------------------------------
current move to tcp is a bit problematic, see #705 for more discussion.
> gossiper scalability
> --------------------
>
> Key: CASSANDRA-617
> URL: https://issues.apache.org/jira/browse/CASSANDRA-617
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Jaakko Laine
> Attachments: averages.png, spread_100.png, spread_50.png, spread_90.png
>
>
> Improve gossiper scalability.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.