RSS 1.0 XML Feed available

Date: 27-Feb-2015/11:52:58-5:00

Tags: c++, open source

Characters: you, me

A Weighty Proposition

$ sudo apt-get install git-core g++ libbz2-dev \
   liblzma-dev libcrypto++-dev libpqxx3-dev scons libicu-dev \
   strace emacs ccache make gdb time automake libtool autoconf \
   bash-completion google-perftools libgoogle-perftools-dev \
   valgrind libACE-dev gfortran linux-tools uuid-dev liblapack-dev \
   libblas-dev libevent-dev flex bison pkg-config python-dev \
   python-numpy python-numpy-dev python-matplotlib libcppunit-dev \
   python-setuptools ant openjdk-7-jdk doxygen \
   libfreetype6-dev libpng-dev python-tk tk-dev python-virtualenv \
   sshfs rake ipmitool mm-common libsigc++-2.0-dev \
   libcairo2-dev libcairomm-1.0-dev

$ sudo apt-get install linux-tools-generic libbz2-dev python-dev scons\
   libtool liblzma-dev libblas-dev make automake \
   ccache ant openjdk-7-jdk libcppunit-dev doxygen \
   libcrypto++-dev libACE-dev gfortran liblapack-dev \
   liblzma-dev libevent-dev libssh2-1-dev libicu-dev \
   g++ google-perftools libgoogle-perftools-dev \
   zlib1g-dev git pkg-config valgrind autoconf

"...Wait, So...What's Going on Here?"

At the present moment, RTBkit is designed to be productive for developers to work on. In particular, we made the conscious choice to require a very specific environment so that we would not need to support all of the effort to port to other architectures and operating systems (and especially to maintain these ports), and we could control the versions of all of the supporting libraries we use (hence platform-deps). This was our way out of dependency hell and #ifdef hell, into which we have already fallen several times.

Secondly we tend to deploy RTBkit as part of a larger product and include it as a submodule under a larger source tree rather than by installing it on the system. This allows us to have a cohesive build over RTBkit and the code it depends upon, and makes it much faster for us to develop it. RTBkit by itself is not terribly useful (although it is getting more so); you need to integrate it with other code to make it do something worthwhile and develop that system as a whole.

boost/      libssh2.h              urcu/            utilspp/
citycrc.h   libssh2_publickey.h    urcu-bp.h        zmq.h
city.h      libssh2_sftp.h         urcu-call-rcu.h  zmq_utils.h
curl/       snappy-c.h             urcu-defer.h     zookeeper/
curlpp/     snappy.h               urcu.h
google/     snappy-sinksource.h    urcu-pointer.h
hiredis/    snappy-stubs-public.h  urcu-qsbr.h

What's RTB, and Why Would Someone Want a Kit For It?

{"!!CV":"0.1","exchange":"dblclk_adx","id":"1497db9a-24a5-4001-15e8-deff04002930",
"ipAddress":"76.209.61.239","language":"en","location":{"cityName":"Elgin",
"countryCode":"US","dma":602,"postalCode":"847","regionCode":"IL"},
"protocolVersion":"0.2","provider":"rtbkit","restrictions":{"clickUrl":
["buzznet.com","mog.com","napster.com","nevadaskideals.com","rhapsody.com",
"tunecore.com"],"creativeAttribute":[3,4,5,6,22]},"segments":{"adxVerticals":[
[220,0.3995213210582733],[529,0.4392172992229462],[592,0.1612613946199417]]},
"spots":[{"formats":["300x250"],"id":"1","position":"NONE","reservePrice":0}],
"timestamp":1307476542.329969,"url":"http://www.playlist.com/","userAgent":
"Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1; Trident/4.0;
Media Center PC 3.0; .NET CLR 1.0.3705; .NET CLR 1.1.4322; AskTbFWV5/5.12.2.16749),
gzip(gfe),gzip(gfe)"}

Ad-Bidding Server...or Ad-Bidding Client?

First, the Toolchain

Third-Party Libraries inside the RTBkit Source

• jsoncpp -- As mentioned, the OpenRTB standard suggests using JSON. And even though Google uses protocol buffers in the bidding, you'd still need JSON for logging.
• tinyxml2 -- XML is used in service connections to Amazon's S3, SQS, and AWS...a layer provided presumably for the ad serving functions. Cursory inspection suggests these services probably offer JSON interfaces now for the same operations. Perhaps it was not always so.
• utf8cpp -- The C++ std::string datatype is lamentably not very different from a std::vector of char. It's actually kind of worse, because a mutable string's .data() method gives you a const char * instead of a plain char *. So if one wants to know something as simple as the number of "actual character codepoints" in an encoded UTF8 string, you're going to need something else.
  RTBkit wraps this tiny library in a custom string class called Datacratic::Utf8String, and wraps the C++11 std::u32string into a class that can be converted to it called Datacratic::Utf32String. Additional conversion methods go between them.
  It's a reasonable solution that doesn't require the full heft of the International Components of Unicode. However, the ICU components wind up installed as a dependency anyway. So it's a slight redundancy.
• leveldb -- I'd heard of this but never installed it. It's a Key-Value store similar to Google's closed-source BigTable they've given presentations on, but it doesn't share any of the dependencies. So they could open-source it with minimal dependencies.
  It is used in what is called the "Post-Auction Loop". It helps with "simple event matching" in order that after an ad has been shown, to track and report "wins, impressions, clicks, and conversions". An auctionId and spotId are hashed to form a key, and the value is presumably the cumulative interesting data about that event.
• "googleurl" is included, which was once known as "The Google URL Parsing Library". Since that time it's no longer packaged as a standalone library, and is now an internal component of the Chromium browser.
  Note The best way to understand what it does and the quirks it handles is probably to read the URL parsing unit tests.
  Using a version from 2007, RTBkit wraps Google's GURL class lightly in its own Datacratic::Url. It expands on the parsing and canonization with the ability to remember an invalid URL by caching the original string passed to the constructor, and serializing that cache to a database.

The JML Library

This code is quite old but extremely efficient and performant, and is used at the core of several machine-learning startups.

• arch -- some architecture-specific functionality, basically timers and low-level stuff.
• db -- simple code for putting nested streams of data into one persistent file; kind of like a .tar file.
• utils -- a grab bag of utilities, for hashing, CSV files, compressing...miscellany like old copies of SGI STL headers...

RTB Optimizer is a real-time bid management system that computes a unique probability score for each impression, then uses that score to calculate an optimal bid price based on campaign goals. It can be integrated with any front-end RTB stack and is powered by Datacratic's Real-Time Machine Learning Platform.

Libraries (and Software) that were Snapshotted

• boost-- Boost is an important library for C++, providing a number of general facilities. RTBkit makes heavy usage of several boost libraries, which is good. It still has some lagging references to things like boost::shared_ptr instead of std::shared_ptr, and some other "not replaced with updated equivalents".
• cairomm -- C++ interface to the Cairo 2-D drawing library. It's used to draw a dynamic advertisement which indicates the win price in the ad bid on top of the ad. For some reason only featured in the exchange tester for the Rubicon ad network. No other use.
• cityhash -- Some non-cryptographic functions for speedy hashing, used a few times to generate unique ID numbers from strings or IP addresses.
• curl and its C++ binding curlpp -- This library is how RTBkit does any GET, POST, etc. that it needs. Used by an "http client", "rest proxy", and connection for "s3". Mostly intended for services to do basic file transfers; the kind of stuff you'd do with cURL at the command line except not needing to call out to a shell to do it.
  cURL is not used to connect to the bidding exchanges. For that, there are custom classes wrapping everything down from the TCP layer on up. So there's still more custom code for commodity functionality that the system is based on. That doesn't mean it's bad code...but it does mean that there's not a lot of manpower and auditing improving it.
  Note I've dabbled in low-level socket programming. (I ported a DHCP server from Windows to Mac (see "When Sockets Attack!", and tinkered around designing a rewriting proxy server called Flatworm.) So I know it's doable but can be hard to get the details right, I'd probably look into Boost.Asio more if ever facing such a situation.
• libssh2 -- Implementation of the SSH secure shell protocol. Provides the ability to do secure file transfers to SFTP servers as a service. The service is not used by any of the published RTBkit code (but it's there).
• node -- Node.js, already mentioned as not built in the Ubuntu14 version, and seems to be a deprecated dependency going forward.
• protobuf -- Google Protocol buffers... already mentioned as the fast piping technique Google uses for ad bidding.
• redis and hiredis -- so both the structured storage system and the C binding for it. For those not-in-the-know, Redis is a key-value store that is known for holding state fully in memory; it's written in C and flexible for what it is. The people I knew of who used Redis used it for fast tracking of metrics when they're willing to fail and miss a few.
  So I was surprised that the first usage I found was in the "banker" as persistence for the banking structures. How could an in-memory system be good for keeping track of account balances and spending limits? Digging further I found out that Redis actually does have recoverable persistence in "append-only-file" mode (AOF), and the ability to get ACID durability with an fsync on every operation.
  But they didn't configure it that way, and one of the RTBkit team members said they don't even use AOF. So it appears the Redis database is just some kind of shadow.
  It's also used in something called a RedisAugmentor, which is a component not used by the distribution, so my only understanding of its usage would be very abstract. It's something about being able to take an ad spot that you're going to pass from the Router to an Agent and add some data to the bid before the Agent has a look--in the case where the data lives in a Redis database somehow.
• snappy -- A compression library which happens to be needed by LevelDB. Its goal is speed, but at the cost that "the compression ratio is 20–100% lower than gzip."
• userspace-rcu -- This is described as a "userspace read-copy-update library for data synchronization, that provides read-side access which scales linearly with the number of cores." While I know a little bit about lock-free programing I don't know the linux kernel term "RCU"...but am bookmarking an article to read more about the implementation.
  It seems to mostly be used in logging. I'll look more at it later.
• zeromq3-x -- is the C binding to ZeroMQ. The C++ binding cppzmq is a the single file zmq.hpp, a snapshot of which is embedded in RTBkit (with some extra JML assertions added).
  Communications between the different services in the system is done using ZeroMQ, as previously mentioned. I gather this means you can run all of them in the same process, or each in their own process...and the code will just work.
• zookeeper -- Apache ZooKeeper is something I'd never heard of. It's a kind of directory service, and is used to let the running services find out about each other. They describe here how the services publish their zeromq and http info.
  The situation is that they've decoupled the services from each other (architecturally, even if they are in the same process). And perhaps there is some dynamism in terms of where a service might pop up; more dynamic than a configuration file could handle. So this is just a way of avoiding the specification of ZeroMQ and TCP endpoints statically...perhaps coping with when some go down and need to come back up. I'd have to look at it more to really understand it.

Libraries Taken for Granted

• libicu-dev - Internet Components for Unicode used by Boost.RegEx and GoogleURL
• libevent-dev - used by Redis.
• libssh2-1-dev - ssh library used by Curl.
• libbz2-dev - bzip compression used by Node (which now seems being phased out as a dependency).

• libblas-dev - "basic linear algebra subprograms"
• liblapack-dev - "linear algebra package"

• python-dev - used by Boost.Python; there is some information about writing a Python Bidder Client on the RTBkit wiki.
• zlib1g-dev - DEFLATE-based library used by the Logger to compress logs.
• liblzma-dev - LZMA-based library (as used in .xz/.7z files). Also used to compress logs (although it's not clear how you get to pick a "ZlibCompressor" vs an "LzmaCompressor".
• libcrypto++-dev - Node and Curl require this. But it's remarked that "Exchanges transmit winning prices in different units, currencies, encodings and encryption schemes." So you'll find some of them requiring (for instance) Blowfish. So in addition to the communications with S3, AWS, and some MD5 hashing you will find cryptography used to communicate with the ad exchanges.
• libACE-dev -- The "ACE adaptive communication environment" is yet another grab-bag of a library. It provides synchronization primitives, timers, and C++ wrappers for things like sockets, signals, datagrams, and INET addresses.
  The codebase uses a few ACE classes as the implementation of JML's "arch" primitives for things like semaphores, and in assisting of the implementation of the socket abstraction classes. I'd never heard of this library before...and despite its age (it has been around since before 2000), there's only a hundred or so questions about it on StackOverflow.
  The most notable-seeming usage of libAce would have seemed to be in the auction.cc file:

  #include "ace/Acceptor.h"
  #include <ace/Timer_Heap_T.h>
  #include <ace/Synch.h>
  #include <ace/Timer_Queue_Adapters.h>
  #include "ace/SOCK_Acceptor.h"
  #include <ace/High_Res_Timer.h>
  #include <ace/Dev_Poll_Reactor.h>
  

  That caught my eye (beyond just the mixture of quoted and angle bracketed includes). Here were high resolution timers, timer heaps, timer queue adapters, dev poll reactors. Serious-sounding business! Except...if you comment those headers out it all still builds. There are no references to any of that. :-)

Still, why 50MB for RTBkit's Repository?

• .cc -- 6 MB -- (The extension debate may never die, but I use .cpp myself)
• .h -- 3.7 MB -- header files, either C or C++ (presumably mostly C++)

{"!!CV":"0.1","exchange":"dblclk_adx","id":"1497db9a-24a5-4001-15e8-deff04002930",
"ipAddress":"76.209.61.239","language":"en","location":{"cityName":"Elgin",
"countryCode":"US","dma":602,"postalCode":"847","regionCode":"IL"},
"protocolVersion":"0.2","provider":"rtbkit","restrictions":{"clickUrl":
["buzznet.com","mog.com","napster.com","nevadaskideals.com","rhapsody.com",
"tunecore.com"],"creativeAttribute":[3,4,5,6,22]},"segments":{"adxVerticals":[
[220,0.3995213210582733],[529,0.4392172992229462],[592,0.1612613946199417]]},
"spots":[{"formats":["300x250"],"id":"1","position":"NONE","reservePrice":0}],
"timestamp":1307476542.329969,"url":"http://www.playlist.com/","userAgent":
"Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1; Trident/4.0;
Media Center PC 3.0; .NET CLR 1.0.3705; .NET CLR 1.1.4322; AskTbFWV5/5.12.2.16749),
gzip(gfe),gzip(gfe)"}

In Conclusion

• While the repository and its dependencies paint an imposing picture, some of the more mysterious components are used rarely (or not at all). A large machine learning library dependency with neural networks, linear algebra, Fortran and t-Distributed Stochastic Neighbor Embedding (t-SNE) has no notable incorporation. This is both bad and good: it's good because it means you don't need a Ph.D in math to understand the software, and bad because it's relatively ordinary pipes+logic vs. any "magic".
• If any magic does exist, it is not open-sourced--except in a library form that requires sophistication to know how to begin to use (and it is one among many such libraries). Options exist to work with partners in the RTBkit Ecosystem, including the company that open sourced RTBkit (whose extensions presumably use the aforementioned unused libraries for machine learning). However, costs for their services do not appear to be publicly disclosed, so it's difficult to know exactly what you'd be in for with that..
• The overwhelming majority of original code in RTBKit is C++11, with a small amount of JavaScript and Python embedding capability. There are no large declarative portions to the code or domain-specific languages. Modifying or understanding the project in any non-trivial way would mandate a practical awareness of C++ with several years of experience.
• Adoption of new C++11 features is relatively conservative, with a focus on efficiency benefits, such as emplace_back as opposed to push_back. Another area are constructs providing convenience (auto, range-based for, lambdas). There is no template metaprogramming, and appear to be no instances of std::enable_if or SFINAE.
• Though std::shared_ptr and std::unique_ptr do appear, there are still a huge number of raw pointer allocations and calls to delete and delete[]. Other areas lagging in modernization are several remaining references to std::auto_ptr (a class that should have never existed in the first place), along with usage of boost::shared_ptr instead of std::shared_ptr, etc.
• Note

  I did find interesting the incorporation of Scoping helpers that are passed lambdas to implement a pseudo-"try/catch/finally" alternative, apparently originating from the D language. Kind of interesting.

  As it's new to me, I don't have experience with using this to say whether it is especially "good" or "bad" compared to more traditional coding styles with exception-handling. I will point out that since destructors run in the reverse order of construction, you'll get some possibly-counterintuitive ordering if you use more than one in a scope.
• A testing system is in place, and valgrind is used to check for memory leaks in an automated fashion, with appropriate suppressions of known issues in libraries. Assuming the tests represent realistic stresses of running in practice, the raw pointers might not be causing problems yet. (Still it should be a priority for someone to go through and fix those).
• One critical weak point is a pervasive dependence on homegrown or obscure libraries, for common functionality that has more popular and/or vetted implementations. Trained developers would likely demand they be given time to update these to more appropriate variants (as opposed to learning or improving the libraries). Less-trained developers might spend excessive time absorbing the nuances of obscure classes, which will also not be a transferable skill to other projects. It may be difficult to find agreements on substitutions that would be endorsed by the repository maintainers...which creates a cost of fragmentation.
• Note Although much of the libraries may be homegrown, they do include tests; so reliability may not be at issue.
• If one were to hire a team to work with this project, prior C++11 experience is likely less important than general C++ familiarity (including how to use libraries like boost to avoid reinventing the wheel). Also of importance would be the developers have current knowledge of--or be very interested in--the technical landscape of emerging server-side technologies. (This would be true in any "build" situation as well.)

Afterword

Developers who decide to build on top of the RTBkit framework can eliminate most of the difficult engineering work required to create a scalable real-time bidder. Its open, service-oriented architecture can be used to assemble a bidder as simple or complex as desired. The software routes bid requests and data through a configurable set of components which can be extended to implement a customized bidder. It is highly efficient and scalable, with the core logic able to support tens of thousands of bid requests per second per commodity server. The framework handles most of the mechanical parts of bidding allowing software developers to focus on truly innovative features like unique bidding logic and data driven optimization.

Project names and graphic designs are All Rights Reserved, unless otherwise noted. Software codebases are governed by licenses included in their distributions. Posts on blog.hostilefork.com are licensed under the Creative Commons BY-NC-SA 4.0 license, and may be excerpted or adapted under the terms of that license for noncommercial purposes.