That's just my age showing, I guess. For me, all 2.5D shooters are DOOMlikes.
I was actually first thinking about calling it a Quake-like since IMHO that is much more well known for its multiplayer, but then I never got around to implement powerups and all the other stuff people might have expected.
DOOM was revolutionary because it switched from raycasting like Wolfenstein to a binary tree rendering system that allowed much more complex architecture.
Yea, I actually thought of the viability of SQL for games while working on DOOMQL. It's just so easy to express a lot of game logic in SQL queries. As an avid OSRS player I was thinking about doing a simple MUD/MMO next.
Thanks for the pointer to SpacetimeDB - haven't heard of it before!
The version is just an atomic integer assigned to that btree node which is monotonically increasing. Each writer increases the version when it releases the lock IF it has modified the node.
Wraparounds are only a theoretical issue. There would have to be exactly UINT64_MAX writers between a reader first checking the version and verifying the version.
"Optimistic locking" is a bad choice of words because no locking is optimistic.
In the well-known access method described here, the writers access the shared data with mutual exclusion, i.e. they use locking.
The readers use no locking, but they access the shared data concurrently and optimistically, hoping that the access will succeed at the first attempt.
When the readers are unlucky, they must retry the access.
So there is locking used by writers for mutual exclusion and there is optimistic access used by the readers.
There is no "optimistic locking", which is a contradiction in terms (locking is pessimistic).
In general, there are only 3 methods for accessing shared data: mutual exclusion (a.k.a. pessimistic access), where locking forces the accesses to be sequential, and 2 methods where accesses may be concurrent, optimistic access (a.k.a. lock-free), where retries may be necessary, and dynamic partitioning of the shared data (typically used for shared arrays or for shared buffers/queues), where neither locking nor retries are needed.
The method described here for accessing B-trees employs a combination of all 3 methods, because the release of the locks at higher levels is a consequence of restricting the future accesses to only a part of the shared data, i.e. the writers that access the shared B-tree start by accessing sequentially the root, but then they partition the tree between themselves, so the next accesses that fall in distinct subtrees may proceed concurrently.
“Optimistic locking” is a well-established and widespread terminology though, not the least due to its catchiness. The more factual, but unwieldy term is “optimistic concurrency control”.
I agree that it is widespread, but whenever you see such illogical terms you have to wonder whether the authors who use them do not understand what they are really doing or they understand, but they succumb to conforming with a widespread inappropriate usage in the hope to be better understood by naive readers.
Understanding the difference between pessimistic access (mutual exclusion implemented by locking) and optimistic access (concurrent accesses with retries when necessary) is absolutely critical for the correct and efficient implementation of algorithms that use shared data structures.
It is frequent to combine both methods in an algorithm, like here, but in English that is not "optimistic locking", but at most "locking and optimistic access" or "optimism and locking".
Pessimistic access means that you expect that another process will attempt to access concurrently the shared data, so you must use a lock to prevent this. Optimistic access means that you expect that no other process will attempt to access concurrently the shared data, so you may proceed to access it immediately, but then you must have some means to detect that your assumption has been wrong and another process has interfered, when the transaction must be retried.
Depending on the application, either pessimistic access or optimistic access results in a better performance, neither is always better than the other. Optimistic access (lock-free access) makes better the best case, but it makes much worse the worst case. Depending on the frequency distribution of such cases optimistic access increases or decreases the performance.
Pessimistic access and optimistic access have the advantage of being applicable to any kind of shared data structure, but dynamic data partitioning, where applicable, like for this shared B-tree example, which can be partitioned in sub-trees accessed concurrently, normally results in better performance than both pessimistic access and optimistic access, by being deterministic and avoiding both locking and retries. Dynamic data partitioning may require locking for a very short time in order to partition the shared resource before accessing the allocated part, though the mutual exclusion provided by atomic instructions may be sufficient for this purpose. It is frequent that an atomic fetch-and-add instruction is enough to partition a shared data structure, like a shared array or a shared message queue, between concurrent processes attempting to access it.
I chuckle every time anyone has tried to handle long(64bit) overflows while incrementing by one.
Other than that, the version checks + retries have been a thing since forever (they are the most bog standard way to do any lock-free datastructures, along with database updates in the same manner). They do need a back off, though.
I have various generations of optane I stocked up on for my own small business and home lab use, and fully agree.
I don’t know if you’re aware but Samsung introduced their own version of optane just shortly before Intel killed their product line. It was called Samsung Z and it was prohibitively expensive for some reason, but I didn’t hear that it was officially killed off (though it likely has been).
> Ultimately, a reliable non-volatile write cache, sized for your workload is the answer.
Author here, I agree! It's quite sad that we need such an involved solution to offset the inherent complexity of the flash medium (latency spikes, erase blocks, ...). We nearly had the perfect solution with Optane[1]: 100ns latency, instantly persisted writes and all that good stuff.
I'm still not over Intel killing it while I did my PhD on it.
More industry experience in real world would've made it clear that they're totally useless for datacenters where there are rarely power outages with many 9's of electrical uptime measured in months or years.
UPSes and BBWC evolved to bring reliability to production gear running in non-DC environments when mainline servers used spinning rust without backup power. Today, it's largely a vendor up-charge.
Write barriers cause far too much latency in practice on servers in tier IV datacenters, so they're almost always turned off except for a tiny fraction of systems.
There has never been a "perfect" or a universal solution, only a risk budget and suitability for a specific use-case.
Write barriers aren't just for durability - they also can even out major latency spikes when bloated buffers ultimately must be flushed. Database, filesystem, RAID, device, flash management and individual chips all become saturated at some point. Managing performance at the database engine layer gives you visibility into the issue at a high level as opposed to rolling merrily along until commits start taking 2000 ms. As an example, ZFS is terrifyingly unpredictable at high loads.
Power availability isn't the only concern when it comes to taking the risk of async writes. Kernel panics will cause unflushed writes to be lost, and storage hardware can experience gray or total failures, sometimes completely suddenly.
Radian makes ultracapacitor backed RAM cards with flash backup that appear to be NVMe devices. They do a nice job for things like Write Ahead Logs and ZFS ARC/ZIL. They offer effectively unlimited write endurance with a tradeoff of cost and capacity.
Yes, the way it is currently implemented, the build side has to fit into RAM. There is no inherent reason we couldn't also spool to disk, but we haven't implemented that yet.
Thanks for confirming. (I deliberately worded my question like that, as it makes sense to roll such features out in phases, just like plenty of others have done - off the top of my head, DuckDB and Apache Impala for example.)
Edit: In the post you mentioned that you optimized the hot path for likely taking the non-matching record path. Sometimes with well-designed partition wise joins, most of the records actually do match and survive the join - I guess in such (estimated or detected) cases you could switch to an alternative path with a match being the likely branch in the hot path…
