elbee

That will work as a way to strengthen the hashes (a few other people pointed that out as well).

My point was that if you have a system which can go straight from SHA2(password) to bcrypt(password) then the system must be storing the plaintext of the password, which would be very bad.

Waiting until login until you upgrade to bcrypt is a requirement is compotent password storage. At this point in time all Linode should know is SHA-2(password) and they can't use that to derive bcrypt(password).

The way upgrade should work is that the user provides their password, which is verified with SHA-2 and then hashed with bcrypt and stored again.

In order to do this without people logging in Linode would have to bcrypt hash the SHA-2 hashed passwords and then keep doing that for all password validations.

If you want to do mutual exclusion using distributed locking then you end up in a painful place (as the article points out). In general you can't distinguish between a process that is running really slowly and a process that is dead. So when confronted with a non-responsive lock owner you end up with two unpleasant options: 1) Assume the lock owner is alive and don't do anything. This approach guarantees mutual exclusion but isn't especially useful because it gets stuck when things die. 2) Assume the lock owner is dead and take the lock. This doesn't guarantee mutual exclusion but "probably" works if you make the timeout "long enough." This can work correctly if you have a realtime system which will monitor the lock owner and kill the owner if the lease on the shared resource expires (this would probably require a special hardware/OS/programming language stack).

On the other hand unsigned types are a huge pain if you want to iterate through an array backwards because you have to use subtraction. A lot of people end up with something like this:

  unsigned int i = strlen(s) - 1;
  for (; i >= 0; --i) { // BUGBUG
      if (s[i] == '.') {
          break;
      }
  }

(Yes, you can make it work, but it is very error-prone when people try).

To be honest, I have no idea what "agility" is. Perhaps I am too cautious but I'll want to see a lot more data than some hand-picked benchmarks and a mystical "unique constraints aren't interesting" before I'm completely convinced.

[Random aside: I greatly dislike block (i.e. InnoDB-style) compression, which is what Tokutek seems to use. Decompressing the entire block just to retrieve one column of one row is crazily expensive, especially as the decompression cost goes up as the block size goes up. There is also the problem of deciding whether to store compressed blocks in the buffer cache (slow), decompressed blocks in the buffer cache (wastes ram) or to have a cache of uncompressed blocks (the InnoDB approach, which kind of combines both problems). I think that format-aware page or column compression (like Oracle, SQL Server or ESENT) is far more effective.]

I guess that this has gotten way off topic but I am glad there are people out there doing exciting new things in the B-tree space. I will keep a closer eye on Tokutek in the future.

So out of the main b-tree operations (Insert/Replace/Delete/Seek/Next/Prev) you make a convincing argument that Tokutek can be faster than b-trees for inserts, if you use non-unique indexes (which automatically disqualifies the primary index in most cases, and makes foreign keys hard).

That is good but not quite "beat B-trees pretty handily across the board" :-)

This reading list will cover a lot the current generation of b-tree techniques, but not the cutting-edge stuff (e.g. Tokutek):

* Ubiquitous B-Tree (Douglas Comer): http://doi.acm.org/10.1145/356770.356776

[A good review of the state-of-the-art in 1979]

* Prefix B-trees (Bayer, Rudolf and Unterauer, Karl): http://doi.acm.org/10.1145/320521.320530

[This paper introduces the idea of what I'm used to calling suffix compression -- the internal page pointers in a B-tree don't need to store the entire key, just enough of it to uniquely identify the node compared to its neighbor. This can be a very useful optimization for some use cases. The idea of reassembling a key as you seek down the tree is cool, but I don't think anyone does it in practice.]

* B-tree indexes, interpolation search, and skew (Goetz Graefe): http://doi.acm.org/10.1145/1140402.1140409

[A lot of interesting ideas around doing search inside of a node, including cache awareness. Interpolated search looks very interesting, but I was never able to get it to go faster than binary search. That could have been my fault though.]

* A survey of B-tree locking techniques (Goetz Graefe): http://doi.acm.org/10.1145/1806907.1806908

[I really like Graefe's database survey papers. They are easy to read and practical/implementation focused. This one discusses a lot of important concepts: the difference between latches and locks, latch coupling, range locks and increment locks.]

That looks extremely interesting! The idea of amortizing the cost of inserts is fascinating. Looking at the design you sketched a few questions come to mind:

1) Multi-threading: suppose I seek down the B-tree for key K. Most B-tree implementations use the latch on the node containing K as the final arbiter of concurrency. For example, if I'm looking at K and then I want the next row (perhaps because I'm using the new Index Condition Pushdown optimization in MySQL 5.6, or I'm doing an online index build and need to scan all the rows) then I can simply look at the next row on the page I currently have (read) latched. With a fractal tree it looks like I have to worry about someone inserting a row immediately after the current row because that insert could have been cached at a higher level. Does this mean I need to keep some sort of latch/lock on the entire b-tree path down to the page I'm reading, instead of using latch coupling to work my way down? Alternatively do I have to work my way down from the top of the tree every time I want the next key?

2) How can you check for uniqueness? Suppose I create a table like this:

CREATE TABLE t1 (id NUMBER PRIMARY KEY, val1 VARCHAR2(30));

Amortizing the inserts seems to imply that primary key uniqueness violations can't be discovered until the inserts are pushed all the way down to the leaf?! In general uniqueness is an important part of data normalization, a good input for query optimization and normally required for foreign key constraints...

I'm not talking about a b-tree that won't fit in L2, I'm talking about a B-tree that won't even fit in main memory. In those cases, even with SSDs, the cost of pulling a page off disk dominates the in-memory cost of the binary search so the number of I/Os needed to find something becomes the dominant factor in performance. That leads to a focus on data density and cache replacement algorithms.

"Binary searches suck"

That is a valid point. Cache misses when doing the search inside of the b-tree can be painful. I know that there is some research into structuring the b-tree nodes to be more cache-friendly (David Lomet mentions this in his "Evolution of Effective B-Tree" paper: http://research.microsoft.com/pubs/77583/p64-lomet.pdf) but haven't actually seen any in production.

Part of the problem here is that page density is so critical that people are often wary of having a less-efficient, but more cache-friendly data representaton. It is normally better to have 10% more records in main memory than being able to search the nodes a touch faster. Various forms of key prefix compression are an example of this tradeoff.

Another consideration is the actual cost of doing the key comparison. I'm most familiar with relational database systems and they all support multi-column keys (e.g string+integer+boolean+date), which normally lead to an expensive, branch-laden comparison function because the comparison has to be type-aware and support various collation options. The cost of doing that branching means the CPU cache misses are a smaller overall part of the overall search cost. One exception to that is ESENT, which uses memcmp-able normalized keys, but doing that creates its own set of problems (Unicode is a pain, lack of denormalization means storing data twice, etc.).

"Rewriting them when you insert a single key is just ridiculous."

I don't think anyone does this. Most implementations have settled on a system that stores the keys in the node in an ad-hoc fashion and have an array of 'pointers' to the keys which starts at the end of the page and grows towards the front (except for Postgres, which appears to do it the other way around). Inserting a new key means moving the pointers, but not the actual keys. Some systems try to avoid doing even that -- for example the InnoDB engine in MySQL links together the keys and the page directory only points to every 4th-8th key. I believe that this is an attempt to balance the speed of the binary search against the cost of update/delete.

In addition, with write-ahead-logging the node isn't flushed when updated, instead the log records describing the update are flushed and the page is lazily flushed in the background by a checkpointing process, hopefully after several other updates have been made to the same node.

Microsoft SQL Server, Microsoft ESENT, MySQL's InnoDB and Postgres' b-tree index all use minor variations on the basic textbook b-tree for their data storage.

Source: Many years working on the ESENT database engine, a brief stint in Microsoft SQL Server, some hacking done on the MySQL InnoDB engine.

The B-tree implementations used in a lot of databases have tweaks, but they are surprisingly similar to the textbook descriptions. In general, B-trees are actually a very useful data structure when: a) Your data is much larger than main memory (e.g. terabytes/petabytes of data and gigabytes of RAM). b) You want to support random insert/update/delete, seek, and next/previous key. c) There has to be a reasonable constraint on storage space (i.e. data density/compaction). In those cases the log(n) performance of a b-tree is extremely hard to improve on.

Alternate data structures a useful if: 1. The ratio of ram/disk is more favourable, in which case using an improved in-memory data structure can be more efficient. 2. Not all operations have to be supported. In particular eliminating the next/previous key operations allows something like a hashtable to be used.

In some systems the problem is that you can never be guaranteed that the after_commit hook will always run. This is especially true in multi-server systems where the cache, database and front-end servers are separated. The front-end server can update the database and then completely die (power outage, networking, reboot) before talking to the cache.

On the other hand I can see how you would want to drive out bugs instead of just sweeping them under the carpet with auto-healing...

One risk of not using expiration at all is that if the database is updated but the after_commit hook doesn't finish (crash, out of resources etc.) then the cached data remains outdated until the record is updated again (which could be never). Setting a generous TTL won't increase your load much, but will let problems like that eventually fix themselves.

1) In main.c the vals array is statically sized at 256 entries, but entries are put into it mod terminal width, with no guarantee that the terminal is <= 256 characters wide. That will lead to a buffer overflow. 2) INT_MIN cannot be negated -- you should check for that and just use INT_MAX instead.