Visit Your Local PBS Station PBS Home PBS Home Programs A-Z TV Schedules Watch Video Donate Shop PBS Search PBS
I, Cringely - The Survival of the Nerdiest with Robert X. Cringely
Search I,Cringely:

The Pulpit
Pulpit Comments
October 13, 2008 -- Cool Threads
Status: [OPEN] add a comment

Hmmm, according to how I understand things (not very well) Bob has mixed up threads with process. Most software today is single process and multi-threaded.

Multiple threads are (relatively) easy to do. Inter-thread communication is (relatively )easy if we ignore the extra complexity required to ensure that data changes are done in a thread safe fashion.

The problem lies with inter-process communications. At the moment it is difficult for different processes to communicate directly with each other which is why most software runs on a single process (which is limited to a single CPU) then spawning multiple threads on that processor.

But I could be wrong of course

Brett | Oct 13, 2008 | 11:51PM

It occurs to me that I didn't explain myself terribly well.

As applied to Bobs ATM scenario, we have already been making massively threaded apps such as this for some time. But the problem is that all the threads are running on a single process and that single process runs on a single CPU. What we need to do is create multi-process apps if we want to make the most of multi-core cpus, and that is the thing that is difficult

Brett | Oct 14, 2008 | 12:03AM

Firstly, I'd like to extend congratulations on discovery of fork(3) ...

I guess the real question would be why in the world would an ATM need the balance to complete a deposit transaction? Most banks reconcile their deposits once a day (especially ATMs, because a bank whose ATM uses the "just trust me" style of deposits is goign to be out of business real soon), usually the end of the business hours, and then the account balance is updated.

David | Oct 14, 2008 | 12:42AM

Uh oh - this column is a bit of a write-off. Threads are NOT processes, Bob. You are seriously confused here.

Chris | Oct 14, 2008 | 12:43AM

"...It works? Cool. Now send 1000 threads into that same piece of code..."

If only it were that simple!

dave | Oct 14, 2008 | 12:53AM

Bigger fool you for:

1) Trusting Banks
2) Marrying a woman so young she can't spell her own middle name correctly

Winston Smith | Oct 14, 2008 | 1:11AM

Sorry Bob but you're making some pretty specific statements about a topic you appear to only have a general understanding of.

Not the least of which being institutional finance software hasn't been working the way you seem to think they do for a long time. Although a typical example in database and programming books and classes it's flat out wrong. Think about it, if it were simple integer updates and journals every American could do 12 transactions a day (in a 12 hour day) that would only be 80,000 atomic transactions a second, pittance. There is SO much more going on when you put money into an ATM than checking and updating an integer in an RDBMS somewhere.

Dave | Oct 14, 2008 | 1:21AM

Sorry Bob, this is a bit of a hack column, not up to your usual standard.

You're conflating threads, processes and database locking strategies. Not much of what you wrote here is actually about improving thread performance with multiple cpu's.

The classic issue with multi-process programming is that many algorithms require sequential programming in at least part of the process, and then Amdahl's law kicks in : no matter how many processors you have, there is a limit to how much speedup you can gain.


jaycee | Oct 14, 2008 | 1:36AM

Huh? In the ATM example, why would the balance need to be a stored value as opposed to calculated when needed.

1. Bob desposits -- ATM sends query request (tells DB executes a stored procedure) and last carried forward balance (from last statement) is grabbed and all transactions since then added and subtracted to calc. the current balance.

2. Alyce deposits and the same thing occurs.

3. They each may or may not see the correct full balance printed on their slips depending on the timing, but who cares since they are not aware of the simultaneous deposits any how.

Most apps I have seen calculate totals as needed and do not store them as distinct fields.

southlander | Oct 14, 2008 | 3:21AM

Wow, I've never seen so many comments which show such a failure to understand an article. I am one of massively scientific programming types and I didn't realise how widely misunderstood this topic was outside of my field, maybe there is hope for my career when I finish my PhD. Some points for previous posters:

1. Yes threads are described as lightweight processes and in most cases are executed inside a single process however try to imagine what would happen if different threads were executed on separate processors/cores. Each thread should be written to be executed in parallel (otherwise you get race conditions)

2. Yes, we understand banks may not operate in the exact way laid out in the article, its an analogy which helps explain the concept. Again try to imagine how the bank account relates to a was variable in memory and how the transactions related to loading and storing from registers.

3. Interprocess communication is in fact quite easy on a shared memory processor (multi core) as you can communicate by sharing memory between processors. How you control the processes is more difficult (see the race condition example). There are now many compiler tools for creating shared memory threads available, the most common being OpenMP which is even in more recent versions of GCC.


4. Yes, race conditions do generally require serial progress through critical sections of code. This is achieved by "atomic" operations through locking. This limits the scalability of application however the difference between the two schemes detailed is that the locking the database introduces false serialisation, whereas using atomic processor instructions only introduces serial code where it is necessary.

Anyway I really enjoyed the article.

Kind regards,

Tom

Tom Edwards | Oct 14, 2008 | 3:51AM

We have seen 1000 + cpu systems at work in business many times before. Just look at any large office building with a LAN, OK, the wires are a bit longer but that is all the difference is. There is a 'sum view' of the information across those systems, but no real integrity, hence the distributed, centralised, distributed flip flop over the years seeking to resolve the integrity. The problem is that you have to design FOR parallel, each and every time you do it.

Jerry Kew | Oct 14, 2008 | 5:17AM

The real problem with race conditions comes with handling withdrawals, not deposits:

Bob's ATM checks the balance ($1000)

Bob asks to withdraw $1000

Alice's ATM checks the balance ($1000)

Alice asks to withdraw $1000

Bob's ATM spits out $1000

Alice's ATM spits out $1000

Bobs ATM updates the balance from $1000 to $0

Alice's ATM tries to update the balance from $1000 to $0, but fails.

Alice's ATM wants to restart the transaction and asks Alice very nicely to hand back the $1000 cash she has in her hand.

Alice walks away with the cash

So does Bob.

Martin | Oct 14, 2008 | 6:17AM

Being an academic that does research on threads and recently submitted a paper on using them efficiently; I have something to say.

First, threads are not fork(3), and not processes. Fork splits and duplicates the entire process and work space, all file tables, etc. Thread does not. A common implementation is pthreads; they are called "lightweight" because the overhead of starting them is much lower than fork(). It only takes about 20 microseconds to tell the OS to launch a new thread, and only about 80 microseconds before it starts its work on a 2.5Ghz core2 duo.

Protection works basically as Bob says if we take that ATM stuff as a metaphor. The truth about ATM's is more of a secure communications strategy to a central area. But the metaphor extends to it; in NUMA machines (Non-Uniform Memory Access) we have individual cores with their own low level memory caches and shared higher level caches and memory, and individual physical packages may have to communicate with each other to access memory owned by the others. The issues are like in the ATM case; we must deal with collisions (two cores trying to write to the same memory) and coherency (the copy of memory in my cache being stale because another core changed the actual memory).

Even though this is all well handled at the hardware level, it still costs time and energy to dynamically manage the resources. So much so, that even programs that can be perfectly divided to run on eight cores and require zero coordination often run only about 4.5 times faster, not eight times faster. Programs that DO require coordination will often run only a few times faster; and small problems will often run slower because in the time it took you to launch the threads, you could have finished using one core!

Unfortunately a great number of applications (such as gaming and scientific simulations and A.I. searching, data mining, database sorting) must solve millions of such small problems in sequence. Persistent worker threads (aka thread pools) can help by decreasing overhead but do not kill the problems.

On top of all that, in academia we have widely explored the problems of splitting problems up for multiprocessing. It still requires a human for most jobs of any significance. Sure, plain old transaction processing has been around forever, but compiler writers have had very little success in automatically parallelizing serial code, and about 99% of programmers don't know how to write anything else.

In my field (high performance computing branch of computer science) we measure our success by the percentage of the theoretical peak performance of which a particular piece of hardware should be capable. On commodity desktops we can often achieve over 95% of peak for a single core. By comparison, the average "C" program runs at about 4% of peak; the average "C++" program runs slower (the indirect referencing by pointers create stalls; meaning subsequent instructions cannot run until the pointer is loaded from memory).

Yet even with very specific and perfectly parallelizable linear algebra problems like matrix multiply; the best code on the planet is running at less than 70% of peak. That is a lot of distance to make up, and the problems are overhead, outdated OS scheduling issues that cause unnecessary stalls, and contention for memory resources.

There are many plans to add more cores to desktops; we won't be able to take much advantage of them if we don't make resource sharing fast enough to service all the cores. Which brings us back to the same clocking dilemma; if the memory bus cannot service 16 cores, we will not get a 16x speedup out of them; we can measure and see contention and bus limitations exploding on just 8 cores. We have a new limiting factor. There is only a certain amount of useful computation that can be accomplished with no memory access.

We usually measure how many gigaflops a machine can do. If core count keeps increasing but leaves memory speed behind, who cares? For HPC the limiting factor is becoming data bandwidth to the processors, and we will have to figure out how to look at our problems in those terms instead.

TonyC SA TX | Oct 14, 2008 | 8:26AM

"A couple of columns ago we touched on the practical rebirth of parallel computing. In case you missed that column (it's in this week's links)"

Is Bob adverse to the idea of hyperlinking, after all, this is HTML, right?

bill | Oct 14, 2008 | 9:25AM

For all my fellow geeks: be sensible. This article is PERFECT for me to forward to my friends who haven't a clue. Yes, there are fine differences between thread and process, and yes, analogies are rarely exact. My own favorite example for multitasking and multiprocessing and concurrency and caching and storage layering is the family kitchen before a big holiday dinner. (And surprisingly the grandmas will suddenly realize they understand it better than the men.)


For Bob (and Martin): You've both described too big an operation to re-do. (Aside from the question of whether the ATM would be calculating the new balance or just sending in a transaction.) For the deposit, it only has to re-do the "add deposit amount to new balance" and try again. For the withdrawal, since you can't get back the money, the order has to be "get permission to give money, THEN give it, then confirm that you gave it", rather than "give money and then check balance", both to protect the bank from giving beyond balance and to protect the customer from having his balance subtracted without getting the cash (power fails in the middle? car runs into building? whatever.)


Scaling has multiple dimensions. My previous company in computer telephony had Unix demo programs with process-per-channel handling. A customer tried to emulate the example and hit a brick wall when the RAM needs exceeded the system by just a little bit. In the single-task approach the program had to do all of the work to manage multiple channels, but the incremental overhead per channel was so much less that many more channels could be handled . . . as long as they didn't all ring at once, because then there weren't enough CPU cycles to get to them all by the fourth ring.


It's a complicated subject. This column is aimed at a knowledgeable-but-not-specialist audience. It succeeds at that level.

DutchUncle | Oct 14, 2008 | 9:33AM

Timely embrace? More like Deadly embrace. har har har

Sean | Oct 14, 2008 | 9:53AM

Pay attention to what jaycee said.

Amdahl's Law
Amdahl's Law
Amdahl's Law

There is a limit to how much speedup you can get from parallel processing.

Greg | Oct 14, 2008 | 10:29AM

This kind of optimistic concurrency is baked right into the programming language Clojure. This is not some research language or obscure toy language, it's a well designed lisp dialect being used for real-world software projects. The feature in question is Software Transaction Memory, and it uses database-like concepts handle concurrency in memory. It runs fast and makes it easy for programmers to write correct multi-threaded code.

Chouser | Oct 14, 2008 | 11:00AM

Optimistic concurrency has been around. I'd argue against your point that "most programmers just choose to have a cup of coffee and wait for [Bob's transaction] to finish." I'm a programmer, and I occasionally do some small scale database designing for my applications to use internally. Sometimes it's just easier to have a SQL backend than serializing to XML or binary files, even if my app is the only one to access the DB. Even when I do this, I usually leave some optimistic concurrency hooks in, just so that I can run external editors on the DB while my app is running, and not have to worry.

Regardless, I'm just not sure I get the point of these recent articles. You ranted about Ellison for a bit, then discussed cloud computing and databases, which was decently interesting. Then you introduced this supposed problem of databases and relations and clouds, and devoted an entire article to a solution that I'm sure Appistry already has implemented. It just seems to me that this single issue of not implementing optimistic concurrency is the least of Appistry/Oracle/Google's problems when they're trying to create multi-thousand thread connections through the cloud to databases.....

brian | Oct 14, 2008 | 11:23AM

... so what you're really saying is that no parallel supercomputer is powerful enough to speed up to release of NerdTV Season 2? Well, shucks. We were all hoping.

Derek | Oct 14, 2008 | 11:32AM

As many users have no doubt already posted (I only read the top 3), event-driven processing has been around a LONG TIME. Initially the events were simple and were dispatched to only one thread, and now we have many. The core issue with multi-threaded processing is not, then, how to do event-driven processing, but how to avoid resource contention.

There are resources which can only be accessed by one process at a time -- the network, the memory bus, the IO bus, not to mention hordes of single-use resources within a typical application. If an application accesses these things in parallel, poof the whole house of cards collapses.

Right now, managing access to all these resources has to be done by smart programmers knowing which resources will have contention and managing appropriately. Traditional languages (C, C++, C#, Java, Perl, etc etc etc) are all procedural in nature, and nothing intrinsic about the language allows the machine to infer dependencies and know what code units can be threaded. That means the programmer has to know.

We're just not that good. Frankly, I'm thrilled when my programs meet the more basic requirements.

So, why are us fallible programmers required to think about such things? What can we do to have the systems know what dependencies are?

Enter functional or declarative languages. Lisp, though arcane, is a great example. Lisp's structure can be analyzed by a compiler into application nodes. These application nodes are trees of commands and data which can be executed independently from the other application nodes. Viola - instathreads.

One more time -- instead of a human thinking about when to execute a thread, the compiler is doing the heavy lifting. No dependencies are missed - the language doesn't allow it. Now we can spread the load across cores, or even across physical machines -- no problem.

Functional programming is much maligned because it's quite different from procedural code. You're not quite asking the computer to execute a series of steps in the way humans are used to thinking about processing. Instead, the programmer has to recursively define the value (or a function to return the value) of the application. This iterative tree of functions to return "the" value is the dark magic.

[[ Note: I am not a Lisp programmer; I'm a Java programmer who is infatuated by Lisp, Haskell and XSLT ]]

PaulProgrammer | Oct 14, 2008 | 11:34AM

This is a very good example of some fundamental database concepts.

Doug | Oct 14, 2008 | 11:50AM

This article has a very good example of fundamental database concepts.

Doug | Oct 14, 2008 | 11:53AM

First of all, not all programs on the client need that much CPU. As a matter of fact, the CPU stays idle most of the time.



On the server side it's another story. But applications on the server sides are often already multithreaded (generally to handle several concurrent requests) so already take part of multi-core CPUs.



But I agree with others: I prefer when you write about higher-level issues than pure technique.

Laurent | Oct 14, 2008 | 11:57AM

I have worked in an environment that used optimistic concurrency and was constantly paying the price for it. The system was a test planning and tracking database for a validation lab. I would regularly make changes in the planned test sequences that I could not commit until they were complete. If a test operator made a single update to any of the associated test results while I was doing this, the system would not allow me to commit any of my changes, but only tell me that after I had it completed them and wanted to save. The response to my complaints was "save early and save often". My team eventually developed a process using email to alert others that we were working on a particular test, so please donít touch it. Thus we created a database locking system outside of the system itself.

While this is an example of a poorly written application, it does illustrate the need to design an optimistic concurrency system very carefully and build in the ability for the system to do intelligent retries, instead of requiring the user to start over.

JohnE | Oct 14, 2008 | 12:46PM

I love it that Bob does not restrict himself in either (any?) direction.

Keep on truckin', Cringe. Part of the pleasure of following your columns is not knowing what might come next.

ken in regina | Oct 14, 2008 | 12:56PM

Ada had multi threading before it was cool! (or useful) I guess the DoD is good at something.

lisa | Oct 14, 2008 | 1:07PM

I am sorry. There is nothing cool about threads. In fact, multithreading is the reason that we have a parallel programming crisis. Concurrent threads are inherently non-deterministic and hard to program, maintain and understand. The problem is so severe that companies like Intel, Microsoft, Nvidia, AMD and other multicore vendors are spending hundreds of millions of dollars in various research labs around the world trying to find a solution. Heterogeneous GPGPU-type processors like Intel's Larrabee and AMD's Fusion are even worse because they mix two incompatible parallel programming models (SIMD and MIMD) on the same die, a match made in hell. The solution to the crisis is to do away with threads altogether. Click on my link for more, if you're interested in knowing more.

Louis Savain | Oct 14, 2008 | 1:11PM

Concurrent programming is harder than sequential. But there are some cool languages that make it simpler. In the presence of thousands of processors languages such as Erlang look like a proper tool.

RIchie Bielak | Oct 14, 2008 | 1:42PM

Richie, Google "Erlang Is Not the Solution" to find out why Erlang is not the solution.

Louis Savain | Oct 14, 2008 | 1:55PM

Bob,
as others have alluded to, your solution to the deposit problem is something I learnt to cope with as a young programmer more than 20 years ago.

The solution it less about parallelism as it is about defining your "unit of work" within a transaction, and taking advantage of database row locking behavior.

Glenn | Oct 14, 2008 | 2:35PM

Check out Python 2.6's new multiprocessing interface. It works like threads, but actually uses subprocesses, so it automatically takes advantage of multiple cores and/or CPUs (it works on any unix or Windows).

nerkles | Oct 14, 2008 | 3:18PM

Bob, my lovely younger wife (by 24 years) also has a problem with her middle name. She spells it "Ann" but her birth certificate says "Anne". Maybe it's a generational thing.

Ronc | Oct 14, 2008 | 4:46PM

"Mary Alyce, who does not like to be kept waiting."

I have to ask - does this work out for you in the bedroom?

Richard Steven Hack | Oct 14, 2008 | 5:57PM

The ATM example is bad. But given that, the idea is sound. It just isn't new.

Optimistic updates have been around for a long time - it's just "lock as late as possible". So instead of "lock, deposit, update balance, unlock" it becomes "deposit, lock, update balance, unlock". Multithreaded programming is hard, but optimistic locking is a minor performance tweak to it.

Sorry, Bob. You're really losing it now.

ge | Oct 14, 2008 | 6:19PM

The ATM example is bad. But given that, the idea is sound. It just isn't new.

Optimistic updates have been around for a long time - it's just "lock as late as possible". So instead of "lock, deposit, update balance, unlock" it becomes "deposit, lock, update balance, unlock". Multithreaded programming is hard, but optimistic locking is a minor performance tweak to it.

Sorry, Bob. You're really losing it now.

ge | Oct 14, 2008 | 6:20PM

To ge: you're wrong; Bob's right. "Optimistic locking" is an oxymoron. Locking, by definition, is pessimistic: "Let's grab this lock just in case someone else wants to use this resource at the same time." Optimistic concurrency control doesn't use locks. Optimistic concurrency control says, "let's go ahead and use this resource, and if anyone else tries to use it at the same time, then let's go back and patch things up after the fact."

For more, google on "software transactional memory."

Rod Price | Oct 14, 2008 | 6:57PM

Lock the whole database? Surely you didn't mean that. Maybe you meant a finer grained lock than the whole DB. Row lock, yes, but not the whole database.

Eh?


Rex | Oct 14, 2008 | 7:43PM

The video game example is not too good. So I'll have one of my fancy fast cores devoted to... a slow waiting thread?

Juan Herrera | Oct 14, 2008 | 8:03PM

Single threaded programs can do things in the background too. Multithreaded programs can be stalled even though there is more than one thread. The real key is the ability for calls to be asynchronous (the idea that you fire you them off but can do something else while you are getting the result). It can be easier to achieve with threads (or continuations) but threads are not the only way.

Anon | Oct 15, 2008 | 1:04AM

Easier said than done : the most difficult part of multithread programming is testing. We can never be sure that multithread code is ok, whatever be the test applied, since everything is in the timing : a race condition or deadlock can occur when we change the processor speed, core quantity, etc. Even if we say that we will do optimistic concurrency, the program must be "proven" to be bug-free, rather than tested bug-free.

philippe stg | Oct 15, 2008 | 11:30AM

Philippe, you got it, man. Timing is the most important issue in software. Unless timing is deterministic, the code is risky, not to mention hard to maintain and debug. Deterministic timing is impossible with threads; that much is well known. I just cannot understand why the computer industry is still addicted to threads. It should be obvious to all that the days of multithreading are numbered. There is a better way to design and program parallel computers that does not involve the use of threads at all. It is based on a method that has been around for decades. Programmers use it routinely to implement video games, cellular automata, neural networks and whatnot. It uses two buffers and an endless loop. While objects in one buffer are being processed, the other buffer is filled with objects to be processed in the next cycle. When the first buffer is done, the buffers are swapped and the cycle repeats. Two buffers are used in order to prevent racing conditions. This method guarantees 100% deterministic timing and, as such, it eliminates all the nasty problems of multithreading. To solve the parallel programming crisis, it suffices to make this mechanism part of the processor and apply it at the instruction level. Of course, you got to have an easy to use and inherently parallel programming model to go with it. It is not rocket science.

The multicore research community is spinning its wheels because they are awash with cash. Finding an actual solution is not in their best interest. However, sooner or later the industry will have to come around because this crisis cannot last forever. Too much money is in the balance.

Louis Savain | Oct 15, 2008 | 3:26PM

@Anon
Single threaded programs can do things in the background too.

When you're doing things in the background, there is tacit treading going on. Most modern programming languages allow for this. They don't need to start a new process, but they do need to have another thread.

Alex Birch | Oct 15, 2008 | 3:52PM

"The check of the balance and the update of the new balance must occur within the microprocessor as an atomic action."

That's not true at all. The check and the update can only occur back at the database server. The microprocessor in the ATM has no ability to access that record atomically. The most it can do is post a conditional update and inspect the result.

So there's no possibility of decoupling the database from transaction processing. But that's good, because ATM machines are small and can't do much, while clusters of bank database servers are large and designed to scale larger as needed.

Ferdinand | Oct 15, 2008 | 5:01PM

Again, multi-threading is NOT parallel computing. Writing multi-threaded applications adds a lot of complexity to plain sequential serial programs. But this multi-threaded paradigm is not parallel computing. Parallel computing would come into play when you take the individual code statements from 1 thread, and run them on separate processors (cores). In order for this to happen, this thread has to be written in a special way to achieve that. This would add much more complexity to multi-threaded programming. And then you would probably find out that there isn't even much parallelism to reap from the application your trying to parallels. Do some research on "Vertical" and "Horizontal" parallelism and you will see what I am talking about.

ParallelMan | Oct 16, 2008 | 9:56AM

As a programmer, this is a bit of an odd column this time, cringley. I mean, this is all just introductory 101 thread-safety. You're not adding any kind of cringley spin here. Just educating lamens on how multicore processing needs to work?

Bog | Oct 16, 2008 | 11:28PM

You say, "although the redo is expensive it hardly ever happens"... The problem is that in some variations on this theme, the redo *does* happen *all* the time. Expanding on your example, lets say some bright young programmer updates the code to also maintain the total amount of money in the bank. Now every transaction is constantly colliding on updating that value, and your system spends most of its time rolling back and retrying transactions. This is why the "optimistic" model often fails miserably...

marc | Oct 16, 2008 | 11:47PM

Apache web server. I'm pretty sure most of us are using it daily for some application (email, web, etc.).

Kurt | Oct 17, 2008 | 2:15PM

To quote Mr. Tom Edwards, "Wow!" As an engineer who has written many multi-threaded applications, I was not aware of the wide-spread misinformation on the subject.

To say that a multi-thread application cannot take advantage of more than one processor (or core) is only partially true. Operating systems like Linux, Windows (NT,2000,...), and Solaris most definitely allow a multi-threaded application to use more than one processor. In fact of the three, only Solaris provides a proprietary feature to not schedule threads the same way as process.

Thank you Bob for your excellent depiction of a Write-After-Read (WAR) race condition, which accurately depicts the need to atomically offset a value. Like other readers, I do believe that I could give it to my wife, a radiologic technologist and definitely not a programmer, and she would be able to understand the issue at hand, and see why there is such an advantage to optimistic concurrency.

Now I'll show my ignorance... I do believe that most of the optimistic concurrency features of modern processors only compensate for basic values in memory, like a single number, or a very short sequence of letters (say 8 or less). Because of this, I agree that the roll-back and redo scenerio you have described can be very expensive, because most often a unit of business data is larger than a single number. For instance, the balance and ID the ATM-Terminal which last modified the balance may need to be updated simultaneously, thus the fall-back to a pessimistic locking is so routine.

Here's the zinger though. I do believe that most of the pessimistic locking is implemented by optimistic concurrency. So really, both are always being used. :)

Matt Battey | Oct 17, 2008 | 4:14PM

Of course the problem gets a little more complicated if you are doing transfers (ie, changing two separate values), because it would then require a rollback of previous values. Cross-transfers might even result in live locks. And then there's problems when it's not enough for a value to be the same, or transactions that can't be redone or rolled back (you can't try to land a plane twice if you crashed it the first time), etc.

All of which are throughly discussed in the literature about transactional memory, which is what you are talking about.

Daniel | Oct 17, 2008 | 5:42PM

Perhaps programmers in their universe regularly discount the possibility of concurrency ? In the machine world, simultaneous events with additive or canceling effects are a probability.
So you program accountability into the system to accommodate multiple, simultaneous events. Sometimes thinking at the assembler level simplifies things.

Last time I dabbled, database servers would tag a field with pending activity, read then write.

In the machine world, events would be assigned their own flag. Originally on a single system, it was a single bit in memory of a single processor. As processes scaled to dozens and then hundreds of processors, it became an object managed by a server that would scale as all the different clients would increase.

Then, using your example, as the server would process the transaction, Bob would see $1,200 and Alice would see $1,300. The next time either of you checked the balance, it would be $1,496.

The final value is not an error, it would be because you guys bank at Key and checked your balance using another bank's ATM, and were penalized $4 for checking your balance. ;p

id10t | Oct 17, 2008 | 10:47PM

Another approach is to change the requests from "set the balance to $1200" to "increment the balance by $200". This then does not presuppose the starting balance, and each transaction is much more atomic. Of course, the clients may be somewhat surprised to see the bank balance has increased by $500 after their deposit if they are not aware of what the other is doing. But a look at the recent transactions will reveal the reason.

Alex VanderWoude | Oct 18, 2008 | 2:40AM

To Brian and others questioning Bob's choice of subjects lately:

You wrote -- "Regardless, I'm just not sure I get the point of these recent articles. You ranted about Ellison for a bit, then discussed cloud computing and databases, which was decently interesting. Then you introduced this supposed problem of databases and relations and clouds, and devoted an entire article to a solution that I'm sure Appistry already has implemented."

A few columns back Bob hinted that he needed money and was looking for consulting contracts. He's using this column as an intro to large IT organizations. It goes like this -- see, I already know your problems and how to solve them. The whole thing started with the series of articles criticizing the consulting business as existing merely to rubber stamp management's pre-conceived notions. Then a series of columns criticizing management styles in general, and offering Bob's ideas on re-engineering the development process.

As for the questions, "where is nerd tv". It doesn't pay, so it's on the back burner.

You have to read between the lines.

Mkkby | Oct 18, 2008 | 2:20PM

The development tool I use (Unique CONCEPT/ Unique 4GL) uses this optimistic concurrency for more than 15 years as the default strategy to avoid locks. Many other tools certainly support this as well. My oldest book about databases "Fundamentals of database systems" from Elmasri/Navathe published in 1989 discusses the optimistic concurrency, too.

It is definitely nothing new, can help in certains situations, but has its disadvantages as well (e.g with classical (hopefully row) locking you usually know at the begin of the transaction when you try to lock the row, if the transaction can be performed. With optimistic concurrency you only find out at the end that the transaction failed, this needs a different approach in the error handling).

Jobst-Hinrich Jacke | Oct 18, 2008 | 6:59PM

The development tool I use (Unique CONCEPT/ Unique 4GL) uses this optimistic concurrency for more than 15 years as the default strategy to avoid locks. Many other tools certainly support this as well. My oldest book about databases "Fundamentals of database systems" from Elmasri/Navathe published in 1989 discusses the optimistic concurrency, too.

It is definitely nothing new, can help in certains situations, but has its disadvantages as well (e.g with classical (hopefully row) locking you usually know at the begin of the transaction when you try to lock the row, if the transaction can be performed. With optimistic concurrency you only find out at the end that the transaction failed, this needs a different approach in the error handling).

Jobst-Hinrich Jacke | Oct 18, 2008 | 7:02PM

You should see the way Tandem handles multiple threads. Add a processor and you just get performance increase.

Karl | Oct 19, 2008 | 12:43AM

I guess you haven't fixed the "double comment post" problem after all (must have had a week where everyone happened to only click it once).

Maybe after you get your new job?

fiddlepaddle | Oct 20, 2008 | 2:51AM

Of course, another solution to the race problem is for the database to simply add the delta amount to the existing value, something like "SET balance=balance+deposit_amount WHERE account_no=31415926535". You could then get the updated balance at the end of the process for receipt printing purposes.

Ben | Oct 21, 2008 | 1:59PM

My preference on the account balance thread is to insert transactions in a table and then regenerate the account state from the combination of the last (daily) checkpoint and posted transactions. This is fairly resistant to concurrency errors.

Fixing the concurrency problem is fairly straightforward - pessimistic locking. Works fine for personal accounts, as they don't have much traffic and the contention window is sort. For high throughput accounts, I'd just have a velocity limit and periodic syncing ala my checkpoint model. If the balance gets low, impose a lower velocity limit. This would require a bit of software to log transactions and track total velocity between syncs, but eliminates a lot of locking at the cost of some extra layering.

chris | Oct 21, 2008 | 5:50PM

Bob, your last few articles on database technology has essentially missed some key technologies that are coming down in the future.

First I think this article is good. I like that you discuss threading, but I feel that you missed the point that threading can happen even on a single core chip. As you have mentioned before, it is the heat issue that kept CPU manufactures from increasing clock speed, not a desire to move to multi-core chips. The move to multi-core chips is a consequence of the heat. There is some "cost" involved with multi core and multi processor setups.

Another technology you missed was the storage technologies. This is in response to your parallel computing article. I think we fundamentally disagree here. I believe for the purposes of running an enterprise database, networking a bunch of slower computers together to do a task is a very stupid idea. Parallel computing is usefull in two circumstances to me:

1.) When you are taking about very high speed individual systems that literally can't be upgraded. Chaining these together to preform more calculations per second. This is how most supercomputers work.

2.) Distributed computing over low speed network connections using peoples spare CPU cycles.

This flies in the face of your argument about money. I understand that money drives everything. This is why parallel computing has sort of taken off, and why google is so involved.

My argument is that we move ahead with technology, and put R&D into products that can offer us the same level of service, but on smaller less distributed systems. Lets face it, it is easier to manage, backup, audit ect... systems that are local versus distributed. This is a problem with databases, but not the with aforementioned distributed large scale programs. Also keep in mind preformance. Anytime you can do something locally, on the same motherboard or over short high speed fiber connections, it is going to be faster and less expensive.

Google does everything in RAM. RAM as we know it is destroyed on loss of power. The contents are wiped. I contend that we should be putting more effort into non-volatile storage that is as fast as RAM. One of the steps in the right direction is the new fusion IO drive. A review can be found here:

http://www.dvnation.com/Fusion-IO-IODrive-SSD-Solid-State-Disk-Drive-Review.html

These surpass the 500MB/s part for read and write on a single "disk" with no raid. With raid, they scale well. They also have a 50 mico-second access time. Yes that is half a millisecond. BUT, these drives are still nowhere near RAM speed. You just arn't going to get there with flash. You must look ahead to technologies like M-RAM. http://en.wikipedia.org/wiki/MRAM

For the hear and now I think we are stuck with distrbuted systems being more popular due to money, but I should we should be looking for solutions to bring it back to the local system.

Matt | Oct 24, 2008 | 11:46AM

Today, multicore processors are great for end users to have because:

1. Botware/malware/trojans are often CPU intensive

2. Flash is frequently CPU intensive, and appears on a large percentage of web pages

CPU has become a dumping ground for malicious, runaway, and inefficient processes.

Andrew S | Oct 28, 2008 | 12:23AM

Yes, multiple threads can run on a single processor, the OS just needs to switch between them. But - it can switch away from a thread that would be suspending waiting on something to happen like disk or network IO. That is, if the program is propertly written. Impropertly written, it won't do any good. Also breaking a program into too many threads will slow the system down - it spends too much time doing context switches. Also, Bob, your email server example doesn't really scale. That's not how webservers are written. There are other technolgies like IO completion ports for building scalable code. Your concurrancy example is good though. Other interesting things are deadlocks.
Brian

Brian K | Nov 18, 2008 | 8:05PM

text me at 757-737-5690

DONALDMCCRAY | Jun 01, 2009 | 1:04AM

add a comment

name:

e-mail:

url (optional):

Comment (br and p tags are not necessary for line breaks)