Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
Here, the paper is now. You can download it from here http://www-ps.informatik.uni-kiel.de/~frk/dstm.pdf. It is one pdf file. The first part is the paper, the second part is the manual that has been there before. Regards, Frank Am 04.08.2010 um 15:55 schrieb Frank Kupke: Good questions. I am about to write a paper explaining the design of the DSTM library in more detail which I will link when available. Please bear with me, here. In the meantime please find some shorter answers below. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
Paul, Yes, I use Read and Show to serialize. I thought of switching to Binary myself but could not find the time yet ;-) Now, a student here is going to work on that. Also, as TCP communication involves a lot of overhead, the library makes some efforts to reduce the amount of messages and makes message exchange itself quite efficient which resulted in a significant efficiency gain. But, there is definitely more optimization potential buried... Frank Am 06.08.2010 um 00:49 schrieb Paul Johnson: Looks interesting. One point: you seem to be using Read and Show typeclasses for serialisation. I think you would be better off using Binary, which is much more efficient. Paul. On 03/08/10 09:35, Frank Kupke wrote: Hi, DSTM is an implementation of a robust distributed Software Transactional Memory (STM) library for Haskell. Many real-life applications are distributed by nature. Concurrent applications may profit from robustness added by re-implementation as distributed applications. DSTM extends the STM abstraction to distributed systems and presents an implementation efficient enough to be used in soft real-time applications. Further, the implemented library is robust in itself, offering the application developer a high abstraction level to realize robustness, hence, significantly simplifying this, in general, complex task. The DSTM package consists of the DSTM library, a name server application, and three sample distributed programs using the library. Provided are a simple Dining Philosophers, a Chat, and a soft real-time Bomberman game application. Distributed communication is transparent to the application programmer. The application designer uses a very simple name server mechanism to set up the system. The DSTM library includes the management of unavailable process nodes and provides the application with abstract error information thus facilitating the implementation of robust distributed application programs. For usage please look into the documentation file: DSTMManual.pdf. The package including the documentation can be found on: http://hackage.haskell.org/package/DSTM-0.1.1 Best regards, Frank Kupke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
Am 04.08.2010 um 23:16 schrieb Andrew Coppin: Frank Kupke wrote: Andrew, Thanks for pointing your finger at it Am 04.08.2010 um 17:48 schrieb Andrew Coppin: In that case, is there a way to determine whether or not the rest of the transaction completed? Because it looks like you can the same exception either way, regardless of whether a commit happened or not. Ah, now I see. Excellent point. I was always focussing the commit case which is well designed, I am certain. OK, so there's design work to do here. (Or at least, things to think about.) But that's OK. It's new and exciting. :-) Andrew, oops. Your question was sure pointing me to an issue I had to rethink twice. My last reply to you was shot a bit too quickly. The implemented design throws an exception to the application in two cases: - if the app reads a TVar, calling readTVar, and the TVar is not accessible - if a transaction, a call of atomic, is validated and one or more of the to be validated TVars are not accessible (that I said also before) However, *no* exception is thrown if the transaction *has been* validated and the failure occurs afterwards during the commit phase (here my reply was incorrect). In this case the transaction silently commits all remaining (i.e. non failing) TVars. Failing TVars are simply ignored besides internal cleanup work which is transparent to the app. Back to your original question then: A transaction throwing the distribution exception (other exceptions are possible, too, but are orthogonal to this one) signals to the app that the transaction did not commit because of a TVar failure (Btw, reading a TVar also occurs in a transaction and in case of such an exception the app knows also that the transaction did not finish, it did not even try to validate, though). What about a transaction that committed in spite of unavailable TVars? Answer: The app would not know until the next time it tries to access the failing TVar. Then it definitely gets an exception, either because of reading it or validating the transaction. A committed (i.e. returning) transaction tells the app that whatever it wanted to synchronize with other parts of the system succeeded and it can continue its work. It does not guarantee, though, that the other parts are still alive. This failure semantics, of course, can be discussed. Any input is welcome. Frank PS: I have uploaded DSTM 0.1.2 with minor changes based on the discussion here. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
Thanks. In fact, the server lookup is needed only to make initial contact to another node, or better - as the distributed architecture is transparent to the app programmer - to make initial contact to another TVar. This initial TVar would then be able to distribute more TVars. It could be typed something like: data initTVar a = TVar [TVar a] Also, once you have made contact (i.e. lookup from name server) to a TVar, you can access it as if it were locally defined. It does not matter if the name server then fails or not. Obviously, a failed name server would not allow to make new contacts. Then your distributed program would need to create redundant name servers and make sure their IP address stays the same or is known to every node. Frank Am 03.08.2010 um 21:59 schrieb Alberto G. Corona: That is really nice. The architecture seems to be around a single server that bring lookup services, so there is a single point of failure. I´m thinking on cloud computing. Can be extended to have backup servers somehow ? Alberto. 2010/8/3 Christopher Done chrisd...@googlemail.com This is very cool, thanks for writing it. I will try it when I get home tonight. On 3 August 2010 10:35, Frank Kupke f...@informatik.uni-kiel.de wrote: Hi, DSTM is an implementation of a robust distributed Software Transactional Memory (STM) library for Haskell. Many real-life applications are distributed by nature. Concurrent applications may profit from robustness added by re-implementation as distributed applications. DSTM extends the STM abstraction to distributed systems and presents an implementation efficient enough to be used in soft real-time applications. Further, the implemented library is robust in itself, offering the application developer a high abstraction level to realize robustness, hence, significantly simplifying this, in general, complex task. The DSTM package consists of the DSTM library, a name server application, and three sample distributed programs using the library. Provided are a simple Dining Philosophers, a Chat, and a soft real-time Bomberman game application. Distributed communication is transparent to the application programmer. The application designer uses a very simple name server mechanism to set up the system. The DSTM library includes the management of unavailable process nodes and provides the application with abstract error information thus facilitating the implementation of robust distributed application programs. For usage please look into the documentation file: DSTMManual.pdf. The package including the documentation can be found on: http://hackage.haskell.org/package/DSTM-0.1.1 Best regards, Frank Kupke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
data InitTVar a = TVar [TVar a] sorry Am 04.08.2010 um 10:04 schrieb Frank Kupke: Thanks. In fact, the server lookup is needed only to make initial contact to another node, or better - as the distributed architecture is transparent to the app programmer - to make initial contact to another TVar. This initial TVar would then be able to distribute more TVars. It could be typed something like: data initTVar a = TVar [TVar a] Also, once you have made contact (i.e. lookup from name server) to a TVar, you can access it as if it were locally defined. It does not matter if the name server then fails or not. Obviously, a failed name server would not allow to make new contacts. Then your distributed program would need to create redundant name servers and make sure their IP address stays the same or is known to every node. Frank Am 03.08.2010 um 21:59 schrieb Alberto G. Corona: That is really nice. The architecture seems to be around a single server that bring lookup services, so there is a single point of failure. I´m thinking on cloud computing. Can be extended to have backup servers somehow ? Alberto. 2010/8/3 Christopher Done chrisd...@googlemail.com This is very cool, thanks for writing it. I will try it when I get home tonight. On 3 August 2010 10:35, Frank Kupke f...@informatik.uni-kiel.de wrote: Hi, DSTM is an implementation of a robust distributed Software Transactional Memory (STM) library for Haskell. Many real-life applications are distributed by nature. Concurrent applications may profit from robustness added by re-implementation as distributed applications. DSTM extends the STM abstraction to distributed systems and presents an implementation efficient enough to be used in soft real-time applications. Further, the implemented library is robust in itself, offering the application developer a high abstraction level to realize robustness, hence, significantly simplifying this, in general, complex task. The DSTM package consists of the DSTM library, a name server application, and three sample distributed programs using the library. Provided are a simple Dining Philosophers, a Chat, and a soft real-time Bomberman game application. Distributed communication is transparent to the application programmer. The application designer uses a very simple name server mechanism to set up the system. The DSTM library includes the management of unavailable process nodes and provides the application with abstract error information thus facilitating the implementation of robust distributed application programs. For usage please look into the documentation file: DSTMManual.pdf. The package including the documentation can be found on: http://hackage.haskell.org/package/DSTM-0.1.1 Best regards, Frank Kupke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
After chatting with Chris privately it turned out that the confusion within the Chat example is partly because I did not find a good and simple solution for mixing user input and chat output asynchronously in one terminal stream. One can possibly do better, here. Also, apparently I left some debug flags active in the library which does not help to explore it. Sorry. You can turn debugging mode off by setting all debug flags to False in DebugBase.hs. I will correct that with the next update as well. As a quick fix to put the documentation online it can be downloaded from http://www-ps.informatik.uni-kiel.de/~frk/dstm.pdf, also available through my very rudimentary institute's web presence http://www.informatik.uni-kiel.de/prog/mitarbeiter/frank-kupke/. Regards, Frank Am 04.08.2010 um 10:43 schrieb Chris Eidhof: This looks very cool! It would be nice to put the pdf online somewhere, and add a link from the package documentation. Also, the chat client seems to have some problems with output buffering on my system (OS X, GHC 6.12). -chris On 3 aug 2010, at 10:35, Frank Kupke wrote: Hi, DSTM is an implementation of a robust distributed Software Transactional Memory (STM) library for Haskell. Many real-life applications are distributed by nature. Concurrent applications may profit from robustness added by re-implementation as distributed applications. DSTM extends the STM abstraction to distributed systems and presents an implementation efficient enough to be used in soft real-time applications. Further, the implemented library is robust in itself, offering the application developer a high abstraction level to realize robustness, hence, significantly simplifying this, in general, complex task. The DSTM package consists of the DSTM library, a name server application, and three sample distributed programs using the library. Provided are a simple Dining Philosophers, a Chat, and a soft real-time Bomberman game application. Distributed communication is transparent to the application programmer. The application designer uses a very simple name server mechanism to set up the system. The DSTM library includes the management of unavailable process nodes and provides the application with abstract error information thus facilitating the implementation of robust distributed application programs. For usage please look into the documentation file: DSTMManual.pdf. The package including the documentation can be found on: http://hackage.haskell.org/package/DSTM-0.1.1 Best regards, Frank Kupke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
Good questions. I am about to write a paper explaining the design of the DSTM library in more detail which I will link when available. Please bear with me, here. In the meantime please find some shorter answers below. Regards, Frank Am 04.08.2010 um 10:53 schrieb Andrew Coppin: Frank Kupke wrote: For usage please look into the documentation file: DSTMManual.pdf. 1. Any danger of puting this somewhere I can read it without having to download and manually unpack the Hackage tarball? Actually not. I just had not thought about it. Here is a link to the pdf. http://www-ps.informatik.uni-kiel.de/~frk/dstm.pdf 2. Since DSTM depends on the Unix package, I presume this won't work on Windows. (?) OOC, what does it use Unix for? Good point. I use System.Posix for benchmark debug code and a sigPIPE handler. Probably both can go without doing any damage. I will look into it. As you can tell, I have not tested using Windows... 3. It is unclear to me what happens in the event of a communications failure. The documentation says an exception is thrown, but does the running transaction rollback or just retry or...? (The documentation seems to suggest that it might actually *commit* in spite of a communications failure, which sounds wrong.) Two things happen in parallel. + One is that the library throws an exception to the application saying basically: Hey, at least one of your TVars you just accessed is broken, you better check which ones and react on it in your program. This is the abstraction level outside of a transaction (atomic function). The app now knows that one or more of its services represented by TVars is down and needs attention. + The other thing is the low-level stuff within the transaction thus within the library. The behavior of the transaction depends on *when* actually the failure is detected. - If the failure comes up *before* the transaction has been validated ok, it is aborted. A normal invalidation abort would restart the transaction automatically but in this case throwing the exception terminates it. Abort is often called rollback (when referring to databases) but I prefer not to because up to now everything has been done safely within the STM monad. Nothing happened in the IO world, hence nothing need to be rolled back. (Btw. *retry* is a different kind of transaction restart. It is not done automatically but forced by the application calling the retry function.) - If the failure comes up *after* the transaction has been validated ok, it is committed. At first, this might look wrong but it is not. Here is why: If the validation is ok, all participating TVars on any node have agreed that the transaction is ready to commit. If then any one of these TVars fails, the decision to commit is still valid as nothing else has changed. Note that all TVars are locked by the library from before validating until after committing. Furthermore, some TVars might have already finished the commit. Then it would be inconsistent for the others not to commit. In both cases, commit or not, however, the library takes precautions that no deadlocks build up by broken TVars unexpectedly quitting the transaction protocol. Also, when is failure detected? Is it only when a transaction tries to access the variable? Yes. However, all such accesses are happening within the library and are fully transparent to the application. As TCP is a connection based protocol only simulating a connection, we do not know exactly when a connection actually breaks. We can peek, though. Either by sending test messages (ping), if they bounce, the connection is obviously broken; Or by just observing when a regular message bounces. Regular messages are due to reading, validating, committing, ... TVars within atomic transactions. The library detects the failure (sooner or later) and informs the application by throwing the exception right after the detection. From an application's perspective the failure is only detected when the application reads from or writes to the TVar within an atomic transaction. If a TVar is not accessed its failure might remain undetected. 4. What network transport does this thing use? TCP? UDP? What port numbers? DSTM uses TCP communication. It searches dynamically for available ports starting at port 60001, using 6 for the name server. If two nodes are running each on a separate machine with a different IP address, chances are that both use the same port 60001. If they run on the same machine, most likely one will use port 60001 and the other 60002. 5. How does it work? Does it spawn a Haskell thread for each machine connection or something? Each node spawns a Haskell thread listening to its designated port and spawning itself a thread for each accepted TCP communication, i.e. one for each foreign node talking to it. Each such thread implements a communication line between two threads. I have tried several communication line schemas
Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
John, a very nice idea. I have not worked with git yet but used an svn repository on our institute server. I will look into it though and eventually set something up. In the meantime you are welcome to send patches to me for merging them into the project. Frank Am 04.08.2010 um 18:54 schrieb John Van Enk: Is there a Git/Darcs dev repo hiding anywhere we could submit patches to? On Tue, Aug 3, 2010 at 4:35 AM, Frank Kupke f...@informatik.uni-kiel.de wrote: Hi, DSTM is an implementation of a robust distributed Software Transactional Memory (STM) library for Haskell. Many real-life applications are distributed by nature. Concurrent applications may profit from robustness added by re-implementation as distributed applications. DSTM extends the STM abstraction to distributed systems and presents an implementation efficient enough to be used in soft real-time applications. Further, the implemented library is robust in itself, offering the application developer a high abstraction level to realize robustness, hence, significantly simplifying this, in general, complex task. The DSTM package consists of the DSTM library, a name server application, and three sample distributed programs using the library. Provided are a simple Dining Philosophers, a Chat, and a soft real-time Bomberman game application. Distributed communication is transparent to the application programmer. The application designer uses a very simple name server mechanism to set up the system. The DSTM library includes the management of unavailable process nodes and provides the application with abstract error information thus facilitating the implementation of robust distributed application programs. For usage please look into the documentation file: DSTMManual.pdf. The package including the documentation can be found on: http://hackage.haskell.org/package/DSTM-0.1.1 Best regards, Frank Kupke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: DSTM 0.1.1
Andrew, Thanks for pointing your finger at it Am 04.08.2010 um 17:48 schrieb Andrew Coppin: Frank Kupke wrote: Good questions. I am about to write a paper explaining the design of the DSTM library in more detail which I will link when available. Please bear with me, here. In the meantime please find some shorter answers below. Well, that was pretty comprehensive. A few questions remain... - If the failure comes up *before* the transaction has been validated ok, it is aborted. Right. So the transaction rolls back and the application gets an exception? Yes, the transaction aborts and the application gets an exception (see remarks below). - If the failure comes up *after* the transaction has been validated ok, it is committed. So if a TVar goes walkabout in the split second between validate and commit, the others commit anyway, and then the application gets an exception? Yes. In that case, is there a way to determine whether or not the rest of the transaction completed? Because it looks like you can the same exception either way, regardless of whether a commit happened or not. Ah, now I see. Excellent point. I was always focussing the commit case which is well designed, I am certain. But, maybe, the abort case above is not. It would probably be better to not only abort but also restart the transaction even in presence of a failure (that is what's being done when there is no failure). I am not quite clear yet about a possible implementation of such a behavior. Currently I'm thinking: Restarting a transaction containing broken TVars will definitely fail again. To avoid that, the validation vote of a broken TVar (i.e. not able to vote any more) should be taken as a valid vote and no exception should be thrown. Eventually every transaction comes to a commit and probably that's the only place where an exception should be thrown. Then the answer to your question is clear, also. Any opinions? 4. What network transport does this thing use? TCP? UDP? What port numbers? DSTM uses TCP communication. It searches dynamically for available ports starting at port 60001, using 6 for the name server. If two nodes are running each on a separate machine with a different IP address, chances are that both use the same port 60001. If they run on the same machine, most likely one will use port 60001 and the other 60002. Right. So both the nameserver and any clients run on random port numbers? (Begs the question of how the clients figure out which port a remote nameserver is on...) Well, not quite. The name server gets a fixed 6 to make it accessible statically, the others may vary. Their dynamic address is used to label the TVars which then always carry their correct address. 5. How does it work? Does it spawn a Haskell thread for each machine connection or something? Each node spawns a Haskell thread listening to its designated port and spawning itself a thread for each accepted TCP communication, i.e. one for each foreign node talking to it. Each such thread implements a communication line between two threads. I have tried several communication line schemas which I will describe in more detail in the paper yet to come... What impact (if any) does threaded vs non-threaded RTS have? I have done a few tests with threads and could not find a significant difference. But I really did not look deep and thorough enough into it to give a qualified answer. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: DSTM 0.1.1
Hi, DSTM is an implementation of a robust distributed Software Transactional Memory (STM) library for Haskell. Many real-life applications are distributed by nature. Concurrent applications may profit from robustness added by re-implementation as distributed applications. DSTM extends the STM abstraction to distributed systems and presents an implementation efficient enough to be used in soft real-time applications. Further, the implemented library is robust in itself, offering the application developer a high abstraction level to realize robustness, hence, significantly simplifying this, in general, complex task. The DSTM package consists of the DSTM library, a name server application, and three sample distributed programs using the library. Provided are a simple Dining Philosophers, a Chat, and a soft real-time Bomberman game application. Distributed communication is transparent to the application programmer. The application designer uses a very simple name server mechanism to set up the system. The DSTM library includes the management of unavailable process nodes and provides the application with abstract error information thus facilitating the implementation of robust distributed application programs. For usage please look into the documentation file: DSTMManual.pdf. The package including the documentation can be found on: http://hackage.haskell.org/package/DSTM-0.1.1 Best regards, Frank Kupke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
