Презентация Facebook на ВМК МГУ

28 октября в на ВМК МГУ ребята из Facebook рассказывали про устройство Facebook TAO - хранилище социального графа.
Небольшая выжимка:

• Социальный граф - набор объектов и связи между ними. Например: пост связан с пользователем, фотография к посту связана с постом, коментарии и лайки других пользователей связаны с постом, пользователи могут иметь отношение дружбы, и т.д.
• Чтобы отрисовать страницу пользователя, нужно загрузить все ноды графа, связанные с последним событием;
• На загрузку одной ноды графа отводится 1 милисекунда;
• Особенность кеширования - наиболее горячие данные те, которые недавно создались;
• У каждого объекта графа есть уникальный 64 битный глобальный идентификатор. Уникальность гарантируется так: в идентификаторе объекта N бит отводится под идентификатор пользователя, остальные биты под событие. Главное для каждого пользователя уметь получить следующий уникальный идентификатор события. Это не сложно и не требует глобальной синхронизации.
• В качестве хранилища свой отбранчёванный MySQL с InnoDB;
• Многоуровневое кеширование c Memcached и McRouter;
• Есть процедура прогревания кеша;
• 99.8% - чтение данных, 0.2% - запись;
• 3 датацентра в США, 1 в Европе;
• В каждом ДЦ есть мастер нода MySQL. Все записи идут в мастер ноду, далее асинхронно реплицируются;
• Если мастер нода падает, выбирается новая мастер нода;
• Чтобы не задолбать бэкенд, над каждым инстансом MySQL располагается Master Cache, через который идут все запросы в этот инстанс. Это позволяет контролировать нагрузку на  MySQL;
• Очень большой кеш-хит, поэтому до бэкенда MySQL долетает мало запросов (около 1 KRPS на инстанс);
• Если все кеши отвалятся, MySQL бекенд нагрузку не выдержит;
• Для проведения аналитики по социальному графу есть выгрузка данных в Hive;
• Шардируют базу по диапазонам идентификатора, поэтому процедуры перешардирования нет;
• Есть региональные прокси для снижения латентности https handshake;

Более подробно можно почитать в статье

Материалы по модели памяти C++

1. C++ and Beyond 2012: Herb Sutter - atomic<> Weapons Part 1
2. C++ and Beyond 2012: Herb Sutter - atomic<> Weapons Part 2
3. C++ Concurrency in Action: Practical Multithreading (Chapter 5)
4. Pershing on programming
5. Threads Cannot be Implemented as a Library
6. Threads and memory model for C++ by Hans Boehm

C++ Type Deduction

На конференции cppcon 2014 был доклад Скота Мейерса про выведение типов - Type Deduction and Why You Care (слайды).
Небольшая шпаргалка:

#include <iostream>

template <typename T>
T func1(T f) {
    return f;
}

template <typename T>
T func2(T& f) {
    return f;
}

template <typename T>
T func3(const T& f) {
    return f;
}

template <typename T>
T func4(T&& f) {
    return f;
}

void func5(const int * const param1,
           const int *       param2,
                 int *       param3) {
    auto p1 = param1;   // p1 = const int*; same as for auto *
    auto p2 = param2;   // p2 = const int*; same as for auto *
    auto p3 = param3;   // p2 = int*; same as for auto *

    auto &rp1 = param1; // p1 = const int *const &; same as for auto &&
    auto &rp2 = param2; // p2 = const int *&; same as for auto &&
    auto &rp3 = param3; // p3 = int *&; same as for auto &&
}

int main(int argc, char* argv[]) {
    int x = 10;
    int &rx = x;
    const int &crx = x;

    func1(x);       // T = int; param = int;
    func1(rx);      // T = int; param = int;
    func1(crx);     // T = int; param = int;

    func2(x);       // T = int; param = int&;
    func2(rx);      // T = int; param = int&;
    func2(crx);     // T = const int; param = const int&;

    func3(x);       // T = int; param = const int&;
    func3(rx);      // T = int; param = const int&;
    func3(crx);     // T = int; param = const int&;

    func4(x);       // T = int&; param = int&;
    func4(rx);      // T = int&; param = int&;
    func4(crx);     // T = const int&; param = const int&;
    func4(42);      // T = int; param = int&&;

    return 0;
}

auto в range base loop

На всех конференциях посвящённых C++ практически всегда рекомендуют использовать для определения переменных auto. Один из доводов в пользу auto, кроме того, что приходится меньше писать, в том, что сгенерированный код быстрее, т.к. всегда выводится корректный тип, и нет места приведению типов. Хотя кажется что тип всегда и так очевиден возможны ситуации, когда по невнимательности типы не совпадают, и компилятор выполняет конвертацию.
Например:

#include <map>
#include <string>

int main() {
  std::map<std::string, int> m;
  for(const auto &a : m) {}
  for(const std::pair<std::string, int> &a : m) {}
  return 0;
}

Вопрос: Какой вариант for быстрее? Ответ: Первый, т.к. auto& выводит корректный тип элемента, который для std::map<std::string, int> - std::pair<const std::string, int>, т.к. для std::map запрещено модифицировать ключ. Для второго for-а создаётся временный объект std::pair<std::string, int>, поэтому он работает медленнее.

Грабли шаблонного конструктора

Допустим у нас есть шаблонный класс с шаблонным конструктором копий и функция create:

#include <string>

template <typename T>
class MyClass {
public:
    MyClass() = default;

    MyClass(T t) : value(t) {}

    template <typename U>
    MyClass(const MyClass<U>& other) : value(other.value) {}

    T value;
};

template <typename T>
MyClass<T> create(T v) {
    return MyClass<T>(v);
}

Также имеются две перегруженные функции:

void func(const MyClass<std::string> &) {}
void func(const MyClass<float> &) {}

Если попытаться скомпилировать такой код:

int main() {
    func(create("Hello"));
    return 0;
}

То получим "странное" сообщение об ошибке:

clang++ -Wall -Wextra -std=c++11 test.cpp -O3 -o test
test.cpp:28:5: error: call to 'func' is ambiguous
    func(create("Hello"));
    ^~~~
test.cpp:16:6: note: candidate function
void func(const MyClass &) {
     ^
test.cpp:19:6: note: candidate function
void func(const MyClass &) {
     ^
1 error generated.
make: *** [all] Error 1

То есть компилятор считает обе функции подходящими вариантами и не знает какую выбрать. На самом деле понятно почему. У MyClass есть шаблонный конструктор копий, который может принимать любой тип. Найдя его при разрешении перегрузки функции func, компилятор даже не проверяет, можно ли реально вызвать этот конструктор, и не будет ли ошибок. А ошибки будут, т.к. const char* не приводится к float.
Такая же проблема была с std::pair до принятие стандарта C++11. То есть такой код:

#include <utility>

void func(const pair<int, int>&) {}
void func(const pair<std::string, std::string>&) {}

int main(int argc, char* argv[]) {
    func(std::make_pair("Hello", "world"));

    return 0;
}

Приводил к такой же ошибке.
Решить эту проблему можно с помощью SFINAE и enable_if:

template <typename T>
class MyClass {
public:
    MyClass() = default;

    MyClass(T t) : value(t) {}

    template <typename U, typename = typename std::enable_if<std::is_convertible<U, T>::value>::type>
    MyClass(const MyClass<U>& other) : value(other.value) {}

    T value;
};

Теперь шаблонный конструктор копий участвует в перегрузке только в том случае, если тип T класса, который передаётся в конструктор конвертируется в тип T класса, который конструируется.
Если шаблонному классу std::enable_if в качестве первого параметра передали true, то внутри него определён typedef с типом второго парамтера. Если же первый параметр false, то typedef не определён.
Поле value в шаблонном классе std::is_convertible равно true или false в зависимости от того, конвертируется ли первый параметр шаблона во второй.
Итого, если в конструкции

std::enable_if<std::is_convertible<U, T>::value>::type>

тип U конвертируется в тип T, то std::enable_if::type определён, и функция учавствует в разрешении перегрузки. В противном случае std::enable_if::type не определён, и вся конструкция является некорректной. Такая ситуация называется "substitution failure". По стандарту она не является ошибкой компиляции (is not an error), и компилятор просто выкидывает шаблонную функцию из рассмотрения. Данный приём называется SFINAE - substitution failure is not an error.

HTML кодировщик для C++ кода

Ссылка

Проверка существоания методов у класса

На cppcon 2014 был доклад для про современное метопрограммирование шаблонов - слайды.

Там в частности рассказывалось как реализовать проверку существует ли для класса оператор копирующего присваивания. Суть метода в том, чтобы получить тип результата некоторого выражения (в данном случае оператора присваивания) через decltype, и инстанцировать этим типом шаблон. Если выражение корректно (то есть у нас есть оператор присваивания), то результатом параметризации будет один тип (например std::true_type), если нет, то другой тип (например std::false_type).

Пример кода из слайдов:

template< class T >
using copy_assign_t = decltype(declval<T&>() = declval< T const& >());

template<class T>
struct is_copy_assignable {
private:
  template< class U, class = copy_assign_t<U> >
  static true_type try_assign( U&& ); // SFINAE may apply!
  static false_type try_assign(...); // catch-all overload
public:
  using type = decltype(try_assign(declval<T>()));
};

Работает это всё благодаря SFINAE.

Я попробовал написать общий класс, который возвращает true_type/false_type в зависимости от того, является ли любое переданное выражение корректным. Его можно использовать, чтобы реализовать свои проверки для типов, при этом не требуется писать много кода.

Например нужно проверить, есть ли в классе нестатическая функция get_value():

//Объявляем тип выражения
template <typename T>
using has_get_value_t = decltype(std::declval<T>().get_value());

template <typename T>
struct has_get_value : is_correct_expression_t<T, has_get_value_t> { };

int main() {
  std::cout << std::is_same<std::true_type, has_get_value<MyClass>::type>::value << std::endl;
}

Как это реализовано:

template <typename T, template<class> class E>
struct is_correct_expression_t {
private:
    template <typename U, typename = E<U>>
    static std::true_type try_evaluate(U&&);
    static std::false_type try_evaluate(...);
public:
    using type = decltype(try_evaluate(std::declval<T>()));
};

Для move/copy assign будет выглядеть так:

template <typename T>
using copy_assign_t = decltype(std::declval<T&>() = std::declval<const T&>());

template <typename T>
struct is_copy_assignable : is_correct_expression_t<T, copy_assign_t> { };

template <typename T>
using move_assign_t = decltype(std::declval<T&>() = std::declval<T&&>());

template <typename T>
struct is_move_assignable : is_correct_expression_t<T, move_assign_t> { };