#2405
- Created on2012-08-19 19:00
- Reported by
- StatusFixed
- PriorityHigh (2)
- Assigned to
- Milestone
- Plan Level-
- Due Date-
Member.ordering violates the holy trinity of hash code, equals, and compareTo
Here is a minimized example of our Member and the problem. Read status == 0 as the special Exiting status.
it is not removed.
The problem is that we violate this clause in java.util.Comparator:
We can not combine equality on address (only) and ordering with address and status.
Suggestion:
Keep the SortedSet, ordered by address only, and filter out Member with Exiting status when looking for leader.
Welcome to Scala version 2.10.0-M6 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_33).
Type in expressions to have them evaluated.
Type :help for more information.
scala> :paste
// Entering paste mode (ctrl-D to finish)
object Member {
implicit val ordering: Ordering[Member] = Ordering.fromLessThan[Member] { (a, b) ?
val addressOrderingResult = a.address.compareTo(b.address)
if (addressOrderingResult == 0) false
else if (a.status == 0 && b.status != 0) false
else if (a.status != 0 && b.status == 0) true
else addressOrderingResult < 0
}
}
class Member(val address: String, val status: Int) {
override def hashCode = address.##
override def equals(obj: Any) = obj match { case other: Member ? address == other.address; case _ ? false }
override def toString = "Member(address = %s, status = %s)" format (address, status)
}
// Exiting paste mode, now interpreting.
defined module Member
defined class Member
scala> import scala.collection.immutable.SortedSet
import scala.collection.immutable.SortedSet
scala> SortedSet(new Member("a", 1), new Member("b", 0), new Member("c", 1))
res0: scala.collection.immutable.SortedSet[Member] = TreeSet(Member(address = a, status = 1), Member(address = c, status = 1), Member(address = b, status = 0))
scala> res0 - new Member("b", 1)
res1: scala.collection.immutable.SortedSet[Member] = TreeSet(Member(address = a, status = 1), Member(address = c, status = 1), Member(address = b, status = 0))it is not removed.
The problem is that we violate this clause in java.util.Comparator:
- Finally, the implementor must ensure that <tt>compare(x, y)==0</tt>
- implies that <tt>sgn(compare(x, z))==sgn(compare(y, z))</tt> for all
- <tt>z</tt>.<p>
scala> val x = new Member("b", 0)
x: Member = Member(address = b, status = 0)
scala> val y = new Member("b", 1)
y: Member = Member(address = b, status = 1)
scala> Member.ordering.compare(x, y)
res15: Int = 0
scala> val z = new Member("c", 1)
z: Member = Member(address = c, status = 1)
scala> Member.ordering.compare(x, z)
res16: Int = 1
scala> Member.ordering.compare(y, z)
res17: Int = -1We can not combine equality on address (only) and ordering with address and status.
Suggestion:
Keep the SortedSet, ordered by address only, and filter out Member with Exiting status when looking for leader.
Leave a comment
Updating tickets (#939, #940, #1941, #2213, #2214, #2215, #2219, #2222, #2223, #2239, #2240, #2249, #2250, #2252, #2253, #2254, #2256, #2259, #2263, #2264, #2265, #2267, #2270, #2271, #2275, #2277, #2286, #2287, #2289, #2290, #2303, #2304, #2308, #2310, #2311, #2317, #2323, #2331, #2374, #2392, #2405, #2423, #2425, #2440, #2444, #2445, #2453, #2456, #2459, #2473, #2477, #2491, #2495, #2523, #2534, #2541, #2544, #2545, #2549, #2582, #2583, #2589, #2626)
Updating tickets (#939, #940, #1941, #2081, #2126, #2213, #2214, #2215, #2219, #2222, #2223, #2239, #2240, #2249, #2250, #2252, #2253, #2254, #2256, #2259, #2263, #2264, #2265, #2267, #2270, #2271, #2275, #2277, #2286, #2287, #2289, #2290, #2303, #2304, #2308, #2310, #2311, #2317, #2323, #2331, #2374, #2392, #2394, #2405, #2408, #2423, #2424, #2425, #2440, #2444, #2445, #2449, #2453, #2456, #2459, #2461, #2473, #2477, #2485, #2491, #2495, #2498, #2501, #2505, #2515, #2517, #2523, #2534, #2541, #2544, #2545, #2549, #2582, #2583, #2588, #2589, #2598, #2599, #2618, #2623, #2626, #2627, #2630, #2631, #2633, #2634, #2635, #2637, #2638, #2642, #2643, #2646, #2647, #2648, #2649, #2650, #2653, #2655, #2657, #2658)