Vor einiger Zeit wurde es möglich, auf die Go-Sprache zu achten, und die Veröffentlichung "Passport Control oder Wie man eineinhalb Gigabyte auf 42 MB komprimiert" wurde veröffentlicht . Der Artikel beschreibt kurz, aber informativ eine Testaufgabe zur Entwicklung eines Dienstes zur Überprüfung der russischen Passnummern auf ihre Anwesenheit in der Liste ungültiger Pässe. Die Hauptanforderungen für die Implementierung sind die Geschwindigkeit der Überprüfung und die Verfügbarkeit des Dienstes.
Nachdem ich den Artikel gelesen hatte, entschied ich selbst, dass Sie auf dieser praktischen Aufgabe Ihr Go-Lernen aufbauen können. In der Tat ist das Problem der Überprüfung ungültiger Pässe interessant, obwohl sie abgedroschen sind, und da Leistungsanforderungen hier Priorität haben, wäre die Implementierung in Go hier durchaus angemessen.
Darüber hinaus geht der oben erwähnte Artikel auf die Probleme einer effizienten Organisation von Bit-Arrays (Bitmaps) aus Sicht des Speichers ein. Und dieses Thema ist sehr relevant und in verschiedenen angewandten Lösungen gefragt, beispielsweise in Form von Bitmap-Indizes für ein DBMS.
Infolgedessen Folgendes: Es besteht der Wunsch, die für sich neue Go-Sprache zu betrachten, es gibt ein interessantes Problem in Form der Organisation und Verwendung von Bitmap (natürlich in Go), es gibt eine praktische Aufgabe welche diese beiden Ziele erarbeitet werden können. Wenn Sie interessiert sind, fahren Sie fort.
Was als Rohdaten
Die eigentliche Aufgabe der Überprüfung von Pässen basiert auf der primären Liste ungültiger Pässe, die auf der Website des Innenministeriums der Russischen Föderation angezeigt wird. Dort können Sie auch die Passnummer manuell überprüfen. Sie können die gesamte Liste als gepacktes Archiv mit einer Größe von 460 MB von der Website herunterladen. Im entpackten Zustand erhalten Sie eine Liste mit einer Größe von ca. 1,5 GB, die als einzelne CSV-Datei mit zwei Spalten dargestellt wird: Serien- und Passnummer.
Bis heute enthält diese CSV-Datei etwa 132 Millionen Passnummern. Die Datei enthält jedoch auch fehlerhafte Zahlen, die nicht eindeutig identifiziert werden können. Beispielsweise werden nicht alle 4 Ziffern für eine Reihe oder alle 6 Ziffern für eine Zahl nicht angegeben. Möglicherweise gibt es alphabetische Reihen.
4- 6- , , , . , , , .. , .
Go , , .
–
. , . , – . , 10 000 ( 0 9999), 1 000 000 ( 0 999998, .. 000001). , ( , G), .. 10 000 bitmap, bitmap 15 625 uint64.
15 625?
, 1 000 000 125 000 , , , 15 625 ( x86-64)
, , 1.25 , 10 000 bitmap. , .. . – , 10 000 bitmap 3 300 ( ).
–
– , , bitmap , . , , , ..15 625 1 000 000 . , . , .
bitmap – roaring bitmap.
–
, , . Pilosa.
Pilosa – . Pilosa , , . – () .
, , , .. Pilosa. , Pilosa, .. (binary matrices).
Pilosa , Go, «» Go, . « ». Pilosa.
, :
. - , – Pilosa.
http . GET , POST, json. .
.
, , ..
, , , Docker .
, . .
. , Go « » , , , , . , , , Go . Go , , , Linux, Mac OS Windows, . , , uint16 uint64.
Go, , , .
, , GitHub. Go, Go «». roaring bitmap Pilosa , .
, , . , , , , . , - API . – , , . . , .. , . , .
API
, , GET
http://localhost:8080/passport?series=8003&number=011384
html json , , ContentType "application/json" .
"application/json":
[{
"series": "8003",
"number": "011384",
"status": "non-valid"
}]
status “valid” “non-valid”
json POST , status:
http://localhost:8080/passport
[
{
"series": "4050",
"number": "039589"
},
{
"series": "5203",
"number": "257719"
},
{
"series": "5000",
"number": "347024"
},
{
"series": "2507",
"number": "857721"
},
{
"series": "2507" ,
"number": "857728"
}
]
, status. - , , ( 100)
i7 7- 16 Gb , Windows Pro WSL2(Windows Subsystem for Linux), Docker Desktop For Windows. , , : Windows, WSL url ApacheBench 1000- , 100 . , Go (benchmark), , .
:
( );
;
.
bitmap
1.5 30 , . , , .
, «» , 1.25 Gb ( ), 440 . - , .. . , .
(1000 100 ), , «Time per request» 0.1 ms , , .
, :
30 ;
440 ;
0.10 ms.
, .
roaring bitmap
1.5 , bitmap. 44 (!) , , , . 0.18ms, , , , .
roaring bitmap:
, bitmap :
90 ;
44 ;
0.18 ms.
. , , .. roaring bitmap, 64- C (Croaring).
Pilosa
Pilosa , . , . , Pilosa Windows, , , . , « ». , Pilosa docker- Windows – .
Pilosa , , .. .
Pilosa – 1 1000 . 132 .
Pilosa WSL2, .
Pilosa 4 , , , , , , , , .. .
Pilosa , , , , .. Pilosa bitmap roaring bitmap.
– 0.5 ms .
Pilosa:
240 ;
;
0.5 ms.
, Pilosa , , , . , (timestamp), Pilosa.
, Go . . , . – Go .
, - , , Go.
roaring bitmap . bitmap bitmap, roaring bitmap.