Transactions and in-memory data (part 3 of n)

Last time I laid out a little framework for transactional rollback.  It clearly is not sufficient for a real honest-to-goodness persistent transaction but if you can tolerate every ESE failing (due to allocating the rollback log entry) it’s pretty compelling.  Pretty much every function can be transactional if it only works with data structures/algorithms which…


Transactions and in-memory data (part 2 of n)

Buffering the opertations wasn’t particularly successful. Let’s look at maintaining a rollback log. Seems pretty simple.  You can do something like: typedef void (*rollback_function_ptr_t)(void *context);typedef struct _rollback_record {   rollback_function_ptr_t rollbackFunction;   struct _rollback_record *next;} rollback_record_t;void do_rollback(rollback_record_t *head) {   while (head != NULL) {      rollback_record_t *next = head->next;      (*head->rollbackFunction)(head + 1);      free(head);      head = next;   }} That’s pretty simple, eh?  Since rollbacks probably have to…


Transactions and in-memory data (part 1 of n)

[Maybe I’ll fill in the “n” when I’m done.  I haven’t had time to plan out the entire series…] In yesterday’s post, I covered basically two approaches towards how to achieve transactionality.  One is to build up a log of what to do when the commit is requested and the other is to keep track…


No Chinese Dictionaries

I want to go on the record and note that I will not be deveoping a Chinese/English Dictionary, in unmanaged code, managed code or any code (pages).


More than one way to skin a (transactional) cat

Let’s briefly look at how databases deal with transaction rollback.  I’m going to ignore a lot of other fun stuff around locking protocols, snapshots, isolation etc. and only focus on how atomicity & durability are achieved.  I’ll keep the conversation in the realm of traditional database objects: tables and rows. Approach 1: Buffer everything until…


Implementation patterns to support transactional functions

Let’s go back now to why I had a hard time with using the STL std::map pattern.  It was because for the primary failure-prone access pattern (insert), there is an inverse operation which could not fail. A common pattern in TxFn (sorry I can’t keep writing the long name) is that you carefully do all…


Local vs. global analysis revisited

I posted that last item before having my coffee so it’s really not suprising that I forgot to get around to my point. My point is this: there are abundant tools (including the human brain) which are good at local analysis.  Global analysis is hard; this is why people with “architect” in their title tend…


Whole program vs. local analysis

A quick note for today. Maybe more tonight. Internally at Microsoft, as you can imagine, we have a number of tools to assist building our software.  Many are internal-only; contrary to the black-helicopter gang out there, there is a lot of cost to shipping software and it can divert your attention and resources from your primary…


Working with inexact error contracts

Last time I lamented that the fact that std::map::erase() is not permitted to fail made it hard to come up with an example. But the vector pattern has the basic problem I wanted to discuss.  First I’ll write the obviously correct C code and then we’ll see how it translates into a world where you’re…


Even good design can’t succeed in isolation

I tried three times to write yesterday’s entry which was intended to explore the same problems with trying to restore invariants in failure paths.  Instead I kept getting fouled up because the collections I was using were based on the STL design.  The STL designers actually did a good job in making it hard to…