What about false sharing?
LMDB was written specifically for multi-threading; all of its shared data structures are cache-line aligned to prevent false sharing. This is also essential to allowing readers to run with no locks.
Btrees are the new black
41–44 of 44 posts
Re: Btrees are the new black
#42Earlier quoted context omitted.
And then we can stack every conceivable use case on top of it, and write that language-agnostic API in a way that makes interfacing with most current languages so onerous that people can build hundreds of thousands of lines of code to make it slightly less painful! Maybe we can make the configuration so convoluted that we can base entire companies and revenue models around maintaining them.
> write that language-agnostic API in a way that makes interfacing with most current languages so onerous that people can build hundreds of thousands of lines of code to make it slightly less painful Those would be people who couldn't be bothered to learn a really simple declarative language, and prefer ad-hoc OO ORMS and other shit like that...
Oh, SQL itself is fairly easy. For many things, I'm a fan.
However, SQL query construction and result munging is painful.
Consider a UI search screen that has eight potential search parameters that requires a one to many join for the results. The query construction, under something like JDBC, can end up with hundreds of lines of tedious code, like (and this is a condensed example!):
String query = "SELECT a.*, b.* from table1 a inner join table2 b on a.fk_id = b.id where" // shorthand
List whereClauses = []
if (params.region) { whereClauses.add(getRegionWhereClause(params.region)) } //hope this doesn't require another join!)
if (params.country) { whereClauses.add(getCountryWhereClause(params.country)) }
...
if (params.lastParam) { whereClauses.add(getLastParamWhereClause(params.lastParam))}
query += whereClauses.join (" AND ")
...
def getRegionWhereClause(regionCodeList) { "a.region IN" } //Hope you never want to change the table alias here!
Then you're going to return a list of rows that looks like | a.1 | a.2 | b.1 | b.2 | | a.1 | a.2 | b.1' | b.2' |
Where you really want: | a.1 | a.2 | [[b.1 | b.2] | [b.1' | b.2']]
So you have to go through and munge it. (Can you use something like CONCAT as a hack and groupby? Sure, but that introduces other problems.)
Having a way to pass in optional parameters to a where clause for the DB to strip out (while staying performant) and being able to return a 1 to many as an array would solve many problems, but it doesn't fit the paradigm of SQL.
Re: Btrees are the new black
#43Earlier quoted context omitted.
I only benchmarked and considered the single-threaded case. Multithreading is a whole new can of worms.
Trivially, one could synchronize around the entire tree. However, if modified nodes are always copied, then the only node that matters is the root node (since there can never be a partially modified tree accessible from the root), which boils down to atomic update of a root node pointer. Should be very efficient. There is, of course, a performance implication of node copying, but it only affects add/delete/replace pe…
If you want different threads to see the same data structure then I think you would also need a mechanism to prevent multiple threads modifying the same node and clobbering each other's changes.
Re: Btrees are the new black
#44Earlier quoted context omitted.
Trivially, one could synchronize around the entire tree. However, if modified nodes are always copied, then the only node that matters is the root node (since there can never be a partially modified tree accessible from the root), which boils down to atomic update of a root node pointer. Should be very efficient. There is, of course, a performance implication of node copying, but it only affects add/delete/replace pe…
If you want different threads to see the same data structure then I think you would also need a mechanism to prevent multiple threads modifying the same node and clobbering each other's changes.
Yes, of course. But there is a difference between read, which only requires synchronization at the root node, and write, which requires synchronization at the modified leaf and potentially all the way back up the path from leaf to root.