As long as all access to these nodes is through the ULL class then the lock at the base node for writes, giving a datastructure wide lock, should make that threadsafe (i.e. only one writer can lock the base at a given time, therefore only one writer can be adjusting the item count at a given time).
Though in this case the lock can be gained against the page node very easily just by changing the order of the code: Node page = checkSplitNode( getPage( node ), node ); page.setProperty( ITEM_COUNT, ((Integer) page.getProperty( ITEM_COUNT )) + 1 ); return page.createRelationshipTo( node, GraphCollection.RelationshipTypes.VALUE ); To: Node page = checkSplitNode( getPage( node ), node ); Relationship relationship = page.createRelationshipTo( node, GraphCollection.RelationshipTypes.VALUE ); page.setProperty( ITEM_COUNT, ((Integer) page.getProperty( ITEM_COUNT )) + 1 ); return relationship; Where from my understanding the creation of the relationship from the page node will lock that node therefore making the subsequent line thread safe even without the global base node lock. I could live easily with having to have a transaction for reading over the collection, as long as multiple readers could be in the collection at the same time. I am trying to think of a way of doing this, basically at present my thinking is along the lines of: 1. multiple read lock nodes are attached to the base node (say N) 2. when a thread accesses the collection for read access it locks one of these nodes (by removing non-existent property) 3. therefore, as long as each read thread locks a different node, N reading threads can be in at once 4. for a write to occur the writer first locks the base node, then locks each of the read lock nodes meaning that neither readers or writers can get their required lock The difficulty comes in point 3 above, how to have threads lock different nodes? To do this accurately you would need to be able to check whether someone else has a lock on a given node at a given time. A simple half working option would be having say 20 read lock nodes hanging off the base node, and randomly choose one. Would mean there is a good chance that multiple readers could run at once. On Sat, Sep 24, 2011 at 10:20 AM, Niels Hoogeveen <pd_aficion...@hotmail.com > wrote: > > Read integrity is really a dog. We haven't even begun to address that in > the other collections. > With regards to write locks ( and this is something we should check in > sortedtree too ) is code like: > page.setProperty( ITEM_COUNT, ((Integer) page.getProperty( ITEM_COUNT )) + > 1 ); > This is only threadsafe if the value returned by page.getProperty( > ITEM_COUNT ) is read from a locked node. > Niels > > > Date: Sat, 24 Sep 2011 09:14:07 +1200 > > From: bryc...@gmail.com > > To: user@lists.neo4j.org > > Subject: Re: [Neo4j] Unrolled Linked List > > > > For writing that works well, and in fact for add node I am doing that > (just > > realised I am not for remove node but I should be). The problems for > > reading are: > > > > - it should allow multiple threads to read at the same time > > - it shouldn't dictate that client code has a transaction in order to > > read > > > > As a simple solution thats probably workable (and probably the safest), > and > > means that HA will just work, but restricting one thread at a time into a > > given node collection isn't the best. > > > > Maybe the client code should set whether it locks the data structure when > > reading, or fails with a ConcurrentModificationException when reading and > > data is changed. > > > > On Sat, Sep 24, 2011 at 6:00 AM, Niels Hoogeveen > > <pd_aficion...@hotmail.com>wrote: > > > > > > > > A quick skim of the code shows me you have a baseNode which is an > > > entrypoint for the ULL. This is a logical candidate node to use for the > > > purpose of locking. > > > What are the pros and cons to locking the baseNode on every read and > write > > > operation? > > > Niels > > > > Date: Fri, 23 Sep 2011 09:39:38 +1200 > > > > From: bryc...@gmail.com > > > > To: user@lists.neo4j.org > > > > Subject: Re: [Neo4j] Unrolled Linked List > > > > > > > > Good stuff. > > > > > > > > I am presently looking into concurrent use of a given > UnrolledLinkedList > > > at > > > > least within the same graph database instance, might be a little bit > > > harder > > > > in HA environment. Its hard enough writing test cases for this, > maybe > > > even > > > > harder than making it work properly! Hoping that some utility code I > am > > > > going to produce will help with testing concurrency of other data > > > > structures. > > > > > > > > By concurrent use I mean concurrent use of the data within the graph, > not > > > of > > > > the given instantiation of the class, e.g. what happens when one > thread > > > gets > > > > an instance of ULL based off a given node and is iterating over it, > then > > > > another thread gets an instance of a ULL and writes into it. > > > > > > > > Cheers > > > > Bryce > > > > > > > > On Fri, Sep 23, 2011 at 4:57 AM, Niels Hoogeveen > > > > <pd_aficion...@hotmail.com>wrote: > > > > > > > > > > > > > > It looks really cool. > > > > > I always find it fun to create something and later find out it is > an > > > > > already known construction (something worth inventing). > > > > > Anyway, I pulled your code and will removed the dependencies to the > > > > > Enhanced API stuff this week. After that we can start adding some > > > > > documentation. > > > > > Niels > > > > > > > > > > > Date: Thu, 22 Sep 2011 15:57:13 +1200 > > > > > > From: bryc...@gmail.com > > > > > > To: user@lists.neo4j.org > > > > > > Subject: [Neo4j] Unrolled Linked List > > > > > > > > > > > > Hi all, > > > > > > > > > > > > I have added an in graph representation of an unrolled linked > list to > > > the > > > > > > graph collections code, currently just in my githug repo: > > > > > > https://github.com/brycenz/graph-collections > > > > > > > > > > > > See this in particular: > > > > > > > > > > > > > > > https://github.com/brycenz/graph-collections/blob/master/src/main/java/org/neo4j/collections/list/UnrolledLinkedList.java > > > > > > > > > > > > The name comes from: > > > > > > http://en.wikipedia.org/wiki/Unrolled_linked_list > > > > > > > > > > > > And it works roughly in the same manner, though I had the idea > prior > > > to > > > > > > reading the wiki article. > > > > > > > > > > > > As the UnrolledLinkedList class implements the NodeCollection > > > interface > > > > > it > > > > > > can be used as the backing of an IndexedRelationship, which is > done > > > in > > > > > tests > > > > > > here: > > > > > > > > > > > > > > > https://github.com/brycenz/graph-collections/blob/master/src/test/java/org/neo4j/collections/indexedrelationship/TestUnrolledLinkedListIndexedRelationship.java > > > > > > > > > > > > The main reason for me being interested in this, and an example > of > > > where > > > > > > this is (probably) really useful is in the following case: > > > > > > > > > > > > - you have a number of tag (or category, folder etc.) nodes > > > > > > - they each link to a large number of document (or article, > > > comments, > > > > > > post etc.) nodes > > > > > > - using a single relationship type > > > > > > - you generally only are interested in showing the newest > > > documents in > > > > > > descending date order (showing the head, in a paged ui) > > > > > > - documents are generally added in ascending date order (added > to > > > the > > > > > > head) > > > > > > > > > > > > The benefits come from being able to iterate over a small > percentage > > > of a > > > > > > collection of nodes in a fixed order without having to first load > all > > > the > > > > > > nodes and sort them. This reduces the amount of data read in > from > > > disk, > > > > > > reduces the turnover of data in memory, and therefore aids with > > > reduction > > > > > in > > > > > > garbage collection. In my case I have a large number of tags > with a > > > > > large > > > > > > number of items against them, I might read the first 100-200 > items > > > out of > > > > > a > > > > > > collection of 30,000 and therefore by not reading in the other > 29800 > > > > > > relationships / nodes (per tag) I should be saving 90% or > more..... > > > > > here's > > > > > > hoping. > > > > > > > > > > > > From the java doc: The structure is broken into "pages" of links > to > > > nodes > > > > > > where the size of the page can be controlled at initial > construction > > > > > time. > > > > > > Page size is not fixed but instead can float between a lower > bound, > > > and > > > > > an > > > > > > upper bound. The bounds are at a fixed margin from the page size > of > > > M. > > > > > When > > > > > > a page drops below the lower bound it will be joined onto the an > > > adjacent > > > > > > page, and when the page goes above the upper bound it will be > split > > > in > > > > > half. > > > > > > > > > > > > I am about to do some tests with this based on my use case and > will > > > > > report > > > > > > back on the performance impacts. > > > > > > > > > > > > Cheers > > > > > > Bryce > > > > > > > > > > > > P.S. still thinking about how to make this thread safe, any > > > suggestions > > > > > > would be appreciated (presently only one thread will be able to > write > > > at > > > > > a > > > > > > time, I am worried about a thread reading while another is > writing, > > > > > > especially when it joins / splits pages or changes the head). > > > > > > _______________________________________________ > > > > > > Neo4j mailing list > > > > > > User@lists.neo4j.org > > > > > > https://lists.neo4j.org/mailman/listinfo/user > > > > > > > > > > _______________________________________________ > > > > > Neo4j mailing list > > > > > User@lists.neo4j.org > > > > > https://lists.neo4j.org/mailman/listinfo/user > > > > > > > > > _______________________________________________ > > > > Neo4j mailing list > > > > User@lists.neo4j.org > > > > https://lists.neo4j.org/mailman/listinfo/user > > > > > > _______________________________________________ > > > Neo4j mailing list > > > User@lists.neo4j.org > > > https://lists.neo4j.org/mailman/listinfo/user > > > > > _______________________________________________ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > _______________________________________________ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > _______________________________________________ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
