News for hackers. Stuff that matters.
Re:MySQL is bazillion times faster than MemSQL by tintor on Tuesday June 26, 2012 @03:59PM (#4163831)
Skip list is essentially a hierarchy of linked lists. It is very hard to make a doubly linked list work concurrently without using locks. One would have to update two pointers atomically in order to insert a new element in a doubly linked list.
Re:MySQL is bazillion times faster than MemSQL by Nitramp on Tuesday June 26, 2012 @05:15PM (#4164170)
You could probably pull that off if you implement it like full text search indices in e.g. Lucene. Have every modification create a "diff" skip list that takes precedence over older skip lists, and then have a merge operation that runs asynchronously (and will either have to lock, or copy the entire data structure and switch it in atomically). That's also essentially how Bigtable's disk format works.
Re:MySQL is bazillion times faster than MemSQL by dhruvbird on Tuesday June 26, 2012 @05:22PM (#4164211)
Actually, there are papers about it http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.4... but I don't know much about the implementation complexity since I've never implemented one.
Re:MySQL is bazillion times faster than MemSQL by bcoates on Tuesday June 26, 2012 @08:30PM (#4164915)
That shouldn't be any harder than updating one pointer atomically, modern x64s have two-pointer sized atomic exchange operations.
Re:MySQL is bazillion times faster than MemSQL by tintor on Wednesday June 27, 2012 @12:02AM (#4165441)
Modern x64s have 128-bit CAS instruction, but the problem is that those two pointers can be far apart in memory, in two different elements of the list.