path: root/Английский язык/Final Practice/practice.tex

\documentclass[spec, och, coursework-kb]{SCWorks}
\usepackage{preamble}
\usepackage{underscore}

\title{Сравнение различных достаточных условий гамильтоновости графов}
\author{Гущина Андрея Юрьевича} % Фамилия, имя, отчество в родительном падеже

\begin{document}
% \input{titlepage.tex}

\section{Письменный перевод деловых писем}

\subsection*{Письмо №1}

\begin{flushleft}
  Jessica Parker, \newline
  Astonway Street, 34, \newline
  London, 23456 \newline
  27th of May
\end{flushleft}

\begin{flushleft}
  Christine Goward \newline
  Relax Hotel, \newline
  Burning Street, 7, \newline
  London, 76535
\end{flushleft}

Dear Miss Goward,

I am writing to you on behalf of Pear Incorporated to express our sincere
gratitude for your continued support and to discuss a potential business
opportunity.

We have been following your company's remarkable growth and outstanding
achievements in the agriculture and food industry with great admiration. As a
leading player in the production of fertilizers, we believe that a strategic
partnership between our organizations could bring about significant mutual
benefits and drive further success.

At Pear Incorporated, we specialize in production of high quality fertilizers
that with our own proprietary formulas. Our innovative solutions have
consistently helped businesses like yours enhance operational efficiency,
increase profitability, and stay ahead in this ever-evolving market. We are
confident that our expertise and resources align perfectly with your needs.

Our proposal entails selling you large quantities of our best products for your
fields. Also we consider sending you preview batches of our newest formulas.
We have carefully analyzed the market trends and competitive landscape, and we
firmly believe that by joining forces, we can leverage our respective strengths
to create a formidable alliance that will captivate the market and foster
sustainable growth.

Furthermore, we would be delighted to arrange a meeting at your convenience to
discuss this opportunity in detail. Our team of experts is eager to showcase how
our collaboration can unlock new possibilities and drive transformative results
for both our organizations. Please let us know your preferred date and time, and
we will ensure that all necessary arrangements are made promptly.

Thank you for considering this proposal. We genuinely believe that working
together will not only amplify our collective potential but also pave the way
for greater achievements and shared success.

Please feel free to contact me directly via email or phone if you have any
questions or require further information. We look forward to the possibility of
collaborating with your esteemed organization.

Yours sincerely,
\begin{flushleft}
  Jessica Parker \newline
  Head of marketing \newline
  Pear Incorporated
\end{flushleft}

\subsection*{Перевод письма №1}

\begin{flushleft}
  Джессика Паркер, \newline
  ул. Астонвэй, 34, \newline
  Лондон, 23456 \newline
  27 мая
\end{flushleft}

\begin{flushleft}
  Кристина Говард \newline
  отель Relax, \newline
  ул. Бёрнинг, 7, \newline
  Лондон, 76535
\end{flushleft}

Уважаемая мисс Говард,

Я пишу вам от имени компании Pear Incorporated, чтобы выразить нашу искреннюю
благодарность за вашу постоянную поддержку и обсудить потенциальное деловое
сотрудничество.

Мы следили за замечательным ростом вашей компании и выдающимися достижениями
в сельском хозяйстве и пищевой промышленности с большим восхищением. Являясь
ведущим игроком в производстве удобрений, мы считаем, что стратегическое
партнерство между нашими организациями может принести значительную взаимную
выгоды и способствовать дальнейшему успеху.

Компания Pear Incorporated специализируется на производстве высококачественных
удобрений с использованием наших собственных запатентованных формул. Наши
инновационные решения постоянно помогают таким предприятиям, как ваше, повышать
операционную эффективность, повысить рентабельность и оставаться впереди на
этом постоянно развивающемся рынке. Мы уверены, что наш опыт и ресурсы идеально
соответствуют вашим потребностям.

Наше предложение подразумевает продажу вам большого количества нашей лучшей
продукции для ваших полей. Также мы рассматриваем возможность отправления вам
предварительных партий наших новейших формул. Мы тщательно проанализировали
тенденции рынка и конкурентную среду, и мы твердо уверены, что, объединив
усилия, мы сможем использовать наши сильные стороны для создания грозного
альянса, который захватит рынок и будет способствовать устойчивый рост.

Более того, мы будем рады организовать встречу в удобное для вас время, чтобы
обсудить эту возможность в деталях. Наша команда экспертов с нетерпением ждет
возможности продемонстрировать, как наше сотрудничество может открыть новые
возможности и обеспечить преобразующие результаты для обеих наших организаций.
Пожалуйста, сообщите нам желаемую дату и время, и мы обеспечим оперативное
принятие всех необходимых мер.

Благодарим вас за рассмотрение этого предложения. Мы искренне верим, что
совместная работа вместе не только усилит наш коллективный потенциал, но и
проложит путь для больших достижений и общего успеха.

Пожалуйста, свяжитесь со мной напрямую по электронной почте или по телефону,
если у вас возникнут вопросы или потребуется дополнительная информация. Мы с
нетерпением возможности сотрудничества с вашей уважаемой организацией.

Искренне Ваша,
\begin{flushleft}
  Джессика Паркер \newline
  Руководитель отдела маркетинга \newline
  Pear Incorporated
\end{flushleft}


\subsection*{Письмо №2}

\begin{flushleft}
  Александр Хлебушкин, \newline
  ул. Пушкина, 20, \newline
  Саратов, 23456 \newline
  27 мая
\end{flushleft}

\begin{flushleft}
  Иван Улитин \newline
  ул. Колотушкина, 95, \newline
  Подольск, 76535
\end{flushleft}

Уважаемый Иван Владимирович,

Я пишу Вам от имени компании "ABC", которая занимается производством электронных компонентов. Мы заинтересованы в закупке электронных чипов и хотели бы запросить у Вас дополнительную информацию по этому вопросу.

Мы обратились к Вам, так как Ваша компания "XYZ" является одним из лидеров в производстве электронных компонентов, и мы уверены, что Ваш опыт и знания могут помочь нам в достижении наших целей.

Мы были бы признательны, если бы Вы могли предоставить нам следующую информацию:

\begin{itemize}
  \item Цена на электронные чипы типа "A12-45"
  \item Минимальный заказ и наличие на складе
  \item Сроки доставки до нашего производства в г. Новосибирск
\end{itemize}

Мы бы также хотели узнать, сможете ли Вы предоставить нам услуги или продукты, соответствующие нашим требованиям, а также информацию о стоимости и сроках выполнения работ.

Мы понимаем, что Ваше время ценно, и поэтому будем благодарны за любую информацию, которую Вы можете предоставить в ответ на наш запрос.

Если у Вас есть какие-либо вопросы или требуется дополнительная информация от нас, пожалуйста, не стесняйтесь обратиться к нам.

\begin{flushleft}
С уважением, \newline
Александр Хлебушкин \newline
Компания "ABC"
\end{flushleft}

\subsection*{Перевод письма №2}

\begin{flushleft}
  Alexander Khlebushkin, \newline
  Pushkina street, 20, \newline
  Saratov, 23456 \newline
  27th of May
\end{flushleft}

\begin{flushleft}
  Ivan Ulitin \newline
  Kolotushkina street, 95, \newline
  Podolsk, 76535
\end{flushleft}

Dear Mr. Ulitin,

I am writing to you on behalf of the company "ABC", which is engaged in the production of electronic components. We are interested in purchasing electronic chips and would like to request more information from you on this matter.

We have approached you as your company "XYZ" is one of the leaders in the manufacture of electronic components and we are confident that your experience and expertise can help us achieve our goals.

We would appreciate if you could give us the following information:

\begin{itemize}
  \item Price of electronic chips such as "A12-45"
  \item Minimum order and stock availability
  \item Time of delivery to our production in Novosibirsk
\end{itemize}

We would also like to know if you can provide us with services or products that meet our requirements, as well as information about costs and lead times.

We understand that your time is valuable, so any information you can give us in response to our request would be greatly appreciated.

If you have any questions or require additional information from us, please feel free to contact us.

\begin{flushleft}
Regards, \newline
Alexander Khlebushkin \newline
ABC Company \newline
\end{flushleft}

\section{Перевод статей профессиональной направленности}

\subsection*{Статья}

At Cloudflare, engineers spend a great deal of time refactoring or rewriting
existing functionality. When your company doubles the amount of traffic it
handles every year, what was once an elegant solution to a problem can quickly
become outdated as the engineering constraints change. Not only that, but when
you're averaging 40 million requests a second, issues that might affect 0.001\%
of requests flowing through our network are big incidents which may impact
millions of users, and one-in-a-trillion events happen several times a day.

Recently, we've been working on a replacement to one of our oldest and
least-well-known components called cf-html, which lives inside the core reverse
web proxy of Cloudflare known as FL (Front Line). Cf-html is the framework in
charge of parsing and rewriting HTML as it streams back through from the website
origin to the website visitor. Since the early days of Cloudflare, we’ve offered
features which will rewrite the response body of web requests for you on the
fly. The first ever feature we wrote in this way was to replace email addresses
with chunks of JavaScript, which would then load the email address when viewed
in a web browser. Since bots are often unable to evaluate JavaScript, this
helps to prevent scraping of email addresses from websites. You can see this
in action if you view the source of this page and look for this email address:
foo@example.com.

FL is where most of the application infrastructure logic for Cloudflare runs,
and largely consists of code written in the Lua scripting language, which runs
on top of NGINX as part of OpenResty. In order to interface with NGINX directly,
some parts (like cf-html) are written in lower-level languages like C and
C++. In the past, there were many such OpenResty services at Cloudflare, but
these days FL is one of the few left, as we move other components to Workers
or Rust-based proxies. The platform that once was the best possible blend of
developer ease and speed has more than started to show its age for us.

When discussing what happens to an HTTP request passing through our network and
in particular FL, nearly all the attention is given to what happens up until
the request reaches the customer's origin. That’s understandable as this is
where most of the business logic happens: firewall rules, Workers, and routing
decisions all happen on the request. But it's not the end of the story. From
an engineering perspective, much of the more interesting work happens on the
response, as we stream the HTML response back from the origin to the site
visitor.

The logic to handle this is contained in a static NGINX module, and runs in the
Response Body Filters phase in NGINX, as chunks of the HTTP response body are
streamed through. Over time, more features were added, and the system became
known as cf-html. cf-html uses a streaming HTML parser to match on specific HTML
tags and content, called Lazy HTML or lhtml, with much of the logic for both it
and the cf-html features written using the Ragel state machine engine.

All the cf-html logic was written in C, and therefore was susceptible to memory
corruption issues that plague many large C codebases. In 2017 this led to a
security bug as the team was trying to replace part of cf-html. FL was reading
arbitrary data from memory and appending it to response bodies. This could
potentially include data from other requests passing through FL at the same
time. This security event became known widely as Cloudbleed.

Since this episode, Cloudflare implemented a number of policies and safeguards
to ensure something like that never happened again. While work has been carried
out on cf-html over the years, there have been few new features implemented on
the framework, and we’re now hyper-sensitive to crashes happening in FL (and,
indeed, any other process running on our network), especially in parts that can
reflect data back with a response.

Fast-forward to 2022 into 2023, and the FL Platform team have been getting
more and more requests for a system they can easily use to look at and rewrite
response body data. At the same time, another team has been working on a new
response body parsing and rewriting framework for Workers called lol-html or
Low Output Latency HTML. Not only is lol-html faster and more efficient than
Lazy HTML, but it’s also currently in full production use as part of the Worker
interface, and written in Rust, which is much safer than C in terms of its
handling of memory. It’s ideal, therefore, as a replacement for the ancient and
creaking HTML parser we’ve been using in FL up until now.

So we started working on a new framework, written in Rust, that would
incorporate lol-html and allow other teams to write response body parsing
features without the threat of causing massive security issues. The new system
is called ROFL or Response Overseer for FL, and it’s a brand-new NGINX module
written completely in Rust. As of now, ROFL is running in production on millions
of responses a second, with comparable performance to cf-html. In building ROFL,
we’ve been able to deprecate one of the scariest bits of code in Cloudflare’s
entire codebase, while providing teams at Cloudflare with a robust system they
can use to write features which need to parse and rewrite response body data.
Writing an NGINX module in Rust

While writing the new module, we learned a lot about how NGINX works, and how we
can get it to talk to Rust. NGINX doesn’t provide much documentation on writing
modules written in languages other than C, and so there was some work which
needed to be done to figure out how to write an NGINX module in our language
of choice. When starting out, we made heavy use of parts of the code from the
nginx-rs project, particularly around the handling of buffers and memory pools.
While writing a full NGINX module in Rust is a long process and beyond the scope
of this blog post, there are a few key bits that make the whole thing possible,
and that are worth talking about.

The first one of these is generating the Rust bindings so that NGINX can
communicate with it. To do that, we used Rust’s library Bindgen to build the
FFI bindings for us, based on the symbol definitions in NGINX’s header files.
To add this to an existing Rust project, the first thing is to pull down a copy
of NGINX and configure it. Ideally this would be done in a simple script or
Makefile, but when done by hand it would look something like this:

With NGINX in the right state, we need to create a build.rs file in our Rust
project to auto-generate the bindings at build-time of the module. We’ll now
add the necessary arguments to the build, and use Bindgen to generate us the
bindings.rs file. For the arguments, we just need to include all the directories
that may contain header files for clang to do its thing. We can then feed them
into Bindgen, along with some allowlist arguments, so it knows for what things
it should generate the bindings, and which things it can ignore. Adding a little
boilerplate code to the top, the whole file should look something like this:

Hopefully this is all fairly self-explanatory. Bindgen traverses the NGINX
source and generates equivalent constructs in Rust in a file called bindings.rs,
which we can import into our project. There’s just one more thing to add-
Bindgen has trouble with a couple of symbols in NGINX, which we’ll need to fix
in a file called wrapper.h.

With this in place and Bindgen set in the [build-dependencies] section of the
Cargo.toml file, we should be ready to build.

With any luck, we should see a file called bindings.rs in the target/debug/build
directory, which contains Rust definitions of all the NGINX symbols.

To be able to use them in the project, we can include them in a new file under
the src directory which we’ll call bindings.rs.

With that set, we just need to add the usual imports to the top of the lib.rs
file, and we can access NGINX constructs from Rust. Not only does this make
bugs in the interface between NGINX and our Rust module much less likely than
if these values were hand-coded, but it’s also a fantastic reference we can
use to check the structure of things in NGINX when building modules in Rust,
and it takes a lot of the leg-work out of setting everything up. It’s really
a testament to the quality of a lot of Rust libraries such as Bindgen that
something like this can be done with so little effort, in a robust way.

Once the Rust library has been built, the next step is to hook it into NGINX.
Most NGINX modules are compiled statically. That is, the module is compiled as
part of the compilation of NGINX as a whole. However, since NGINX 1.9.11, it has
supported dynamic modules, which are compiled separately and then loaded using
the load_module directive in the nginx.conf file. This is what we needed to use
to build ROFL, so that the library could be compiled separately and loaded-in
at the time NGINX starts up. Finding the right format so that the necessary
symbols could be found from the documentation was tricky, though, and although
it is possible to use a separate config file to set some of this metadata, it’s
better if we can load it as part of the module, to keep things neat. Luckily, it
doesn’t take much spelunking through the NGINX codebase to find where dlopen is
called.

When writing an NGINX module, it’s crucial to get its order relative to the
other modules correct. Dynamic modules get loaded as NGINX starts, which means
they are (perhaps counterintuitively) the first to run on a response. Ensuring
your module runs after gzip decompression by specifying its order relative to
the gunzip module is essential, otherwise you can spend lots of time staring at
streams of unprintable characters, wondering why you aren’t seeing the response
you expected. Not fun. Fortunately this is also something that can be solved by
looking at the NGINX source, and making sure the relevant entities exist in your
module.

We’re essentially saying we want our module rust_nginx_module to run just before
the ngx_http_headers_more_filter_module module, which should allow it to run in
the place we expect.

One of the quirks of NGINX and OpenResty is how it is really hostile to making
calls to external services at the point that you’re dealing with the HTTP
response. It’s something that isn’t provided as part of the OpenResty Lua
framework, even though it would make working with the response phase of a
request much easier. While we could do this anyway, that would mean having to
fork NGINX and OpenResty, which would bring its own challenges. As a result,
we’ve spent a lot of time over the years thinking about ways to pass state from
the time when NGINX’s dealing with an HTTP request, over to the time when it’s
streaming through the response, and much of our logic is built around this style
of work.

For ROFL, that means in order to determine if we need to apply a certain feature
for a response, we need to figure that out on the request, then pass that
information over to the response so that we know which features to activate.
To do that, we need to use one of the utilities that NGINX provides you with.
With the help of the bindings.rs file generated earlier, we can take a look at
the definition of the ngx_http_request_s struct, which contains all the state
associated with a given request.

As we can see, there’s a member called ctx. As the NGINX Development Guide
mentions, it’s a place where you’re able to store any value associated with
a request, which should live for as long as the request does. In OpenResty
this is used heavily for the storing of state to do with a request over its
lifetime in a Lua context. We can do the same thing for our module, so that
settings initialised during the request phase are there when our HTML parsing
and rewriting is run in the response phase. 

Notice that ctx is at the offset of the ctx_index member of ngx_http_rofl_module
- this is the structure of type ngx_module_t that’s part of the module
definition needed to make an NGINX module. Once we have this, we can point it
to a structure containing any setting we want.

The function is called get_or_init_ctx here- it performs the same job as
get_ctx, but also initialises the structure if it doesn’t exist yet. Once we’ve
set whatever data we need in ctx during the request, we can then check what
features need to be run in the response, without having to make any calls to
external databases, which might slow us down.

One of the nice things about storing state on ctx in this way, and working with
NGINX in general, is that it relies heavily on memory pools to store request
content. This largely removes any need for the programmer to have to think about
freeing memory after use- the pool is automatically allocated at the start of
a request, and is automatically freed when the request is done. All that’s
needed is to allocate the memory using NGINX’s built-in functions for allocating
memory to the pool and then registering a callback that will be called to free
everything.

This should allow us to allocate memory for whatever we want, safe in the
knowledge that NGINX will handle it for us.

It is regrettable that we have to write a lot of unsafe blocks when dealing
with NGINX’s interface in Rust. Although we’ve done a lot of work to minimise
them where possible, unfortunately this is often the case with writing Rust
code which has to manipulate C constructs through FFI. We have plans to do more
work on this in the future, and remove as many lines as possible from unsafe.
Challenges encountered

The NGINX module system allows for a massive amount of flexibility in terms of
the way the module itself works, which makes it very accommodating to specific
use-cases, but that flexibility can also lead to problems. One that we ran into
had to do with the way the response data is handled between Rust and FL. In
NGINX, response bodies are chunked, and these chunks are then linked together
into a list. Additionally, there may be more than one of these linked lists per
response, if the response is large.

Efficiently handling these chunks means processing them and passing them on as
quickly as possible. When writing a Rust module for manipulating responses, it’s
tempting to implement a Rust-based view into these linked lists. However, if you
do that, you must be sure to update both the Rust-based view and the underlying
NGINX data structures when mutating them, otherwise this can lead to serious
bugs where Rust becomes out of sync with NGINX. Here’s a small function from an
early version of ROFL that caused headaches:

What this code was supposed to do is take the output of lol-html’s HTMLRewriter,
and write it to the output chain of buffers. Importantly, the output can be
larger than a single buffer, so you need to take new buffers off the chain
in a loop until you’ve written all the output to buffers. Within this logic,
NGINX is supposed to take care of popping the buffer off the free chain and
appending the new chunk to the output chain, which it does. However, if you’re
only thinking in terms of the way NGINX handles its view of the linked list, you
may not notice that Rust never changes which buffer its free_chain.head points
to, causing the logic to loop forever and the NGINX worker process to lock-up
completely. This sort of issue can take a long time to track down, especially
since we couldn’t reproduce it on our personal machines until we understood it
was related to the response body size.

Getting a coredump to perform some analysis with gdb was also hard because once
we noticed it happening, it was already too late and the process memory had
grown to the point the server was in danger of falling over, and the memory
consumed was too large to be written to disk. Fortunately, this code never made
it to production. As ever, while Rust’s compiler can help you to catch a lot of
common mistakes, it can’t help as much if the data is being shared via FFI from
another environment, even without much direct use of unsafe, so extra care must
be taken in these cases, especially when NGINX allows the kind of flexibility
that might lead to a whole machine being taken out of service.

Another major challenge we faced had to do with backpressure from incoming
response body chunks. In essence, if ROFL increased the size of the response
due to having to inject some large amount of code into the stream (such as
replacing an email address with a large chunk of JavaScript), NGINX can feed the
output from ROFL to the other downstream modules faster than they could push
it along, potentially leading to data being dropped and HTTP response bodies
being truncated if the EAGAIN error from the next module is left unhandled. This
was another case where the issue was really hard to test, because most of the
time the response would be flushed fast enough for backpressure never to be a
problem. To handle this, we had to create a special chain to store these chunks
called saved_in, which required a special method for appending to it.

Effectively we’re ‘queueing’ the data for a short period of time so that we
don’t overwhelm the other modules by feeding them data faster than they can
handle it. The NGINX Developer Guide has a lot of great information, but many
of its examples are trivial to the point where issues like this don’t come
up. Things such as this are the result of working in a complex NGINX-based
environment, and need to be discovered independently. A future without NGINX

The obvious question a lot of people might ask is: why are we still using NGINX?
As already mentioned, Cloudflare is well on its way to replacing components
that either used to run NGINX/OpenResty proxies, or would have done without
heavy investment in home-grown platforms. That said, some components are easier
to replace than others and FL, being where most of the logic for Cloudflare’s
application services runs, is definitely on the more challenging end of the
spectrum.

Another motivating reason for doing this work is that whichever platform we
eventually migrate to, we’ll need to run the features that make up cf-html, and
in order to do that we’ll want to have a system that is less heavily integrated
and dependent on NGINX. ROFL has been specifically designed with the intention
of running it in multiple places, so it will be easy to move it to another
Rust-based web proxy (or indeed our Workers platform) without too much trouble.
That said it’s hard to imagine we’d be in the same place without a language
like Rust, which offers speed at the same time as a high degree of safety, not
to mention high-quality libraries like Bindgen and Serde. More broadly, the
FL team are working to migrate other aspects of the platform over to Rust,
and while cf-html and the features of which make it up are a key part of our
infrastructure that needed work, there are many others.

Safety in programming languages is often seen as beneficial in terms of
preventing bugs, but as a company we’ve found that it also allows you to do
things which would be considered very hard, or otherwise impossible to do
safely. Whether it be providing a Wireshark-like filter language for writing
firewall rules, allowing millions of users to write arbitrary JavaScript
code and run it directly on our platform or rewriting HTML responses on the
fly, having strict boundaries in place allows us to provide services we
wouldn’t be able to otherwise, all while safe in the knowledge that the kind of
memory-safety issues that used to plague the industry are increasingly a thing
of the past.


\subsection*{Перевод статьи}

В Cloudflare инженеры тратят много времени на рефакторинг или переписывание
существующей функциональности. Когда ваша компания удваивает объем трафика,
который она обрабатывает каждый год, то, что когда-то было элегантным решением
проблемы, может быстро может быстро устареть по мере изменения технических
ограничений. Мало того, когда вы обрабатываете в среднем 40 миллионов запросов в
секунду, проблемы, которые могут повлиять на 0,001\% запросов, проходящих через
нашу сеть, становятся крупными инцидентами, которые могут повлиять на миллионы
пользователей, а события один на триллион происходят несколько раз в день.

Недавно мы работали над заменой одного из наших самых старых и наименее
известных компонентов под названием cf-html, который находится внутри ядра
обратного веб-прокси Cloudflare, известного как FL (Front Line). Cf-html ---
это фреймворк, отвечающий за разбор и переписывание HTML по мере того, как он
передается от сайта к посетителю сайта. С первых дней существования Cloudflare
мы предлагаем функции, которые будут переписывать тело ответа веб-запросов для
вас на лету. Первой функцией, которую мы написали таким образом, была замена
адресов электронной почты фрагментами JavaScript, которые затем загружали адрес
электронной почты при просмотре в веб-браузере. Поскольку боты часто не могут
оценить JavaScript, это помогает предотвратить поиск адресов электронной почты
с веб-сайтов. Вы можете увидеть это в действии, если просмотреть источник этой
страницы и найти этот адрес электронной почты: foo@example.com.

FL - это место, где работает большая часть логики инфраструктуры приложений
Cloudflare, и в основном состоит из кода, написанного на скриптовом языке
Lua, который работает поверх NGINX как часть OpenResty. Для того чтобы
взаимодействовать с NGINX напрямую, некоторые части (например, cf-html) написаны
на языках более низкого уровня, таких как C и C++. В прошлом было много подобных
сервисов OpenResty в Cloudflare, но в наши дни FL - один из немногих оставшихся,
поскольку мы переводим другие компоненты на Workers или прокси-серверы на основе
Rust. Платформа, которая когда-то была наилучшим возможным сочетанием простоты и
скорости работы разработчиков, уже более чем начала показывать свой возраст.

При обсуждении того, что происходит с HTTP-запросом, проходящим через нашу сеть
и в частности FL, почти все внимание уделяется тому, что происходит до тех пор,
пока пока запрос не достигнет клиентского источника. Это понятно, поскольку
именно здесь происходит большая часть бизнес-логики: правила брандмауэра,
Workers и решения по маршрутизации принимаются на этапе запроса. Но это еще
не конец истории. С инженерной точки зрения, большая часть интересной работы
происходит на этапе ответа, когда мы передаем HTML-ответ обратно от источника к
посетителю сайта.

Логика для обработки этого содержится в статическом модуле NGINX и выполняется
на этапе фильтрации тела ответа в NGINX, поскольку фрагменты тела ответа HTTP
передаются в потоковом режиме. Со временем были добавлены дополнительные
функции, и система стала называться cf-html. cf-html использует потоковый парсер
HTML для поиска определенных HTML тегов и содержимого, называемый Lazy HTML
или lhtml, причем большая часть логики для него и функций cf-html написана с
использованием механизма машин состояния Ragel.

Вся логика cf-html была написана на C, и поэтому была подвержена проблемам
повреждения памяти, которые характерны для многих больших кодовых баз на языке
Си. В 2017 году это привело к ошибке безопасности, когда команда пыталась
заменить часть cf-html. FL считывал произвольные данные из памяти и добавлял
их в тело ответа. Это могло потенциально включать данные из других запросов,
проходящих через FL в то же самое время. Это событие безопасности стало широко
известно как Cloudbleed.

После этого эпизода Cloudflare внедрила ряд политик и мер безопасности для
того, чтобы подобное никогда не повторилось. Несмотря на то, что работа над над
cf-html велась на протяжении многих лет, было реализовано мало новых функций в
фреймворке, и теперь мы очень чувствительны к сбоям, происходящим в FL (и любом
другом процессе, запущенном в нашей сети), особенно в тех частях, которые могут
отражать данные обратно с ответом.

Переходя к 2022-2023 годам, команда FL Platform получает все больше и больше
запросов к системе, которую они могли бы легко использовать для просмотра
и перезаписи данных тела ответа. В то же время другая команда работала над
новой системой разбора и перезаписи тела ответа для Workers под названием
lol-html или Low Output Latency HTML. lol-html не только быстрее и эффективнее,
чем Lazy HTML, но он также в настоящее время полностью используется в
производстве как часть интерфейса Worker и написан на языке Rust, который
намного безопаснее языка Си с точки зрения его обращения с памятью. Поэтому он
идеально подходит для замены древнего и скрипучего парсера HTML, который мы до
сих пор использовали в FL.

Поэтому мы начали работать над новым фреймворком, написанным на Rust, который
бы включил lol-html и позволил другим командам писать функции разбора тела
ответа без угрозы возникновения серьезных проблем с безопасностью. Новая система
называется ROFL или Response Overseer for FL, и это совершенно новый модуль
NGINX, полностью написанный на языке Rust. На данный момент ROFL работает в
продакшене и обрабатывает миллионы ответов в секунду, с производительностью,
сравнимой с cf-html. При создании ROFL, мы смогли снять с эксплуатации один
из самых страшных кусков кода во всей кодовой базе, в то же время предоставив
командам Cloudflare надежную систему, которую они могут использовать для
написания функций, нуждающихся в разборе и переработке данных тела ответа.

В процессе написания нового модуля мы многое узнали о том, как работает NGINX,
и как мы можем заставить его общаться с Rust. NGINX не предоставляет много
документации по написанию модулей, написанных на языках, отличных от C, и
поэтому нам пришлось проделать некоторую работу, чтобы понять, как написать
модуль NGINX на языке программирования выбранном нами. Начиная работу, мы
активно использовали части кода из проекта nginx-rs, особенно в части работы с
буферами и пулами памяти. Хотя написание полноценного модуля NGINX на Rust ---
долгий процесс и выходит за рамки этой статьи, есть несколько ключевых моментов,
которые делают все это возможным, и о которых стоит поговорить.

Первый из них - это создание привязки Rust, чтобы NGINX мог взаимодействовать с
ним. Для этого мы использовали библиотеку Rust Bindgen для создания FFI привязки
для нас, основываясь на определениях символов в заголовочных файлах NGINX.
Чтобы добавить это в существующий проект Rust, первым делом нужно достать копию
NGINX и настроить его. В идеале это должно быть сделано в простом скрипте или
Makefile, но при выполнении вручную это будет выглядеть примерно так:

Когда NGINX находится в нужном состоянии, нам нужно создать файл build.rs в
нашем проекте Rust для автоматической генерации привязок во время сборки модуля.
Теперь мы добавим необходимые аргументы в сборку и воспользуемся Bindgen для
генерации файла bindings.rs. Для аргументов нам просто нужно включить все
директории, которые могут содержать заголовочные файлы для работы clang. Затем
мы можем передать их в Bindgen вместе с некоторыми аргументами разрешающего
списка, чтобы он знал, для каких вещей он должен генерировать привязки, а какие
вещи он может игнорировать. Добавив немного шаблонного кода, весь файл должен
выглядеть примерно так:

Надеюсь, все это достаточно понятно. Bindgen просматривает источник NGINX и
генерирует эквивалентные конструкции на языке Rust в файле bindings.rs, который
мы можем импортировать в наш проект. Есть только одна вещь, которую нужно
добавить - У Bindgen есть проблемы с парой символов в NGINX, которые нам нужно
будет исправить в файле под названием wrapper.h.

Когда все готово, а Bindgen установлен в разделе [build-dependencies] файла
Cargo.toml, мы должны быть готовы к сборке.

Если повезет, мы должны увидеть файл bindings.rs в каталоге target/debug/build
который содержит Rust определения всех символов NGINX.

Чтобы иметь возможность использовать их в проекте, мы можем включить их в новый
файл в каталоге каталоге src, который мы назовем bindings.rs.

Когда все готово, нам остается только добавить обычные импорты в верхнюю часть
файла lib.rs и мы можем получить доступ к конструкциям NGINX из Rust. Это не
только делает ошибки в интерфейсе между NGINX и нашим модулем Rust гораздо
менее вероятными, чем если бы эти значения были закодированы вручную, но это
также фантастическая справка, которую мы можем использовать для проверки
структуры в NGINX при создании модулей на Rust, и это снимает много работы
по конфигурированию. То что подобное можно сделать с минимальными усилиями и
надежным способом, свидетельствует о качестве многих библиотек Rust, таких как
Bindgen.

После того, как библиотека Rust собрана, следующим шагом будет подключение ее
к NGINX. Большинство модулей NGINX компилируются статически. То есть, модуль
компилируется как часть NGINX в целом. Однако, начиная с версии NGINX 1.9.11,
поддерживаются динамические модули, которые компилируются отдельно и затем
загружаются с помощью директивы директивы load_module в файле nginx.conf. Это
то, что нам нужно было использовать для сборки ROFL, чтобы библиотека могла
быть скомпилирована отдельно и загружена во время запуска NGINX. Было непросто
найти такой правильный формат, чтобы необходимые символы можно было найти в
документации, и хотя можно использовать отдельный конфигурационный файл для
установки некоторых из этих метаданных, будет лучше, если мы можем загрузить их
как часть модуля, чтобы все было аккуратно. К счастью, для этого не нужно долго
копаться в кодовой базе NGINX, чтобы найти, где вызывается dlopen.

При написании модуля NGINX очень важно, чтобы его порядок относительно других
модулей был правильным. Динамические модули загружаются при запуске NGINX,
что означает, что они (возможно, нелогично) запускаются первыми при получении
ответа. Обеспечить запуск вашего модуля после декомпрессии gzip, указав его
порядок относительно модуля gunzip очень важно. Иначе вы можете потратить много
времени, глядя на потоки непечатаемых символов, недоумевая, почему вы не видите
ответа, который вы ожидали. Это не весело. К счастью, эту проблему также можно
решить, если взглянуть на исходный код NGINX и убедиться, что соответствующие
сущности существуют в вашем модуле.

По сути, мы хотим, чтобы наш модуль rust_nginx_module выполнялся непосредственно
перед модулем ngx_http_headers_more_filter_module, что должно позволить ему
запускаться в том месте, где мы ожидаем.

Одна из причуд NGINX и OpenResty заключается в том, что они очень недружелюбно
относятся к вызову внешних сервисов в тот момент, когда вы обрабатываете HTTP
ответ. Это то, что не предусмотрено как часть OpenResty Lua фреймворка OpenResty
Lua, хотя это сделало бы работу с фазой ответа на запрос намного проще. Хотя мы
могли бы сделать это в любом случае, это означало бы необходимость создавать
форк NGINX и OpenResty, что принесло бы свои проблемы. В результате мы потратили
много времени, размышляя о том, как передать состояние пока NGINX работает с
HTTP-запросом, до того момента, когда он обрабатывает ответ, и большая часть
нашей логики построена вокруг этого стиля работы.

Для ROFL это означает, что для того, чтобы определить, нужно ли нам применить
определенную функцию для ответа, мы должны выяснить это в запросе, а затем
передать эту информацию информацию в ответ, чтобы мы знали, какие функции
активировать. Для этого нам нужно воспользоваться одной из утилит, которые
предоставляет NGINX. С помощью файла bindings.rs, созданного ранее, мы можем
взглянуть на определение структуры ngx_http_request_s, которая содержит все
состояние связанное с данным запросом.

Как мы видим, в ней есть член под названием ctx. Как говорится в руководстве по
разработке NGINX упоминается, это место, где вы можете хранить любое значение,
связанное с запросом, которое должно жить столько же, сколько и запрос. В
OpenResty это место активно используется для хранения состояния, связанного с
запросом, в течение его в контексте Lua. Мы можем сделать то же самое для нашего
модуля, чтобы настройки, инициализированные на этапе запроса, сохранялись, когда
наш HTML парсинг и переписывания в фазе ответа.

Обратите внимание, что ctx находится по смещению члена ctx_index модуля
ngx_http_rofl_module --- это структура типа ngx_module_t, которая является
частью модуля определения, необходимого для создания модуля NGINX. Как только
мы получим эту структуру, мы можем указать ее на структуру, содержащую любой
параметр, который нам нужен.

Здесь функция называется get_or_init_ctx, которая выполняет ту же работу, что и
функция get_ctx, но также инициализирует структуру, если она еще не существует.
Как только мы установили все необходимые данные в ctx во время запроса, мы можем
проверить, какие какие функции должны быть запущены в ответе, без необходимости
делать какие-либо вызовы к внешним базам данных, что может замедлить работу.

Одна из приятных особенностей хранения состояния в ctx таким образом и работы
с NGINX в целом, является то, что он в значительной степени полагается на пулы
памяти для хранения содержимого запросов. Это в значительной степени устраняет
необходимость для программиста думать об освобождении памяти после использования
--- пул памяти автоматически выделяется в начале запроса и автоматически
освобождается, когда запрос завершен. Все, что необходимо сделать --- это
выделить память, используя встроенные функции NGINX для выделения памяти в пул,
а затем зарегистрировать обратный вызов, который будет вызван для освобождения
всего.

Это позволит нам выделять память под все, что мы хотим, будучи уверенными в том,
что NGINX справится с этим зная, что NGINX сделает это за нас.

К сожалению, нам приходится писать много unsafe блоков, когда мы имеем дело
с интерфейсом NGINX в Rust. Хотя мы проделали большую работу, чтобы свести к
минимуму их, где это возможно, к сожалению, это часто случается при написании
Rust кода, который должен манипулировать конструкциями языка C через FFI. У нас
есть планы сделать больше работы над этим в будущем, и убрать как можно больше
строк из небезопасного кода.

Система модулей NGINX позволяет проявлять огромную гибкость в том, что касается
того, как работает сам модуль, что делает его очень приспособленным к конкретным
сценариям использования, но эта гибкость также может привести к проблемам. Одна
из них, с которой мы столкнулись связана с тем, как обрабатываются данные ответа
между Rust и FL. В NGINX, тела ответов разбиваются на фрагменты, и эти фрагменты
затем соединяются вместе в список. Кроме того, на один ответ может приходиться
более одного такого связанного списка, если ответ большой.

Эффективная работа с этими кусками означает их обработку и передачу как
можно быстрее. При написании модуля на языке Rust для манипулирования
ответами, очень заманчиво реализовать представление на основе Rust в этих
связанных списках. Однако, если вы сделаете это, вы должны быть уверены, что
обновите и представление на основе Rust, и базовые структуры NGINX при их
изменении, иначе это может привести к серьезным ошибкам, когда Rust становится
рассинхронизированным с NGINX. Вот небольшая функция из ранней версии ROFL,
которая вызывала головную боль:

Этот код должен был делать следующее: брать вывод HTMLRewriter'а lol-html, и
записывать его в выходную цепочку буферов. Важно отметить, что вывод может
быть больше, чем один буфер, поэтому вам нужно брать новые буферы из цепочки
в цикле, пока не будет записан весь вывод в буферы. В рамках этой логики,
NGINX должен позаботиться о том, чтобы выдернуть буфер из свободной цепочки и
добавляя новый чанк в цепочку вывода, что он и делает. Однако, если вы думаете
только о том, как NGINX обрабатывает свое представление связного списка, вы
можете не заметить, что Rust никогда не меняет буфер, на который указывает
его free_chain.head, что приводит к вечному циклу логики и полной блокировке
рабочего процесса NGINX. Отслеживание такого рода проблемы может занять много
времени, тем более, поскольку мы не могли воспроизвести ее на наших персональных
машинах, пока не поняли, что она связана с размером тела ответа.

Получить coredump для проведения анализа с помощью gdb было также сложно, потому
что как только мы заметили, что это происходит, было уже слишком поздно, и
память процесса выросла до такой степени, что сервер был в опасности падения, а
потребляемая память была слишком велика для записи на диск. К счастью, этот код
так и не попал в производство. Как всегда, хотя компилятор Rust может помочь
вам отловить множество распространенных ошибок, он не так сильно поможет, если
данные передаются через FFI из другого окружения, даже без прямого использования
unsafe, поэтому в таких случаях нужно быть особенно внимательным, особенно когда
NGINX позволяет такую гибкость, что может привести к выводу из строя целой
машины.

Еще одна серьезная проблема, с которой мы столкнулись, была связана с обратным
давлением от входящих кусков тела ответа. По сути, если ROFL увеличивал
размер ответа из-за необходимости внедрить в поток большое количество кода
(например, замена адреса электронной почты на большой кусок JavaScript), NGINX
может передать вывод от ROFL другим модулям, расположенным ниже, быстрее, чем
они могли бы продвигать это далее. Потенциально это может привести к тому,
что данные будут потеряны, а тела HTTP-ответов обрезаны, если ошибка EAGAIN
следующего модуля останется необработанной. Это был еще один случай, когда
проблему было очень трудно протестировать, потому что в большинстве случаев
ответ удалялся достаточно быстро, чтобы обратное давление никогда не было
проблемой. Чтобы справиться с этим, мы должны были создать специальную цепочку
для хранения этих фрагментов называемую saved_in, которая требует специального
метода для добавления к ней.

Эффективно мы "ставим в очередь" данные на короткий промежуток времени, чтобы не
перегружать другие модули, подавая им данные быстрее, чем они могут обработать
их. Руководство разработчика NGINX содержит много замечательной информации,
но многие примеры в нем тривиальны настолько, что такие вопросы, как этот, не
возникают. Такие вещи, как эта, являются результатом работы в сложной среде на
базе NGINX и должны быть обнаружены самостоятельно.

Многие могут задать очевидный вопрос: почему мы до сих пор используем NGINX?
Как уже упоминалось, Cloudflare уже на пути к замене компонентов, которые либо
использовали прокси-серверы NGINX/OpenResty, либо могли бы это сделать без
больших инвестиций в собственные платформы. Тем не менее, некоторые компоненты
заменить легче, чем другие, и FL, где работает большая часть логики для сервисов
Cloudflare приложений, определенно находится на более сложном конце спектра.

Другой мотивирующей причиной для выполнения этой работы является то, что на
какую бы платформу мы в конечном итоге не перешли, нам нужно будет запускать
функции, составляющие cf-html, и для этого мы хотим иметь систему, которая
менее сильно интегрирована и зависима от NGINX. ROFL был специально разработан
с намерением чтобы его можно было запускать в разных местах, поэтому его будет
легко перенести на другой веб-прокси на базе Rust (или на нашу платформу
Workers) без особых проблем. Тем не менее, трудно представить, что мы были бы
на том же месте, если бы не было такого языка, как Rust, который предлагает
скорость и одновременно высокую степень безопасности, не говоря уже о таких
высококачественных библиотеках, как Bindgen и Serde. В более широком смысле,
команда FL работает над переносом других частей платформы на Rust, и хотя
cf-html и функции, из которых он состоит, являются ключевой частью нашей
инфраструктуры, над которой необходимо поработать, есть и многие другие.

Безопасность в языках программирования часто рассматривается как благо с
точки зрения предотвращения ошибок, но как компания мы обнаружили, что
она также позволяет вам делать вещи, которые считались бы очень трудными
или вообще невозможными для выполнения безопасно. Будь то предоставление
Wireshark-подобного языка фильтрации для написания правил брандмауэра, позволяя
миллионам пользователей писать произвольный код на JavaScript и запускать его
непосредственно на нашей платформе или переписывать HTML-ответы "на лету".
Наличие строгих границ позволяет нам предоставлять услуги, которые мы не смогли
бы предоставить в противном случае, при этом мы можем быть уверены в том, что
такие проблемы с безопасностью памяти, от которых раньше страдала индустрия, все
больше уходят в прошлое.


\section{Перевод аннотации к статье}

\subsection{Аннотация №1}

\begin{center}
  \bf Арушанян И.О. Применение метода граничных интегральных уравнений для численного решения задачи Дирихле в областях с угловыми точками // Вычислительные методы и программирование. 2000. Т.1. С. 1-7.
\end{center}

Аннотация

Задача Дирихле на области с угловыми точками сводится к граничному интегральному уравнению, для численного решения которого предлагается метод, обладающий экспоненциальной скоростью сходимости. Рассматривается способ вычисления нормальной производной решения указанной задачи. Приводятся оценки количества арифметических операций.

Ключевые слова: задача Дирихле, области с угловыми точками, граничные интегральные уравнения, экспоненциальная скорость сходимости, метод квадратур, аппроксимация, системы линейных алгебраических уравнений, разрывы в угловых точках.

\subsection{Перевод аннотации №1}

\begin{center}
\bf Arushanyan I.O. Application of the method of boundary integral equations for numerical solution of the Dirichlet problem in regions with angular points // Computational Methods and Programming. 2000. VOL.1. P. 1-7.
\end{center}

Abstract

The Dirichlet problem on the domain with angle points is reduced to the boundary integral equation. This paper is proposing method for numerical solution that possesses exponential speed of convergence for this equation. A method for calculating the normal derivative of the solution of the above problem is considered. Estimates of the number of arithmetic operations are given.

Keywords: Dirichlet problem, regions with corner points, boundary integral equations, exponential convergence rate, quadrature method, approximation, systems of linear algebraic equations, discontinuities in corner points.

\subsection{Аннотация №2}

\begin{center}
  \bf
Титаренко В.Н., Ягола А.Г. Метод отсечения выпуклых многогранников и его применение к некорректным задачам // Вычислительные методы и программирование. 2000. Т.1. С. 8-13.
\end{center}

Аннотация

Рассматриваются линейные некорректные задачи на компактных множествах специальной структуры. Предлагаются два подхода для оценки погрешности приближенного решения, основанные на методе отсечения выпуклых многогранников. Строится область, которой принадлежит точное решение обратной задачи для уравнения теплопроводности.

Ключевые слова: некорректная задача, оценка погрешности, метод отсечения выпуклых многогранников, уравнение теплопроводности.

\subsection{Перевод аннотации №2}

\begin{center}
  \bf 
Titarenko V.N., Yagola A.G. The method of cutting off convex polyhedrons and its application to incorrect problems // Computational Methods and Programming. 2000. VOL. 1, P. 8-13.
\end{center}

Abstract

We consider linear incorrect problems on compact sets of special structure. Two approaches for the estimation of the error of approximate solution based on the method of cutting off convex polyhedrons are proposed. The domain, which the exact solution of the inverse problem for the heat conduction equation belongs to, is constructed.

Keywords: incorrect problem, error estimation, convex polyhedron cutoff method, heat conduction equation.

\subsection{Аннотация №3}

\begin{center}
\bf Антонов Т.Ю., Фрик П.Г., Соколов Д.Д. Рост корреляций в свободно распадающейся МГД турбулентности // Вычислительные методы и программирование. 2000. Т.1. С. 14-18.
\end{center}

Аннотация

С помощью каскадных моделей турбулентности исследовалась долговременная
эволюция магнитного поля и поля скорости в условиях магнитогидродинами ческой
турбулентности с различными типами начального состояния. Для каждого типа
моделировались 24 реализации процесса со случайным шумом в начальных условиях.
Вычисления производились на кластере НИВЦ МГУ, состоящем из 24 параллельных
процессоров. В большинстве случаев развивалось когерентное состояние с высоким
уровнем корреляции между магнитным полем и полем скорости, для которого
характерен низкий уровень диссипации энергии. В то же время несколько реализаций
вели себя по-другому, показывая низкий уровень перекрестной спиральности и, как
следствие, быстрое вырождение процесса.

Ключевые слова: каскадные модели турбулентности, магнитогидродинамическая турбулентность, число Рейнольдса, диссипация энергии, математическое моделирование, параллельные процессоры.

\subsection{Перевод аннотации №3}

\begin{center}
\bf Antonov T.Y., Frik P.G., Sokolov D.D. Correlation growth in freely decaying MHD turbulence // Computational Methods and Programming. 2000. VOL. 1. P. 14-18.
\end{center}

Abstract

The long-term evolution of the magnetic field and velocity field under
magnetohydrodynamic turbulence conditions with different types of initial
states was investigated using cascade turbulence models. For each type, 24
implementations of the process with random noise in the initial conditions
were simulated. The computations were performed on a cluster of the NRWC of
Moscow State University consisting of 24 parallel processors. In most cases, a
coherent state with a high level of correlation between the magnetic field and
the velocity field developed, which is characterized by a low level of energy
dissipation. At the same time, a few realizations behaved differently, showing
a low level of cross-helixity and, as a consequence, rapid degeneracy of the
process.

Keywords: cascade turbulence models, magnetohydrodynamic turbulence, Reynolds number, energy dissipation, mathematical simulation, parallel processors.

\subsection{Аннотация №4}

\begin{center}
\bf Зяббарова А.А. Дифференциальная рента как основная форма рентного дохода в современной экономике // Экономические науки. 2007. 1(26). С. 172-174.
\end{center}

Аннотация

Предложена авторская классификация форм и видов ренты, в основу которой положено
отношение форм рентного дохода и этапов процесса ресурсопользования. Таким
образом, предложенная классификация является наиболее эффективной как с точки
зрения изучения природы, причин формирования рентного дохода и построения
системы управления рентным доходом, так и с точки зрения возможностей переноса
понятий из смежных теорий. Один из наиболее сложных моментов при построении
данной классификации заключался в формализации понятий “чистая рента” и
“квазирента”.

\subsection{Перевод аннотации №4}

\begin{center}
\bf Ziabbarova A.A. Differential rent as the main form of rent income in the modern economy // Economic Sciences. 2007. 1(26). P. 172-174.
\end{center}

Abstract

The author's classification of the forms and kinds of rent, which is based on
the relation between the forms of rent incomes and the stages of the process
of resource use, is offered. Thus, the offered classification is the most
effective both from the point of view of studying the nature and reasons of
formation of the rent incomes and construction of the rent incomes management
system, and from the point of view of possibilities to transfer concepts from
the adjacent theories. One of the most difficult moments in the construction
of this classification was the formalization of the concepts of "net rent" and
"quasi-rent".


\subsection{Аннотация №5}

\begin{center}
\bf Galby E. The complexity of blocking (semi)total dominating sets with edge contractions // Theoretical Computer Science. 2023. Vol. 950, #113678. https://doi.org/10.1016/j.tcs.2022.12.028.
\end{center}

Abstract

We consider the problem of reducing the (semi)total domination number of a graph
by one by contracting edges. It is known that this can always be done with at
most three edge contractions and that deciding whether one edge contraction
suffices is an NP-hard problem. We show that for every fixed $k \in \{2,3\}$,
deciding whether exactly k edge contractions are necessary is NP-hard and
further provide for k=2 complete complexity dichotomies on monogenic graph
classes.

Keywords: Total domination number; Semitotal domination number; Edge contraction; Blocker problem; H-free graphs

\subsection{Перевод аннотации №5}

\begin{center}
\bf Гэлби Э. Сложность блокирования (полу)полных доминирующих множеств с сужениями краев // Теоретическая информатика. 2023. Т. 950, #113678. https://doi.org/10.1016/j.tcs.2022.12.028.
\end{center}

Аннотация

Мы рассматриваем проблему уменьшения числа (полу)полного доминирования графа
на единицу путем сокращения ребер. Известно, что это всегда можно сделать не
более чем тремя сокращениями ребер и что решение вопроса о том, достаточно ли
одного сокращения ребра, является NP-трудной задачей. Мы показываем, что для
каждого фиксированного $k \in \{2,3\}$ решение вопроса о необходимости ровно
k сокращений ребер является NP-трудной задачей, и далее приводим k=2 полные
дихотомии сложности для классов моногенных графов.

Ключевые слова: Полное число доминирования; Полутотальное число доминирования; Сжатие ребер; Проблема блокировщика; H-свободные графы

\subsection{Аннотация №6}

\begin{center}
\bf Chang Y.-J., Studený J., Suomela J. Distributed graph problems through an automata-theoretic lens // Theoretical Computer Science. 2023. Vol. 951. #113710.
https://doi.org/10.1016/j.tcs.2023.113710.
\end{center}

Abstract 

The locality of a graph problem is the smallest distance T such that each node
can choose its own part of the solution based on its radius-T neighborhood. In
many settings, a graph problem can be solved efficiently with a distributed
or parallel algorithm if and only if it has a small locality. In this work we
seek to automate the study of solvability and locality: given the description
of a graph problem Π, we would like to determine if Π is solvable and what
is the asymptotic locality of Π as a function of the size of the graph. Put
otherwise, we seek to automatically synthesize efficient distributed and
parallel algorithms for solving Π. We focus on locally checkable graph problems;
these are problems in which a solution is globally feasible if it looks feasible
in all constant-radius neighborhoods. Prior work on such problems has brought
primarily bad news: questions related to locality are undecidable in general,
and even if we focus on the case of labeled paths and cycles, determining
locality is PSPACE-hard (Balliu et al., PODC 2019). We complement prior negative
results with efficient algorithms for the cases of unlabeled paths and cycles
and, as an extension, for rooted trees. We study locally checkable graph
problems from an automata-theoretic perspective by representing a locally
checkable problem Π as a nondeterministic finite automaton M over a unary
alphabet. We identify polynomial-time-computable properties of the automaton M
that near-completely capture the solvability and locality of Π in cycles and
paths, with the exception of one specific case that is co-NP-complete.

Keywords: Distributed algorithms; Computational complexity; Algorithm synthesis; Automata theory; LOCAL model; LCL problems 

\subsection{Перевод аннотации №6}

\begin{center}
\bf Chang Y.-J., Studený J., Suomela J. Распределённые графовые задачи с точки зрения теории автоматов // Теоретическая информатика. 2023. Т. 951. #113710.
https://doi.org/10.1016/j.tcs.2023.113710.
  
\end{center}

Аннотация 

Локальность графовой задачи - это наименьшее расстояние T, такое, что каждый
узел может выбрать свою часть решения на основе своей окрестности радиуса-T.
Во многих случаях графовая задача может быть эффективно решена с помощью
распределенного или параллельного алгоритма тогда и только тогда, когда
она имеет малую локальность. В данной работе мы стремимся автоматизировать
исследование разрешимости и локальности: учитывая описание графовой задачи Π,
мы хотели бы определить, разрешима ли Π и какова асимптотическая локальность
Π как функция размера графа. Говоря иначе, мы стремимся автоматически
синтезировать эффективные распределенные и параллельные алгоритмы для решения
Π. Мы фокусируемся на локально проверяемых проблемах графов; это проблемы,
в которых решение глобально выполнимо, если оно выглядит выполнимым во всех
окрестностях постоянного радиуса. Предыдущие работы по таким проблемам принесли
в основном плохие новости: вопросы, связанные с локальностью, неразрешимы в
общем случае, и даже если мы сосредоточимся на случае маркированных путей и
циклов, определение локальности является PSPACE-трудным (Balliu et al., PODC
2019). Мы дополняем предыдущие отрицательные результаты эффективными алгоритмами
для случаев немаркированных путей и циклов и, в качестве расширения, для
деревьев с корнями. Мы изучаем локально проверяемые проблемы графов с точки
зрения теории автоматов, представляя локально проверяемую проблему Π в виде
недетерминированного конечного автомата M над унарным алфавитом. Мы определяем
вычислимые за полиномиальное время свойства автомата M, которые почти полностью
отражают разрешимость и локальность Π в циклах и путях, за исключением одного
конкретного случая, который является co-NP-полным.

Ключевые слова: Распределенные алгоритмы; вычислительная сложность; синтез алгоритмов; теория автоматов; модель LOCAL; задачи LCL


\section{Редактирование машинного перевода}

\subsection*{Текст оригинала}

\begin{center}
  \bf
  «„Искусственный интеллект“ — это просто новостной хайповый термин»
\end{center}

«„Искусственный интеллект“ — это просто новостной хайповый термин». Интервью
с Алексеем Тихоновым, специалистом по машинному обучению, о силе и слабости
современных нейросетей.

Мясные машины ака живые люди морально устаревают не по дням, а по часам, зато
нейросети растут как грибы после дождя. Журнал «Нож» привык держать руку на
пульсе, поэтому мы решили провести смотр войск и выяснить, на что уже способны
искусственные нейроны и чему научатся в ближайшее время. За разъяснениями
мы обратились к специалисту по машинному обучению Алексею Тихонову, а он
рассказал нам о генерации киберпараноидального бреда, о сходстве нейросетей с
попугайчиками, о том, что искусственного интеллекта не существует, а также о
других любопытных вещах и феноменах.

— Недавно в нью-йоркском издательстве Dead Alive вышла книга Paranoid
Transformer — дневник параноика, сгенерированный вами при помощи нейросетей.
Расскажите, пожалуйста, подробнее об этом проекте.

— Есть такое ежегодное мероприятие NaNoGenMo, оно проводится уже много лет
подряд каждый ноябрь и привлекает людей из разных стран: они собираются онлайн
и в формате скорее коллаборации и обсуждения, чем соревнования, придумывают и
проверяют разные идеи и гипотезы по немодерируемой генерации и обработке текста.
Никакого утилитаризма в этом нет: грубо говоря, если вам нужны стихи, то проще
нанять поэта — выйдет дешевле и качественнее, чем генерировать нейросетью.

Я давно собирался принять в этом мероприятии участие и в 2019 году наконец
нашел время. После того как NaNoGenMo закончился, ко мне обратились ребята,
которые, судя по всему, тоже в нем когда-то участвовали, а потом сделали журнал,
где публикуют всякие странные проекты, связанные с генерацией поэтических
и прозаических литературных текстов — надо понимать, что это очень нишевая
штука. Так вот, им понравился мой проект, и они предложили принять участие
в их конкурсе. Я подумал, что скучно два раза подавать одно и тоже, и решил
что-нибудь доделать в этом проекте: добавил нейросеть, рисующую на полях
картинки-каракули, а сам текст представил как «написанный от руки» с помощью еще
одной нейросети, причем дрожание почерка сделал зависимым от эмоциональности
записываемого текста. После того как я выиграл конкурс, мне предложили издать
текст в виде книги.

— А на каких корпусах текстов вы обучали нейросети и как вообще осуществляется
их обучение?

— Весь проект англоязычный, как и конкурс. Что касается обучения, сформулирую
так: есть современная парадигма в обучении нейросетей, которая называется
Transfer learning. В случае с текстами этот подход подразумевает использование
большого корпуса текстов для обучения базовой модели («большой» — это
максимально большой, условно говоря, «весь доступный интернет» или «вся
„Википедия“»). В результате эта предобученная модель получает информацию о
том, как вообще устроены человеческие тексты. Она может выучить морфологию,
синтаксис, пунктуацию, общие знания и т. д. А затем берется какая-то
относительно небольшая пачка данных под конкретную задачу, и на ней происходит
донастройка сети.

Схожим образом, например, делался проект «Нейронная оборона»: не написал, к
сожалению, ни Егор Летов, ни даже Пушкин, столько текстов, чтобы на них можно
было с нуля обучить нейросеть. Когда объема текстов недостаточно, сеть может эти
тексты только вызубрить наизусть, но не научиться самостоятельно генерировать
похожие.

В этом случае можно на большом универсальном корпусе один раз обучить базовую
языковую модель, а дальше она уже будет использоваться как основа для обучения
в разных задачах: желающие могут ее брать и с помощью относительно небольших
корпусов производить доучивание под конкретную ситуацию, например для генерации
текста в заданной стилистике. В процессе этой донастройки сеть предположительно
должна схватить суть того, что от нее требуется в данном конкретном случае,
какая задача перед ней ставится, и по факту она справляется с этим гораздо
лучше, чем непредобученная сеть.

В проекте Paranoid Transformer было ровно это использовано: взята предобученная
сеть GPT (доступная для всех) и относительно небольшой корпус текстов,
состоящий из афоризмов, киберпанковских, шифропанковских и разных атмосферных
в определенном смысле текстов. Я специально настроил сеть на то, чтобы она, с
одной стороны, писала немного киберпанковские по тематике тексты, а с другой —
чтобы форма их была ближе к афоризмам или коротким высказываниям. В результате
получился поток каких-то странных мыслей, что достаточно хорошо вписывалось в
концепцию дневника.

— Правильно ли я понимаю, что научить нейросеть писать «в стиле Льва Толстого»,
например, проще, чем «в стиле Фонвизина», просто потому что Толстой написал
девяносто томов, а Фонвизин два?

— Наверное, в каком-то смысле это могло бы быть правдой. Когда мы говорим о
постановке задачи «научить сеть писать что-то в стиле кого-то», речь же в
конечном счете идет о математической задаче. Нам нужно сначала четко определить,
что такое «стиль» и что такое «писать в стиле», а это не всегда очевидно.
Пока мы этого не сделаем, довольно сложно объективно оценить, кто у нас лучше
получается — Толстой или Фонвизин. Без такой детализации вопроса довольно сложно
на него ответить, потому что может оказаться, что, несмотря на то, что некий
автор написал гораздо больше текстов — то есть оставил нам большее количество
информации о своем стиле, — сам стиль у него в каком-то смысле более сложный,
и поэтому нужно еще больше текстов. То есть пока этот вопрос не приземлен на
какую-то количественную конкретику, он остается открытым. Но исходя из общих
соображений, общей логики, наверное, да: чем больше текстов — тем проще.

— Что нейросеть схватывает в первую очередь во время обучения — морфологию?

— Когда мы говорим про обучение сетей, это всегда компромисс между тем, как мы
об этом думаем, и тем, что на самом деле происходит. По правде говоря, в области
машинного обучения достаточно давно наступила эпоха, когда обучение не является
в чистом виде интерпретируемым. Модели учатся и дают хороший результат, а как
именно это происходит, в какой последовательности оно там, внутри, усваивается,
мы часто можем лишь гадать и оценивать по каким-то косвенным признакам, и,
кажется, это всегда будет некоторой спекуляцией.

Подобно тому, как вы будете попугайчика учить разговаривать, и однажды
он заговорит, но определить, в какой момент он усвоил слова, в какой
последовательности и насколько он их понимает, довольно сложно.
Это отдельная наука — попытаться придумать, как понять, что происходит внутри
сложной нейросетевой модели, когда она обучается. Например, современные
английские модели типа GPT-3 читают при обучении сотни гигабайт текста. Это
гораздо больше, чем любой из нас прочитает за всю свою жизнь, но при этом
такая сеть ничего, кроме текстов, не изучает, не взаимодействует с миром и не
связывает слова с окружающими явлениями. Она лишь пытается, например, в каждый
момент предсказать следующее слово текста и, предсказывая неверно, учится на
своих ошибках.

\subsection{Отредактированный машинный перевод}

\begin{center}
  \bf
"Artificial Intelligence is just a word hyped up by news"
\end{center}

"'Artificial Intelligence' is just a word hyped up by news". Interview with
Alexey Tikhonov, a machine learning specialist, about the strengths and
weaknesses of modern neural networks.

Meat machines aka living people are becoming obsolete by leaps and bounds, but
neural networks are growing like mushrooms after the rain. The Knife magazine is
used to keeping its finger on the pulse, so we decided to review the troops and
find out what artificial neurons are already capable of and what they will learn
in the near future. We turned to machine learning specialist Alexey Tikhonov
for clarification, and he told us about the generation of cyber-paranoid
delirium, about the similarity of neural networks with parrots, that artificial
intelligence does not exist, as well as about other curious things.

— Recently, the New York publishing house "Dead Alive" published the book
"Paranoid Transformer" - the diary of a paranoid, generated by you with the help
of neural networks. Please tell us more about this project.

— There is such an annual event NaNoGenMo, it has been held for many years
in a row every November and attracts people from different countries: they
gather online and in the format of collaboration and discussion rather than
competition, invent and test different ideas and hypotheses on unmoderated
generation and text processing. There is no utilitarianism in this: roughly
speaking, if you need poems, it is easier to hire a poet — it will be cheaper
and better than generating a neural network.

I have been planning to take part in this event for a long time and in 2019 I
finally found the time. After NaNoGenMo ended, I was approached by guys who,
apparently, also participated in it once, and then made a magazine where they
publish all sorts of strange projects related to the generation of poetic and
prose literary texts - you have to understand that this is a very niche thing.
They liked my project, and offered to take part in their competition. I thought
it was boring to submit same thing twice, and decided to improve this project: I
added a neural network that is drawing doodles on the margins, and presented the
text itself as "handwritten" with the help of another neural network, and made
the trembling of the handwriting dependent on the emotionality of the written
text. After I won the contest, I was offered to publish the text in the form of
a book.

— And on which corpus of texts did you train neural networks and how is their
training carried out in general?

— The whole project is in English, as is the competition. As for training, I'll
say this way: there is a modern paradigm in training neural networks, which is
called Transfer learning. In the case of texts, this approach implies the use of
a large corpus of texts for teaching the basic model ("large" is the largest,
relatively speaking, "all available Internet" or "all Wikipedia"). As a result,
this pre-trained model receives information about how human texts are arranged
in general. It can learn morphology, syntax, punctuation, general knowledge,
etc. And then some relatively small bundle of data is taken for a specific task,
and the network is fine-tuned on it.

In a similar way, for example, the Neural Defense project was done:
unfortunately, neither Egor Letov nor even Pushkin wrote so many texts that they
could be used to train a neural network from scratch. When the volume of texts
is not enough, the network can only memorize these texts by heart, but not learn
how to generate similar ones on its own.

In this case, it is possible to train the basic language model once on a large
universal corpus, and then it will already be used as a basis for learning other
tasks: someone can take it and use relatively small corpus to complete training
for a specific situation. For example, to generate text in a given style. In the
process of this adjustment, the network is presumed to grasp the essence of what
is required of it in this particular case, understand the given task. And in
fact it handles tasks much better than an untrained network.

In the Paranoid Transformer project, exactly this was used: a pre-trained
GPT network (accessible to everyone) and a relatively small corpus of texts
consisting of aphorisms, cyberpunk, cipherpunk and various texts with a certain
atmosphere were taken. I have specifically set up the network so that, on the
one hand, it writes a little cyberpunk texts on the subject, and on the other —
so that their form is closer to aphorisms or short statements. The result was a
stream of some strange thoughts, which fit well enough into the concept of the
diary.

— Do I understand correctly that it is easier to teach a neural network to write
"in the style of Leo Tolstoy", for example, than "in the style of Fonvizin",
simply because Tolstoy wrote ninety volumes, and Fonvizin two?

— Probably, in some sense it could be true. When we talk about setting the
task "to teach the network to write something in the style of someone", we are
ultimately talking about a mathematical problem. We need to first clearly define
what is "style" and what is "writing in style", and this is not always obvious.
Until we do this, it is quite difficult to objectively assess who we do better
— Tolstoy or Fonvizin. Without details, it is quite difficult to answer such
question. It may turn out that, despite the fact that a certain author wrote
much more texts — that is, he left us more information about his style — his
style itself is in some sense more complex, and therefore even more texts are
needed. That is, as long as this question is not grounded on some quantitative
specifics, it remains open. But based on general considerations and general
logic, probably yes: the more texts — the easier.

— What does the neural network grasp first of all during training — morphology?

— When we talk about training of networks, it's always a compromise between
how we think about it and what actually happens. To tell the truth, for quite
a while in the field of machine learning the learning itself is not purely
interpretable. Models learn and give a good result, and how exactly this
happens, in what sequence it is internalized there, inside, we can often only
guess and evaluate by some indirect signs, and it seems that there will always
be some speculation.

You can teach a parrot to talk, and one day he will speak, but it is quite
difficult to determine at what point he learned the words, in what sequence and
how much he understands them. It is a separate science to try to figure out how
to understand what is happening inside a complex neural network model when it is
being trained. For example, modern English models like GPT-3 read hundreds of
gigabytes of text during training. This is much more than any of us will read in
our entire lives, but at the same time, such a network does not study anything
except texts, does not interact with the world and does not connect words with
surrounding phenomena. It only tries, for example, to predict the next word of
the text at every moment and, predicting incorrectly, learns from its mistakes.


% \bibliographystyle{gost780uv}
% \inputencoding{cp1251}
% \bibliography{sources}
% \inputencoding{utf8}

\end{document}