Modern memory management via vmbuf

About memory management

Memory management in high throughput servers can become an extremely difficult challenge if not thought carefully beforehand. Traditional memory management relies on malloc and free, where major performance improvement can be achieved by using memory pools and memory pools per thread to avoid global locks. Modern memory management relies on the dramatic advancement in hardware, more specifically the MMU (Memory Management Unit). Today software can easily leverage the new hardware to further improve throughput and latency.

Relying solely on the MMU and the best implementation of malloc and free, can bring you far but not far enough. There are certain guidelines that must be followed in addition to that, at Adap.tv when we discuss server architecture we call them prime directives to signify thier importance.

• Never call ‘free’ (or delete in C++) in the code. ‘free’ consumes many CPU cycles since it needs to coalesce free blocks and deal with fragmentation. Freeing memory is allowed only when using memory mapped files and only in the case of mapping new data while discarding old.
• Always reuse memory. In high throughput servers, all the requests are roughly the same pattern? which means memory could be reused.
• Avoid copying and/or moving memory regions.

There are several ways to obey the above directives, we chose, what we believe the best way for our needs. We call our solution vmbuf, it combines together well known techniques where most of the innovation is on the way we combine these techniques.

64 bit architecture

Virtual memory on 64 bit architecture is very powerful, compared to its counterpart 32 bit. The main reason behind it is the address space. Address space on 64bit architecture is 128TB (linux x86_64), vs. ~3GB on 32bit architecture. Having 128TB is important when it comes to allocating and resizing buffers. When allocating virtual memory, the OS allocates address space only, no physical memory is involved until memory is actually used (minor page fault). Armed with that knowledge and 128TB of address space, it is now possible to double the size of the buffer upon resize, hence avoiding many system calls to mmap, without consuming physical memory beyond what is actually needed and without copying the actual data. In some cases, when there is enough knowledge about the memory usage, over allocation of VM can be used as well to accommodate any expected usage and completely avoid resizing. On 32bit systems, resizing can easily lead to lack of contiguous address spaces, making resizing impossible, hence, it would be more effective to use vmbuf on 64 bit architecture.

vmbuf

vmbuf is part of our opensource projects RIBS and RIBS2.0 which can be found on github:

https://github.com/Adaptv/ribs

https://github.com/Adaptv/ribs2

Capabilities 

• Allocate memory auto-resizing when needed avoiding copying physical memory blocks
• string/memory functions: sprintf, strftime, strcpy, memcpy
• Read and write until end of data, EAGAIN or other errors
• Containers: hashtables, linked list, heap, vector
• vmfile: persist the data in memory mapped file.

How does it work?

vmbuf is using mmap and mremap to allocate and resize memory regions. One can argue and say that malloc, free and realloc can achieve exactly the same and they are also portable, however, we chose the non-portable way since we do care about the extra CPU cycles that can be saved when bypassing malloc and calling mmap directly. Furthermore the memory copy that takes place when calling realloc can be avoided if using mremap, offloading most of the work to the MMU.

How to use vmbuf or similar solution that uses malloc/realloc (remember no ‘free’)?

• All the data structures that are stored in vmbuf must used offsets instead of pointers. We implemented, vectors, linked lists, hashtables and more that are vmbuf based.
• vmbufs can be allocated per connection and/or per thread (or global if not using threads). For example: the request and response buffers are per connection where temporary buffer to convert timestamp to string is allocated once per thread and reused by all requests.
• There are extremely rare cases that large chunk of memory is needed temporarily at the connection level but only tiny percentage of the time, in that case ‘free most’ can be used to free most of the pages leaving enough pages for the common requests.

Why we use C++ (without using STL or boost)

Audience: SaaS and SOA designers and engineers who uses Linux.
Not yet audience: apps and desktop apps designers and engineers.

C++ refers to the language without using STL.

“There are two ways of constructing a software design. One is to make it so simple that there are obviously no deficiencies; the other is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”
– C. A. R. Hoare The Emperor’s Old Clothes, CACM February 1981

There are plenty of reasons not to use C or C++. In http://catb.org/esr/writings/taoup/html/why_not_c.html Eric Steven Raymond documented the most common reason: “The central problem of C and C++ is that they require programmers to do their own memory management” and “C memory management is an enormous source of complication and error.” “Not so long ago, manual memory management made sense anyway. But there are no ‘small systems’ any more, not in mainstream applications programming.”

Others complain also about strings http://www.kuro5hin.org/story/2004/2/7/144019/8872, missing types, and being trapped in the 1970s.

So why use it? Because you can build very efficient, large scale systems, fast. You are probably asking yourself how did the word ‘fast’ in the context of ‘build fast’ got in here? read on.

Performance – It does not make sense to even try and compare C or C++ to Java or Perl or PHP or Python etc. as those are all written in C and some C++, so inherently they are slower – the additional layer will always cost something. However, If you really insist, there are many benchmarks out there that will prove the point. (some benchmarks credit the gcc optimizer, not the language) Using my personal experience over the years, you will need 4 to 80 times the hardware just by deciding not to use C or C++.

Even with the hit on performance and cost, many still avoid C and C++, mainly because the perception of additional engineering time due to memory management.

At Adap.tv, we decided to solve the problem. It is well known fact that the problem with managing memory is actually freeing memory, so we’ve decided to avoid it completely and not to free memory. Rather than freeing memory, we reuse memory without any locking. Doing so, together with event-driven technology, allowed us to quickly build high scale systems. By high scale I mean 10,000s connected clients (persistent connection) and 100,000s queries per second per server.

The key to this are large buffers and 64bit technology. (It is possible to do the same with 32bit, however, the 2GB user address space is a limiting factor, and extensive use of technologies like PAE are required) With 64bit, the address space is limited to 128TB. Those large buffers (called vmbuf) are being used to save data and also to allocate structures (“objects”) when the task is done the vmbuf’s internal offset is simply being reset() to 0. vmbuf’s exists per reusable context, such as server context or client context, and per thread. Per thread only vmbufs are good as long as the server or client does not need to wait for a network event. (remember, it is also event-driven)

There are several rules that we are obeying in order to keep the performance high;
Avoid malloc(), calloc() or new
No free() or delete (and no need for tcmalloc)
No STL, boost etc.
Avoid locking as much as possible
# threads = # CPU cores (hyperthread is a trade-off between latency and throughput)

vmbuf is included in the Robust Infrastructure for Backend Systems (RIBS) which is the infrastructure that we use to build our servers: https://github.com/Adaptv/ribs/

Our next blog post will describe in details the design of vmbuf and will also include an example of how to use it in your servers.

Three forecasting techniques

How well are we doing when forecasting for online ads at Adap.tv? Can we do better? To start answering such questions, we used R to experiment with three well-known forecasting techniques and used an hourly metric (transformed for data privacy) across all ads for seven days (Feb 1-Feb 7) as our training data set. We then used each of the techniques to predict for the eight day (Feb 8), and compare the predicted values with actual data. Here’s a synopsis of the three:

1. Exponential Weighted Moving Average (EWMA)

Strictly speaking, the smoothing filter that we currently use at Adap.tv for forecasting is not EWMA, but more like Weighted Moving Average. EWMA is defined by:

(ref)

So, if a = 0.9, S[t] = 0.9 ( y[t-1] + 0.1*y[t-2] + 0.01*y[3] … 1e-6*y[t-7]) would be an implementation of EWMA. Instead, our implementation is: S[t] = 0.9 ( y[t-1] + 0.9*y[t-2] + 0.81*y[3] … 0.531441*y[t-7]) / (0.9+…). The critical difference is in the way past data is weighted – with EWMA data in remote past is heavily penalized, whereas, comparatively, in our implementation it is not.

Fig. 1 below shows a plot that forecasts our metric for Feb 8 using Weighted Moving Average akin to our implementation. The metric forecasted for Feb 8 was 68392533 whereas observed value was 63868927, giving an absolute difference of ~7.1%. The absolute hourly differences lie between 0.6-29%.

2. Harmonic regression

Harmonic regression attempts to find the best-fitting periodic signals that can characterize a time series. For example, a time series may be represented by a linear sum of sinusoids:

(ref)

Generally, a combination of Fourier transform and least-squares regression in used to find the harmonics who linear sum best fit training data. In our experiment, we used the top seven harmonics with highest power density (i.e. contribution to the model), and then used linear regression to find their amplitudes. Fig. 2 shows the model (in red) and actual data (in blue). The forecast for Feb 8 was 60476559 whereas the observed value was 63868927, giving an absolute difference of ~5.3%. The absolute hourly differences lie between 0.05-25%.

3. Holt-Winters method

Holt-Winters method augments EWMA to account for data trends and seasonality.

ref)

The model we used assumes that the seasonal component is additive (instead of being multiplicative). Fig. 3 illustrates the breakdown of seasonality, trend and randomness in the data,  Fig. 4 contrasts observed data with predicted data (note that the prediction start after one period, and the phase lag in predicted data), while Fig. 5 shows Holt-Winters prediction for Feb 8 versus observed data. The forecasted metric for Feb 8 was 63801332 whereas observed value was 63868927, giving an absolute difference of ~0.11%. The absolute hourly differences lie between 1.3-20%.