Programming


This piece of code we are about to discuss was used in production software and i was tasked with reviewing the patch. Try to see if you can spot *any* issues with code. Later we will take a look at the exact observations, which are hugely interesting and instructive regarding system behavior.

The Query

This query retains top n records of a particular type and deletes the other rows in the table of the same type from a Sybase database.

for (int i = 0;i < ListOfTypes; i++)
{
ExecuteQuery “delete from table where PrimaryKey NOT IN (select top n PrimaryKey from table where Id = i) AND Id = i”
}

Observation – No Data to be Deleted in the database

  1. CPU consumption during query execution is negligible when there are matching rows to be deleted. The fact that this code is issuing multiple dynamic queries which have to be parsed does not seem to be too much of an issue for Sybase.
  2. 2000 queries took around 3 seconds overall at around 12% of CPU cost on a Xeon box.

Observation – delete finds rows for deletion

  1. With data to be deleted, the query took 5 minutes when there was valid data in 30 loops, that is over 5 hours when deletes are extrapolated to be repeated 2000 times.
  2. The CPU consumption figure remained the same.

Why are Database Deletes So Slow ?

Relational databases tracks everything using logs or otherwise called Transaction Logs because they record all the transactions aka changes that happen to the database. The ACID nature of transactions are guaranteed using these logs. So when you make a change to the database, a LOG is written to disk.

The actual change is only made in memory and not written to the disks immediately, for efficiency sake. But Logs are always written promptly and without fail, so that if the machine crashes or rollback is required, this log can be used to reconstruct the state of the database with minimal loss of data. This means that every time you make an individual delete you are going to make the disk spin and disks spinning are horridly slower that anything else you can think about.

How slow can the disks be ?

Numbers from a talk by Jeff Dean (works on both MapReduce and BigTable) of Google, as reported here

Comparative slowness aka latency in terms of CPU cycles

Floating point calculations = 0.25 to 3 cycles
L1  cache access                       = 3 cycles
L2 cache access                       = 14 cycles
Dram                                            = 200 cycles
Flash                                            = 3 Million cycles
Disk                                               = 15 Million cycles

Comparative Slowness aka Latency in absolute time

L1 cache reference                                                        0.5 ns
Branch mispredict                                                             5 ns
L2 cache reference                                                             7 ns
Mutex lock/unlock                                                        100 ns
Main memory reference                                              100 ns
Compress 1K bytes with XXX                              10,000 ns
Send 2K bytes over 1 Gbps network                 20,000 ns
Read 1 MB sequentially from memory          250,000 ns
Round trip within same datacenter                500,000 ns
Disk seek                                                              10,000,000 ns
Read 1 MB sequentially from network    10,000,000 ns
Read 1 MB sequentially from disk            30,000,000 ns
Send packet CA->Netherlands->CA      150,000,000 ns

Can you speed up the disks?

SCSI disk array on a server

SCSI disk array on a server

You bet !!. We tried to speed up this whole experiment by moving the tests from an IDE based system (with 7500 rpm drive) to a system with a single (the picture has six – no we used just one of them) 15k RPM SCSI disk + SCSI controller (no on board memory).

The results from moving to SCSI system –

  1. The delete time improved by a factor of 4-5 times and the worse case average time period dropped to around 133 minutes from 5 hours.
  2. However with the SCSI system in use, the CPU consumption during query execution also jumped by the same amount, by 4-5 times because there are fewer blocks due to disks and therefore more query execution (4-5 times worth) is done by the DB engine.

As you can see, it would be really easy for us to calculate how many disks we would need to speed up the deletes to a manageable time. I might have to go with a couple of SCSI disks in a RAID configuration and try to achieve the speeds that i want.  At the same time the database engine’s CPU consumption would also have to be separately addressed such that it does not have to do much work in finding the rows to be deleted.

Is there any way to improve this ?

  1. Use Transactions –

    SQL server engine makes transactional records only as part of a single transaction. Not sure how this works vis via Java and sybase engine using which this query was tested. So if you ensure all your changes are made as part of a single transaction the disks would be less affected than if it was done otherwise.

  2. Do not use a database for real time stuff
    An even more optimal solution will be to not rely on the database at all and instead do all this in a specialized in memory component in a thread safe hash or something equivalent. Use database only as a slow data backup for being used during failure recovery. This would give the incomparable throughputs compared to any RDBMS / disk based solution.

My suggestion to improve CPU (untested)

  1. Move the entire loop into a stored procedure
  2. Run a select to get the top 20 and extract the ID of the bottom one
  3. Run a delete to delete all ID > ID extracted.What are the advantages – You remove  possible query compilation for the execution of 2000 queries and at the same time, remove usage of possibly highly inefficient NOT IN operator. This needs to be verified though.
  4. Remove all foreign key references to the current table – but of-course that would be going against the grain of RDBMS concept itself. However for desperate situations, this might work ….

What was implemented in the end?

Well, the production software had this delete sequence running every 30 mins. The no of events this system claims support to is only upto 25 events per hour.  So at this rate, there would be no pile up and no big deletes happening. So we dont have a problem !!!!

Advertisements

Just listened to a podcast from Scoble, interviewing the so called king of tech shows Leo Laparte.  The talk does impart the impression on how content is most important than any glam and glitter and their wow’s about the new media, and some general other information about content sharing.

While they went on about the history of the show, they mentioned how they both have ran into one another a long time back and how Leo has touched based with many folks in the industry and even launched their careers.

This seems to be a theme that i have heard repeating every now and then with Scoble and many others. All these guys who have been in the Valley or manage to be in tech scenery in the States, seems to have run into the others “who matter”, at some time or other.

It really does seem to matter where you are from, for you to get picked up in the flow, noticed and perhaps to also feed you the enthusiasm to do more, and see more groovy stuff done and launch you into new circles that matter perhaps (VC’s anyone?)

Since all that is not here, i might as well keep myself fixated on the idea that the useful tool i will create some day will have to be at least 50% better than it might been necessary, had i been from the Valley.

I hope you realize that too.

Cheers !!

I ‘m beginning this series, as extracts of notes from some of the best comp science classes i have ever witnessed, recorded by MIT.

However i will be emphasizing only the points which struck me, after 10 years of experience as worth remembering again, that I feel the industry might do well to never forget . I will try to leave out the details, like the data structures, recursive techniques and such, which most people are likely know. I would highly recommend you to access the full text or videos, if you feel  that you missed out any of your comp classes or have never listened to comparable masters explaining this art.

My aim is to capture the pearls of wisdom that i might pickup listening to this class all over again. This is part 1 of such notes and this is the reason why i felt i ought to do it.

What is Computer Science

Computer Science is not about computers in the same sense, that geometry is not really about surveying instruments. But when geometry was created in ancient Egypt, it really was about surveys and instruments, in the same way computer science started off with computers in the twentieth century.

What computer science is really about is

1. Formalizing intuitions about process ie “How to” knowledge

eg How to compute sqrt vs “what is sqrt”
eg How to draw triangle vs “what is a triangle”

So whats so hard about this? Real issues of computer science is not about telling people how to do stuff. That would be too easy. Real problems come when we try to build very very large systems that performs these processes. Real problems arise with these systems that have programs that are too big to fit in any one person’s head. Therefore,

2. Computer science, is also, all about techniques to control complexity of  large systems.

Abstract Characteristic (vs other engineering disciplines)

The components we use in computer science are asbtract, like an array or a hash. Unlike other disciplines that also deal with complexity the difference here is that the complexity comp science face is not physical in nature. They do not face the physical realities of real world like in the case of other engineering fields. Leakage, resisitace, heating, drag and such physical issues does not dog computer science. Rather what ails it, are the constraints of human mind in holding and keeping track of big programs.

In this sense computer science is an abstract form of engineering and therefore its most important tools are tools for abstraction, that aid human understanding and kill complexity. This is what comp science is mostly all about.

What are the techniques for controlling complexity

  1. Black-Box Methods
  2. Conventional Interfaces
  3. Large Scale System Integration Metaphors
    1. OO
    2. Streams
  4. New Languages

Black Box Techniques

Refers to making something and building a box about it such that it can be used without knowledge of its internals much like an IC chip. You want to suppress details so that you can build bigger boxes that use this.

You can also use black box techniques to express generality. eg A routine add might be able to add numbers, vectors, signals etc.

Conventional Interfaces

Are agreed upon ways of plugging things together.

These are operations that all kinds of “abstracts” might support eg +

Languages

Help you control complexity by dempahsizing certain aspects of the complexty and emphasizing others eg SQL emphasizes only the data modification part and hides everything else

Learning a language is like learning chess it just takes 2 minutes but learning the implications takes a lifetime.

Framework for evaluating and understanding Languages

If we view languages in the context of tools in reducing complexity, it immediately becomes clear that a new language is not all about how many lines of code to do the next cool thing. Rather they should be evaluated in terms of 

  • What are the tools for abstractions it provides
  • What are the primitives that it provides
  • What are the ways of combining these primitives


My thoughts : The idea of computer science as only about tools to control complexity is not too well imbibed into the many minds (including my iniitial years)  i have come across in my decade of experience. Rather, computers are all about “coding” or Java or C++ and networking. If code is viewed and reviewed from this angle alone, much of the issues that plague the industry would have been non existent.

In these lectures everything that follows is a function of this characterisitc, of ways to reduce complexity, evident in the way languages are evalauted. I’m excited to take the new (rather old) take on all other topics in the following series and will be posting the follow up posts on the same.

I felt the topic to be at the core of what i do. So spun it off as a permanent page always available on the site.

That’s easy – You start by looking at what parts of your code are the most expensive – Keep drilling down into the costly calls until you find which part of code really is the culprit. And then you optimize it. Easy isnt it ??

If you do not have ways to do this, your tool-set sucks.

[i use the Intel Thread Checker]
[click to see the big picture]

I just noticed that the biggest app running in my work laptop,  with respect to memory consumption is FireFox (3.0.4 if you have to know).  It consumes on an average of about 500 MB worth of memory. Even Outlook, comes only a far second. Of-course i have Visual Studio, MSDN and SQL -server et-all installed. But FireFox beats everything hands down when it comes to the frequency which with i use them.

All other applications seem to support the browser, or launch it within themselves. No applications seems to be made these days, without web being their core interface and to that end again browser has become a a single point of access. Even VM’s seems to favour running their clients inside a browser window.  When viewed from this angle, the rationale behind google’s shiny new web browser, chrome, becomes more apparent.

In short, the browser has become a platform of sorts, with the biggest players vying with each other for a piece of the action. What with all the VM efforts and Javascript optimization efforts , bearing fruit, the concept of browser as a platform, and Javascript as the ultimate language might be happening faster than we realize !!!

(note : Javascript is still 10x slower than compiled Java – but the point is, everyone involved seems to be accelerating their efforts to get there faster)

In a previous post i pointed out how questions posted in reward based discussions sites like stackoverflow.com never gets answered satisfactorily. This post is a look at one such feeble answer and makes an effort to explain in more detail a basic question about hashes.

The Question

In Java, the hash code for a String object is computed as

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. Why is 31 used as a multiplier? So why not 29, or 37, or even 97?

The partially wrong answer

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

NOTE :  Primes are part of an older technique for hashing and there are supposedly better hashes which use more sophisticated techniques. I do not know the mathematical foundations for these, so cant vouch for them but its true that the prime number technique is quite old.

The correct but longer explanation

The reason 31 is chosen is because it is prime – not because it is odd. It so happens that primes are un-divisible by any other numbers. This includes 2 and this makes it odd too but the real reason, is its primeness and one other factor which we shall go into shortly .

So why a prime ?

Hashing works by allocating a value into one of the many storages, a hash has, for fast retrieval later on. The storage a hash has is also termed as buckets in comp literature, for reasons which will become clear later on.

hash-new-itemNow, how does the hash identify which bucket it needs to store the value in? This is an important question, due to the property of hashes, which makes it compulsory that a hash be able to tell you in constant time (which is hopefully fast)  in which bucket the value is stored in.hash-check-items

The slooow hash find logic

for(i = 0; i < totalkeys; i++) { if (CheckForEquality(key[i], "Samuel")) return i; } [/sourcecode] This sort of sequential search, would cause the hash performance to worsen, directly dependent on the number of value it contains. In other words, you would have a linear performance cost (O(n)), which becomes progressively bad with larger and larger no of keys(n). The other complication is the actual type of the value you are dealing with. If you are dealing with strings and other such complex types, the no of checks or comparisons itself becomes prohibitive in terms of cost.

Now we have 2 problems

  1. Complex values which are difficult to compare
  2. Sequential searches are not fast and cannot give constant time lookups

Solving the complex value problem

The easy way out for this issue is to derive  a way to decompose complex values into a key or a hash that is easy to work with. The easiest way to achieve this of-course is to generate UNIQUE numbers from your value. The number has to be UNIQUE since we want to distinguish one value from another. This UNIQUE side of things is where primes come in handy.

Primes

Primes are unique numbers. They are unique in that, the product of a prime with any other number has the best chance of being unique (not as unique as the prime itself of-course) due to the fact that a prime is used to compose it. This property is used in hashing functions.

Given a string “Samuel”, you can generate a unique hash by multiply each of the constituent digits or letters with a prime number and adding them up. This is why primes are used.

However using primes is an old technique. The key here to understand that as long as you can generate a sufficiently unique key you can move to other hashing techniques too. Go here for more on this topic about hashes without primes.

Now why is 31 used?

Ok, so now you have your unique identifier generated for each value. Now how do you allocate this value to a bucket or a container you have.

Lets say your container is a fixed array of 16 items. The easiest way to decide where to stick the value or the generated unique number, from now on referred to as the hash key, is to stick the key in the same location as its value.

So if your hash is 3 you stick your key in the location number 3. But of-course what would happen if the hash number is bigger than your container size. For this reason the initial or the very first hashing algorithms used to divide the generated hash key and stick the key in the location pointed to by the remainder. (This again necessitated that the no of storage locations in a hash was a prime number so as to generate unique remainder values).

So assuming your hash has 11 items, the hash key 12, would be stuck into 12%11 remainder 1 – 1st  location.

why is 31 used?

Well, when you stick your keys in the containers, depending on the prime used, you would get a different key number and therefore a different distribution of the keys in your array.

So the same key “abc” would be a*31+b*31+c*31 for prime 31 and it would generate a different key for the abc with 29 – a*29+b*29+c*29.

Since the key produced is different, the data would go into a different location depending on the prime used.

Researchers found that using a prime of 31 gives a better distribution to the keys, and lesser no of collisions. No one knows why, the last i know and i had this question answered by Chris Torek himself, who is generally credited with coming up with 31 hash, on the C++ or C mailing list a while back.

Collissions

There are chances that certain strings might cause the same key to be generated. In such cases, the individual has storage is turned into a link list or some other type of storage that can store all the duplicate keys. This is the reason why the individual hash storage is called as a bucket.

Better hashing algorithms

But the modulo hashing algorithm we just looked at is extremely simplistic. There are much more complex and more faster hash algorithms that can be used. There are even tools that will generate the algorithm for you, given the type of keys you use.

Here are some fast and better distributing hash functions / modules if you wish to improve on the ones you have –

Paul Hseih’s Hash

Bob Jenkin’s Hash and his Dr Dobbs Article on the same

One from Google

3 cheers for better performance !!!

« Previous PageNext Page »