Universal Frameworks for iOS

As of the time of this writing, Xcode does not offer a framework project to for Cocoa Touch (only Cocoa). Apple’s primary reasons behind this decision are security, performance, and memory footprint.  As such Xcode limits iOS developers to the Static Library project type. Static libraries are quite cumbersome to work with since we must make compile-time decisions when working with the iOS Simulator or an iOS device. The iOS simulator on Mac OS X uses the i386 architecture whereas the iOS devices use either armv6 or armv7.

Additionally, iOS 5 introduces a new compile-time memory management feature known as Automatic Reference Counting (ARC). The abridged version is you will never need to type retain or release again, which dramatically simplifies the development process while reducing crashes and memory leaks. The compiler has a complete understanding of your objects, and releases each object the instant it is no longer used, so apps execute much faster, with predictable, smooth performance. However, it’ll take the community some time to refactor various open source libraries to support ARC. Therefore, we have a much larger need today than ever before to move these source files into static libraries that are compiled with ARC disabled so we can compile our primary applications with ARC enabled.

Alternatively, if you are including files that don’t yet support ARC in a project that is ARC enabled, you can set the -fno-objc-arc compiler flag for each of these files. To do this in Xcode, go to your active target and select the “Build Phases” tab. In the “Compiler Flags” column, set -fno-objc-arc for each of the source files. Of course, this can be a very laborious process.

Apple defines a framework as a bundle (a structured directory) that contains a dynamic shared library along with associated resources, such as nib files, image files, and header files. When you develop an application, your project links to one or more frameworks. For example, iOS application projects link by default to the Foundation, UIKit, and Core Graphics frameworks. Your code accesses the capabilities of a framework through the application programming interface (API), which is published by the framework through its header files. Because the library is dynamically shared, multiple applications can access the framework code and resources simultaneously. The system loads the code and resources of a framework into memory, as needed, and shares the one copy of a resource among all applications. A universal (or multi-architecture) file is nothing more than an application bundle.

As I mentioned above, iOS does not support dynamic shared libraries but using lipo (a tool which comes with iOS SDK) we are able to merge several static libraries into a single static library. By using lipo, we are able to create a static library that supports all architectures (armv6, armv7, and i386) packaged as a universal framework. Here’s how.

Within Xcode, either create a new iOS project or open an existing iOS project. If you do decide to create a new project then feel free to choose any application template you prefer. Which one you choose is irrelevant. Add a “Cocoa Bundle” target (not Cocoa Touch Bundle). Select the newly created bundle target in the left navigation panel, select the “Build Settings” tab and modify the following settings as required:

  1. Architectures (ARCHS): Standard (armv6 armv7). In Xcode 4.2, use the value of $(ARCHS_STANDARD_32_BIT). If you wish to compile for older devices then add a new line with a value of armv6. Please see this Apple Developer forum post for more details.
  2. Base SDK (SDKROOT). Latest iOS (iOS X.X).
  3. Build Active Architecture Only (ONLY_ACTIVE_ARCH). No. This allows us to compile for armv6 and armv7.
  4. Valid Architecture (VALID_ARCHS): Standard (armv6 armv7). In Xcode 4.2, use the value of $(ARCHS_STANDARD_32_BIT). If you wish to compile for older devices then add a new line with a value of armv6.
  5. Dead Code Stripping (DEAD_CODE_STRIPPING): No
  6. Link With Standard Libraries (LINK_WITH_STANDARD_LIBRARIES): No
  7. Mach-O Type (MACH_O_TYPE): Relocatable Object File. This is the most important change. Here, we instruct the compiler to treat the Bundle as a relocatable file, by doing this, we can turn it into a framework with the wrapper setting.
  8. Wrapper Extension (WRAPPER_EXTENSION). framework. Here we change the Bundle to a Framework. To Xcode, frameworks is just a folder with the extension .framework, which has inside one or more compiled binary sources, resources and some folders, a folder, usually called Headers, contains all the public headers.
  9. Generate Debug Symbols (GCC_GENERATE_DEBUGGING_SYMBOLS): No.
  10. Generate Position-Dependent Code (GCC_DYNAMIC_NO_PIC): No
  11. Targeted Device Family (TARGETED_DEVICE_FAMILY). iPhone/iPad.

With the bundle target still in focus, select the “Info” tab and ensure the “Bundle OS Type code” is equal to FMWK. Add any source code and resources to the bundle. With the bundle target selected, click the “Build Phase” tab. At the bottom, press the “Add Phase” button and then “Add Copy Headers“. Open the newly created “Copy Headers” section and separate your public headers from private or project headers. Open the “Compile Source” section and add any .m, .c, .mm, .cpp and any other compilable source file. If your framework contains any non-compilable files such as images, sounds, and other resources, you can add them to the “Copy Bundle Resources” section. You can access any non-compilable resources by using NSBundle.

[[NSBundle mainBundle] pathForResource:@"MyFramework.framework/Resources/FileName" ofType:@"fileExtension"];

Next we’ll create a new Aggregate Target. As mentioned earlier, to join both architectures products into one, we must to use lipo. Add a new target by pressing the “Add Target” button. Under the Cocoa Touch section, select the “Other” subcategory and then choose the “Aggregate” target. The “Product Name” is arbitrary. Add a new “Run Script” phase under this newly created target. Copy and paste the following script into the “Run Script” phase.

# The framework name and version
X_FRAMEWORK_NAME=MyFramework
X_FRAMEWORK_VERSION=A

# This folder contains the final output of the framework.
X_INSTALL_DIR=${SRCROOT}/Products/${X_FRAMEWORK_NAME}.framework

# This working directory will be deleted after completion.
X_WORKING_DIR=build
X_DEVICE_DIR=${X_WORKING_DIR}/${CONFIGURATION}-iphoneos/${X_FRAMEWORK_NAME}.framework
X_SIMULATOR_DIR=${X_WORKING_DIR}/${CONFIGURATION}-iphonesimulator/${X_FRAMEWORK_NAME}.framework

echo "******************************************************"
echo "X_DEVICE_DIR = ${X_DEVICE_DIR}"
echo "X_SIMULATOR_DIR = ${X_SIMULATOR_DIR}"
echo "******************************************************"

# Build both simulator and device architectures.
xcodebuild clean
xcodebuild -configuration ${CONFIGURATION} -target "${X_FRAMEWORK_NAME}" -sdk iphoneos
xcodebuild -configuration ${CONFIGURATION} -target "${X_FRAMEWORK_NAME}" -sdk iphonesimulator

# Clean the oldest.
if [ -d "${X_INSTALL_DIR}" ]
then
rm -rf "${X_INSTALL_DIR}"
fi

# Recreate the folder structure for the final product binaries.
mkdir -p "${X_INSTALL_DIR}"
mkdir -p "${X_INSTALL_DIR}/Versions"
mkdir -p "${X_INSTALL_DIR}/Versions/${X_FRAMEWORK_VERSION}"
mkdir -p "${X_INSTALL_DIR}/Versions/${X_FRAMEWORK_VERSION}/Resources"
mkdir -p "${X_INSTALL_DIR}/Versions/${X_FRAMEWORK_VERSION}/Headers"

# Create the required symbolic links. Please note the paths MUST relative,
# otherwise the symbolic links will be invalid when the folder is copied/moved.
ln -s "${X_FRAMEWORK_VERSION}" "${X_INSTALL_DIR}/Versions/Current"
ln -s "Versions/Current/Headers" "${X_INSTALL_DIR}/Headers"
ln -s "Versions/Current/Resources" "${X_INSTALL_DIR}/Resources"
ln -s "Versions/Current/${X_FRAMEWORK_NAME}" "${X_INSTALL_DIR}/${X_FRAMEWORK_NAME}"

# Copy the headers and resources files to the final product folder.
cp -R "${X_DEVICE_DIR}/Headers/" "${X_INSTALL_DIR}/Versions/${X_FRAMEWORK_VERSION}/Headers/"
cp -R "${X_DEVICE_DIR}/" "${X_INSTALL_DIR}/Versions/${X_FRAMEWORK_VERSION}/Resources/"

# Remove artifacts from the resources folder.
rm -r "${X_INSTALL_DIR}/Versions/${X_FRAMEWORK_VERSION}/Resources/Headers" "${X_INSTALL_DIR}/Versions/${X_FRAMEWORK_VERSION}/Resources/${X_FRAMEWORK_NAME}"

# Use lipo to merge both binary files (i386 + armv6/armv7) into one universal files.
lipo -create "${X_DEVICE_DIR}/${X_FRAMEWORK_NAME}" "${X_SIMULATOR_DIR}/${X_FRAMEWORK_NAME}" -output "${X_INSTALL_DIR}/Versions/${X_FRAMEWORK_VERSION}/${X_FRAMEWORK_NAME}"

# Remove the working directory
rm -r "${X_WORKING_DIR}"

You’ll need to modify the first non-comment line in the script to be equal to the product name of your framework bundle target.

Now build the Aggregate target. It does not matter which architecture you select to build (iOS Device or Simulator) since the script creates a working folder, compiles the framework target twice (once for the iOS device and once for the iOS Simulator) and generates the output to a folder named “Products” located in the $(SRCROOT) root folder

If you previously upgraded from Xcode 3.x to 4.2, then your existing $(SYMROOT) value will very likely cause the above script to fail. The failure is caused because the script expects your $(SYMROOT) value to be set to the new Xcode 4 value of “build”, which refers to a relative path to $(SRCROOT). Unfortunately, you are not able to modify this setting in Xcode 4 due to an already reported bug. To work around this bug, close Xcode and simply delete the existing SYMROOT key and value from your com.apple.dt.Xcode.plist file, which is located in ~/Library/Preferences/.

Isn’t it about time for the WWDC to be here again?

Update Sequence Numbers

A colleague and I discussed the value in using a 64 bit Update Sequence Number (USN) versus a 128 bit USN. Here are my thoughts assuming 64-bits.

To provide a bit of context, we were considering a solution space that incremented the USN value for each write operation for a specific set of protected data. The USN is 64 bits, and is advanced for each update on a given server. At 100 writes per second, the USN will roll over in 58,494,241,735 years (approximately).

On a very busy server performing 10,000 writes per second it will roll over much sooner, in 584,942,417 years. Either way, the sun will burn out or go nova first, making USN’s moot (for this astronomical neighborhood anyway).

Just using 128 bits for USNs would give us a few more millennia breathing room. Now for the good news. In point of fact, since USN’s from different servers are never compared, all that is required is detecting rollover of the USN on a given server, for which algorithms are available. See RFC 1982 for a discussion.

The Apple in Everyone’s i

Steve Jobs

I thought it only appropriate to post Steve Job’s 2005 Stanford commencement address in lieu of his passing.

“I am honored to be with you today at your commencement from one of the finest universities in the world. I never graduated from college. Truth be told, this is the closest I’ve ever gotten to a college graduation. Today I want to tell you three stories from my life. That’s it. No big deal. Just three stories.

The first story is about connecting the dots.

I dropped out of Reed College after the first six months, but then stayed around as a drop-in for another 18 months or so before I really quit. So why did I drop out?

It started before I was born. My biological mother was a young, unwed college graduate student, and she decided to put me up for adoption. She felt very strongly that I should be adopted by college graduates, so everything was all set for me to be adopted at birth by a lawyer and his wife. Except that when I popped out they decided at the last minute that they really wanted a girl. So my parents, who were on a waiting list, got a call in the middle of the night asking: “We have an unexpected baby boy; do you want him?” They said: “Of course.” My biological mother later found out that my mother had never graduated from college and that my father had never graduated from high school. She refused to sign the final adoption papers. She only relented a few months later when my parents promised that I would someday go to college.

And 17 years later I did go to college. But I naively chose a college that was almost as expensive as Stanford, and all of my working-class parents’ savings were being spent on my college tuition. After six months, I couldn’t see the value in it. I had no idea what I wanted to do with my life and no idea how college was going to help me figure it out. And here I was spending all of the money my parents had saved their entire life. So I decided to drop out and trust that it would all work out okay. It was pretty scary at the time, but looking back it was one of the best decisions I ever made. The minute I dropped out I could stop taking the required classes that didn’t interest me, and begin dropping in on the ones that looked interesting.

It wasn’t all romantic. I didn’t have a dorm room, so I slept on the floor in friends’ rooms, I returned Coke bottles for the 5-cent deposits to buy food with, and I would walk the seven miles across town every Sunday night to get one good meal a week at the Hare Krishna temple. I loved it. And much of what I stumbled into by following my curiosity and intuition turned out to be priceless later on. Let me give you one example:

Reed College at that time offered perhaps the best calligraphy instruction in the country. Throughout the campus every poster, every label on every drawer, was beautifully hand calligraphed. Because I had dropped out and didn’t have to take the normal classes, I decided to take a calligraphy class to learn how to do this. I learned about serif and san serif typefaces, about varying the amount of space between different letter combinations, about what makes great typography great. It was beautiful, historical, artistically subtle in a way that science can’t capture, and I found it fascinating.

None of this had even a hope of any practical application in my life. But 10 years later, when we were designing the first Macintosh computer, it all came back to me. And we designed it all into the Mac. It was the first computer with beautiful typography. If I had never dropped in on that single course in college, the Mac would have never had multiple typefaces or proportionally spaced fonts. And since Windows just copied the Mac, its likely that no personal computer would have them. If I had never dropped out, I would have never dropped in on this calligraphy class, and personal computers might not have the wonderful typography that they do. Of course it was impossible to connect the dots looking forward when I was in college. But it was very, very clear looking backwards 10 years later.

Again, you can’t connect the dots looking forward; you can only connect them looking backwards. So you have to trust that the dots will somehow connect in your future. You have to trust in something–your gut, destiny, life, karma, whatever. This approach has never let me down, and it has made all the difference in my life.

My second story is about love and loss.

I was lucky–I found what I loved to do early in life. Woz and I started Apple in my parents garage when I was 20. We worked hard, and in 10 years Apple had grown from just the two of us in a garage into a $2 billion company with over 4000 employees. We had just released our finest creation–the Macintosh–a year earlier, and I had just turned 30. And then I got fired. How can you get fired from a company you started? Well, as Apple grew we hired someone who I thought was very talented to run the company with me, and for the first year or so things went well. But then our visions of the future began to diverge and eventually we had a falling out. When we did, our Board of Directors sided with him. So at 30, I was out. And very publicly out. What had been the focus of my entire adult life was gone, and it was devastating.

I really didn’t know what to do for a few months. I felt that I had let the previous generation of entrepreneurs down–that I had dropped the baton as it was being passed to me. I met with David Packard and Bob Noyce and tried to apologize for screwing up so badly. I was a very public failure, and I even thought about running away from the Valley. But something slowly began to dawn on me–I still loved what I did. The turn of events at Apple had not changed that one bit. I had been rejected, but I was still in love. And so I decided to start over.

I didn’t see it then, but it turned out that getting fired from Apple was the best thing that could have ever happened to me. The heaviness of being successful was replaced by the lightness of being a beginner again, less sure about everything. It freed me to enter one of the most creative periods of my life.

During the next five years, I started a company named NeXT, another company named Pixar, and fell in love with an amazing woman who would become my wife. Pixar went on to create the worlds first computer animated feature film, “Toy Story,” and is now the most successful animation studio in the world. In a remarkable turn of events, Apple bought NeXT, I returned to Apple, and the technology we developed at NeXT is at the heart of Apple’s current renaissance. And Laurene and I have a wonderful family together.

I’m pretty sure none of this would have happened if I hadn’t been fired from Apple. It was awful tasting medicine, but I guess the patient needed it. Sometimes life hits you in the head with a brick. Don’t lose faith. I’m convinced that the only thing that kept me going was that I loved what I did. You’ve got to find what you love. And that is as true for your work as it is for your lovers. Your work is going to fill a large part of your life, and the only way to be truly satisfied is to do what you believe is great work. And the only way to do great work is to love what you do. If you haven’t found it yet, keep looking. Don’t settle. As with all matters of the heart, you’ll know when you find it. And, like any great relationship, it just gets better and better as the years roll on. So keep looking until you find it. Don’t settle.

My third story is about death.

When I was 17, I read a quote that went something like: “If you live each day as if it was your last, someday you’ll most certainly be right.” It made an impression on me, and since then, for the past 33 years, I have looked in the mirror every morning and asked myself: “If today were the last day of my life, would I want to do what I am about to do today?” And whenever the answer has been “No” for too many days in a row, I know I need to change something.

Remembering that I’ll be dead soon is the most important tool I’ve ever encountered to help me make the big choices in life. Because almost everything–all external expectations, all pride, all fear of embarrassment or failure–these things just fall away in the face of death, leaving only what is truly important. Remembering that you are going to die is the best way I know to avoid the trap of thinking you have something to lose. You are already naked. There is no reason not to follow your heart.

About a year ago I was diagnosed with cancer. I had a scan at 7:30 in the morning, and it clearly showed a tumor on my pancreas. I didn’t even know what a pancreas was. The doctors told me this was almost certainly a type of cancer that is incurable, and that I should expect to live no longer than three to six months. My doctor advised me to go home and get my affairs in order, which is doctor’s code for prepare to die. It means to try to tell your kids everything you thought you’d have the next 10 years to tell them in just a few months. It means to make sure everything is buttoned up, so that it will be as easy as possible for your family. It means to say your goodbyes.

I lived with that diagnosis all day. Later that evening I had a biopsy, where they stuck an endoscope down my throat, through my stomach and into my intestines, put a needle into my pancreas and got a few cells from the tumor. I was sedated, but my wife, who was there, told me that when they viewed the cells under a microscope the doctors started crying, because it turned out to be a very rare form of pancreatic cancer that is curable with surgery. I had the surgery and I’m fine now.

This was the closest I’ve been to facing death, and I hope its the closest I get for a few more decades. Having lived through it, I can now say this to you with a bit more certainty than when death was a useful but purely intellectual concept:

No one wants to die. Even people who want to go to heaven don’t want to die to get there. And yet death is the destination we all share. No one has ever escaped it. And that is as it should be, because death is very likely the single best invention of Life. It is life’s change agent. It clears out the old to make way for the new. Right now the new is you, but someday not too long from now, you will gradually become the old and be cleared away. Sorry to be so dramatic, but it is quite true.

Your time is limited, so don’t waste it living someone else’s life. Don’t be trapped by dogma–which is living with the results of other people’s thinking. Don’t let the noise of others’ opinions drown out your own inner voice. And most important, have the courage to follow your heart and intuition. They somehow already know what you truly want to become. Everything else is secondary.

When I was young, there was an amazing publication called “The Whole Earth Catalog,” which was one of the bibles of my generation. It was created by a fellow named Stewart Brand not far from here in Menlo Park, and he brought it to life with his poetic touch. This was in the late 1960’s, before personal computers and desktop publishing, so it was all made with typewriters, scissors, and polaroid cameras. It was sort of like Google in paperback form, 35 years before Google came along: It was idealistic, and overflowing with neat tools and great notions.

Stewart and his team put out several issues of “The Whole Earth Catalog,” and then when it had run its course, they put out a final issue. It was the mid-1970s, and I was your age. On the back cover of their final issue was a photograph of an early morning country road, the kind you might find yourself hitchhiking on if you were so adventurous. Beneath it were the words: “Stay Hungry. Stay Foolish.” It was their farewell message as they signed off. Stay Hungry. Stay Foolish. And I have always wished that for myself. And now, as you graduate to begin anew, I wish that for you.

Stay Hungry. Stay Foolish.

Thank you all very much.”

You can watch the video here. Namaste.

Stop the line so the line never stops.

I recently read The Lean Startup and a corresponding interview by Chris Dixon (@cdixon) at CrunchBase with the author, Eric Ries (@ericries).  Ries tells Dixon one of the phrases Toyota uses on the production line is “stop the line so that the line never stops.” It means “if you want to be able to sustainably have high productivity you have to stop as soon as you have a quality problem and remove it because quality problems pile up and compound… eventually you can grind your whole development organization to a halt.”

One of the more interesting concepts (to me anyway) is the notion of continuous deployment, which is a natural extension of Continuous Integration. Continuously integrate (commit early and often). On commit automatically run all tests. If the tests pass deploy to the cluster. If the deploy succeeds, repeat.

The book is really quite eye-opening and offers a different way of thinking about not only the process of software engineering (by noting a slightly modified version of the Agile development methodology) but the impact of a change to revenue by ignoring vanity metrics.

I highly recommend this book for anyone who wants to create something new.

Efficient Memory Usage in iOS

I wrote a post some time back on the value of singletons in a garbage collected language as an important component of scalability. The majority of my work these days targets Apple iOS devices and so a reduced memory footprint and overall memory management is not only fundamental but paramount. The use of singleton objects and an effective caching strategy are simple patterns to get you started.

I suggest reading Apple’s Thread Programming Guide as a prerequisite, which also covers some of the basic concepts behind Blocks and Grand Central Dispatch (GCD).

Singletons

For purposes of this discussion, a singleton is a class that only allows a single instance of itself to be created within an operating system process.

Apple’s documentation on creating a singleton recommends a pattern that works for most iOS applications but is not thread-safe. Beginning with iOS 2.0 and prior to iOS 4.1, one of the most widely used methods to introduce a thread-safe singleton was through the use of the @synchronized directive.

+ (MyClass*) instance {
    static MyClass *gInstance = nil;
    @synchronized(self) {
        if(nil == gInstance) {
            gInstance = [[MyClass alloc] init];
        }
    }
    return (gInstance);
}

There are a few inefficiencies with this approach because not only generates a recursive mutex lock but also introduces an exception handler. Specifically, Apple’s documentation indicates that as a precautionary measure, the @synchronized block implicitly adds an exception handler to the protected code. This handler automatically releases the mutex in the event that an exception is thrown. This means that in order to use the @synchronized directive, you must also enable Objective-C exception handling in your code. If you do not want the additional overhead caused by the implicit exception handler, you should consider using the lock classes.

At the time of this writing, the @synchronized directive turns into this basic pseudo-code:

id _eval_once = ;
objc_sync_enter( _eval_once );
@try {
    /* code goes here */
}
@finally {
    objc_sync_exit( _eval_once );
}

For implementation details see: http://www.opensource.apple.com/source/objc4/objc4-437.1/runtime/objc-sync.m

Much of Apple’s sample code prior to iOS 4.0 use this approach. There is a technically more efficient and lock-free approach for applications that target operating systems earlier than Mac OS X version 10.5 or iOS 4.0.

+ (MyClass*) gInstance {
    static void * volatile gInstance = nil;
    while (!gInstance) {
        MyClass *temp = [MyClass [alloc] init];
        if(!OSAtomicCompareAndSwapPtrBarrier(0x0, temp, &gInstance)) {
            [temp release];
        }
    }
    return (gInstance);
}

You can read more about preferred versions of the atomic and synchronization operations here.

For applications that target operating systems equal to or greater than Mac OS X 10.6 or iOS 4.0, the recommended singleton pattern uses dispatch_once, which relies on components of Grand Central Dispatch (GCD).

+ (MyClass *) instance {
    static MyClass* gInstance = nil;
    static dispatch_once_t pred;

    dispatch_once(&pred, ^{
        gInstance = [[MyClass alloc] init];
    });
    return (gInstance);
}

It should go without saying but I’ll do so for completeness. All instance-level methods of classes that implement a singleton pattern MUST be thread-safe.

NSCache

I suspect this class remains relatively unused by most iOS developers. NSCache is essentially a container that it stores key-value pairs but unfortunately does so without an O(1) time complexity (like that of NSMutableDictionary) but does automatically evicts objects from its store when the ‘cost’ (a heuristic that of course involves memory pressure) of the cache rises above a configurable threshold.

Per Apple’s documentation, NSCache objects differ from other mutable collections in a few ways:

  • The NSCache class incorporates various auto-removal policies, which ensure that it does not use too much of the system’s memory. The system automatically carries out these policies if memory is needed by other applications. When invoked, these policies remove some items from the cache, minimizing its memory footprint.
  • You can add, remove, and query items in the cache from different threads without having to lock the cache yourself.
  • Retrieving something from an NSCache object returns an autoreleased result.
  • Unlike an NSMutableDictionary object, a cache does not copy the key objects that are put into it.These features are necessary for the NSCache class, as the cache may decide to automatically mutate itself asynchronously behind the scenes if it is called to free up memory.

Though not required, NSCache works in conjunction with objects that implement the NSDiscardableContent protocol in that the discardContentIfPossible method is called when an object is removed.

The two most widely used caching strategies are proactive and reactive loading.

  1. Proactive Cache Loading. A proactive cache loading strategy attempts to retrieve all required state when a process or application starts and cache it for the lifetime of the process or application. A decision to use a proactive cache loading strategy is generally done so in conjunction with either asynchronous pull loading based on expected not actual usage of the information being cached or notification-based loading whereby an application’s services are notified when cached state changes.
  2. Reactive Cache Loading. A reactive cache loading strategy retrieves data as it is requested by the application and caches it for future requests. A decision to use a reactive cache loading strategy is generally done so in conjunction with synchronous pull loading since the pattern is relatively easy to test and implement.

Regardless of the selected caching strategy, determining a cache expiration policy is is key for most applications. There are a plethora of expiration policy patterns but the majority of them fall into the following general categories:

  • Time-based. Cached information is invalidated based on relative (sliding window) or absolute time periods.
  • Notification-based. Cached information is invalidated based on instructions from a source.
  • Counter-based. Cached information is invalidated based on a reference counts.

Respective of the expiration policy, scavenging based on memory pressure and other heuristics are key to a proper cache design and symmetry of that design is a key component in any distributed algorithm.

For most applications, a reactive cache loading strategy with a synchronous pull model is the most appropriate option. NSCache does evict objects based on memory pressure and so I strongly recommend you implement the NSDiscardableContent protocol for any objects you plan to store in NSCache. NSDiscardableContent is a simple counter-based pattern. For information stored in NSCache that represents NSData objects, Apple provides the NSPurgeableData class. NSPurgeable data inherits from NSMutableData and is available in iOS 4.0 and Mac OS X 10.6 and later. A description of how to use this class can be found be reading Caching and Purgeable Memory.

I’d like to make one last point. Please be careful not to over-engineer your caching strategy but be elegant about your design.

Apple WWDC 2011

I’ve attended the Apple WWDC for the past 4 years and it’s been nothing short of exciting each year. This year, event sold out in 10 hours and so I am fortunate to have a spot. In contrast to last year, the event sold out in approxiately 14 days. Steve Jobs delivered a very interesting keynote speech with features that in my opinion ensure Apple will continue to stay a few years ahead of all other mobile companies. It’s amazing to think how far we’ve come since my first 4 Macs, which were the Apple II, IIc, IIe, and IIGS. Ahhh…and let us not forget other microcomputers such as the Amiga, Commodore 64, and the earlier TRS-80 (also known as the “trash 80″).  The TRS-80 was in fact technically my first personal computer.

Here are a few very interesting statistics:

  • There are over 225 million iOS devices worldwide.
  • Apple represents a 48% share of the tablet and mobile market.
  • 25 million iPads have been sold to date.
  • There are 425,000 applications in the App Store with 90,000 of those applications specifically designed to run on the iPad.
  • The App Store has enjoyed over 14 billion downloads
  • Apple has 225 million credit card accounts.
  • Apple has shipped 54 million Macs and growing, which is a 28% growth over last year. To contrast this, PC growth is at a negative 1% growth over the same year.
  • 73% of the Macs shipped today are notebooks

These statistics are astounding.  I am of course not at liberty to discuss any information not made public by Apple regarding the upcoming technologies but it is sufficed to say Mac OS X Lion + iCloud + iOS 5 represents another leap in market share for Apple and a set of very useful features for consumers.

A Word on Elegance

What do I mean by elegance? Most software engineers equate elegance to efficiency. Still some equate elegance to robustness. Others choose correctness. All are variables in the equation of elegance. Many other variables exist and all are important.

Make no mistake, software is art. Some artists prefer oil on canvas as their medium. Others choose water color. As software design engineers (SDEs), we have chosen 1s and 0s to communicate our creative visions. Elegance must exist at each step in the engineering process and not only as an afterthought in the development phase. Elegance is the responsibility of each and every participant with accountability functioning as the enforcement point. Without accountability, chaos reigns. Accountability starts within.

Many software engineers find themselves searching for or memorizing patterns that “work” to shortly find themselves bulimically spewing the results onto their canvas. What happened to the elegance of originality? It’s far too easy to become a GP (“Google programmer”). Why? Because creativity and originality aren’t as convenient as letting others do the work, which leads to chaos and hard-to-maintain code; especially, when you’re not the original developer.

Stay with me; we’re only scratching the surface. Do you remember the last time you really evaluated the usability of your consumer API surface? Did your evaluation begin in the design phase? Start with a high-level view of the scenarios. Then oscillate between architectural design and the scenario-based consumer API surface. Do not think about technical design until you’re satisfied with the consumer API surface and the architectural design. Keep in mind; it’s certainly acceptable to refactor your architectural design and consumer API based on the technical design.

An apparent and even larger obstacle I’ve noticed lately is the inability for an SDE to make the jump from procedure (function)-oriented design concepts to that of object-oriented design while keeping an eye to efficiency in terms computational complexity and network round-trips. The devil is in the details. In my opinion, one can’t be an effective architect without being an even more effective SDE; period. The implementation details do change the architecture.

In general, people tend to migrate toward what makes them feel good. Rework doesn’t feel good; no one enjoys it. But, if that was true—if you truly don’t enjoy rework—then why would you not elegantly architect, design, and develop your code initially? Why do you make more work for yourself? Elegance as a foundational element is difficult. More often than not, SDEs take the easy way out because they equate efficiency to speed of completion. I’m not advocating “analysis paralysis” but instead a balanced design. Deadlines must be met. Deadlines should not be met at the expense of elegance.

It’s your canvas.

Fabric of a Distributed System

” It has been said that art is a collaboration between God and the artist, which works best when the artist contributes as little as possible; so too with designing distributed systems ” –Unknown 

Try to image the strategic direction of distributed computing frameworks. Just for a moment transition into a state where you think of nothing and yet listen to everything. What key technologies (disruptive or otherwise) have we experienced over recent years? 

Notion of Autonomous Computing

Arguably, one of the most well known papers on the subject of autonomic computing to be recently released is titled “Autonomic Computing: IBM’s Perspective on the State of Information Technology” [URI]; authored by Paul Horn, Senior Vice President of IBM Research. As outlined by Dr. Horn’s manifest, there are many challenges we face over the next decade within Information Technology. 

Within the autonomic landscape, each system node must satisfy the following criteria:

  • self-identification, self-knowing 
  • self-(re)configuration 
  • self-recovery (from perturbations) 
  • self-protection (security) 
  • self-learning (including from errors) 
  • self-regulating (to open standards) 
  • self-resource-allocation

Notion of Grid Computing

Wouldn’t it be nice to economically provide a highly available and fault tolerant system that can support an annual uptime guarantee of 99.999 percent—which equates to 5.256 minutes of annual unscheduled downtime—and that scales up by a factor of 106? That is, an application’s storage and processing capacity can automatically grow by a factor of a million, doing jobs faster (106x speed up) or doing 106 larger jobs in the same time (106x scale up), just by adding more resources. Stay focused.

The concept of Grid (or Utility) computing was coined in the mid 1990s and is best defined—to quote The Anatomy of the Grid—the real and specific problem that underlies the Grid concept is coordinated resource sharing and problem solving in dynamic, multi-institutional virtual organizations. 

The Grid Global Forum (GGF) has made great headway; so has OGSA (Open Grid Services Architecture). Message Passing Interface (MPI) is widely accepted. Microsoft entered the HPC game with the Microsoft Compute Cluster Server, which I installed many months ago and is now consuming most of my free time. 

Notion of Adaptive Autonomous Agents

An agent is a system that tries to fulfill a set of goals of goals in a complex, dynamic environment. An agent it situated in the environment; it can sense the environment through its sensors and act upon the environment using its actuators. An agent’s goal can take many different forms: they can be “end goals”, or particular states the agent tries to achieve; they can be selective reinforcement or reward that the agent attempts to maximize; they can be internal needs or motivations that the agent has to keep within certain viability zones and so on. An agent is called autonomous if it operates completely autonomously, i.e. if it decides itself how to relate its sensor data to motor commands in such a way that its goals are attended to successfully. An agent it said to be adaptive, if it is able to improve over time, i.e. if the agent becomes better at achieving its goals with experience. 

The study of Adaptive Autonomous Agents is grounded in two important insights, which serve as “guiding principles” for most of the current research performed:

  • Looking at complete systems changes the problems often in a favorable way. 
  • Interaction dynamics can lead to emergent complexity.

Essentially, an agent is viewed as a set of competence modules (often called behaviors). These modules are responsible for a particular small task-oriented competence. Each of the modules is directly connected to its relevant sensors and actuators. Modules interface to one another via extremely simple messages rather than a common representation of beliefs, and so on. The communication between modules is almost never of a “broadcast” nature, but happens rather on a point-to-point (or one-to-one) bases. Typically, the messages consist of activation energy, or simple suppression and inhibition signals, or simple tokens in a restricted language. In addition to communication via simple messages, modules also communicate “via the environment”. One module may change some aspect of the environment, which will trigger another module, etc.

Notion of the Semantic Web

Simply put, the Semantic Web is the representation of data on the web in which information is given well-defined meaning—“to be a universal medium for the exchange of data”. 

The principal technologies of the Semantic Web fit into a set of layered specifications called the Resource Description Framework (RDF). The current components of that framework are the RDF Core Model, the RDF Vocabulary Description Language and the Web Ontology Language, which all build on the foundation of URIs, XML, and XML namespaces.

The most interesting of these languages is the Web Ontology Language (OWL), which is a descriptive layer built on top of RDF used to model classes, properties, and objects. 

Ontology is also a term borrowed from philosophy that refers to the science of describing the kinds of entities in the world and how they are related. Stated another way, an ontology defines the terms used to describe and represent an area of knowledge.

Notion of Service Oriented Architectures (SOA)

I think everyone has been beaten of the head with the “SOA stick”, which is why you won’t feel a thing; keep reading.

In computing, the term Service-Oriented Architecture (SOA) expresses a software architectural concept that defines the use of services to support the requirements of software users. In a SOA environment, nodes on a network make resources available to other participants in the network as independent services that the participants access in a standardized way. Most definitions of SOA identify the use of Web services (i.e. using SOAP or REST) in its implementation. Here and here are two links worth reading. However, one can implement SOA using any service-based technology.  

The WS* specifications have gained wide adoption but other advances are needed.

One last point as related to service orientation; I caution everyone to not forget about the elegance in design of class libraries as they are the underpinnings of every SOA. Design for the in-process consumer first with an eye to areas of the API surface that might benefit from hosting within an SOA.

Other advances…

There are many others such as advances in peer-to-peer algorithms, discrete-event simulation and the event horizon, social networking, recovery-oriented systems, storage and machine virtualization, bioinformatics, biotechnology, and quantum computing to name but a few. In my mind, the two most important questions to answer are which of these variables are of significant weighting in the equation of strategic direction and which are “noise”?  I certainly have my opinion…but then again, you know what those are like.

Most readers and programmers have little patience to read discussions of this length. However, the length (at least to me) seems disproportionate to the importance of the topic. There is so much more to say and even more to ponder. But, before you run off to save the world let me leave you with one additional thought:

“The map is not the territory.”
Alfred Korzybsky
Science and Sanity, 1933


Google’s BigTable Design

I periodically prune and clean several key folders on my hard drive and in doing so this morning ran into notes (I’m not sure from whom) taken from a talk given by Jeff Dean at the University of Washington on Google’s BigTable design. The following notes and the PDF published by Google on their BigTable design are very interesting.

Today Jeff Dean gave a talk at the University of Washington about BigTable – their system for storing large amounts of data in a semi-structured manner. I was unable to find much info about BitTable on the internet, so I decided to take notes and write about it myself.

First an overview. BigTable has been in development since early 2004 and has been in active use for about eight months (about February 2005). There are currently around 100 cells for services such as Print, Search History, Maps, and Orkut. Following Google’s philosophy, BigTable was an in-house development designed to run on commodity hardware. BigTable allows Google to have a very small incremental cost for new services and expanded computing power (they don’t have to buy a license for every machine, for example). BigTable is built atop their other services, specifically GFS, Scheduler, Lock Service, and MapReduce.

Each table is a multi-dimensional sparse map. The table consists of rows and columns, and each cell has a time version. There can be multiple copies of each cell with different times, so they can keep track of changes over time. In his examples, the rows were URLs and the columns had names such as “contents:” (which would store the file data) or “language:” (which would contain a string such as “EN”).

In order to make each manage the huge tables, the tables are split at row boundaries and saved as tablets. Tablets are each around 100-200 MB and each machine stores about 100 of them (they are stored in GFS). This setup allows fine grain load balancing (if one tablet is receiving lots of queries, it can shed other tablets or move the busy tablet to another machine) and fast rebuilding (when a machine goes down, other machines take one tablet from the downed machine, so 100 machines get new tablet, but the load on each machine to pick up the new tablet is fairly small).

Tablets are stored on systems as immutable SSTables and a tail of logs (one log per machine). When system memory is filled, it compacts some tablets. He went kind of fast through this, so I didn’t have time to write everything down, but here is the overview: There are minor and major compactions. Minor compactions involve only a few tablets, while major ones involve the whole system. Major compactions can reclaim hard disk space. The location of the tablets are actually
stored in special BigTable cells. The lookup is a three-level system. The clients get a pointer to the META0 tablet (there is only one). This tablet is heavily used, and so one machine usually ends up shedding all its other tablets to support the load. The META0 tablet keeps track of all the META1 tablets. These tables contain the location of the actual tablet being looked up. There is no big bottleneck in the system, because they make heavy use of pre-fetching and caching.

Back to columns. Columns are in the form of “family:optional_qualifier”. In his example, the row “www.cnn.com” might have the columns “contents:” with the HTML of the page, “anchor:cnn.com/news” with the anchor text of that link (“CNN Homepage”), and  “anchor:stanford.edu/” with that anchor text (“CNN”). Columns have type information. Columns families can have attributes/rules that apply to their cells, such as “keep n time entries” or “keep entries less than n days old”. When tablets are rebuilt, these rules are applied to get rid of any expired entries. Because of the design of the system, columns are easy to create (and are created implicitly), while column families are heavy to create (since you specify things like type and attributes). In order to optimize access, column families can be split into locality groups.

Locality groups cause the columns to be split into different SSTables (or tablets?). This increases performance because small, frequently accessed columns can be stored in a different spot than the large, infrequent columns.

All the tablets on one machine share a log; otherwise, one million tablets in a cluster would result in way too many files opened for writing (there seems to be a discrepancy here, he said 100 tablets per machine and 1000 machines, but that doesn’t equal one million tablets). New log chunks are created every so often (like 64 MB, which would correspond with the size of GFS chunks). When a machine goes down, the master redistributes its log chunks to other machines to process (and these machines store the processed results locally). The machines that pick up the tablets then query the master for the location of the processed results (to update their recently acquired tablet) and then go directly to the machine for their data.

There is a lot of redundant data in their system (especially through time), so they make heavy use of compression. He went kind of fast and I only followed part of it, so I’m just going to give an overview. Their compression looks for similar values along the rows, columns, and times. They use variations of BMDiff and Zippy. BMDiff gives them high write speeds (~100MB/s) and even faster read speeds (~1000MB/s). Zippy is similar to LZW. It doesn’t compresses as highly as LZW or gzip, but it is much faster. He gave an example of a web crawl they compressed with the system. The crawl contained 2.1B pages and the rows were named in the following form: “com.cnn.www/index.html:http”. The size of the uncompressed web pages was 45.1 TB and the compressed size was 4.2 TB, yielding a compressed size of only 9.2%. The links data compressed to 13.9% and the anchors data compressed to 12.7% the original size.

They have their eye on the future with some features under consideration.

1. Expressive data manipulation, including having scripts sent to clients to modify data.
2. Multi-row transaction support.
3. General performance for larger cells.
4. BigTable as a service. It sounds like each service (such as Maps or Search History) have their own cluster running BigTable. They are considering running a Google-wide BigTable system, but that would require fairly splitting resources and compute time, etc.

The talk was very interesting and it contained lots new information I had never heard before (I haven’t seen a BigTable paper yet). This information is accurate to the best of my knowledge, but if you see a mistake, please e-mail me. I wonder what the next Google talk will be about… I can’t wait.

The use of a Bloom filter in their design is quite an interesting application in place of a more traditional Distributed Hash Table (DHT) approach used in P2P implementations.

MethodImplOptions.Synchronized

Recent discussions with colleagues regarding use of MethodImplOptions.Synchronized prompted me to discuss its implications.

Let’s begin with formal documentation. The MethodImplOptions.Synchronized option “specifies that the method can be executed by only one thread at a time. Static methods lock on the type, while instance methods lock on the instance. Only one thread can execute in any of the instance functions and only one thread can execute in any of a class’s static functions”.

I’d like to focus on the statement “static methods lock on the type”. Microsoft strongly discourages locking on any public types, or on instances you do not control. This means the common constructs lock(this), lock(typeof(SomeType)), and lock(“myLock”) violate this guideline. If you’re not yet familiar with the reason behind this guideline then please read Joe Duffy’s blog entry titled “Rude unloads and orphaned locks“. To provide additional support for Joe’s comments, the formal documentation for MethodImplOptions states “Locking on the instance or on the type, as with the Synchronized flag, is not recommended for public types because code other than your own can take locks on public types and instances. This might cause deadlocks or other synchronization problems.”

To be explicit, the lock(typeof(MyClass)) semantic is exactly what MethodImplOptions.Synchronized implements when adorned on static methods . The lock in this case is across all AppDomains in the same operating system process. Consider the following code, which if executed from multiple AppDomains would result in a conflict.

ManualResetEvent e1= new ManualResetEvent(false);
lock (typeof(object))
{
    AppDomain domain = AppDomain.CreateDomain("MyDomain");
    domain.DoCallBack(delegate
    {
        ThreadPool.QueueUserWorkItem(delegate
        {
            ManualResetEvent e2= new ManualResetEvent(false);
            lock (typeof(object))
            {
                e2.Set();
            }
        });
    });

    e1.WaitOne();
}

As a result, you should shy away from using MethodImplOptions.Synchronized for the same reasons you wouldn’t use lock(this) or lock(typeof(SomeClass)).

Additionally, the MethodImplOptions.Synchronized option favors neither readers nor writers. Use of a low-locking technique such as a spinlock or the intrinsic ReaderWriterLockSlim and Monitor classes will perform and scale much better on both single-core and multi-core (CPU) hardware.

The above points are important for several reasons:

  1. The scope of a lock is very relevant if a goal of your code is reuse. As a framework writer is it your responsibility to ensure consumers writing applications with differing scalability thresholds and concurrency rates are equally favored; the solution should either work for all consumers or offer options for each category of consumer.
  2. If you’re writing code that is to be used in systems where efficient use of system resources (CPU and memory) is paramount then it is your responsibility to provide an implementation that meets this fundamental goal.
  3. If you’re executing under the Microsoft SQL Server CLR host and your code takes too long to execute then SQL will force an AppDomain unload, which means (as a specific example), that a finally block wishing to execute Monitor.Exit won’t even be run. As Joe indicates, until you’ve created 4,294,967,295 threads such that the Thread IDs wrap around and the old ID gets assigned to a new thread, and that thread spuriously decides to Exit the Monitor without acquiring it first, your system is going to be locked up for a bit. In other words, deadlocked.
  4. The MethodImplAttribute can only be used to adorn (you guessed it) methods.

So how much of a difference can a low-locking technique really make? That obviously depends on the technique. I wrote a parallelized program (using the Microsoft Parallel Extensions for .NET 3.5) that tests synchronization using MethodImplOptions.Synchronized, Monitor, Interlocked, ReaderWriterLockSlim, and a spin-lock. For those interested, I’ve included my spin-lock implementation to the bottom of this article.

Result Set 1: Write-only access:

  • Monitor executed 10,000,000 iterations in 13,372,540 (ticks), which is 747 iterations per tick.
  • Interlocked executed 10,000,000 iterations in 18,767,746 (ticks), which is 532 iterations per tick.
  • ReaderWriterLockSlim executed 10,000,000 iterations in 18,908,171 (ticks), which is 528 iterations per tick.
  • MethodImpl executed 10,000,000 iterations in 22,724,176 (ticks), which is 440 iterations per tick.
  • SpinLock executed 10,000,000 iterations in 17,713,122 (ticks), which is 564 iterations per tick.

Result Set 2: Read/write access with an equal read and write frequency:

  • Monitor executed 10,000,000 iterations in 23,701,864 (ticks), which is 421 executions iterations per tick.
  • Interlocked executed 10,000,000 iterations in 19,864,150 (ticks), which is 503 iterations per tick.
  • ReaderWriterLockSlim executed 10,000,000 iterations in 33,751,562 (ticks), which is 296 iterations per tick.
  • MethodImpl executed 10,000,000 iterations in 43,442,379 (ticks), which is 230 iterations per tick.
  • SpinLock executed 10,000,000 iterations in 20,713,905 (ticks), which is 482 iterations per tick.

Result Sets 3: Read-only access:

  • Monitor executed 10,000,000 iterations in 13,810,171 (ticks), which is 724 iterations per tick.
  • Interlocked executed 10,000,000 iterations in 17,628,526 (ticks), which is 567 iterations per tick.
  • ReaderWriterLockSlim executed 10,000,000 iterations in 20,326,949 (ticks), which is 491 iterations per tick.
  • MethodImpl executed 10,000,000 iterations in 34,891,919 (ticks), which is 286 iterations per tick.
  • SpinLock executed 10,000,000 iterations in 7,046,085 (ticks), which is 1,419 iterations per tick.

The results are not surprising. Use of the MethodImplOptions.Synchronized option on static methods resulted in a lower concurrency rate. If you require thread synchronization for static methods then I strongly recommend you consider an alternate synchronization technique.

The full source code is attached to this blog entry.

SpinLock.zip