Now Wave is dead, Lars works for Facebook, and they’ve recently announced graph search, a technology that allows you to search anything shared with you on Facebook. I’ve been interested in the technical details for a while and lately I’ve found Lars answering questions on Reddit. So for those who are lazy to read whole Q/As I’ve written a quick summary of graph search architecture quoting author as much as possible.

At the back-end they have inverted-index system called Unicorn that is used to select nodes in the social graph based on edge-relationships to other nodes. Unicorn is akin to document search systems for other contexts like email, webpages, or files on your computer; but it also has some graph-centric features that make it especially useful for searching over the social graph.

All the search requests from users are sent to the index servers. Hive, Hadoop, and HBase are used to convert database contents into an inverted index on a regular basis, and then they push messages to index servers to have realtime updates from the base index.

When a user fires a search request the query gets translated two times. First NLP translator transforms natural language query to a semantic language that describes the interpretation of the natural language, and then further down in the stack they use an s-expression syntax to retrieve potential results from an inverted index.

Lars gave the following example. When user types

My friends who live in Sydney, Australia

it is interpreted to semantical form of

intersect(friends(me), residents(110884905606108))

and then to s-expression

(and friend:767560056 city_to_user:110884905606108)

If you have tried graph search you may noticed that you can’t use a random query to search stuff, when you start typing system automatically suggests you matched queries and you can fire only suggested ones. How does it work? At the core of the system sits a Context-Free Grammar describing all the queries the system can understand. The grammar in general contains many different ways of expressing the same question. As a user types in the search field, a Parser attempts to find the queries from the grammar that most closely matches what the user has typed, and displays those as suggestions in a drop-down below the search field.

As part of the parser they’ve developed named entity recognition engine. For example, if you search for photos of jane doe the parser will figure out which Jane Doe you are looking for. When in doubt, they tend of course to pick the Jane who has the most friends in common with you.

Graph search is an exciting piece of technology as mush as Wave was, and it definitely pushed industry forward. I hope you’ve find my notes interesting, and by the way I guess Lars is still answering the questions!

So what do I mean by coordination? Let’s start with the simple one. Common challenge in distributed systems is getting the naming right. Many distributed algorithms should be able to distinguish one process from another in order to work correctly. The trick is to come up with the that works in a distributed way, gives a processes unambiguously identifiable names among the system, and could support dynamic addition and removal of the nodes in cluster.

Configuration management is another coordination problem that pops out frequently. Every sophisticated system has to deal with the configuration information. Property files may sound great but consider you have hundreds of nodes in the cluster running particular deployment packages and now you have to change the configuration property on all of this servers. It turns out that property files are great if configuration is static but using them for dynamic configuration doesn’t seems to be good idea.

To explain next problem named group membership let’s picture some real world project. Imagine you are working on a social network web-site and there are two types of distributed processes: front-end servers that handle http requests and image servers responsible for efficient image storage. Whenever user uploads the photo, front-end server has to communicate with the image storage to save the image, so front-end server has to be configured to know the addresses of the image servers. Now suddenly this photo sharing feature becomes extremely popular and we need to increase number of image servers in order to handle all content uploads. In addition let’s be realistic and accept the fact that some of the servers might fail and we need to track that information and avoid sending requests to the failed server. Sounds non-trivial.

If you worked on multi-threaded programs, apparently you should be familiar with the concurrency issues. While developing distributed app we basically face the same challenges as we would face in the multi-threaded environment plus. In the distributed system race conditions between the processes could easily happen if there are some shared resources, so you might be forced to implement some decent locking mechanism to solve them. Race condition is not the only issue, some of your data may require ACID guaranties (atomicity, consistency, integrity and durability) and you should be ready to get you hands dirty and implement transactions by yourself.

Many popular distributed databases, search servers, file systems require single master node to coordinate activities across other nodes in some way. But how do you select the master? Obvious way to do this is to choose it by yourself. It works but as we already know, predefined configuration is not that flexible. Plus, remember we are living in distributed world, we need master to be fault tolerant: in case if current master crashes some other node should come up and do the job. The problem of automatically select(elect) master(leader) process is called leader election. Technically speaking leader election is the same old locking problem. Think of leader as a process that acquired and holds lock forever until shut down or failed. But since it is frequently encountered it is considered separately.

Coordination problems I’ve described may sound easy but implementing them correctly in fault tolerant way may lead you to the nights of hardcore debugging of highly concurrent code. No fun, believe me, I’ve seen a project where custom distributed transactions are implemented. Fortunately, Apache ZooKeeper comes to rescue by providing set of reliable primitives, building blocks that allow us to tackle coordination problems with ease.

How big is the source code you are working on? How many developers do you have in your team? If you are going to add new feature tomorrow, how fast will you be able to do that?

Maintainability matters. Well, it matters in case if you’re willing to build a successful applications evolving over the years. And if you would like to be able to quickly add new features you definitely want to see the developers spending most of the time on writing code and hacking on a new stuff.

Working mostly on enterprise projects I used to see multi-developer teams working on a single gigantic piece of software, usually built using one particular technology. This turns out to be inefficient and leads to unmaintainable code. A developer on a such project is forced to spend most of his time on trying to understand the way the current system works instead of adding concrete value. And I’m sorry, there is no value in reading pages of purely written legacy code. The only real value programmer can add is a new code.

Another disaster is the verification of the produced code. Getting instantaneous feedback by executing a newly written code is the essential part of the developer’s productivity. Unfortunately running enterprise software is usually a real pain. You are forced to use rare application servers, monstrous databases, and in addition you have huge codebase with everlasting build time.

Decomposition for the win

Increasing program-to-developer ratio is the way of building things that keeps the developers productive and happy. Instead of having hordes of programmers working on one single codebase, split your system to a small programs that could be deployed independently. Beautiful reusable code should be extracted as a libraries and be maintained independently. Open source that libraries if possible and you’ll get the feedback from the peers.

Writing small programs or services, if we talk about web apps, benefits in long term perspective. First of all small services are easy to reason about. The key is to stick with open closed principle, write services that do one thing, and do it well. It’s easy to execute these services independently and see whether they work or not. For example for Gmail you might extract a service responsible for sending and receiving emails, you might have a separate service that does spam filtering, separate service for storing e-mails, a service that can apply filters and a standalone web-app that communicates with these services.

One big advantage of splitting you program is that you are no longer restricted to use one particular platform. We know that ruby or node.js make you really productive in writing web apps but their performance is pretty inefficient comparing to C++ or Java. Since we are able to deploy services independently we can forget about monolithic Java EE and combine different technologies and for example build a web app with rails and backend services using C++ and use some convenient protocol like Protobuf or Apache Thrift for communication.

Truth been told decomposition of the system is somewhat non-trivial. One thing is becoming obvious, well known layered architecture is going to ruin maintainability of your project. It’s tempting to stick with classical enterprise approach and create a service for accessing the database, service that encapsulates caching, service that does business logic and a presentation service. But features are cross-cutted usually through these layers. So any new sophisticated feature will require changes in every layer. In addition most of the code will be responsible for converting messages from one format to another.

Software design and development is a pretty sophisticated activity and doesn’t fully depend on how smart you are and how many books you’ve read. It’s just so many thing you have to care about in order to achieve good quality solution. Keeping programs small is a great simple tool that allows you to reduce complexity of the solution and results in clean design and improved developers productivity.

Современные библиотеки позволяют сохранять информацию на различных уровнях логгирования. В проектах, в которых я участвовал, обычно используется четыре уровня логгирования:

• ERROR – сюда выводится информация о критичных ошибках в системе.
• WARN – используется для вывода не критичных, но все же некорректных сиптомов неправльной работы приложения
• INFO – используется для вывода интересных событий происходлящих в системе
• DEBUG – детальныая информация о том, что происходит с системой. обычно используется при разработке либо при отладке.

Обычно запись в лог выглядит довольно просто:

1
2
3
4

log.error("SOMETHING REALLY BAD HAPPENED")
log.warn("Something bad happened")
log.info("Startup")
log.debug("Processing request" + request)

Уровни логгирования легко конфигурируются, так что мы можем наблюдать debug информацию при разработке и видеть чистый лог в продакшне.

До сих пор, строки кода в open source библиотеках вида:

1
2
3

if (log.isDebugEnabled()) {
    log.debug("Processing request" + request);
}

вызывали недоумения: зачем это нужно, ведь запись в лог будет лишь при включенном дебаге, соответсвенно проверка влюченности дебага попахивает излишеством.

Однако, недавно я обнаружил, что подход без использования проверки влюченности уровня логгирования несет недостатки о которых мне раньше не приходилось задумываться.

Очень часто во время вывода в debug строки конкатенируются. И конкатенируются они независимо от того влючен дебаг или нет. Это во-первых приводит к тому, что создаются лишние строки что приводит к большим вызовам GC.

Во-вторых, операция toString может занимать продолжительное количество времени, и как показала недавняя история до 15% времени тормозящего метода.

Получается писать проверку влюченности уровня необходимо. Но не удобно. Количество строчек кода для записи в лог увеличивается в три раза.

Однако, если в проекте используется библиотека логирования slf4j, можно обойтись малой кровью используя шаблоны в строках. Как это работает:

Вместо конкатенации строк при логировании

1

log.debug("Processed request " + request + " sending response " + response);

писать

1

log.debug("Processed request {} sending response {}", request, response);

Чаще всего, конечно, можно воспользоваться гуглом, задать вопрос на stackoverflow, но в некоторых ситуациях ничего не остается, кроме как провести эксперименты самому.

Такая инженерная практика именуется microbenchmarking. Суть микробенчмаркинга в измерении производительности (загрузки процессора, памяти или операций с сетью, диском) небольших кусков кода для того, чтобы понять какой код лучше подходит для текущего сценария.

Стоит заметить, что микробенчмаркинг и профайлинг – это не одно и то же. Различия между ними напоминают различия между unit тестированием и интеграционным тестированием. Профайлинг подразумевает исследование производительности всего приложения в целом, тогда как микробенчмаркинг – это, в свою очередь, исследование актуальной в данный момент функциональности.

Зная что нужно измерять, написать бенчмарк довольно тривиально, и, часто, вполне можно обойтись одним единственным статическим методом main. Однако, используя фреймверк Caliper от компании Google, бенчмарки можно писать быстро и с удовольствием, выкинув при этом кучу boilerplate кода.

API Caliper в чем то напоминает старую версию JUnit. Для того чтобы написать простой бенчмарк нужно:

1. Отнаследоваться от класса com.google.caliper.SimpleBenchmark
2. Написать тестовые методы, название которых начинается со слова time.
3. Подготовка данных и очистка ресурсов происходит в методах setUp и tearDown соответственно.

Caliper изначально поставляется с большим количеством примеров. Один из интересных LoopingBackwardsBenchmark, который сравнивает скорость итерирования вперед и назад.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class LoopingBackwardsBenchmark extends SimpleBenchmark {
    @Param({"2", "20", "2000", "2000000", "20000000", "200000000"})
    private int max;


    public int timeForwards(int reps) {
        int dummy = 0;
        for (int i = 0; i < reps; i++) {
            for (int j = 0; j < max; j++) {
                dummy += j;
            }
        }
        return dummy;
    }


    public int timeBackwards(int reps) {
        int dummy = 0;
        for (int i = 0; i < reps; i++) {
            for (int j = max - 1; j >= 0; j--) {
                dummy += j;
            }
        }
        return dummy;
    }


    public static void main(String[] args) throws Exception {
        Runner.main(LoopingBackwardsBenchmark.class, args);
    }


}

Запустив тест мы убедимся, что разницы в производительности нет.

Еще один пример. Допустим, мы разрабатываем функциональность которая предполагает огромное количество операций над дробными числами, и мы думаем стоит ли использовать BigDecimal или лучше остановить свой выбор на старом добром быстром double. Сравнить насколько медленней будет работать BigDecimal для такой операции как умножение не сложно.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class DoubleVsBigDecimalBenchmark extends SimpleBenchmark {
    @Param({"1", "1.01", "1.0123456789", "20", "20.01", "20.0123456789", "1000000000", "1000000000.01", "1000000000.0123456789"})
    private double value;

    private BigDecimal[] bigDecimalVal = new BigDecimal[1];
    private double[] doubleVal = new double[1];

    @Override
    protected void setUp() throws Exception {
        bigDecimalVal[0] = BigDecimal.valueOf(value);
        doubleVal[0] = value;
    }


    public void timeDouble(int reps) {
        double dummy = 0;
        for (int i = 0; i < reps; i++) {
            int v = i / (reps + 1);
            dummy = doubleVal[v] * doubleVal[v];
        }
        doubleVal[0] = dummy;
    }

    public void timeBigDecimal(int reps) {
        BigDecimal dummy = BigDecimal.ZERO;
        for (int i = 0; i < reps; i++) {
            int v = i / (reps + 1);
            dummy = bigDecimalVal[v].multiply(bigDecimalVal[v]);
        }
        bigDecimalVal[0] = dummy;
    }

    public static void main(String[] args) {
        Runner.main(DoubleVsBigDecimalBenchmark.class, new String[]{});
    }

}

Прогнав тест, становится видно, что для небольших чисел и чисел с небольшой дробной частью BigDecimal работает в 5 раз медленней, а для больших чисел либо чисел с большим количеством символов после запятой в 20 раз.

Следует заметить, что JVM хитрая штука, и постоянно занимается оптимизацией кода, что сказывается на результатах бенчмарка, по-этому иногда надо выкручиваться. Например, в бенчмарке DoubleVsBigDecimalBenchmark используется массив и странный способ инициализации переменной v нулем.

В последнее время мне удалось поработать с GWT, итак за и против.

За GWT:

1. Не нужно учить Javascript. Если вы гуру и не одну собаку съели педаля на жабе и принципиально не хотите учить javascript, то gwt в самый раз.
2. Все приимущества Java. Статическая типизация, IDE, дебаггер, рефакторинги, анализаторы кода – все к вашим услугам.
3. Один код на сервере и на клиенте. Код написанный для сервера может быть скомпилирован в javascript и работать на клиенте.
4. Google. GWT разрабатывается, не командой волосатых программистов из гаража, а корпорацией google и используется в проектах компании.
5. Кросс-браузерность.Разрабатывая с помощью GWT можно не беспокоится про кросс-браузерность, клиент компилируется в поддерживаемый современными браузерами код.

Против GWT:

1. Java == No fun. Писать на жаве UI неудобно. Количество строк кода в результате – огромно.
2. Медленно. Скорость разработки на GWT на порядок меньше чем с помощью javascript’a. В большинстве из-за количества кода, которое приходится писать. Скорость работы GWT-овского компилятора уничтожает желание использовать GWT.
3. Отсутсвие подходов к написанию программ с помощью GWT. Best practices и подходы по написанию программ с помощью GWT постоянно меняются. RequestFactory и Activity Framework до сих пор сырые.

ZooKeeper – это распределенный, open-source сервис координнации для расспределенных приложений. Он предоставляет низкоуровневый API, с помощью которого приложения могут реализовать высокоуровневые сервисы для координации и синхронизации процессов в расспредеелнной системе.

API ZooKeeper’a черезвычайно прост. Распределенные процессы могут координироваться между собой с помощью расшаренной на всех клиентов иерархии znode’ов, организация которых по структуре похожа на файловую систему. Как и в файловой системе каждый znode идентифицируется своим уникальным путем, вида /node1/stuff/logs. В отличии от привычной файловой системы, каждый znode может быть корневым узлом для других znode’ов. Если говорить в терминах файловой системы: файл может выступать в роли директории. Znode’ы версионируются и ZooKeeper позволяет “смотреть”(watch) за изменениями в ноде. Как только znode’a изменяется, клиент, смотрящий за нодой, получает пакет, который говорит что в ноде произошло измение.

ZooKeeper реплицируемый и обрабатывает команды в строгой последовательности. Первое намного повышает его надежность, второе дает возможность пользователям разрабатывать примитивы синхронизации для распределенных систем. Все данные ZooKeeper держит в памяти, что позволяет ему работать черезвычайно быстро. Разработчики дауют нам следующие гарантии:

• Sequential Consistency – Обновления от клиента будут применены в порядке в котором они были отправены
• Atomicity – Изменения от клиента атомарны, они либо исполняются либо нет
• Single System Image – Клиент получет одинаковый набор znode’ов вне зависимости от того к какому серверу он подключен
• Reliability – Как только измение было применено, состояние будет неизменно до тех пор пока клиент не перетрет его
• Timeliness – Состояние системы для клиент гарантированно up-to-date с некоторой погрешностью по времени

Однако, нужны ли нам автоматизированные тесты, если у нас в команде есть группа тестировщиков или QA-инженеров, способных обеспечить качество проекта на должном уровне? Я считаю, что автоматизированные тесты дополняют QA-инжеров, избавляя их от ненужной рутинной работы. Зачем тратить время на регрессию, если ее может сделать за тебя компьютер?

К тому же тесты гарантируют, что ошибка не повторится вновь, а если и повторится, команда узнает о ней в скором времени. При этом разрабочики могут безболезненно вносить изменения в существующий код и добавлять новые фичи, зная что поломка может быть выявлена на этапе разработки. В то же время QA-инженер может занятся более интересными вещами, такими как usability, security тестирование, и поиск хитрых, заковыристых багов.

Однако у тестов есть свои недостатки. Прежде всего, их нужно кому-то писать. Т.е. если у нас в команде нет людей, знакомых с автоматизацией, то нужно либо дать им возможность ошибаться и научиться, либо искать экспертов на стороне. Так же тесты требуют настройки инфраструктуры. Настройка билд конфигурации, развертывание серверов для запуска тестов и параллельный запуск тестов могут оказаться нетривиальными и потребовать времени и усилий.

Нужно понимать, что тесты, как и любой код другой код требуют поддержки. Если у нас в приложении изменилась функциональность, то в тесты на эту функциональность придется вносить изменения, а возможно даже и переписывать.

Несмотря на недостатки тестов, если удастся взрастить команду, которая может успешно автоматизировать приемочное тестирование, это будет выгодно всем. Бизнес получает более качественный продукт в меньшие сроки, сотрудники же занимаются интересными вещами, траятя свое время эффективно.

Первый вопрос который стоит перед командой при написании автоматизированных тестов – как мы будем запускать тесты? Точнее – какой фреймворк для тестирования нам выбрать? Если мы программируем на Java, выбор не велик. JUnit или TestNG.

Помню, когда мы начинали заниматься функциональными тестами на нашем последнем проекте, мы долго решали что же выбрать. Победил TestNG. Легкость создания test suit’a, возможность группировать тесты и запускать их параллельно – вот что определило наш выбор. В тот момент я подписался на интересные блоги и рассылки связанные с тестированием, и через некоторое время обнаружил, что JUnit активно развивается и догоняет TestNG по функциональности, при этом превосходит его в продуманности API.

Так, в JUnit начиная с версии 4.8 появился механизм для метки и группировки тестов, под названием Categories.

Процесс группировки тестов в JUnit до появления категорий можно стравнить с организацией писем в Microsoft Outlook. Мы можем группировать тест методы в классы, а классы в пакеты.

Теперь, с помощью категорий, группировка тестов похожа на группировку писем в GMail.

Представляются категории в виде java интерфейсов, что дает приемущества по сравнению с группами в TestNG. В отличии от строковых констант коими являются группы, мы можем переименовывать категории в IDE, плюс есть возможность построить йерархии категорий, что дает нам гибкость в организации тестов.

Предположим, что у нас есть 4 категории: SmokeTest говорит что наш тест - смоук тест, BrokenTest показывает, что тест тестирует поломанный функционал, а с помощью FastTest и SlowTest мы помечаем тесты по времени выполнения.

1
2
3
4
5
6
7

public interface SmokeTest {}

public interface BrokenTest {}

public interface FastTest {}

public interface SlowTest {}

Допустим у нас есть два тест класса с помеченными методами:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

@Category(SmokeTest.class)
public class SomeSmokeTests {
  @Test
  @Category(FastTest.class)
  public void someFastTest() {
    // test something
  }

  @Test
  @Category(SlowTest.class)
  public void someReallySlowTest() {
    // test something
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class SomeTestCase {

  @Test
  @Category({SmokeTest.class, FastTest.class})
  public void fastSmokeTest() {
    // test something
  }

  @Test
  @Category({SmokeTest.class, FastTest.class, BrokenTest.class})
  public void fastBrokenSmokeTest() {
    // test something
  }

  @Test
  @Category({SmokeTest.class, SlowTest.class})
  public void slowSmokeTest() {
    // test something
  }

}

С помощью категорий мы можем построить test suite, который будет запускать быстрые smoke тесты с работающим функционалом:

1
2
3
4
5

@RunWith(Categories.class)
@IncludeCategory(SmokeTest.class, FastTest.class)
@ExcludeCategory(BrokenTest.class)
@SuiteClasses(SomeSmokeTests.class, SomeTestCase.class)
public class RunFastSmokeTestCases {}

Правда, с увеличением количества классов в suite, конфигурация получаеться громоздкой, а куча аннотаций никак не добавляет читабельности коду.

К счастью эта проблема решается с помощью библиотеки [junit-suite-configurator][1]. Так выглядит конфигурация эта же конфигурация написанная с ее помощью:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

@RunWith(Suite.Configuration.class)
public class Suite {

  public static class Configuration extends AbstractConfiguration {

  public Configuration(Class testClass) {
    super(testClass);
  }

  @Override
  protected void configure() {
    run(classes(SomeSmokeTests.class, SomeTestCase.class))
      .filter(includeCategories(SmokeTest.class, FastTest.class))
      .filter(excludeCategories(BrokenTest.class))
        .applyRule(new Rule1())
    ).invokeIn(singleThread());
  }
 }
}