{ work }

Memcached for Dummies

The other day I was chatting with a colleague about Memcached.  Eviction policy came up, and I casually mentioned that Memcache isn't strictly LRU.  But a quick Bing search said Memcache is LRU, like this Wikipedia entry.  Hmm, I was 99.9% sure Memcache is not LRU, something to do with how it manages memory, but maybe I was wrong all these years.  After reading through some Danga mailing lists and documentation, the answer is, Memcached is LRU per slab class, but not globally LRU.  

So what does this exactly mean.  Imagine starting Memcached with these command-line arguments to override the defaults,

memcached -vv -m 1 -I 1k -f 3 -M

-vv
for verbose output

-m 1
maximum 1 megabyte cache

-I 1k
1 kilobyte (1024 byte) page size

-f 3
chunk size growth factor of 3 

-M
return error on memory exhausted (rather than removing items)
just to see things more explicitly

The output will be something like this,

slab class   1: chunk size        96 perslab      10
slab class   2: chunk size       288 perslab       3
slab class   3: chunk size      1024 perslab       1
<26 server listening (auto-negotiate)
<27 server listening (auto-negotiate)
<28 send buffer was 9216, now 5592405
<29 send buffer was 9216, now 5592405
<28 server listening (udp)
<28 server listening (udp)
<28 server listening (udp)
<28 server listening (udp)
<29 server listening (udp)
<29 server listening (udp)
<29 server listening (udp)
<29 server listening (udp)

The visual representation below may be helpful, 

We have a cache with a max memory limit of 1 megabyte.  This 1 megabyte of memory is divided into 1 kilobyte (1024 byte) pages.  These 1024 byte pages are assigned, as needed, on a first come, first serve basis, to the three slab classes.  Page assignment to a slab class is permanent.  The three slab classes are determined by the page size and the chunk size growth factor.  If you change the page size and/or chunk size growth factor you'll get a different slab class configuration.

With our settings, slab 1 has a chunk size of 96 bytes (the smallest, initial chunk size).  There are 10 chunks per page (11 chunks would be more than the 1024 byte page size) in slab 1.  Slab 2 has a chunk size of 288 (96 x 3 growth factor).  There are only 3 chunks per page in slab 2.  Finally, slab 3 has a chunk size equal to the page size and obviously only 1 chunk per page.

Each chunk can hold an item up to its size.  By item, I mean the key, the value and some overhead.  The item's size determines which slab it is stored in.  Small items, say 40 or 60 bytes, are put in slab 1.  Leftover storage is wasted.  That is, putting a 60 byte item in a 96 byte chunk results in 36 byte wasted space.  These 36 bytes are not available for other use.  Slab 2 holds items between 96-288 bytes.  Slab 3 holds items between 288-1024 bytes.  With our arguments, we could not store items larger than 1024 bytes.

So that's an overview of how Memcached is layed out.  Pages, chunks, slabs.  Now imagine we store a bunch of small items and a bunch of large items but no medium items until all pages from the page pool are used.   

Slab 1 might have 800 pages and slab 3 might have 200 pages (those numbers are not exact, won't add up).  Everything is good, until we try to store a medium size item.

Memcached will give us an out of memory error (or won't store the item  w/o the -M option) because slab class 2 has no available pages to use.  Pages from slab class 1 and slab class 3 can't be re-assigned to slab 2.  You can think of Memcached as having separate internal caches defined by the slab classes.  

Finally, this brings us back to the LRU question.  Since each slab class is essentially a separate cache, there is no global LRU, only slab class LRU.  The least recently used item won't get evicted for a new item if the items are not in the same slab class.  Depending on your storage/access patterns, you could end up with one slab class constantly evicting recently used items, while another slab having a bunch of old items that just sit around. 

Which brings me to another point, items/chunks are not actively reclaimed/expired.  Memached does not have a background thread that explicitly expires items, reclaiming used chunks for new items.  When a slab needs a chunk and there are no more pages, Memcache will look at the queue tail for items to evict.  Memcache will make a best effort to evict expired items (items you've explicitly set to expire after some time).  In scenario 1, item 2, an expired item, is evicted.  However, in scenario 2, item 1, which has not yet expired, will be evicted, even though item 4 would seem like the better candidate.  But since item 4 is not near the tail, Memcached stops looking and just expires item 1. 

Another example of leaky abstraction?  The Memcached API is very simple, straightforward.  But at a certain point, you need implementation knowledge to make sure things are behaving as expected.

It's All Garbage

Amazon.com says I bought Programming Ruby (2nd edition) on November 4, 2004.  Seven short years of Java later I'm finally putting it to use.  One immediate question is, how does garbage collection work in Ruby?  Is it a tracing or reference counting collector?  Is it generational, and if so, how many generations?  These questions eventually led me to an interesting paper by David Bacon, Perry Cheng and VT Rajan on A Unified Theory of Garbage Collection.

Universally, garbage collectors are viewed as either tracing or reference counting.  The Sun HotSpot VM, for example, is a tracing collector.  It traverses the object graph from the roots, finding reachable live objects and reclaiming unreachable dead objects.  PHP, on the other hand, uses reference counting to decide which objects can be safely garbage collected.  This table summarizes the typical characterization of each collector type,

	Tracing	Reference Counting
Collection Style	Batch	Incremental
Cost per Mutation	None	High
Throughput	High	Low
Pause Times	Long	Short
Real Time	No	Yes
Collects Cycles	Yes	No

The first observation is, once optimizations are added to the basic tracing and reference counting collectors, they begin to converge.  For example, with deferred reference counting there is a periodic scanning of stack references to reduce per-mutation cost.  A generational tracing collector, on the other hand, imposes a per-mutation overhead but gains shorter pause times.  So even though collectors are typically described as one or the other, we should really view them as hybrids.

The second interesting observation is, tracing algorithms are the duals of the reference counting algorithms.  Both types of algorithms share the same structure.

	Tracing	Reference Counting
Starting Point	Roots	Anti-Roots
Graph Traversal	Forward from roots	Forward from anti-roots
Objects Traversed	Live	Dead
Initial Reference Count	Low (0)	High
Reference Count Reconstruction	Addition	Subtraction
Extra Iteration	Sweep Phase	Trial Deletion

Tracing collectors start at the root, traverse foward, finding live objects.  Initially all reference counts are zero (an underestimate) but live objects have their reference count incremented to their true value (keeping a bit flag is just an optimization of actual count).  Reference counting collectors start from non-root objects, traversing forward to find dead objects.  Reference counts are initially high (an overestimation that includes references from dead objects) but decremented until the true reference count is obtained.  Ultimately, the difference is just the initial value (an underestimate or overestimate) and whether we increment or decrement to obtain the true reference count.

So that was interesting, but lets return my the original question about Ruby garbage collection and add a few other languages in for fun.  Here's a quick summary.  Don't quote me on it, corrections appreciated. 

Language	Garbage Collection (for reference/popular implementation - others may be available)
Erlang	tracing - per process (very small processes), compacting then generational optimization
Haskell	tracing - generational (3), 512KB nursery
Java	tracing - generational (2), serial, concurrent, concurrent + incremental
Perl	reference counting - does not handle cycles
PHP	reference countng  - 5.3 handles cycles w/ "on the fly" cycle detector, prior versions did not
Python	reference counting - handles cycles w/ tracing cycle detector
Ruby	tracing - non-generational
Scala	see Java

Causal Atomic Broadcast

Spent the other day reading up on ZooKeeper a little.  ZooKeeper is a distributed, open-source coordination service for distributed applications.  Out of the box ZooKeeper can be used for name service, configuration and group membership.  Building on ZooKeeper's primitives, you can create barriers, locks, queues, etc.

Sounds interesting enough, but what got me really interested was ZooKeeper's atomic broadcast, the guts of ZooKeeper.  Atomic broadcast is very closely related to consensus (apparently equivalent in certain asynchronous systems).  Both are fundamental problems in distributed systems.

So what exactly is atomic broadcast?  To answer this, lets work our way from Reliable Broadcast.

Reliable Broadcast

Reliable Broadcast is the weakest type of fault-tolerant broadcast.  Informally, if a correct process broadcasts a message then all correct processes eventually receive that message.  Reliable Broadcast doesn't impose any message delivery ordering.

FIFO Broadcast

FIFO Broadcast is reliable broadcast that satisifies FIFO Order.  If a process broadcasts message m₁ before message m₂, then no correct process delivers m₂ before it delivers m₁.  For example, if message m₁ is a deposit of $100 into your banking account and message m₂ is a subsequent withdrawal of $75, you most definitely want FIFO Broadcast, otherwise your bank will charge you an overdraft fee (on top of their ridiculous $5 ATM fee).

Causal Broadcast

Sometimes FIFO Order is not enough because FIFO ordering too limited in context (a single process).  You need Causal Order to guarantee that if the broadcast of message m₁ "happens before" or "causally precedes" the broadcast of message m₂, then no correct process delivers m₂ before it delivers m₁.

For example, imagine three processes a, b and c.  Process a broadcasts m_1a, "Banks to charge $5 ATM fee."  Process b delivers m_1a then broadcasts message m_1b, "That's outrageous!"  Without Causal Order, process c could deliver message m_1b before m_1a,

m_1b : "That's outrageous!"
m_1a : "Banks to charge $5 ATM fee."

which doesn't make sense (what is outrageous?).  Causal Order requires delivery of m_1a before m_1b.

Atomic Broadcast

Causal Order imposes a partial ordering in the system, so messages without causal relationships are logically concurrent and do not have any delivery order guarantees.  This can be problematic in some cases.  For example, imagine two replicated databases DB₁ and DB₂.  Process a broadcasts message m_1a, "deposit $100."  Process b broadcasts message m_1b, "charge 10% fee."  Since there is no causal relationship between the messages, this situation may arise,

DB₁ : $0 + $100 - ($100 * 10%) = $90
DB₂ : $0 - ($0 * 10%) + $100 = $100

which is obviously not desirably.

Atomic Broadcast imposes a Total Order on the system so that all messages are delivered in the same order, whatever that order maybe.  So in this example, it's either $90 or $100 but never $90 in one database and $100 in the other.

We can further classify Atomic Broadcast by the actual ordering it imposes.  FIFO Atomic Broadcast is then Reliable Broadcast that is FIFO Order and Total Order.  Causal Atomic Broadcast is then Reliable Broadcast that is Causal Order and Total Order.  Causal Atomic Broadcast is the strongest guarantee we've examined.

Summary

This diagram nicely summarizes Reliable Broadcast and the orderings above (taken from "A Modular Approach to Fault-Tolerant Broadcasts and Related Problems," which the above is basically a summary of).

So there you have, atomic broadcast.

Sequential Random Sampling

Time flies when you're having fun (even when you're not).  It's been more than a year since my last work related blog.  Writing about random computer science and programming topics is like going to the gym; once you get off the routine it's very easy to just sit on your literal and figurative ass.

For my first topic back I want to relay some sequential random sampling algorithms I came across this week.  It started out when we needed some random samples from the database.  Performance issues aside, MySQL lets you do

select column from table order by rand() limit n

to select n random rows from a table.  The randomness of the rand() function aside, someting troubled me about this approach.  Won't your results be skewed toward the lower rows when you get duplicate random values?

So I was searching around for some random sampling algorithms and ran across a few from the works of Jeffrey Vitter I found rather interesting.

Algorithm S

Sequentially go through N elements to select n random samples.  For each element generate an independent random variable U between 0 and 1 and test that NU > n.  If true, skip, otherwise select for the sample and decrement n.  In either case decrement N.

Algorithms A-D

These algorithms optimize Algorithm S by skipping elements.  Define a skip function S(n,N) that will tell us how many elements to skip.

Algorithm S and its optimizations are for sequential sampling where N is known.  But sometimes N is not known or it's prohibitive to determine N.  Then we turn to reservoir samping. 

Algorithm R

There is a reservoir R of n sample elements.  The invariant is that the reservoir is a random sample of all the elements we've processed thus far.  To maintain the invariant, as we sequentially process each element generate an independent random variable between 0 and the current element.  Then either put the current element into the reservoir or ignore it.

Algorithms X, Y and Z

Optimization of algorithm R so we can skip over elements, much like Algorithms A-D.

 

Tries, John Mitchell, Memcache and Read-Only PHP Sessions

Too busy with work to blog lately, but here are some random thoughts I've been meaning to write about. 

Burst Tries

Several prominent (Google ranking) articles on implementing autocomplete suggest using a trie data structure.  Unfortunately, none of those articles point out how horribly space consuming tries are.  A naive, non-compacting trie structure is exponential in space.  With an a-z alphabet you have 26 exponent word length nodes.  That's a lot of nodes.  If you want the best of both worlds, the memory requirement of a binary search tree and the speed of a trie, try the burst trie.  Burst tries: A Fast, Efficient Data Structure for String Keys by Steffen Heinz, Justin Zobel and Hugh E. Williams.

John Mitchell

In my blog on F-Bounded Polymorphism I forgot to credit John Mitchell as one of the authors of F-Bounded Polymorphism for Object-Oriented Programming.  This was purely accidental and has nothing to do with the fact that he's a Stanford guy.

Memcached

Memcached is awesome.  Locks, CAS, is there anything it can't do?  PHP's support for memcached makes PHP just barely tolerable as a language.  The "M" in LAMP needs to be officially changed to Memcache, not MySQL.

PHP

What a mess of a language.  It has deviated too far from its original goals.  Really miss type safety, because, "after all, run time is a little late to find out whether you have a landing gear." (Eiffel dude)  Really miss all of Java's built in libraries.  I find it incredible that no one using PHP has had the need for a red-black tree, because I can't seem to find an implementation of one.  I do like PHP's request processing model better than Java's, though.  Adios threads, synchronized, volatile.   

Read Only Sessions

I find it really puzzling that PHP doesn't have a notion of read-only sessions.  Seems like this would be a no-brainer considering that PHP web apps are typically read dominant.  And you can't write your own quickly because there's no function to decode a session string, except to decode it and overwrite  the current session.  Someone did provide a function to decode the session string here, but I'm not sure if I fully trust it to decode everything correctly.

Think that's about it for now.

Pure Inefficiencies

Skimmed a paper titled "Pure versus Impure Lisp" by Nicholas Pippenger the other day.  Impure Lisp dialects allow mutations.  Pippenger wanted to know if pure Lisp, without mutation, was less "powerful".  Under two conditions he showed the following,  

A computation in impure Lisp upper bounded by O(n) is lower bounded in pure Lisp by big-omega n log n.  Basically, given the same problem there's a theoretical lower limit to pure Lisp's efficiency compared to impure Lisp. 

But then the guys at FP Lunch lead me to a follow-up paper titled "More Haste, Less Speed: Lazy Versus Eager Evaluation".  In it, Bird, Jone and de Moor showed that if you changed the pure Lisp evaluator to pure and lazy as oppose to Pippenger's original pure and eager then you can get the same linear time as the impure program.  Interestingly enough, the authors noted that lazy evaluation is often implemented with mutations behind the scenes (via memoization), so it's really a discussion of restricted mutation.  This is along the lines of an earlier posting I made about the problem with immutability and how compilers can, behind the scenes, solve some of the inefficiencies of immutability, but then it becomes a philosophical debate on what it really means to be immutable (or pure).

And that concludes another installment of interesting topics I'll never need to know.

Fail Fast, Debugging and Systems that Never Stop

If you're a Java guy you're probably familiar with the phrase "fail fucking fast" in the context of Iterators (I added the fucking part).  But fail fast is much more than just iterators, it's a general design principle--and a very important one at that. 

Jim Gray on fail fast: "it [the process] should either function correctly or it should detect the fault, signal failure and stop operating."  You can replace "the process" with component, class, etc.  Whatever you designate as your logical unit, the fail fast principle remains.  What you absolutely don't want to do is detect the fault, don't signal failure and continue.  This is why swallowing exceptions is one of my all time pet peeves.  Fail fast is often described in terms of fault detection latency, the time between initial error detection and the fault.  You want your latency to be small. 

There are two advantages to failing fast. First, easier debugging and analysis.  It complicates things greatly if your code detects errors but continues.  Eventually something will go wrong but now you can't easily track down the root cause.  I recently worked with a component (one that shall remain nameless) that doesn't follow the fail fast principle.  During initialization the component knew it was missing a configuration file but instead of halting it continued on.  When the component was finally invoked things obviously did not work, but the root cause was not obvious.  Ended up wasting two days tracking down the root cause, when it really should have taken 30 seconds. 

Second, ability to build "systems that never stop".  Failing fast is so important to building highly available systems that Joe Armstrong talks about it at great lengths in his presentation on "systems that never stop (and Erlang)."  In this presentation he presents 6 laws,

1. Isolation
2. Concurrency
3. Failure Detection
4. Fault Identification
5. Live Code Upgrade
6. Stable Storage

Without failure detection you can't fail fast, and if you can't fail fast you can't achieve isolation.  Real world example: Amazon S3's massive outage last year.  A huge embarrassment to Amazon's otherwise great cloud stack.  Their code didn't have adequate failure detection, allowing a single corrupt bit to propagate throughout the system.  The result was hours of downtime while engineers scrambled.  If Amazon had been able to detect the single corrupt bit then they could have isolated the failing component instead of letting the error bring down the entire system.

Few of us will be coding S3 like systems, but it doesn't mean we can't follow the fail fast approach.  It will make debugging easier and just might prevent similar embarrassments.  I think some programmers don't like to fail fast because they worry they'll be blamed for the failure, so just pretend things are good and pray nothing bad happens downstream.  I suppose it depends on how much you believe in God. 

WTF is F-Bounded Polymorphism

Here's an example of where I read random articles just because the title is very catchy: F-Bounded Polymorphism for Object-Oriented Programming by Peter Canning, William Cook, Walter Hill, Walter Olthoff and John Mitchell.  Polymorphism is already confusing enough.  Just look at the Wikipedia entry on type polymorphism: "this article may be confusing or unclear to readers".

There's parametric polymorphism, let-polymorphism, impredicative polymorphism, ad-hoc polymorphism, intensional polymorphism and subtype polymorphism.  So WTF is F-bounded polymorphism then.  If there's no Wikipedia entry does it really exist?  Despite no mention in Wikipedia F-bounded polymorphism is pretty important and I'm using it everyday without knowing it.

Lets start with "bounded quantification".  With bounded quantification you can do something like this

Moveable {
 Moveable move(int x, int y)
}

Moveable moveMeOneInch(Moveable m) {...}

The method moveMeOneInch takes in some a Moveable, moves it one inch, and returns a Moveable.  It is polymorphic and will work on Cars, Trains, Points--anything that's Moveable.  All good, except we'll have to do some unsafe type casting.

Car c = ...
Car movedCar = (Car) moveMeOneInch(c);

But with Java 5 we can do something like this

<T extends Moveable> T moveMeOneInch(T m) {...}

Car c = ...
Airplane p = ...

Car movedCar = moveMeOneInch(c);
Airplane movedAirplane = moveMeOneInch(p);

and get the type safety we want, because "run time is a little late to find out whether you have a landing gear".  What we've done is created an "F-bound".

F-Moveable[t] = { move : int, int -> t }
F-Moveable[Car] = { move : int, int -> Car }
F-Moveable[Airplane] = { move : int, int -> Airplane }

Note the type appears on both sides. 

Here's a real world example.  The Collections utility class has a max method that takes in a Collection of Comparables and return the max of the collection.

public static <T extends Object & Comparable<? super T>> 
 T max(Collection<? extends T> coll) {...}

//Integer implements Comparable<Integer>
Collection<Integer> ints = ...
Integer i = Collections.max(ints);

Here we bound the type of the collection and the type is part of the bound for Comparable.  A collection of integers, and integers are comparable to integers.

That's F-bounded polymorphism in a nutshell.  Now you can say, "yea, I like Java, it supports F-bounded polymorphism."

Scala, FUD and the PCP Drug

When something new comes along the established players often spread fear, uncertainty and doubt (FUD) in an attempt to remain dominant.  But what's the opposite of FUD?  I propose praise, certainty and perfection: PCP.  Every now and then something new comes along that so enamors early adopters they uncontrollably praise its merits, the certainty of its value and its utter perfection.  Like a drug, PCP is dangerous unless carefully supervised.

Take Scala, for example. There's so much PCP surround Scala I'm about to overdose.  DZone's top link for the last two days has been a blog titled Scala is my next choice.  It's a nice entry highlighting some of Scala's strengths but the author is too generous with some of the claims.  A quick read might well lead a programmer to conclude Scala will solve all of our programming problems.  Lets look at two claims.

Efficient

Scala is an efficient language, actually due to the latest benchmarks Scala is almost as fast as Java. The JVM implementation of Scala compiles down to bytecode, but during so, the code passes through optimization phaze. An optimization example is the tail recursion optimization, to help you stick to the functional paradigm without sacrificing the performance.

While the Scala compiler (which I praised here) does do tail recursion optimization it's very limited, a performance hack if you will.  The tail call has to be within a final method or local function (and has to be to itself, hence the recursive qualifier).  Rich Dougherty has a nice post on tail calls in Scala that goes into this further.  The fundamental issue is that unlike Scheme or Haskell there's no guarantee of tail calls in Scala because the JVM doesn't support tail calls. See John Rose's post here for further information on tail call support in the JVM and the difference between soft tail calls (the Scala hack) and hard tail calls. Bottom line: recursion in Scala will affect your performance.

Concurrency

Thus Scala suggests another concurrency model called Actors, where an actor sends and receives asynchronous messages in it’s inbox instead of sharing data. This is called: shared nothing model. Once you stop thinking about shared data, you relief yourself from the headache of thinking of code synchronization and deadlocks problems.

I'm not going to argue which concurrency model is better, but it's incorrect to say that you won't get deadlocks using Actors. See James Iry's post on deadlocks in Erlang, or see Charles Leiserson's discussion of deadlocks with MPI, another message based model used by the super computer guys.  Anytime there's a cycle in the dependencies you can get deadlocks, including when you're just passing messages around. Bottom line: Scala won't stop your deadlock problems.

I don't have anything against Scala but lets not make Scala out to be this magically language that will solve all our performance, scalability and concurrency problems.

Everything is a Function

I picked up Real World Haskell last week when Gilad Bracha warned me that I might become unemployable if I don't brush up on my functional programming skills.  I found his comment amusing because I have Lisp on my resume and have always wondered if anybody cared that I know Lisp.  Know is an exaggeration;  all I remember is cons, car, cdr and thinking why the f*** are there so many parentheses.  Yet here I am, a decade older, reading up on lambda-calculus and folding to remain marketable.

One thing that might confuse the imperative programmer when reading Haskell code for the first time is the unfamiliar function definitions.  In Java if you have an "add" method that adds two ints and returns an int you might write it as

add (int, int) : int

or

int add (int a, int b)

or

(int, int) -> int

In any case it's clear that add takes two ints and returns an int.  But in Haskell your add function will be

add :: Int -> Int -> Int

You might guess that the first int is the first argument, the second int is the second argument, and the final int the return type.  But not really.  In Haskell all functions are single argument functions.  Add is a function that takes an int, returns a function that takes an int, returns a function that evaluates to an int.  Here's an example with the map function. 

map abs [-1,-3,4,-12] 
[1,3,4,12]

:type map
map :: (a -> b) -> [a] -> [b]

It appears that the map function takes two arguments, a mapping function (in this case the abs function that returns the absolute value of a number) and a list, and applies the mapping function to each element of the list.  But as you can see in the type definition map is a function that takes a mapping function (a->b), returns a function that takes a list [a], returns a function that evaluates to a list [b]. 

This is because the lambda-calculus which Haskell is based upon doesn't have built-in support for multi-argument functions.  It'd be pretty easy to support multi-argument functions according to Benjamin Pierce, but to confuse us imperative programmers they decided it would be easier and better to use higher-order functions (functions that accept and/or return functions). Instead of f = λ(x,y).s we have f = λx.λy.s.  Then we would just write f v w and do two "reductions" instead of writing something like f(v,w). 

Converting multi-argument functions into higher-order functions is called "currying" after Haskell Curry, for whom the Haskell language is named.  Haskell was a contemporary of Alonzo Church, who developed the lambda-calculus during the 1920s.  While at Princeton Church supervised the doctoral thesis of Alan Turing, the tape machine guy, who committed suicide in 1954 after being prosecuted for his homosexuality.   (That was for all the history buffs out there.)

Once you see it a few times the notation becomes "normal".  It's actually very elegant (among other things).  Everything is a single argument function.  I mean everything.  You know how Smalltalk guys are always saying everything is an object, well the lambda ultimate guys say everything is a function, including numbers like 23 and 17.  Maybe that's what Java's missing, a pithy tag line.  Java, where everything is a....