[CASSANDRA-3881] reduce computational complexity of processing topology changes

• Type: Bug
• Status: Resolved
• Priority: Normal
• Resolution: Fixed
• Fix Version/s: 1.2.0 beta 1
• Labels: vnodes
• Severity: Normal
• Assignee: Sam Overton
• Reporter: Peter Schuller

Authors

Sam Overton

Reviewers

Jonathan Ellis

• Created: 09/Feb/12 10:31
• Updated: 16/Apr/19 09:32
• Resolved: 03/Jul/12 18:24

Description

This constitutes follow-up work from CASSANDRA-3831 where a partial improvement was committed, but the fundamental issue was not fixed. The maximum "practical" cluster size was significantly improved, but further work is expected to be necessary as cluster sizes grow.

Edit0: Appended patch information.

Patches

Compare	Raw diff	Description
00_snitch_topology	00_snitch_topology.patch	Adds some functionality to TokenMetadata to track which endpoints and racks exist in a DC.
01_calc_natural_endpoints	01_calc_natural_endpoints.patch	Rewritten O(logN) implementation of calculateNaturalEndpoints using the topology information from the tokenMetadata.

---

Note: These are branches managed with TopGit. If you are applying the patch output manually, you will either need to filter the TopGit metadata files (i.e. wget -O - <url> | filterdiff -x*.topdeps -x*.topmsg | patch -p1), or remove them afterward (rm .topmsg .topdeps).

Issue Links

• blocks: CASSANDRA-4119 Support multiple non-consecutive tokens per host (virtual nodes)
• relates to: CASSANDRA-3831 scaling to large clusters in GossipStage impossible due to calculatePendingRanges