http://ayende.comAyende @ RahienCopyright (C) Ayende Rahien 2004 - 2021 (c) 202660Highly unlikely http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment21http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment21Mon, 26 Jul 2010 18:56:03 GMTDemis, The problem is simple, doubly linked list requires you to have mutable data structure. I am trying to do this in an immutable, append only, manner http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment20http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment20Wed, 23 Jun 2010 10:27:59 GMTVery interesting perspective indeed. Out of curiosity, why would you go with the dual 'front and back' lists approach over say a double-linked list e.g. C# LinkedList collection datatype? I would've thought that a double-linked list is the perfect collection type for adding items to the head and tail of a list in constant time. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment19http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment19Wed, 23 Jun 2010 02:02:44 GMTMikeS, Yes, it would http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment18http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment18Fri, 18 Jun 2010 14:47:20 GMTSo, reading between the lines, does this mean that RavenDB supports or will soon support highly performant snapshot isolation? That would be very cool - and in line with Couch & Mongo. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment17http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment17Fri, 18 Jun 2010 14:34:34 GMTMikeS, Yep, that is pretty much what is going on there. In the code here, we pretty much have this situation. Readers & Writers operate independently from one another. We don't have to worry about a thing. The actual name for that is MVCC (multi version concurrency control), append only system that support more than a single thread are naturally MVCC and support this natively http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment16http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment16Fri, 18 Jun 2010 14:04:45 GMTCorrection: I should have said snapshot isolation, not serializable isolation. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment15http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment15Fri, 18 Jun 2010 13:36:04 GMTAyende, True, writers block writers but that's a lot better than writers blocking readers as well. [en.wikipedia.org/.../InterBase](http://en.wikipedia.org/wiki/InterBase#Multi-generational_architecture) [en.wikipedia.org/.../Multiversion_concurrency_c...](http://en.wikipedia.org/wiki/Multiversion_concurrency_control) It's one of the things that attracted me to Interbase years ago and then Firebird after Borland open-sourced the code. Not requiring locking allows cheap serializable isolation. There has to be some garbage collection for versions that no longer have active transactions. Oracle added it in v3 and SQL Server finally got around to it in 2005. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment14http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment14Fri, 18 Jun 2010 13:31:07 GMTFWIW, This method means that readers don't block writers and writers don't block readers, but writers blocks writers. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment13http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment13Fri, 18 Jun 2010 12:36:23 GMTMike, Any more information about that? http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment12http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment12Fri, 18 Jun 2010 12:35:46 GMTNice, I like the speed :-) I'm curious whether you considered versioning as an alternative solution? I believe Interbase was the first RDBMS systems to introduce it - they call it Multi-Generational Architecture. It allow readers not to block and writers not to block readers. I don't know whether it would apply to the requirements for which you built this solution, but it's an interesting alternative to logs and append-only WRT implementing transactional systems. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment11http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment11Fri, 18 Jun 2010 11:56:22 GMTTim, A special value is written if the value is null. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment10http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment10Thu, 17 Jun 2010 14:54:29 GMTThanks for the reply. I've found the answer to writing integers with 7 bit encoding... but still the question remains: "Reason I'm asking is that I'm uncertain what a method like WriteBitEncodedNullableInt64(long? value) would write to disk." What do you write if the value is null? http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment9http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment9Thu, 17 Jun 2010 14:42:23 GMTCorey & William, This is useful for the managed storage option for Raven. William, I think you meant, RAvenDB is going to have Append Only support http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment8http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment8Thu, 17 Jun 2010 14:37:03 GMTCorey & William, This is useful for the managed storage option for Raven. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment7http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment7Thu, 17 Jun 2010 14:36:39 GMTTim, The binary reader / writer just inherit BinaryWriter and BinaryReader and does 7 bit encoding, that is all. You can look how they do that in Reflector, BinaryWriter.Write7BitEncodedInt http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment6http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment6Thu, 17 Jun 2010 14:36:06 GMTRafal, 1) no, this is not multi threaded. In general, both transaction log & append only need to ensure consistent flushes, so they serialize writes to the transaction log / append only stream. 2) It is actually pretty efficient. The perf test produced a file that was 701MB in size, with the raw data being 683 MB of that. We are talking about 3% overhead, which is more than reasonable, I think. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment5http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment5Thu, 17 Jun 2010 14:35:12 GMT@Cory Not sure myself but maybe RavenDB is going to have a Transaction Log support http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment4http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment4Thu, 17 Jun 2010 14:14:22 GMTI always love your posts that explain how to do something but don't give context as to why you are doing it. Where are you going with this? http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment3http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment3Thu, 17 Jun 2010 13:29:08 GMTVerry interesting... I've been reading this article a couple of times now but I keep wondering: The two binary reader and writer classes you are new'ing up several times in your code: where's the code for the implementation of these (BinaryReaderWith7BitEncoding & BinaryWriterWith7BitEncoding)? Reason I'm asking is that I'm uncertain what a method like WriteBitEncodedNullableInt64(long? value) would write to disk. http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment2http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment2Thu, 17 Jun 2010 13:24:36 GMT1. Is it multithreaded? What about two threads writing to the same file at once? 2. What about the size of queue file? Won't it be too big? http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment1http://ayende.com/4540/building-a-managed-persistent-transactional-queue#comment1Thu, 17 Jun 2010 12:41:22 GMT