🙌🏼 🤱🏻 🙆 Highload Cup 2017または9位の歴史に関する5つのコペック ⏱️ 👋🏽 🧀

Higload Cupについては既にいくつかの記事がありますので、それが何であったかについては書きません。あなたが見逃した人は、「Highload Cup 2017での13位の歴史」で読むことができます。

また、自分の観点から、自分自身を繰り返さず、興味深い解決策を共有しないようにします。カットの下：

データ構造について少し
定義でのJSONの解析
URIエスケープ
UTFデコード
HTTPサーバー
ネットワーク調整

そして多くのコード。

自転車

net / httpとencoding / jsonを使用してGoで最初のバージョンを作成しました。そして、彼女は2,000 RPSに行きました。その後、net / httpはfasthttpに、encoding / jsonはeasyjsonに置き換えられました。この構成により、私はそもそも寝ることができましたが、午前中はすでに3位でした。ここでジレンマが発生しました：Goでコードを最適化するか、C ++ですぐに記述して、ナノ秒が重要な場合に、より柔軟なツールを最終段階に近づけます。

2番目のオプションを選択しましたが、システムライブラリのみを使用してHTTPサーバーを記述することにしました。この場合、不必要なものやJSONパーサー/シリアライザーに時間を浪費しません。また、最初はlibnumaとSSE 4.2のコマンドを使用したかったのですが、先を見越して、最長の操作はソケットへの書き込みでしたので、それには至りませんでした。

以下のすべてのコードは「プロダクション対応」ではありません。コンテストの特定のテストケース用に作成されたもので、オーバーフローに対する保護はありません。

データ構造について少し

合計3つのテーブルがあります。

戦車のカートリッジには、1,000,000を少し超えるユーザー、約80万の場所、および10,000,000を超える訪問がありました。

サービスは、IDによってこれらのテーブルから要素を返します。最初の望みはそれらをマップに追加することでしたが、幸いなことにIDは実質的にギャップなしであることが判明したため、連続配列を割り当ててそこに要素を格納できます。

また、サービスは集約された情報、すなわち

ユーザーがアクセスした場所のリストを、アクセスした日付順にソートして返します
場所の平均を返す

これを効率的に行うには、インデックスが必要です。

各ユーザーに対して、 std::set<uint32_t, visitsCmp>

を入力しましたvisitsCmp

使用visitsCmp

と、訪問の日付順にソートして訪問のIDを保存できvisitsCmp

。すなわち出力時には、訪問を別の配列にコピーしてソートする必要はありませんが、すぐにシリアル化された形式でバッファに出力できます。次のようになります。

 struct visitsCmp { Visit* visits; bool operator()(const uint32_t &i, const uint32_t &j) const { if (visits[i].VisitedAt == visits[j].VisitedAt) { return visits[i].Id < visits[j].Id; } else { return visits[i].VisitedAt < visits[j].VisitedAt; } }

ロケーションの平均評価の場合、順序は重要ではないため、各ロケーションについて、 std::unordered_set<uint32_t>

タイプのフィールドに入力しました。これには、特定のロケーションへの訪問が含まれます。

訪問を追加/変更するたびに、影響を受けるインデックスのデータを更新することを忘れないでください。コードでは、次のようになります。

 bool DB::UpdateVisit(Visit& visit, bool add) { if (add) { memcpy(&visits[visit.Id], &visit, sizeof(Visit)); //     users[visit.User].visits->insert(visit.Id); locations[visit.Location].visits->insert(visit.Id); return true; } //    ,      if (visit.Fields & Visit::FIELD_VISITED_AT) { users[visits[visit.Id].User].visits->erase(visit.Id); visits[visit.Id].VisitedAt = visit.VisitedAt; users[visits[visit.Id].User].visits->insert(visit.Id); } if (visit.Fields & Visit::FIELD_MARK) { visits[visit.Id].Mark = visit.Mark; } //               if (visit.Fields & Visit::FIELD_USER) { users[visits[visit.Id].User].visits->erase(visit.Id); users[visit.User].visits->insert(visit.Id); visits[visit.Id].User = visit.User; } // ,   location if (visit.Fields & Visit::FIELD_LOCATION) { locations[visits[visit.Id].Location].visits->erase(visit.Id); locations[visit.Location].visits->insert(visit.Id); visits[visit.Id].Location = visit.Location; } return true; }

一般に、インデックスの要素の平均数は10、最大は150です。したがって、配列を作成するだけで、データの局所性が向上し、変更が大幅に遅くなることはありません。

定義でのJSONの解析

私がC / C ++用に見つけたこれらのJSONパーサーは、構文解析を使用してツリーを構築しますが、これらは不要な割り当てであり、高負荷では受け入れられません。データを変数に直接追加するものもありますが、この場合、JSONオブジェクトに含まれるフィールドを見つけることはできません。これは重要です。オブジェクトを変更するとき、JSONにはフィールドの完全なセットはなく、必要なフィールドのみが含まれているためです変更する。

サービスを解析するJSONは非常にシンプルで、既知のフィールドのみを含む単一レベルのオブジェクトであり、行内に引用符はありません。ユーザーJSONは次のようになります。

 { "id": 1, "email": "robosen@icloud.com", "first_name": "", "last_name": "", "gender": "m", "birth_date": 345081600 }

すなわちメタでパーサーを書くのはとても簡単です

 bool User::UmnarshalJSON(const char* data, int len) { JSON_SKIP_SPACES() JSON_START_OBJECT() while (true) { JSON_SKIP_SPACES() //   if (data[0] == '}') { return true; //   } else if (data[0] == ',') { data++; continue; //  "id" } else if (strncmp(data, "\"id\"", 4) == 0) { data += 4; JSON_SKIP_SPACES() JSON_FIELDS_SEPARATOR() JSON_SKIP_SPACES() //       Id JSON_LONG(Id) //  ,   Id   JSON Fields |= FIELD_ID; //  "lastname" } else if (strncmp(data, "\"last_name\"", 11) == 0) { data += 11; JSON_SKIP_SPACES() JSON_FIELDS_SEPARATOR(); JSON_SKIP_SPACES() //       Id JSON_STRING(LastName) //  ,   LastName   JSON Fields |= FIELD_LAST_NAME; } else if (strncmp(data, "\"first_name\"", 12) == 0) { data += 12; JSON_SKIP_SPACES() JSON_FIELDS_SEPARATOR() JSON_SKIP_SPACES() JSON_STRING(FirstName) Fields |= FIELD_FIRST_NAME; } else if (strncmp(data, "\"email\"", 7) == 0) { data += 7; JSON_SKIP_SPACES() JSON_FIELDS_SEPARATOR() JSON_SKIP_SPACES() JSON_STRING(EMail) Fields |= FIELD_EMAIL; } else if (strncmp(data, "\"birth_date\"", 12) == 0) { data += 12; JSON_SKIP_SPACES() JSON_FIELDS_SEPARATOR() JSON_SKIP_SPACES() JSON_LONG(BirthDate) Fields |= FIELD_BIRTH_DATE; } else if (strncmp(data, "\"gender\"", 8) == 0) { data += 8; JSON_SKIP_SPACES() JSON_FIELDS_SEPARATOR() JSON_SKIP_SPACES() JSON_CHAR(Gender) Fields |= FIELD_GENDER; } else { JSON_ERROR(Unknow field) } } return true; }

メタ言語コマンドを置き換えるものを決定するだけで、パーサーの準備ができています。

 #define JSON_ERROR(t) fprintf(stderr, "%s (%s:%d)\n", #t, __FILE__, __LINE__); return false; #define JSON_SKIP_SPACES() data += strspn(data, " \t\r\n") #define JSON_START_OBJECT() if (data[0] != '{') { \ JSON_ERROR(Need {}) \ } \ data++; #define JSON_FIELDS_SEPARATOR() if (data[0] != ':') { \ JSON_ERROR(Need :) \ } \ data++; #define JSON_LONG(field) char *endptr; \ field = strtol(data, &endptr, 10); \ if (data == endptr) { \ JSON_ERROR(Invalid ## field ## value); \ } \ data = endptr; #define JSON_STRING(field) if (data[0] != '"') {\ JSON_ERROR(Need dquote); \ } \ auto strend = strchr(data+1, '"'); \ if (strend == NULL) { \ JSON_ERROR(Need dquote); \ } \ field = strndup(data+1, strend - data - 1); \ data = strend + 1; #define JSON_CHAR(field) if (data[0] != '"') {\ JSON_ERROR(Need dquote); \ } \ if (data[2] != '"') {\ JSON_ERROR(Need dquote); \ } \ field = data[1]; \ data += 3;

URIエスケープ

ユーザーが訪問した場所のリストには、国別のフィルターがあり、URIエンコードされた行の形式にすることができます： /users/1/visits?country=%D0%A0%D0%BE%D1%81%D1%81%D0%B8%D1%8F

。 StackOverflowでのデコードについては、+をスペースに置き換えるサポートを追加したすばらしいソリューションが見つかりました。

 int percent_decode(char* out, char* in) { static const char tbl[256] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }; char c, v1, v2; if (in != NULL) { while ((c = *in++) != '\0') { switch (c) { case '%': if (!(v1 = *in++) || (v1 = tbl[(unsigned char) v1]) < 0 || !(v2 = *in++) || (v2 = tbl[(unsigned char) v2]) < 0) { return -1; } c = (v1 << 4) | v2; break; case '+': c = ' '; break; } *out++ = c; } } *out = '\0'; return 0; }

UTFデコード

JSONオブジェクトの文字"\u0420\u043E\u0441\u0441\u0438\u044F"

の形式は、 "\u0420\u043E\u0441\u0441\u0438\u044F"

です。一般的なケースでは、これは恐ろしいことではありませんが、国との比較があるため、1つのフィールドをデコードできる必要があります。 percent_decode

をpercent_decode

として、Unicodeの場合にのみ、 \u0420

を2バイト0x0420に\u0420

するだけでは不十分です。この数値はUTF文字にマップする必要があります。幸いなことに、キリル文字とスペースしかありません。したがって、表を見ると、文字「p」と「p」の間にギャップが1つしかないことがわかります。したがって、オフセットを使用して変換できます。

 void utf_decode(char* in) { static const char tbl[256] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }; char *out = in; while (in[0] != 0) { if (in[0] == '\\' && in[1] == 'u') { uint16_t u = tbl[in[2]] << 12 | tbl[in[3]] << 8 | tbl[in[4]] << 4 | tbl[in[5]]; //  ASCII     if (u < 255) { out[0] = u; out++; } else { uint16_t w; // < '' if (u >= 0x0410 && u <= 0x043f) { w = u - 0x0410 + 0xd090; // >= '' } else { w = u - 0x0440 + 0xd180; } out[0] = w >> 8; out[1] = w; out += 2; } in += 6; } else { out[0] = in[0]; in++; out++; } } out[0] = 0; }

HTTPサーバー

パーサー

HTTPリクエストから、メソッド（GET / POST）、クエリ（パス+パラメーター）、およびPOSTリクエストの場合は本文を取得する必要があります。 POSTリクエストのContent-Lentgthヘッダーを除き、ヘッダーの解析と保存には意味がありませんが、後で判明したように、すべてのリクエストが1回の読み取りに収まるため、これは必要ありません。その結果、このパーサーが得られました。

 ... auto body = inBuf.Data; const char *cendptr; char *endptr; while (true) { switch (state) { case METHOD: body += strspn(body, " \r\n"); if (strncmp(body, "GET ", 4) == 0) { method = GET; body += 4; } else if (strncmp(body, "POST ", 5) == 0) { body += 5; method = POST; } else { state = DONE; WriteBadRequest(); return; } body += strspn(body, " "); cendptr = strchr(body, ' '); if (cendptr == NULL) { WriteBadRequest(); return; } strncpy(path.End, body, cendptr - body); path.AddLen(cendptr - body); cendptr = strchr(cendptr + 1, '\n'); if (cendptr == NULL) { WriteBadRequest(); return; } state = HEADER; body = (char*) cendptr + 1; break; case HEADER: cendptr = strchr(body, '\n'); if (cendptr == NULL) { WriteBadRequest(); return; } if (cendptr - body < 2) { if (method == GET) { doRequest(); return; } state = BODY; } body = (char*) cendptr + 1; case BODY: requst_body = body; doRequest(); return; } ...

ルーティング

ハンドラーは非常に少ないので、メソッドで切り替えるだけで、プレフィックスの検索内で簡単な比較ができます。

 ... switch (method) { case GET: if (strncmp(path.Data, "/users", 6) == 0) { handlerGetUser(); } else if (strncmp(path.Data, "/locations", 10) == 0) { handlerGetLocation(); } else if (strncmp(path.Data, "/visits", 7) == 0) { handlerGetVisit(); } else { WriteNotFound(); } break; case POST: if (strncmp(path.Data, "/users", 6) == 0) { handlerPostUser(); } else if (strncmp(path.Data, "/locations", 10) == 0) { handlerPostLocation(); } else if (strncmp(path.Data, "/visits", 7) == 0) { handlerPostVisit(); } else { WriteNotFound(); } break; default: WriteBadRequest(); } ...

キープアライブ

Yandex.Tankは、カートリッジの「接続」見出しに注意を払いませんが、サーバーからの応答でこの見出しのみを調べます。したがって、接続を切断する必要はありませんが、常にキープアライブモードで作業する必要があります。

ネットワーキング

非同期相互作用を実装するために、epollが自然に選択されました。マルチスレッドアプリケーションでepollを操作するための3つの一般的なオプションを知っています。

N個のスレッドには共通のepollがあり、1つのスレッドはブロッキングモードで受け入れを待機し、クライアントソケットをepollに登録します
N個のスレッドは、N個のepolls + 1つのスレッドがブロッキングモードで受け入れを待機し、クライアントソケットをepollsに登録します。たとえば、RoundRobinを使用します。
各スレッドには独自のエポールがあり、非ブロッキング状態のサーバーソケットと、このスレッドがキャプチャしたクライアントソケットが登録されます。

オプション2と3を比較し、ローカルテストでは3番目のオプションが少し勝ちました。次のようになります。

 void Worker::Run() { int efd = epoll_create1(0); if (efd == -1) { FATAL("epoll_create1"); } connPool = new ConnectionsPool(db); //     epoll auto srvConn = new Connection(sfd, defaultDb); struct epoll_event event; event.data.ptr = srvConn; event.events = EPOLLIN; if (epoll_ctl(efd, EPOLL_CTL_ADD, sfd, &event) == -1) { perror("epoll_ctl"); abort(); } struct epoll_event *events; events = (epoll_event*) calloc(MAXEVENTS, sizeof event); while (true) { auto n = epoll_wait()(efd, events, MAXEVENTS, -1); for (auto i = 0; i < n; i++) { auto conn = (Connection*) events[i].data.ptr; if ((events[i].events & EPOLLERR) || (events[i].events & EPOLLHUP) || (!(events[i].events & EPOLLIN))) { /* An error has occured on this fd, or the socket is not ready for reading (why were we notified then?) */ fprintf(stderr, "epoll error\n"); close(conn->fd); if (conn != srvConn) { connPool->PutConnection(conn); } continue; //      ,    accept } else if (conn == srvConn) { /* We have a notification on the listening socket, which means one or more incoming connections. */ struct sockaddr in_addr; socklen_t in_len; in_len = sizeof in_addr; int infd = accept4(sfd, &in_addr, &in_len, SOCK_NONBLOCK); if (infd == -1) { if ((errno == EAGAIN) || (errno == EWOULDBLOCK)) { continue; } else { perror("accept"); continue;; } } int val = true; if (setsockopt(infd, IPPROTO_TCP, TCP_NODELAY, &val, sizeof(val)) == -1) { perror("TCP_NODELAY"); } event.data.ptr = connPool->GetConnection(infd); event.events = EPOLLIN | EPOLLET; if (epoll_ctl(efd, EPOLL_CTL_ADD, infd, &event) == -1) { perror("epoll_ctl"); abort(); } continue; //    ,      } else { bool done = false; bool closeFd = false; while (true) { ssize_t count; count = read(conn->fd, conn->inBuf.Data, conn->inBuf.Capacity); conn->inBuf.AddLen(count); if (count == -1) { /* If errno == EAGAIN, that means we have read all data. So go back to the main loop. */ if (errno != EAGAIN) { perror("read"); done = true; } else { continue; } break; } else if (count == 0) { /* End of file. The remote has closed the connection. */ done = true; closeFd = true; break; } if (!done) { done = conn->ProcessEvent(); break; } } if (done) { if (closeFd) { close(conn->fd); connPool->PutConnection(conn); } else { conn->Reset(conn->fd); } } } } } }

意思決定を終えた後、私はエポールを放棄し、わずか1,500スレッドの古典的なプリフォークモデルを作成することにしました（Y. Tankは1000以上の接続を開きました）。デフォルトでは、各ストリームはスタック用に8MBを予約します。これにより、1,500 * 8MB = 11.7GBになります。そして、競合の条件に従って、4GB RAMがアプリケーションに割り当てられます。ただし、幸いなことに、 pthread_attr_setstacksize

関数を使用してスタックサイズを縮小できます。最小スタックサイズは16KBです。なぜならスレッド内のスタックに大きなものは何もありません。スタックサイズ32 KBを選択しました。

  pthread_attr_t attr; pthread_attr_init(&attr); if (pthread_attr_setstacksize(&attr, 32 * 1024) != 0) { perror("pthread_attr_setstacksize"); } pthread_create(&thr, &attr, &runInThread, (void*) this);

スレッドは、現在1,500 * 32KB = 47MBを占有しています。

ローカルテストでは、そのようなソリューションはエポールよりもわずかに悪い結果を示しました。

ネットワーク調整

プロファイリングには、 gperftoolsを使用しました。これは、最も長い操作がstd::to_string

であることを示しstd::to_string

。これはかなり迅速に修正されましたが、現在では主な時間はepoll_wait

、 write

およびwritev

操作でした。私はメダリストに入る価値があるかもしれない最初のものに注意を払わなかった、と私はwrite

ために何をすべきかを研究し始め、同時にaccept

ための加速を見つけました

TCP_NODELAY

デフォルトでは、ネットワーク最適化のカーネルは小さなデータを1つのパケット（ Neiglアルゴリズム）に接着します。この場合、サービスは常に小さなパケットを送信するため、できるだけ早く送信する必要があるため、これは私たちだけに干渉します。オフにします：

  int val = 1; if (setsockopt(sfd, IPPROTO_TCP, TCP_NODELAY, &val, sizeof(val)) == -1) { perror("TCP_NODELAY"); }

TCP_DEFER_ACCEPT

このオプションを使用すると、TCPハンドシェイクでクライアントからのACKを待たずに応答を送信できます。

  int val = 1; if (setsockopt(sfd, IPPROTO_TCP, TCP_DEFER_ACCEPT, &val, sizeof(val)) == -1) { perror("TCP_DEFER_ACCEPT"); }

TCP_QUICKACK

念のため、このオプションを設定しますが、その動作原理は完全には理解されていません。

  int val = 1; if (setsockopt(sfd, IPPROTO_TCP, TCP_QUICKACK, &val, sizeof(val)) == -1) { perror("TCP_QUICKACK"); }

SO_SNDBUFおよびSO_RCVBUF

バッファサイズもネットワーク転送速度に影響します。デフォルトは約16KBです。カーネルの設定を変更せずに、約400KBに増やすことができますが、サイズは問いません。

  int sndsize = 2 * 1024 * 1024; if (setsockopt(sfd, SOL_SOCKET, SO_SNDBUF, &sndsize, (int) sizeof(sndsize)) == -1) { perror("SO_SNDBUF"); } if (setsockopt(sfd, SOL_SOCKET, SO_RCVBUF, &sndsize, (int) sizeof(sndsize)) == -1) { perror("SO_RCVBUF"); }

このサイズでは、壊れたパケットとタイムアウトが現れました。

accept4

通常、 accept

関数は、クライアントソケットと2つのfcntl

呼び出しを取得してfcntl

フラグを設定するために使用されます。 3つのシステムコールの代わりに、 accept4

を使用する必要があります。これにより、最後の引数で1つのシステムコールにSOCK_NONBLOCK

フラグを渡すことで同じことができます。

  int infd = accept4(sfd, &in_addr, &in_len, SOCK_NONBLOCK);

あいお

IOを非同期で使用する別の方法。 Aioにはlio_listio

関数があり、複数のwrite/read

lio_listio

を1つのシステムコールに結合することができます。これにより、カーネルスペースへの切り替えの遅延を削減できます。

アイデアはシンプルでした。複数のイベントが同時にエロールされるため、すべてのクライアントに回答を準備して同時に送信できます。残念ながら、改善はありませんでした。拒否しなければなりませんでした。

epoll_wait（....、-1）-> epoll_wait（....、0）

判明したように、これは罰金を約30秒減らすことができる重要な機能でしたが、残念ながら、私はこれが遅すぎることを知りました。

追記

コンテストの主催者に感謝しますが、すべてが順調に進みませんでした。とても刺激的で有益でした。

Highload Cup 2017または9位の歴史に関する5つのコペック

自転車