Он должен уменьшиться. Идея в том, чтобы бежать по числам (как сказали выше, можно рассматривать каждое 4-е число если работать в 30-ричной системе счисления) и проверять каждое из них каким-то быстрым тестом на простоту. Этот тест может давать ложноположительные срабатывания, но чисел на которых он это делает должно быть не так много и их можно сохранить отдельно.
Кроме того, можно строить таблицу на лету, например, с помощью решета эратосфена, что на хорошем компьютере быстрее, чем считать её с диска.
Вот тест посложнее, должен не врать до 1 трлн. Под pypy3 тестирует около 3 млн чисел в секунду.
код
def miller_rabin(n):
if n == 2:
return True
if n % 2 == 0:
return False
A = [2, 13, 23, 1662803]
if n in A:
return True
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for a in A:
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
Сильное уменьшение таблицы может дать использование быстрого вероятностного теста на простоту и хранение тех чисел на которых этот тест "врёт" что оно простое. Например такого:
def fast_test(n):
for p in [997, 32416190071]:
if pow(p, n-1, n) != 1:
return False
return True
Можно подобрать таких свидетелей простоты (вместо 997 и 32416190071) для которых тест не ошибается если входные числа лежат в заданных пределах.
Насколько я знаю оба установить не получится т.к. у них модули называются одинаково. Есть pycryptodomex у которого называются по-другому модули. Ещё, кстати, поддержал pycryptography, он должен быть очень быстрый т.к. использует openssl
Я больше про то, что epoll может сказать про сокет "в него можно писать и он не заблокируется", а при попытке писать получить EAGAIN (что то же самое, что EWOULDBLOCK). При этом мне не известны приложения, которые как-то обрабатывают эту ситуацию, не впадая в бесконечный цикл epoll_wait->send->epoll_wait->… со 100% загрузкой CPU
Недавно наткнулся на то, что epoll в режиме level triggered может возвращать что в сокет можно писать, а send при этом — возвращать EAGAIN. Это может происходить из-за того, что в системе начала заканчиваться память под tcp-буферы (sysctl net.ipv4.tcp_mem), но ещё не закончилась. При этом приложение обычно повторяет epoll_wait и ситуация повторяется. Это приводит к 100% загрузке CPU.
При этом send теоретически может возвращать ENOBUFS или ENOMEM, но возвращает почему-то именно EAGAIN.
Авторы MTProto на C предприняли много усилий чтобы всё работало быстро на большой нагрузке. Но CPU грузит удивительно много, при отсутствующей нагрузке будет процентов 5%.
Так это были реально потоки ОС? Я когда увидел 50 посчитал что речь идёт о TCP-потоках.
Кстати, у прокси есть недокументированная особенность. Если хочется больше одного таска, например, у вас многоядерный CPU и не хватает производительности, то можно просто запустить несколько экземпляров программы. Они автоматически поделят между собой нагрузку.
Могу. В самом начале клиент генерирует случайные 56 байт и посылает их серверу. На основе этих байт и общего секрета, обе стороны генерируют по два ключа шифрования: для шифрования данных от сервера к клиенту и в обратную сторону. После этого и клиент и сервер перед посылкой данных шифруют их соответствующими ключами.
После случайных 56 байт клиент посылает зашифрованные магические четыре байта и номер датацентра с которым его должен соединить прокси. По этим магическим четырем байтам сервер понимает, что с ним действительно общаются по нужному протоколу, но, для внешнего наблюдателя эти данные выглядят как случайные т.к. он не знает секрета, на основе которого сформированы ключи шифрования.
Ключевое слово "простого". Когда я собрал официальный прокси, я дочитал readme до слов "Simple MT-Proto proxy" и ошибочно подумал что запуск будет простым. Примерно таким ./proxy <port> <secret>. Я запустил его с --help и увидел следующее: https://alexbers.com/proxy.png. Затем было несколько часов безуспешных попыток его поднять, закончившиеся гуглением.
Перечислю несколько проблем, которые усложняют запуск без докера:
Не указан минимальный набор опций, которые необходимо передать, чтобы прокси заработал.
В параметрах сказано, что прокси может быть запущен с конфигурационным файлом, однако, нет информации о формате, в котором он должен быть или примера такого файла
Базовые и экспертные опции идут вперемешку. Понять, что делают некоторые опции можно только читая исходный текст
Для запуска нужно совершить действия, которые, кажутся "магическими": загрузить "секрет" из адреса в интернете, передать свой внутренний и внешний ip-адрес, загрузить некий список узлов
В выводе --help надпись "Simple MT-Proto proxy" вводит в заблуждение. Вместо "simple" можно было бы написать что без чтения readme даже не пытайтесь его поднять.
На самом деле потребление памяти получается примерно одинаковым, там почти вся память — разнобразные буферы, которые занимают примерно одинаково на си и на питоне.
С pypy3 и alpine возникла проблема — такого пакета по умолчанию нет. Проблема находится в процессе решения.
Отличный вопрос. У меня есть проект, который работает ровно так как описано: https://github.com/alexbers/tgsocksproxy. Правда, работает по протоколу socks т.к. протокол MTProto не поддерживает испльзование логина/пароля.
Он должен уменьшиться. Идея в том, чтобы бежать по числам (как сказали выше, можно рассматривать каждое 4-е число если работать в 30-ричной системе счисления) и проверять каждое из них каким-то быстрым тестом на простоту. Этот тест может давать ложноположительные срабатывания, но чисел на которых он это делает должно быть не так много и их можно сохранить отдельно.
Кроме того, можно строить таблицу на лету, например, с помощью решета эратосфена, что на хорошем компьютере быстрее, чем считать её с диска.
Результаты запуска на хорошем компьютере (E5-2697 v4 x 2)
Sieve size = 256 kilobytes
Threads = 36
100%
Primes: 37607912018
Seconds: 10.011
Триллион чисел генерируются за чуть больше двух минут на обычном ноутбуке (i7-7500U), что сравнимо со скоростью считывания 24ГБ данных с диска:
$ ./primesieve 1000000000000
Sieve size = 256 kilobytes
Threads = 4
100%
Primes: 37607912018
Seconds: 147.634
Вот тест посложнее, должен не врать до 1 трлн. Под pypy3 тестирует около 3 млн чисел в секунду.
Сильное уменьшение таблицы может дать использование быстрого вероятностного теста на простоту и хранение тех чисел на которых этот тест "врёт" что оно простое. Например такого:
Можно подобрать таких свидетелей простоты (вместо 997 и 32416190071) для которых тест не ошибается если входные числа лежат в заданных пределах.
Насколько я знаю оба установить не получится т.к. у них модули называются одинаково. Есть pycryptodomex у которого называются по-другому модули. Ещё, кстати, поддержал pycryptography, он должен быть очень быстрый т.к. использует openssl
Я больше про то, что epoll может сказать про сокет "в него можно писать и он не заблокируется", а при попытке писать получить EAGAIN (что то же самое, что EWOULDBLOCK). При этом мне не известны приложения, которые как-то обрабатывают эту ситуацию, не впадая в бесконечный цикл epoll_wait->send->epoll_wait->… со 100% загрузкой CPU
Недавно наткнулся на то, что epoll в режиме level triggered может возвращать что в сокет можно писать, а send при этом — возвращать EAGAIN. Это может происходить из-за того, что в системе начала заканчиваться память под tcp-буферы (sysctl net.ipv4.tcp_mem), но ещё не закончилась. При этом приложение обычно повторяет epoll_wait и ситуация повторяется. Это приводит к 100% загрузке CPU.
При этом send теоретически может возвращать ENOBUFS или ENOMEM, но возвращает почему-то именно EAGAIN.
Авторы MTProto на C предприняли много усилий чтобы всё работало быстро на большой нагрузке. Но CPU грузит удивительно много, при отсутствующей нагрузке будет процентов 5%.
В боте статистика по уникальным пользователям, а в прокси сервере — по tcp-соединениям. И то, и другое полезно
Так это были реально потоки ОС? Я когда увидел 50 посчитал что речь идёт о TCP-потоках.
Кстати, у прокси есть недокументированная особенность. Если хочется больше одного таска, например, у вас многоядерный CPU и не хватает производительности, то можно просто запустить несколько экземпляров программы. Они автоматически поделят между собой нагрузку.
Могу. В самом начале клиент генерирует случайные 56 байт и посылает их серверу. На основе этих байт и общего секрета, обе стороны генерируют по два ключа шифрования: для шифрования данных от сервера к клиенту и в обратную сторону. После этого и клиент и сервер перед посылкой данных шифруют их соответствующими ключами.
После случайных 56 байт клиент посылает зашифрованные магические четыре байта и номер датацентра с которым его должен соединить прокси. По этим магическим четырем байтам сервер понимает, что с ним действительно общаются по нужному протоколу, но, для внешнего наблюдателя эти данные выглядят как случайные т.к. он не знает секрета, на основе которого сформированы ключи шифрования.
Ключевое слово "простого". Когда я собрал официальный прокси, я дочитал readme до слов "Simple MT-Proto proxy" и ошибочно подумал что запуск будет простым. Примерно таким ./proxy <port> <secret>. Я запустил его с --help и увидел следующее: https://alexbers.com/proxy.png. Затем было несколько часов безуспешных попыток его поднять, закончившиеся гуглением.
Перечислю несколько проблем, которые усложняют запуск без докера:
На самом деле потребление памяти получается примерно одинаковым, там почти вся память — разнобразные буферы, которые занимают примерно одинаково на си и на питоне.
С pypy3 и alpine возникла проблема — такого пакета по умолчанию нет. Проблема находится в процессе решения.
Впилить можно, но тогда нужно будет пропатчить всех клиентов, чтобы они не передавали в открытом виде пароль.
В MTProto-версии поддерживается произвольное число секретов, но сильно много не рекомендуется.
Да, такой протокол. С этим, к сожалению, ничего не поделать
Отличный вопрос. У меня есть проект, который работает ровно так как описано: https://github.com/alexbers/tgsocksproxy. Правда, работает по протоколу socks т.к. протокол MTProto не поддерживает испльзование логина/пароля.
Он деманд
Хорошая идея, попробую реализовать в ближайшее время
Чтобы конфигурационный файл был в yaml и указывался через опцию можно написать примерно так: https://pastebin.com/Amzh5jJe
Для других форматов это будет выглядеть аналогично.