Highload Cupに適したソリューションを作成する方法ですが、トップに到達するには十分ではありません

先週、HighLoad Cupコンテストは終了しました。そのアイデアは、旅行者のWebサイトにHTTPサーバーを実装することでした。 5日間でGoの決定をどのように書くかについては、295の全体的な分類で52の地位をもたらすでしょう。

タスクの説明

ユーザーAfinogenは彼の記事ですでにコンテストの条件を説明していますが、便宜上、簡単に繰り返します。 サーバーは、旅行者のWebサイト用のAPIを実装し、旅行者（ユーザー）、アトラクション（場所）、訪問（訪問）の3種類のエンティティをサポートする必要があります。 APIは、新しいエンティティをデータベースに追加し、それらを受信して​​更新し、それらに対して2つの操作を実行する機能を提供する必要があります-平均関心点（avg）を取得し、旅行者が訪問した場所（訪問）を取得します。 これらの各操作には、応答を作成するときに考慮する必要がある一連のフィルターもあります。 たとえば、APIを使用すると、2010年4月1日から18歳から25歳までの男性の観光の平均評価を取得できます。 これにより、実装がさらに困難になります。

念のため、APIの簡単な正式な説明を行います。

• GET / <entity> / <id>はエンティティデータを取得します
• 更新するPOST / <entity> / <id>
• POST / <entity> /作成する新規
• GET / users / <id> / visitsでユーザーの訪問リストを取得します
• GET / locations / <id> / avgにより、関心のある平均地点を取得します

データを保存する方法

問題の状態を熟知しているすべての人に生じる最初の質問は、データの保存方法です。 多くの（私のように）最初に、メモリに収まらず、松葉杖を作れない大量のデータを期待して、ある種のデータベースを使用しようとしました。 ただし、このアプローチはランキングで高い位置を与えませんでした。 事実、コンテストの主催者はデータのサイズに非常に民主的に近づいたため、ストレージ構造を最適化せずに、すべてのデータをメモリに簡単に保存できました。 合計で、約100万人の旅行者、10万人のアトラクション、1,000万人の訪問が評価シェルにあり、各エンティティの識別子は1から順になりました。一見すると、ボリュームが大きいように見えますが、データの保存に使用できる構造のサイズを見るとまた、構造内の線のサイズによって、平均してサイズが大きすぎないことがわかります。 以下に引用したフィールドの構造とサイズ：

type Visit struct { // overall 40 bytes Id int // 8 bytes Location int // 8 bytes User int // 8 bytes VisitedAt int // 8 bytes Mark int // 8 bytes } type User struct { //overall 133 bytes Id int // 8 bytes Email string // 22 bytes + 16 bytes FirstName string // 12 bytes + 16 bytes LastName string // 18 bytes + 16 bytes Gender string // 1 byte + 16 bytes Birthdate int // 8 bytes } type Location struct { // overall 105 bytes Id int // 8 bytes Place string // 11 bytes + 16 bytes Country string // 14 bytes + 16 bytes City string // 16 bytes + 16 bytes Distance int // 8 bytes }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「平均文字列長」+「文字列オブジェクトのサイズ」の形式で構造体の文字列サイズを指定しました。 各構造の平均サイズにオブジェクトの数を掛けると、純粋にデータストレージに必要なのは約518 MBだけです。 最大4 GBのローミングが可能であれば、それほど多くはありません。

最大のメモリ消費は、一見奇妙ではないため、シェル自体ではなく、データの読み込み段階で発生します。 実際には、最初はすべてのデータが.zipアーカイブにパックされており、最初の10分でサーバーはこれらのデータをさらに処理するためにアーカイブからこのデータをダウンロードする必要があります。 解凍されたアーカイブの重量は200 MB、解凍後のファイルの重量は1.5 GBです。 正確なデータ処理と、より積極的なガベージコレクターの設定がなければ、すべてのデータの読み込みに失敗しました。

2番目のポイントは非常に重要でしたが、誰もがすぐに気づいたわけではありません。サーバーのシェル化が行われたため、原則として競合状態が解決できませんでした。 サーバーのテストは3段階で行われました。最初の段階では、オブジェクトを受信して​​avg（平均スコア）およびvisits（受信したユーザーの訪問）メソッドを呼び出すGETリクエストが送信されました。データ）そして最後の段階で、GET要求が再度送信され、新しいデータに対してのみ、より大きな負荷がかかりました。 GET要求とPOST要求は厳密に分離されているため、ストリーム同期プリミティブを使用する必要はありませんでした。

したがって、これらの2つのポイントを考慮し、各エンティティのオブジェクトのIDが1から始まる順番になったことを覚えていれば、結果としてすべてのデータを次のように保存できます。

 type Database struct { usersArray []*User locationsArray []*Location visitsArray []*Visit usersMap map[int]*User locationsMap map[int]*Location visitsMap map[int]*Visit }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すべてのオブジェクトは、配列のサイズが十分であれば、型に対応する配列に配置されます。 オブジェクトのIDが配列のサイズよりも大きい場合、対応する辞書に収まります。 今、最終的にはデータがまったく変更されていないことを知って、辞書が不要であることを理解しましたが、その後は保証されませんでした。

指数

すぐに、avgメソッドとvisitsメソッドをすばやく実装するために、User構造体とLocation構造体だけでなく、ユーザーの訪問IDと関心ポイントを構造体自体とともにそれぞれ保存する必要があることが明らかになりました。 その結果、Visitsフィールドを追加しました。これは、これら2つの構造に通常の配列であるため、このユーザー/アトラクションに関連付けられたすべてのVisit構造をすばやく見つけることができました。

テストの過程で、標準ライブラリの「コンテナ/リスト」を使用することも考えましたが、このコンテナのデバイスを知ると、要素へのアクセス速度とメモリの両方が常に失われることがわかりました。 その唯一のプラス-ユーザーへの訪問の比率は約10対1であるため、任意のポイントへの迅速な削除/追加機能はこのタスクにとってそれほど重要ではありません。ロケーションおよびユーザー構造のVisitコンテナーは約10と想定できます。 10単位の配列の先頭から要素を削除することは、一般的な背景に対してそれほど高価ではなく、頻繁な操作ではありません。 メモリについては、次のコードで消費量を説明できます。

 package main import ( "fmt" "runtime" "runtime/debug" "container/list" ) func main() { debug.SetGCPercent(-1) runtime.GC() m := &runtime.MemStats{} runtime.ReadMemStats(m) before := m.Alloc for i:=0;i<1000;i++ { s := make([]int, 0) for j:=0;j<10;j++ { s = append(s, 0) } } runtime.ReadMemStats(m) fmt.Printf("Alloced for slices %0.2f KB\n", float64(m.Alloc - before)/1024.0) runtime.GC() runtime.ReadMemStats(m) before = m.Alloc for i:=0;i<1000;i++ { s := list.New() for j:=0;j<10;j++ { s.PushBack(1); } } runtime.ReadMemStats(m) fmt.Printf("Alloced for lists %0.2f KB\n", float64(m.Alloc - before)/1024.0) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは次の出力を提供します。

スライスに割り当て117.19 KB

リストに割り当て343.75 KB

このコードは、1000の配列と1000のリストを作成し、10の要素で埋めます。これは平均訪問数です。 要素を追加すると、8番目の要素で16個の要素に拡張され、それにより必要以上に多くのメモリが消費されるため、配列には10という数字が不適切です。 結果によると、リストの各要素が次の前の要素とリスト自体へのポインタを格納するため、スライスを使用したソリューションが消費するメモリが3分の1であることがわかります。これは理論と一致します。

ファイナルに達した他のユーザーは、さらにいくつかのインデックスを作成しました。たとえば、visitsメソッドのカントリーインデックスです。 これらのインデックスは、おそらくソリューションを高速化しますが、ユーザーの訪問を保存し、このオブジェクトに関する情報とともに関心のある場所への訪問を保存するほどではありません。

図書館

httpサーバーを実装するための標準ライブラリは非常に使いやすく、十分に分散されていますが、速度に関しては、誰もがfasthttpを推奨しています。 したがって、ロジックを実装した後の最初のこととして、標準のhttpサーバーを破棄し、fasthttpに置き換えました。 これらの2つのライブラリには異なるAPIがありますが、置き換えはまったく苦労しませんでした。

さらに、標準のJSONエンコード/デコードライブラリが代わりに使用されました。 easyjsonを選んだのは、優れた速度/メモリデータを示し、「エンコード/ json」APIに似ていたためです。 Easyjsonは、データ構造ごとに独自のパーサーを生成します。これにより、このような印象的な結果を表示できます。 唯一のマイナスは、少数の設定です。 たとえば、タスクにリクエストがあり、フィールドの1つが欠落しているためにエラーが発生しますが、easyjsonはそのようなフィールドを静かにスキップしたため、パーサーのソースコードにアクセスする必要がありました。

その他の最適化

POSTメソッドを除くすべてのAPIメソッドは追加のメモリを使用せずに実装されたため、ガベージコレクタを無効にすることにしました-とにかく、十分なメモリがある場合、それを駆動するのはなぜですか？

要求ルーティングも書き直されました。 各要求は1文字で決定され、文字列比較を保存できます。 学校の最適化。

結果

競技会の最後の5日間で、そのような競技会に参加した経験が全くないので、295人の参加者のうち52位になったソリューションをGoに書きました。 残念なことに、決勝に行く前に私は少しも持っていませんでしたが、一方で、決勝に値するライバルが集まったので、タスクのデータと条件が変わらなかったという事実のために、私が高く上がる可能性は低いです。

ソリューションを備えたGithub