Há algum tempo, foi possível prestar atenção à linguagem Go e surgiu a publicação "Controle de Passaportes, ou Como Comprimir Um Gigabyte e Meio para 42 Mb" . O artigo descreve resumidamente, mas de forma informativa, uma tarefa de teste para desenvolver um serviço para verificar os números de passaporte russo quanto à sua presença na lista de passaportes inválidos. Os principais requisitos para a implementação são a velocidade de verificação e a disponibilidade do serviço.
Depois de ler o artigo, decidi por mim mesmo que é nessa tarefa prática que você pode construir seu aprendizado Go. Na verdade, o problema de verificar passaportes inválidos, embora banal, é interessante e, uma vez que os requisitos de desempenho são uma prioridade aqui, a implementação em Go seria bastante apropriada aqui.
Além disso, o artigo mencionado acima aborda as questões de organização eficiente, do ponto de vista da memória, de arrays de bits (bitmaps). E este tópico é bastante relevante e em demanda em várias soluções aplicadas, por exemplo, na forma de índices de bitmap para um SGBD.
Como resultado, o seguinte: há um desejo de olhar para a linguagem Go, que é nova por si mesma, há um problema interessante na forma de organização e uso de bitmap (naturalmente em Go), há uma tarefa prática em quais esses dois objetivos podem ser trabalhados. Se estiver interessado, vá em frente.
O que são dados brutos
A própria tarefa de verificar passaportes é construída em torno da lista primária de passaportes inválidos apresentada no site do Ministério de Assuntos Internos da Federação Russa , onde você também pode verificar manualmente o número do passaporte. Você pode baixar a lista inteira do site como um arquivo compactado de 460 MB de tamanho, enquanto descompactado, obtemos uma lista de cerca de 1,5 GB de tamanho, apresentada como um único arquivo CSV com duas colunas: série e número do passaporte.
Até o momento, este arquivo CSV contém cerca de 132 milhões de números de passaporte. Mas o arquivo também contém números errados que não podem ser identificados de forma inequívoca, por exemplo, todos os 4 dígitos para uma série ou todos os 6 dígitos para um número não são indicados, pode haver séries alfabéticas.
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.