Mutual Exclusion In JavaSpaces

Discussions

News: Mutual Exclusion In JavaSpaces

  1. Mutual Exclusion In JavaSpaces (18 messages)

    Lorenzo Puccetti has written "Mutual Exclusion In JavaSpaces," which attempts to start a trend in discussion of common patterns for space-based architecture. The pattern presented is, obviously, mutual exclusion - similar to synchronized blocks for regular Java code. The pattern discussion itself is fairly interesting: one solution is to take the space entry from the space, replacing the entry when the local processing is done. However, if the local processing fails, then the space won't magically get the entry back. The next step is to repair that by using transactions in the space; if the transaction leasetime expires, then the entry is released and other processes can access it as if nothing has happened. He closes the discussion of the pattern by pointing out that the "as if nothing has happened" phrase is incorrect - after all, the lease time will have expired, which means time has passed. This can lead to resource starvation, unless your architecture properly compensates for it. That compensation mechanism isn't gone into by Mr. Puccetti; what techniques would you suggest for compensating for multiple requests for a single element? (After all, this is appropriate beyond space-based architectures; consider java.util.concurrency's Latch mechanism, for example.) Also... what other patterns would you like to point out regarding space-based architectures?
  2. As mentioned in my blog post detailing the use of Jini Transactions... found here: "1) If client determines a particular duration for TX (10 secs) and it takes longer to process (12 secs) then we have an aborted TX and wasted effort on the part of the client and system. In addition if it is hard-coded or otherwise inflexible, we could get into a situation of the poison pill where noone is ever able to complete that unit of work! 2) If client determines a longer duration for TX (in case it takes longer than first predicted, how long should that be? However long they choose is likely to be too long. . .(They might choose FOREVER) and then if the client dies the TX and associated resources are locked preventing good work from occurring as well as potentially overloading a system if lots of failures occur. The upshot: Use LeaseRenewalManager to allow runtime flexibility and assurance that neither of those situations will ensue." The Jini LeaseRenewalManager allows the programmer to specify two things: 1)a frequency rate at which to renew the lease associated with a resource (such as a transaction) for example, every 5 seconds 2)the final cutoff time at which point the resource is released (if not already committed or aborted) for example, 24 hours Once established, the LeaseRenewalManager will continue to extend the lease on the specified resource (transaction) every 5 seconds until it is released through commit, abort, or until 24 hours have passed at which point it will no longer be in effect and anything locked in the transaction will be released for use by another thread. code snippet demonstrating this behavior is here Cheers, Owen. Owen Taylor Senior Director - Worldwide Technical Communications GigaSpaces Technologies Web: www.gigaspaces.com Blog: www.gigaspacesblog.com My Blog: http://jroller.com/page/owentaylor
  3. The pattern is fine where you have course grained synchronization, such as the example Lorenzo gives where there is a need to have quick failover between services where one service is active and another waiting in the wings to take over. In terms of the specifics of the algorithm there is a missing piece to consider which is the bootstapping of the process to ensure that the token that will be used for locking exists in the space! Something/one needs to take responsibility for writing the entry to the space to allows others to race to take it! John
  4. I must be me that I am missing the point, and without any judgement on the article, I think the 90% (or more) of the topic is covered in several (old) CS books. I studied these things in middle 80's using James L. Peterson, Abraham Silberschatz: Operating System Concepts Guido.
  5. This is a perfect example of how the JavaSpaces API can successfully deliver both un-inversion of control (UIOC) and requires massive amounts of complex, redundant, error-prone code to do the simplest things. Welcome to 1994.
    That compensation mechanism isn't gone into by Mr. Puccetti; what techniques would you suggest for compensating for multiple requests for a single element?
    Well, instead of having multiple requests, why not just use guaranteed once-and-only once processing? Then instead of having each server spin up threads to do the same exact "wait for something to do", you can have each server automatically "do" its fair share. (It's called Inversion of Control, or IoC, and it's all the rage this decade. ;-) Peace, Cameron Purdy Tangosol Coherence: The Java Data Grid
  6. Hey Cameron, I believe you are referring to the blocking take usage of a JavaSpace which provides guaranteed once and only once processing. Example: //--not shown creation of tx Task template = new Task(); Task todo = (Task)space.take(template, tx, 24*3600*1000); //--not shown creation of result space.write(result, tx, 24*3600*1000); tx.commit(); Clearly, the author had something else in mind when he suggested Mutual Exclusion with a space. Cheers, Owen.
  7. Example:
    //--not shown creation of tx
    Task template = new Task();
    Task todo = (Task)space.take(template, tx, 24*3600*1000);
    //--not shown creation of result
    space.write(result, tx, 24*3600*1000);
    tx.commit();
    Owen, You are making my case for me .. just look at that code! Peace, Cameron Purdy Tangosol Coherence: The Java Data Grid
  8. This is a perfect example of how the JavaSpaces API can successfully deliver both un-inversion of control (UIOC) and requires massive amounts of complex, redundant, error-prone code to do the simplest things.

    Welcome to 1994.

    :-) Could hardly say it better. In Russia we have good saying pertaining to approaches like that - “Manual Sunset”, something you don’t have to do... manually. Seriously, I get the technical feasibility of what is proposed but it looks way complicated for what it does and there are other solutions that do that simpler. Best, Nikita Ivanov GridGain – Open Source Grid Computing For Java
  9. Cameron Just as small reminder for something you said recently that i found relevant to this discussion:
    Our reason for considering the introduction of JavaSpaces into Coherence is to allow programmers to use the spaces model and the JavaSpaces API to code parts of those transactions. While JavaSpaces is not an effective data management API (i.e. it's not good for replacing a database), it is an effective data processing API (i.e. it can easily be used for computational processing in a grid). So Coherence can certainly bring those two concepts together (data managed by a database and processed using a spaces approach). source
    I would also suggest to look at the following post from that same thread for a reference of a user that is using similar pattern already successfully. Anyway i fail to see the complexity with the example that Owen just outlined. If you need to be able to execute tasks and guarantee not just that it will be executed once and only once but that it will roll-back to its previous state and enable other worker to continue the processing from that exact point in a case of a failure you will need to follow those steps in one way or the other. Having said that a Spring-Remoting abstraction enables you to utilize the master/worker pattern implicitly and invoke method on POJO-Workers as if they where just a local instance. Here is a snippet of how the master would look like with this approach: ITask proxy = (ITask)applicationContext.getBean("worker-proxy"); Result res = proxy.execute("data") In the above example the interaction with the space happens behind the scenes when the master-application call's proxy.execute("data") . At this stage the proxy calls the space.write(..) with the method-name and argument as a command-entry. That command is then delivered to a generic delegator on the worker side that invoke the method on the right bean. The return-value of that invocation is writen back to the space as a response. I think that it shows how IoC and Space based programming can actually fit nicely together by applying the right level of abstraction. Nati S. GigaSpaces Write Once Scale Anywhere
  10. Just as small reminder for something you said recently that i found relevant to this discussion..
    Yes, and as I said above, "I could show you in our product several areas where we are considering supporting it".
    Anyway i fail to see the complexity with the example that Owen just outlined.
    I recognize that, and I don't believe that to be a good thing ;-) We too have engineers that -- left unchecked -- would inflict the same sorts of pain on our customers. That's why it's important to go through extensive reviews (including by application developers) of architectures and APIs before loosing them on the unsuspecting public. JavaSpaces is a great example of an API that would have greatly benefited from a vetting by at least a few real-world developers. Instead, it is an eclectic collection of the flawed religious convictions of its designers. Why JoeO bothers to push it here despite its obvious failure is beyond me.
    Having said that a Spring-Remoting abstraction enables you to utilize the master/worker pattern implicitly and invoke method on POJO-Workers as if they where just a local instance.

    Here is a snippet of how the master would look like with this approach:


    ITask proxy = (ITask)applicationContext.getBean("worker-proxy");
    Result res = proxy.execute("data")
    Now you're talking! That's a much better example, and one that you should lead with! Please, no more hard-coded 24*3600*365 stuff ..
    In the above example the interaction with the space happens behind the scenes ..
    Exactly. JavaSpaces, as it is, is raw plumbing. Exposing it at an application level, i.e. forcing application developers to be aware of it, is a huge mistake. (That's why Paremus hides it, for example.)
    I think that it shows how IoC and Space based programming can actually fit nicely together by applying the right level of abstraction.
    The nice thing about the abstraction is that it has nothing to do with "space based programming". IMHO, the problem is that -- for general purpose programming concerns -- "space based programming" using JavaSpaces is an awful abstraction. OTOH, I can see some specific places where the tuple-space style API can be used appropriately, when you want those concerns to be surfaced, e.g. across process spaces. p.s. At some point, we should really talk about what these APIs should look like. That would be a much more fun conversation, and would feel less like abusing a deceased horse. ;-) Peace, Cameron Purdy Tangosol Coherence: The Java Data Grid
  11. Hear hear
  12. The nice thing about the abstraction is that it has nothing to do with "space based programming". IMHO, the problem is that -- for general purpose programming concerns -- "space based programming" using JavaSpaces is an awful abstraction.
    There is always a trade-off between flexibility/completeness and simplicity of API. The right way to deal with that trade-off IMO is to make sure that the underlying implementation can address the full set of requirements and provide abstraction on top of it to ensure that the simple scenario remains simple. For the sake of this discussion i think that it is important to understand the the full set of requirements for parallel task execution and understand what of those requirements are covered in each option before making an opinion which option is better. Following is a partial list of such requirements 1. Enable execution of once and only once execution 2. Enable broadcasting of tasks to all workers 3. Enable synchronous and asynchronous execution of tasks 4. Enable recoverability of task execution in case of a failiure 5. Enable load balancing of task distribution 6. Handle slow consumer scenario Let's see how JavaSpaces addresses all of these requirements: 1. Master/Worker where the worker uses take operation 2. Master/worker where the worker uses notify operation 3. Master can wait for a response to support synchronous execution(perform blocking take or the result entry), or asynchronously. 4. Through the distributed transaction semantics 5. In pull-mode workers compete on task execution between themselves, with this model slow/busy workers will consume less tasks then fast workers without any need for expensive scheduling. 6. Through pull mode (we also handle that under push(notify) mode. As can be seen the master/worker pattern ontop of the space can address those set of requirements using a combination of 3 API's (write, take, notify) therfore i think that it is fairly simple if you take into consideration the set of requirements it can address. The Remoting abstraction is used to simplify the scenario in which i'm only interested in parallel method invocation to individual service. It cannot address the full set of requirements mentioned above, specifically the many to many relationship. For that i would probably use another abstraction such as the Executor interface. A good example of a big investment bank that is actually using both models under the same analytical application context can be found here This brings me to the last point: JavaSpaces is a simple API that addresses a relatively complex problem - distributed computing. Through the right level of abstraction it can be simplified to address specific scenarios such as Remoting without compromising on functionality. In some cases it will make sense to use the more generic API and in other cases the more specialized one even under the same application. Having said that i would agree with you that it wouldn't be a bad idea if the current spec would be upgraded to make it a better fit with new programming practices and capabilities that didn't exist when the spec was defined, specifically i think that it needs to support POJO's semantics, Generics, Declerative transactions etc. These are things that we've already done and are doing through our own extensions with the intent to suggest them as extension to the current spec
    p.s. At some point, we should really talk about what these APIs should look like. That would be a much more fun conversation, and would feel less like abusing a deceased horse. ;-)
    Good idea, i know that a lot of people in the community are actually waiting for that to happen. If you're interested i would even welcome you to drop a visit to Tel-Aviv, you'll find that the sea, the weather and the food is actually great at this time of the year. As for the "deceased horse", I'm sure you'll be glad to know that he is live and kicking and is actually doing pretty well these days:) Cheers Nati S GigaSpaces Write Once Scale Anywhere
  13. If you're interested i would even welcome you to drop a visit to Tel-Aviv, you'll find that the sea, the weather and the food is actually great at this time of the year.
    I've got some open invites to visit some customers in Israel, so next time I'm over .. ;-)
    As for the "deceased horse", I'm sure you'll be glad to know that he is live and kicking and is actually doing pretty well these days :)
    I didn't mean any specific technology, just the argument itself .. as in beating a dead horse. Peace, Cameron Purdy Tangosol Coherence: The Java Data Grid
  14. I've got some open invites to visit some customers in Israel, so next time I'm over .. ;-)
    Sounds good. I look forward for it. We should probably do the same next time I'm in Boston. Nati S.
  15. I've used used both GigaSpaces and Coherence and would be quite happy to use either one in the future. I have to say that Coherence has about the most thoughtfully designed APIs I have ever used, and finds a way to combine simplicity with flexibility. For a data grid, its ValueExtractors and Filters are exactly what you need. Similarly for WorkManager, EntryProcessor, Aggregations etc. GigaSpaces on the other hand does not have such beautiful APIs. Sorry Nati! Where it makes up for it, is with a set of distributed computing atomic operations that can be used to build exactly those sorts of APIs yourself. We had some GigaSpaces professional services guys visiting recently who were surprised that very few people on our GigaSpaces project actually wrote Space code. It's simply because when we find a need to use the Space, we hide it with an abstraction. There are only a couple of people on our project that know GigaSpaces, mostly we focus on our Domain. Our data in the Space is accessed through DAOs. Our desktop clients use Spring GigaSpaces remoting to access standard business interfaces. Our optimistic locking used for ETL is hidden behind an abstraction, hiding all the IJSpace code. public interface CreateOrUpdateOperation { T create() throws Exception; T update(T existing) throws Exception; } When we identified a common pattern of running complex calculations across large numbers of domain objects, we put an abstraction that takes care of partitioning, data affinity and runs the calculations inside the JVM that contains the data. public interface AnalysisService { R calculate(Selection selection, Calculation calculation); } This is an implementation of the JavaSpaces Master Worker pattern, but with the academic code hidden and the business logic brought to the surface.
  16. When we find a need to use the Space, we hide it with an abstraction. There are only a couple of people on our project that know GigaSpaces, mostly we focus on our Domain.

    Our data in the Space is accessed through DAOs.

    Our desktop clients use Spring GigaSpaces remoting to access standard business interfaces.

    Our optimistic locking used for ETL is hidden behind an abstraction, hiding all the IJSpace code.


    public interface CreateOrUpdateOperation {
    T create() throws Exception;
    T update(T existing) throws Exception;
    }


    When we identified a common pattern of running complex calculations across large numbers of domain objects, we put an abstraction that takes care of partitioning, data affinity and runs the calculations inside the JVM that contains the data.


    public interface AnalysisService {
    R calculate(Selection selection, Calculation calculation);
    }


    This is an implementation of the JavaSpaces Master Worker pattern, but with the academic code hidden and the business logic brought to the surface.
    Yuri having Remtoing, DAO and other abstraction the way you did is the right practice for every project and every technology to avoid locking to specific implementation. I therfore think that your approach is the right one and should serve as an example for everyone that is facing similar challenges. My argument wasn't the Space API is the answer for everything i was actually arguing that there isn't a single API that fit's it all. My argument was that flexibility of the Space makes it the superset for addressing messaging and data requirements and various degrees of reliability. It provide high degree of flexibility around those area's at a cost of usability. Putting abstraction on top of it makes it more user friendly for specific use-cases. In this way people can easily write their own abstraction and extension without being dependent on us in the same way you did and benefit from the fact that they have a consistent underlying runtime implementation across the different set of API's. As you already mentioned part of our Spring support already provides some of those abstractions out of the box. We will be providing more of those abstraction with our next release. With our upcoming openspaces community project we intend to extend the community around that model so i expect that more people like yourself would be able to contribute and share tools and abstractions as well influence the project direction specifically around API. I think that you had been very influential so far in this area and I hope to see you continue with that enthusiasm even more with openspaces. HTHs Nati S. GigaSpaces Write Once Scale Anywhere
  17. Thanks Gents for the comments. My turn now for a few clarifications.
    @Owen: whether you want to use the jini LeaseRenewalManager or write your own thread to renew the transactions that is an implementation detail. The point of the pattern is isolate out the user from that aspect and give him/her a simple interface to say: ... gate.enter(); // some work gate.exit(); ... @Joseph: the "compensation mechanism" for resource starvation is delierately missing. As I say: You could improve the solution in different ways to enforce fair access to shared resources but you probably don't want to do that. Infact if that is the case it is likely that your distributed architecture has some clear performance bottlenecks, specifically around your multi-process synchronized blocks. By the way you are right in observing that I intended to hear more about common patterns for space based architectures.
    @john: Good Point ! The pattern does assume that when the space is created the required gate entries are written in the space. This task is responsibility of the process which starts/embeds the space.
    @cameron: Surely not the biggest fan of javaspaces :-) I genuinely don't see why a pattern to coordinate the activity of processes around a space can be classed UIOC.
  18. @cameron: Surely not the biggest fan of javaspaces :-) I genuinely don't see why a pattern to coordinate the activity of processes around a space can be classed UIOC.
    No, I'm just not a fan of QAPI-style architectures :-) What I mean by "UIOC" is that the code that does the actual processing work gets polluted with and convoluted by the needs of the "server code", instead of just servicing the work. Compare an MDB with the JavaSpaces example above to see what I mean .. not cool. I think that where UIOC is warranted or acceptable, then JavaSpaces works. I could show you in our product several areas where we are considering supporting it, such as client-driven C/C++ connections into a data grid. In general, though, adopting JavaSpaces as a general-purpose programming paradigm is a recipe for excruciating pain, which most people fortunately realized a long time ago. Oh, and BTW -- your "gate" example is much better, but I'd still rather just say "here's the thing that implements some service interface that I want you to call; make sure it's running on exactly one server at all times". That's IoC. Peace, Cameron Purdy Tangosol Coherence: The Java Data Grid
  19. In computer science there are many ways of doing the same thing. IMHO the challenge is making it simple, usable and flexible. Solutions such as Terracotta, Coherence and JBoss Cache do a good job, but I dislike to reliance on AOP and annotations or meta-data. For mutual exclusion I have found the Visitor pattern work well and you can use plain-old-java. In this example, the Store can be backed by disk or database and multi-mastered across multiple JVMs. Here the visitor is applied atomically and transactionally. If an exception is throw, the transaction is rolled back and thrown by the caller. Note: There is no need for annotations, AOP, meta-data, XML files or explicit transactions. public class UniqueIdManager { private final Store uniqueIds; public UniqueIdManager(Store uniqueIds) { this.uniqueIds = uniqueIds; } public long getIds(final String name, final long blockSize) { return uniqueIds.visit(new Visitor, Long>() { public Long visit(Store visited) throws VisitorException { return visited.getMapView().get(name).getIds(blockSize); } }); } public static class UniqueId { public final String name; private long value; public UniqueId(String name, long value) { this.name = name; this.value = value; } public synchronized long getIds(long blockSize) { long ret = value; value += blockSize; return ret; } } } The Store has a number of views as either a Queue, ConcurrentMap or JCache. Listeners can be added to a Store and listen to changes which occur on any node which support event driven processing. In this case, a timeout shouldn't be required, however a timeout can be set on the transaction.