[
https://issues.apache.org/jira/browse/HBASE-5311?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13202178#comment-13202178
]
Todd Lipcon commented on HBASE-5311:
------------------------------------
I don't think so... funnily enough I was just taking a break from my usually
scheduled work and working on this.
I don't have much so far, but my design uses some lock-free tricks to safely
swap around internal pieces of the data structure. Here's a sketch of what I
was hacking on:
I created a lock free data structure tentatively named "GatedSection" which is
sort of like a lock/critical section but not quite. It has the following API:
{code}
/**
* Return true if the thread should be allowed to enter the critical section,
* false if any other thread has already closed the gate
*/
boolean enterSection();
/**
* Must be called by any thread that has successfully entered above
*/
void exitSection();
/**
* Disallows any new threads from entering the section (future calls to
* enterSection() will return false). Blocks until all other threads which
* are already in the section have called exitSection().
* Postcondition: no threads are in the section or will be able to enter it
* after this method returns.
*/
void closeGateAndFlushThreads();
{code}
If you're familiar with JVM internals, this is a little bit like how
'checkpoints' work.
I then created another data structure:
{code}
class State {
GatedSection gate;
List<Map<K,V>> mapLayers; // writes go to idx 0, reads merge all
}
{code}
and the overall datastructure has a {{volatile State state;}} member.
Operations which mutate the current state (eg put) then do something like:
- in a loop, try to grab a local copy of the State variable, and then enter its
gate, until successful.
- modify its top map layer
- exit the gate
A "flush" works as follows:
- step 1: create a new top layer for writes
-- create a new State object which is identical except a new concurrent map has
been inserted at the "top" of mapLayers
-- swap the volatile "state" pointer to the new state. At this point, writers
will be writing into _either_ of the top two layers
-- close the "gate". After the gate is closed, writers will only be writing to
the _top_ layer
- step 2: freeze the old top layer
-- create a new efficient immutable datastructure for mapLayers.get(1) (no
rush to complete this phase)
-- swap it into place by swapping out the volatile state object
A compaction works similarly to "step 2" above.
Might be worth using a technique like fractional cascading on the "mapLayers"
structure as well to avoid O(k log n) lookups with k layers.
> Allow inmemory Memstore compactions
> -----------------------------------
>
> Key: HBASE-5311
> URL: https://issues.apache.org/jira/browse/HBASE-5311
> Project: HBase
> Issue Type: Improvement
> Reporter: Lars Hofhansl
>
> Just like we periodically compact the StoreFiles we should also periodically
> compact the MemStore.
> During these compactions we eliminate deleted cells, expired cells, cells to
> removed because of version count, etc, before we even do a memstore flush.
> Besides the optimization that we could get from this, it should also allow us
> to remove the special handling of ICV, Increment, and Append (all of which
> use upsert logic to avoid accumulating excessive cells in the Memstore).
> Not targeting this.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
