From 5f36d81e47fd142ee7b7c172012917b11411db8d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Kjetil=20=C3=98rbekk?= Date: Tue, 24 Jan 2012 11:27:57 +0100 Subject: Refactor Paxos: Return proposal values. --- .../main/java/com/orbekk/paxos/MasterProposer.java | 37 ++++++++++++++-------- .../main/java/com/orbekk/paxos/PaxosService.java | 10 ++++-- .../java/com/orbekk/paxos/PaxosServiceImpl.java | 14 ++++---- .../java/com/orbekk/paxos/MasterProposerTest.java | 8 ++--- .../java/com/orbekk/paxos/PaxosServiceTest.java | 18 +++++------ 5 files changed, 52 insertions(+), 35 deletions(-) diff --git a/same/src/main/java/com/orbekk/paxos/MasterProposer.java b/same/src/main/java/com/orbekk/paxos/MasterProposer.java index 912de7e..7bc4350 100644 --- a/same/src/main/java/com/orbekk/paxos/MasterProposer.java +++ b/same/src/main/java/com/orbekk/paxos/MasterProposer.java @@ -17,37 +17,48 @@ public class MasterProposer { this.connections = connections; } - private boolean internalPropose(int proposalNumber) { + private int internalPropose(int proposalNumber) { + int bestPromise = proposalNumber; int promises = 0; for (String url : paxosUrls) { PaxosService paxos = connections.getPaxos(url); - boolean success = paxos.propose(myUrl, proposalNumber); - if (success) { + int result = paxos.propose(myUrl, proposalNumber); + if (result == proposalNumber) { promises += 1; } + bestPromise = Math.min(bestPromise, result); + } + if (promises > paxosUrls.size() / 2) { + return proposalNumber; + } else { + return bestPromise; } - return promises > paxosUrls.size() / 2; } - private boolean internalAcceptRequest(int proposalNumber) { + private int internalAcceptRequest(int proposalNumber) { + int bestAccepted = proposalNumber; int accepts = 0; for (String url : paxosUrls) { PaxosService paxos = connections.getPaxos(url); - boolean success = paxos.acceptRequest(myUrl, proposalNumber); - if (success) { + int result = paxos.acceptRequest(myUrl, proposalNumber); + if (result == proposalNumber) { accepts += 1; } + bestAccepted = Math.min(bestAccepted, result); + } + if (accepts > paxosUrls.size() / 2) { + return proposalNumber; + } else { + return bestAccepted; } - return accepts > paxosUrls.size() / 2; } public boolean propose(int proposalNumber) { - boolean success = false; - success = internalPropose(proposalNumber); - if (success) { - success = internalAcceptRequest(proposalNumber); + int result = internalPropose(proposalNumber); + if (result == proposalNumber) { + result = internalAcceptRequest(proposalNumber); } - if (success) { + if (result == proposalNumber) { return true; } else { return false; diff --git a/same/src/main/java/com/orbekk/paxos/PaxosService.java b/same/src/main/java/com/orbekk/paxos/PaxosService.java index b515fa9..a92a794 100644 --- a/same/src/main/java/com/orbekk/paxos/PaxosService.java +++ b/same/src/main/java/com/orbekk/paxos/PaxosService.java @@ -1,6 +1,12 @@ package com.orbekk.paxos; public interface PaxosService { - boolean propose(String clientUrl, int proposalNumber); - boolean acceptRequest(String clientUrl, int proposalNumber); + + /** + * @return N == proposalNumber if a promise is made. + * -M if another promise already was made, where M is the promise + * highest proposal number. + */ + int propose(String clientUrl, int proposalNumber); + int acceptRequest(String clientUrl, int proposalNumber); } diff --git a/same/src/main/java/com/orbekk/paxos/PaxosServiceImpl.java b/same/src/main/java/com/orbekk/paxos/PaxosServiceImpl.java index 1e8387e..3ecf523 100644 --- a/same/src/main/java/com/orbekk/paxos/PaxosServiceImpl.java +++ b/same/src/main/java/com/orbekk/paxos/PaxosServiceImpl.java @@ -17,36 +17,36 @@ public class PaxosServiceImpl implements PaxosService { } @Override - public synchronized boolean propose(String clientUrl, + public synchronized int propose(String clientUrl, int proposalNumber) { if (proposalNumber > highestPromise) { - highestPromise = proposalNumber; logger.info(tag + "propose({}, {}) = accepted", new Object[]{clientUrl, proposalNumber}); - return true; + highestPromise = proposalNumber; + return highestPromise; } else { logger.info(tag + "propose({}, {}) = rejected " + "(promised: {})", new Object[]{clientUrl, proposalNumber, highestPromise}); - return false; + return -highestPromise; } } @Override - public synchronized boolean acceptRequest(String clientUrl, + public synchronized int acceptRequest(String clientUrl, int proposalNumber) { if (proposalNumber == highestPromise) { logger.info(tag + "acceptRequest({}, {}) = accepted", new Object[]{clientUrl, proposalNumber}); highestAcceptedValue = proposalNumber; - return true; + return highestAcceptedValue; } else { logger.info(tag + "acceptRequest({}, {}) = rejected " + "(promise={})", new Object[]{clientUrl, proposalNumber, highestPromise}); - return false; + return -highestPromise; } } } diff --git a/same/src/test/java/com/orbekk/paxos/MasterProposerTest.java b/same/src/test/java/com/orbekk/paxos/MasterProposerTest.java index 45ee53e..dfc0b19 100644 --- a/same/src/test/java/com/orbekk/paxos/MasterProposerTest.java +++ b/same/src/test/java/com/orbekk/paxos/MasterProposerTest.java @@ -30,8 +30,8 @@ public class MasterProposerTest { @Test public void successfulProposal() { connections.paxosMap.put("p1", p1); - when(p1.propose("client1", 1)).thenReturn(true); - when(p1.acceptRequest("client1", 1)).thenReturn(true); + when(p1.propose("client1", 1)).thenReturn(1); + when(p1.acceptRequest("client1", 1)).thenReturn(1); MasterProposer c1 = new MasterProposer( "client1", @@ -42,8 +42,8 @@ public class MasterProposerTest { @Test public void unsucessfulProposal() { connections.paxosMap.put("p1", p1); - when(p1.propose("client1", 1)).thenReturn(true); - when(p1.acceptRequest("client1", 1)).thenReturn(false); + when(p1.propose("client1", 1)).thenReturn(1); + when(p1.acceptRequest("client1", 1)).thenReturn(1); MasterProposer c1 = new MasterProposer( "client1", diff --git a/same/src/test/java/com/orbekk/paxos/PaxosServiceTest.java b/same/src/test/java/com/orbekk/paxos/PaxosServiceTest.java index f9ee058..0165d4c 100644 --- a/same/src/test/java/com/orbekk/paxos/PaxosServiceTest.java +++ b/same/src/test/java/com/orbekk/paxos/PaxosServiceTest.java @@ -37,23 +37,23 @@ public class PaxosServiceTest { @Test public void simpleCase() { - assertTrue(p1.propose(client, 1)); - assertTrue(p1.acceptRequest(client, 1)); + assertEquals(1, p1.propose(client, 1)); + assertEquals(1, p1.acceptRequest(client, 1)); } @Test public void lowerProposalFails() { - assertTrue(p1.propose(client1, 10)); - assertFalse(p1.propose(client2, 9)); - assertTrue(p1.propose(client2, 100)); + assertEquals(10, p1.propose(client1, 10)); + assertEquals(-10, p1.propose(client2, 9)); + assertEquals(100, p1.propose(client2, 100)); } @Test public void testAccept() { - assertTrue(p1.propose(client1, 3)); - assertTrue(p1.propose(client2, 4)); - assertFalse(p1.acceptRequest(client1, 3)); - assertTrue(p1.acceptRequest(client2, 4)); + assertEquals(3, p1.propose(client1, 3)); + assertEquals(4, p1.propose(client2, 4)); + assertEquals(-4, p1.acceptRequest(client1, 3)); + assertEquals(4, p1.acceptRequest(client2, 4)); } public List paxosUrls() { -- cgit v1.2.3