Commit Details
Repository
https://sgs-server.dev.java.net/svn/sgs-server/trunk
/trunk
by
jloizeaux
on
2009-12-07 21:47
(3 months ago)
Additions for finding affinity groups in Darkstar systems, required for issue #54 (Load balancing between nodes).
============ Misc changes =================
M sgs-server/src/main/java/com/sun/sgs/impl/kernel/Kernel.java
A sgs-server/src/main/java/com/sun/sgs/impl/kernel/SystemIdentity.java
- Add a SystemIdentity type, and make the Identity created by the Kernel for the system
this type. The affinity graph listener does not include object access information
for the system identity in the affinity graphs.
M sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/NodeMappingServiceImpl.java
- Hook for creating the affinity subsystem. An affinity group finder is created, which
checks properties to see if the other parts of the affinity system should be instantiated.
NOTE this change will likely be modified once this work is integrated with the rest
of Keith's node health changes. The key idea is we have a single object that needs
to be constructed to integrate the affinity group finding objects.
M sgs-server-internal-api/src/main/java/com/sun/sgs/profile/ProfileListener.java
- Fix typo in documentation for required constructor.
M sgs-server-internal-api/src/main/java/com/sun/sgs/management/TaskAggregateMXBean.java
- Fix typo.
M sgs-server/src/main/etc/findbugs-exclude.xml
- Quiet findbugs warning.
M sgs-server/pom.xml
M sgs-server-dist/src/main/assembly/dist.xml
M pom.xml
- Include JUNG graph package.
M sgs-server-dist/src/main/etc/CHANGELOG
- Note changes.
============ Affinity package + new JMX interface =================
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/package-info.java
- Package for affinity group finding using the label propagation algorithm (LPA). This
package contains generic pieces that can be used by all implementations.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/AffinityGroupFinder.java
- Interface for parts of the system which find affinity groups.
Likely to be moved once we integrate with the group coordinators.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/LPAAffinityGroupFinder.java
- Extension for the AffinityGroupFinder, used by the LPA variations, which adds the ability to
request an algorithm run begin.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/AffinityGroupFinderFailedException.java
- Exception thrown if LPAAffinityGroupFinder has problems finding affinity groups.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/AffinityGroup.java
- Interface for an AffinityGroup, which is a set of identities and an affinity group id.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/AffinitySet.java
- A simple, serializable AffinityGroup.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/RelocatingAffinityGroup.java
- Concrete AffinityGroup, based on work in Keith's branch (so should be considered a stub).
This affinity group is returned by the multi-node LPA implementations and eventually will
cause member identities to be relocated to healthy nodes in the system.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/AbstractLPA.java
- An abstract class containing key pieces of the LPA implementations that are common
to all.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/BasicState.java
- An encapsulation of some basic states needed by both affinty group finders and graph builders.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/LPADriver.java
- An affinity group finder which drives the LPA algorithm implementation (the implementation is
selected by property), instantiating the required pieces for the implementation.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/AffinityGroupGoodness.java
- A pair of goodness measures for affinity groups. Modularity is a popular method of determining
if found groups are any better than random groups within the same graph (but require an intact
graph to make the calculation, so are not useful if the graph is divided over several nodes).
The Jaccard index is a common way to measure the amount of similarity between two sets of groups.
Both measures are discussed in the literature about finding groups within large graphs, and
are useful for testing.
A sgs-server-internal-api/src/main/java/com/sun/sgs/management/AffinityGroupFinderMXBean.java
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/AffinityGroupFinderStats.java
- JMX exposed information for AffinityGroupFinders. All finders support this.
============ Affinity graph package + new JMX interface =================
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/graph
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/graph/package-info.java
- Package containing graph classes and interfaces. These graphs are consumed by AffinityGroupFinders.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/graph/AffinityGraphBuilder.java
- Interface for affinity graph builders.
Graphs represent identities (vertices) and the number of common interations. Currently, those
interations are data object accesses.
Graphs are pruned over time, so old data is removed.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/graph/GraphListener.java
- ProfileListener which gathers identity + object access information for each task on a node.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/graph/WeightedEdge.java
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/graph/LabelVertex.java
- Edges and vertices in our affinity graphs. The vertices represent an identity in the system,
and includes a label (which is the label manipulated during the LPA processing). Edges are weighted,
and represent the number of common object accesses between its two endpoint vertices. Note
that edge weights can represent any number or manner of interactions between identities (currently,
we track object accesses).
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/graph/AbstractAffinityGraphBuilder.java
- A base class for parsing common properties and maintaining state, used by all graph builders.
A sgs-server-internal-api/src/main/java/com/sun/sgs/management/AffinityGraphBuilderMXBean.java
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/graph/AffinityGraphBuilderStats.java
- JMX exposed information for AffinityGraphBuilders. All builders support this.
============ Single Node LPA =================
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/single
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/single/package-info.java
- LPA implementation that works on a single node only. This is (of course) not useful for mult-node
load balancing, but is a useful way to test the algorithm itself.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/single/SingleLabelPropagation.java
- The LPA implementation. It follows the Raghavan, Albert, and Kumara 2007 paper almost directly.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/single/SingleGraphBuilder.java
- The graph builder for single-node LPA. A side data structure is maintained for the object accesses
for each identity, and a count of those accesses. It is used to detect common accesses between
identities.
- Some methods are used to make wrapping this class in another easier (the dgb implementation wraps this
class).
============ Distributed Graph Builder LPA =================
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dgb
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dgb/package-info.java
- An implementation of LPA where the graph builder is distributed. Each node contains a graph builder
which consumes profile task information about object accesses and forwards it to a server graph builder
on the core server node. The core server node, then, can build the entire affinity graph and can
act much like the single node LPA implementation.
- This implementation will be useful for testing. It does not have a dependency on the caching data
service, but probably won't scale as well as the distributed LPA version will.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dgb/DistGraphBuilderServer.java
- Interface for the server which accepts graph updates.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dgb/DistGraphBuilder.java
- The portion of the graph builder that's on the application nodes, which forwards graph updates to
the server.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dgb/DistGraphBuilderServerImpl.java
- Server which accepts graph updates and is also an affinity group finder. It wraps the single node
builder and finder.
============ Distributed LPA =================
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/package-info.java
- The distributed LPA implementation. In this implementation, the algorithm itself is distributed.
Each node maintains the portion of the affinity graph that is created on that node, and can
exchange information about the graph with other nodes.
The server drives the algorithm, telling the participating nodes to prepare for a run, and then
to run each iteration. The server stops the algorithm when all nodes have converged on an answer,
or when the iteration count becomes high (papers show that higher iterations don't get us closer
to a "good" answer).
- This implementation is INCOMPLETE (and thus not tested on a live system) because it depends on
getting node conflict information from the caching data store. This information is used by each
node to stitch together the affinity graph across nodes.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/LPAClient.java
- Interface for the client portion of the algorithm. The application nodes are the clients.
- One set of methods is called by the server to drive running the algorithm.
- Another set (notifyCrossNodeEdges and getRemoteLabels) are called by other LPAClients based on the
conflict information they have obtained. These calls allow them to find out the labels of
vertices that are not on their node.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/LPAServer.java
- Interface for the server portion of the algorithm.
- Callbacks for the LPAClients to call indicating their asynchronous actions are done (readyToBegin
and finishedIteration), as well as a way for clients to register with the server (for when
a new node joins a Darkstar cluster), and a way for clients to find proxies for other clients.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/LabelPropagation.java
- The LPAClient, instantiated on each application node.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/LabelPropagationServer.java
- The LPAServer, instantiated on the core server node.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/graph
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/graph/package-info.java
- The graph builder portion of the distributed LPA algorithm. I ended up implementing two versions,
so I split it into its own package.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/graph/DLPAGraphBuilder.java
- Interface for the distributed graph builder (useful since I had two implementations).
This adds a way to get conflict and object use information, and some node bookkeeping.
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/graph/WeightedGraphBuilder.java
- A version of the graph builder which takes in task information and, on the fly, converts the information
into the affinity graph form that's easiest for the LPA to process (identities are vertices, edges are
weighted and represent common object accesses). I believe this will be our default version, as testing
(on smallish programs only) showed that it was fastest to build the affinity graph on the fly.
A side data structure of object use counts is also maintained; I have not measured how large this can
get ... but that's a concern. That side data structure is also useful for figuring out how the graph
spans nodes, though, as the caching data service will give us information about objects, which we need
to relate to Identities that use those objects.
- NOTE: will need to be updated to support listener interface supplied by the caching data service (I have
a hook for it implemented).
A sgs-server/src/main/java/com/sun/sgs/impl/service/nodemap/affinity/dlpa/graph/BipartiteGraphBuilder.java
- A version of the graph builder which holds the information as it comes to us from the profiling system,
and converts it into what the LPA algorithm wants on demand. The information we get is bipartite in
nature: vertices are either Identities or objects, and the weighted edges between them are the number
of times an Identity has used a particular object (recall that the LPA implementation wants to know the
number of times two identities have used objects in common, not caring what those particular objects are).
- NOTE: will need to be updated to support listener interface supplied by the caching data service (I have
a hook for it implemented).
============ Testing changes =================
M sgs-server/src/test/java/com/sun/sgs/test/impl/profile/TestMBeans.java
- Fix minor typo.
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity
- New tests for the LPA based affinity group finders.
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/GraphBuilderTests.java
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/TestSingleNodeBuilder.java
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/TestDistLPABuilder.java
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/TestDistGraphBuilder.java
- Tests for the various graph builders, which differ mostly in how they are constructed.
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/TestLPA.java
- Tests for the Distributed LPA algorithm.
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/TestAffinityGroupGoodness.java
- Tests for the "goodness" measures.
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/AbstractTestGraphBuilder.java
- A base class for test graph builders, to help implement the interface. The test graphs are "canned",
in that we use known graphs.
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/ZachBuilder.java
- Utility test graph builder, used by a couple of the tests, which constructs a Zachary karate club graph.
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/TestLPAPerf.java
A sgs-server/src/test/java/com/sun/sgs/test/impl/service/nodemap/affinity/TestLPADistGraphPerf.java
- Performance tests for the various implementations. All use the Zachary karate network, hand-constructed
to represent how identities and conflicts might occur across nodes, which allows us to use modularity
as a goodness measure.
M sgs-server/src/test/java/com/sun/sgs/test/util/SgsTestNode.java
- Disable affinity groups by default.
M sgs-server/src/test/properties/logging.properties
- Add (commented out) useful property for tracing affinity group algorithm.
Language Totals
| Language | Code Added | Code Removed | Comments Added | Comments Removed | Blanks Added | Blanks Removed | |
|---|---|---|---|---|---|---|---|
| Java | 7153 | 3 | 3774 | 2 | 1024 | 0 | |
| XML | 17 | 0 | 2 | 0 | 4 | 0 |
Files Changed
[62 total ]
| File | Language | Code Added | Code Removed | Comments Added | Comments Removed | Blanks Added | Blanks Removed |
|---|---|---|---|---|---|---|---|
pom.xml
|
|||||||
| XML | 6 | 0 | 0 | 0 | 1 | 0 | |
sgs-server-dist/src/main/assembly/dist.xml
|
|||||||
| XML | 1 | 0 | 0 | 0 | 0 | 0 | |
sgs-server-dist/src/main/etc/CHANGELOG
|
|||||||
sgs-server-internal-api/src/main/java/com/sun/sgs/management/AffinityGraphBuilderMXBean.java
|
|||||||
| Java | 11 | 0 | 58 | 0 | 9 | 0 | |
sgs-server-internal-api/src/main/java/com/sun/sgs/management/AffinityGroupFinderMXBean.java
|
|||||||
| Java | 17 | 0 | 93 | 0 | 15 | 0 | |
sgs-server-internal-api/src/main/java/com/sun/sgs/management/TaskAggregateMXBean.java
|
|||||||
| Java | 0 | 0 | 1 | 1 | 0 | 0 | |
sgs-server-internal-api/src/main/java/com/sun/sgs/profile/ProfileListener.java
|
|||||||
| Java | 0 | 0 | 1 | 1 | 0 | 0 | |
sgs-server/pom.xml
|
|||||||
| XML | 4 | 0 | 0 | 0 | 1 | 0 | |
sgs-server/src/main/etc/findbugs-exclude.xml
|
|||||||
| XML | 6 | 0 | 2 | 0 | 2 | 0 | |
sgs-server/src/main/java/com/sun/sgs/impl/kernel/Kernel.java
|
|||||||
| Java | 1 | 1 | 0 | 0 | 0 | 0 | |