Deterministic Parallel Execution of Applications

제목부터 어렵네. deterministic은 우리말로 결정론적인데 쉽게 함수를 생각하면 되지. 함수는 어떠한 외부 조건에 영향 받지 않고 동일한 입력을 주면 동일한 출력을 보장하잖아. 어떤 입력을 주면 어떤 출력이 나올거라는 것이 결정되었다는 거지. 다수의 행위들을 병렬적으로 처리하려면 각 행위들은 서로 독립적이어야 해. 어떤 행위의 결과가 다른 행위들의 결과에 영향을 받아서는 안 되지.

Blockchain consensus depends upon deterministic (reproducible) behavior. This means all parallel execution must be free from the use of mutexes or other locking primitives. Without locks there must be some way to guarantee that transactions that may be executed in parallel do not create non-deterministic results.

행위들이 서로에 행위에 의존한다면 병렬 처리를 위해서 하나가 실행될 때 다른 하나는 실행하지 못하도록 잠가두어야 해. 결정론적이라면 그럴 필요가 없지. 다수의 행위들을 가지고 그들 사이의 의존관계를 분석해서 잠금을 설계하는 것은 쉬운 일이 아니야. 잘못하면 문제도 많이 생기지. 처음 부터 결정론적 임을 증명하면 문제가 쉬워지는 거지.
다수의 노드들이 블록체인에서 합의 한다는 것은 같은 입력에 대해 동일한 결과가 나와야 가능하지. 누구나 같은 입력으로 다시 해 봐도 같은 결과를 얻게 되어야 한다는 거지. 블록체인 합의에 있어 '결정론적' 행위가 중요한 이유.

The June 2018 release of EOS.IO software will run single threaded, yet it contains the data structures necessary for future multithreaded, parallel execution.

아직까지는 싱글 쓰레드에서 돌아간다는 거지. 앞으로 멀티 쓰레드가 가능하도록 병렬 처리할 수 있도록 하겠다는 거고. 그렇게 하는 데 필요한 데이터 구조들을 포함할 거라는 거고.

In an EOS.IO software-based blockchain, once parallel operation is enabled, it will be the job of the block producer to organize Action delivery into independent shards so that they can be evaluated in parallel. The schedule is the output of a block producer and will be deterministically executed, but the process for generating the schedule need not be deterministic. This means that block producers can utilize parallel algorithms to schedule transactions.

일단 병렬 처리가 가능해지면, 액션 전달을 샤드(shards)들로 조직화하는 것은 BP의 일이 될 것이다. 샤드까지 등장하네. 병렬 처리를 어떻게 할 지는 BP들의 몫이고, BP들은 분산 시스템 아키텍처를 설계하고 구축한다는 거지.
BP들은 트랜잭션들을 스케줄링하기 위해서 병렬처리 알고리즘을 사용할 수 있겠지. 스케줄링은 BP들에 의해서 만들어지는 거니까.
그렇다고 스케줄을 만들어 내는 일 까지 병렬처리할 필요는 없겠지. 앞 뒤 문장들을 이해하는 데 방해가 될 수 있는, 굳이 언급하지 않아도 될 것 같은데 백서 수준에서 언급하는 이유는 뭘까? 뭔가 중요한 의미가 있는 건가?

Part of parallel execution means that when a script generates a new Action it does not get delivered immediately, instead it is scheduled to be delivered in the next cycle. The reason it cannot be delivered immediately is because the receiver may be actively modifying its own state in another shard.

액션 수신자가 다른 샤드에서 자신의 상태를 변경하고 있다면 즉각적으로 액션을 전달 받을 수 없겠지. 이런 경우 스크립트는 새로운 액션을 생성하고 다음 사이클에 전달하는 것으로 스케줄을 잡겠지. 순서에 상관 없이 병렬처리 되니까 이런게 가능한 거지.

Minimizing Communication Latency

Latency is the time it takes for one account to send an Action to another account and then receive a response. The goal is to enable two accounts to exchange Actions back and forth within a single block without having to wait 0.5 seconds between each Action. To enable this, the EOS.IO software divides each block into cycles. Each cycle is divided into shards and each shard contains a list of transactions. Each transaction contains a set of Actions to be delivered. This structure can be visualized as a tree where alternating layers are processed sequentially and in parallel.

지연은 한 계정에서 다른 계정으로 액션(수행 요청)을 보내고 응답을 받기까지의 시간. 계정에서 계정으로 액션을 보낸다? 이건 정말 오해의 소지가 있어 보이네. 액션은 계약에 묶여 블록체인에 배포되고, 액션 수행을 요청하는 계정에 의해 액션을 수행하는 것인데. 액션 수행 요청은 메시지라는 용어를 사용하는 게 더 좋은데 이전 버전에서 메시지를 사용하다가 액션으로 바꾼 것을 보니 뭔가 의도가 있는 것 같은데.
목표는 지연시간을 0.5초 이내로 하겠다는 거잖아. 0.5초 마다 블록이 생성되니 하나의 블록 내에서 액션 요청에서 액션 실행 응답까지 마치겠다는 거잖아. 자꾸 액션을 주고 받는다고 하니 헷갈리네. 진짜 액션을 주고 받는 것은 아니겠지.
이렇게 하려니 성능을 높일 수 있는 방법이 필요하지. 성능을 높이는 방법은 분산처리로 병행처리 하는 거 겠지. 하나의 블록에는 다수의 트랜잭션들이 포함되고 하나의 트랜잭션에는 다수의 액션들이 포함되잖아. 실제적으로 처리해야 할 일은 액션에서 일어나는 거고 액션의 로직을 병행처리해야 하지. 이것에 대해서는 앞에서 살펴봤고.*
하나의 블록에 다수의 트랜잭션들이 포함되니 트랜잭션을 순차적으로 처리하면서 액션을 병행 처리해 봐야 큰 이득을 얻을 수 없겠지. 결국 트랜잭션들을 좀 더 작은 그룹으로 묶어서 분산 병행 처리해야겠지. 그래서 샤드를 등장시키는 거고.
그런데 제시된 계층은 좀 더 복잡하네. 순차와 병행을 번갈아 가면서 구조화하고 있네. 그렇게 하는 좀 더 복잡한 이야기가 있겠지.

Block
Region
Cycles (sequential)
Shards (parallel)
Transactions (sequential)
Actions (sequential)
Receiver and Notified Accounts (parallel)

블록의 구조화를 이렇게 하겠다는 거. 너무 복잡한 거 아냐?

Transactions generated in one cycle can be delivered in any subsequent cycle or block. Block producers will keep adding cycles to a block until the maximum wall clock time has passed or there are no new generated transactions to deliver.

한 사이클 내에 포함된 트랜잭션들은 다음 사이클이나 다음 블록으로 전달될 수 있어. 한 사이클에서 처리되지 않은 트랜잭션은 다음 사이클로 넘어가고, 한 블록에서 처리되지 않은 트랜재션은 다음 블록으로 넘어 가겠지. 그런데 사이클은 어떤 기준으로 몇 개 정도가 만들어지는걸까? BP는 maximum wall clock이 지났거나 추가할 트랜잭션이 없을 때까지 계속 사이클을 추가할 거야. *maximum wall clock - 우리말로 바꾸기 참 뭐하네. 암튼 한 블록을 생산할 수 있는 최대 시간, 현재는 0.5초.

It is possible to use static analysis of a block to verify that within a given cycle no two shards contain transactions that modify the same account. So long as that invariant is maintained a block can be processed by running all shards in parallel.

한 사이클에 포함된 트랜잭션들 중에 같은 계정을 수정하는 것이 있는지는 쉽게 알 수 있지. 트랜잭션에 포함된 액션의 계정을 보면 알 수 있지. 같은 계정을 수정하는 트랜잭션이 아니라면 병렬 처리 가능한거고. 같은 계정을 수정하는 트랜잭션들은 다른 샤드로 분리해서 병렬처리하면 되겠지.

Read-Only Action Handlers

Some accounts may be able to process an Action on a pass/fail basis without modifying their internal state. If this is the case, then these handlers can be executed in parallel so long as only read-only Action handlers for a particular account are included in one or more shards within a particular cycle.

어떤 계정들은 내부 상태 변경 없이 성공/실패에 기반해 액션을 처리할 수도 있어. 이런 경우 액션을 처리하는 액션 핸들러를 읽기 전용이라고 하고. 당연히 이러한 액션들은 병렬처리가 가능하겠지. 읽기 전용이 되는 구체적인 사례는?

Atomic Transactions with Multiple Accounts

Sometimes it is desirable to ensure that Actions are delivered to and accepted by multiple accounts atomically. In this case both Actions are placed in one transaction and both accounts will be assigned the same shard and the Actions applied sequentially.

계약을 이행하기 위해 다수의 참여자들이 요구되는 계약도 있지. 예를 들어 에스크로(escrow)는 삼자가 필요해. 이러한 경우 계약의 액션들 중에 다수의 계정들이 요구하는 것들이 있을 수 있고, 이것들은 한 트랜잭션 내에서 처리되어야 하지. 당연히 이러한 경우 액션들을 나눠서 병렬처리할 수 없겠지. 한 샤드 내에 포함되어 순차적으로 처리되어야 겠지.

Partial Evaluation of Blockchain State

Scaling blockchain technology necessitates that components are modular. Everyone should not have to run everything, especially if they only need to use a small subset of the applications.

An exchange application developer runs full nodes for the purpose of displaying the exchange state to its users. This exchange application has no need for the state associated with social media applications. EOS.IO software allows any full node to pick any subset of applications to run. Actions delivered to other applications are safely ignored if your application never depends upon the state of another contract.

확장성을 위해 모듈화 하겠다는 거지. 소스코드를 보면 다수의 플러그인(plub-in)들이 있고, 노드 실행 시 플러그인들을 설정할 수 있도록 되어 있어.

Subjective Best Effort Scheduling

스케줄링은 주관적이라는 거. 누구의 주관? BP의 주관.

The EOS.IO software cannot obligate block producers to deliver any Action to any other account. Each block producer makes their own subjective measurement of the computational complexity and time required to process a transaction. This applies whether a transaction is generated by a user or automatically by a smart contract.

BP들은 트랜잭션을 처리하는 데 요구되는 계산 복잡성과 시간을 주관적으로 측정할 수 있어. 알아서 가장 좋은 방법으로 하라는 거지.

On a launched blockchain adopting the EOS.IO software, at a network level all transactions are billed a computational bandwidth cost based on the number of WASM instructions executed. However, each individual block producer using the software may calculate resource usage using their own algorithm and measurements. When a block producer concludes that a transaction or account has consumed a disproportionate amount of the computational capacity they simply reject the transaction when producing their own block; however, they will still process the transaction if other block producers consider it valid.

액션을 수행하기 위해서는 자원이 필요하지. 액션은 WASM(웹어셈블리)의 형태로 실행 되기 때문에 WASM의 명령 수에 따라 비용을 계산할 수 있어.
BP들은 그들 자신의 알고리즘과 측정 방법을 사용해서 자원 사용량을 계산 해. BP는 과도한 수준의 계산 역량을 요구하는 액션이 포함된 트랜잭션이라고 판단되면 자신의 블록에 포함하는 것을 거부할 수 있어. 그렇다고 무조건 거부하면 안 되겠지. 다른 BP들이 유효하다고 판단하면 그때는 그 트랜잭션을 처리해야 해.

In general, so long as even 1 block producer considers a transaction as valid and under the resource usage limits then all other block producers will also accept it, but it may take up to 1 minute for the transaction to find that producer.

일반적으로 한 블록 생산자가 유효하다고 판단하면 다른 블록 생산자들은 받아들여. 하지만 경우에 따라서는 트랜잭션을 블록에 포함할 BP를 찾기 위해 1분 정도의 시간이 걸릴 수도 있어.

In some cases, a producer may create a block that includes transactions that are an order of magnitude outside of acceptable ranges. In this case the next block producer may opt to reject the block and the tie will be broken by the third producer. This is no different than what would happen if a large block caused network propagation delays. The community would notice a pattern of abuse and eventually remove votes from the rogue producer.

어떤 BP가 허용 범위를 벗어난 트랜잭션을 포함해 블록을 생산하는 경우가 있을 수 있지. 이런 경우 두 번째 블록 생산자는 그 블록을 거부할 수 있어. 블록을 거부하는 거? 트랜잭션을 거부하는 거겠지. 이런 트랜잭션은 첫 번째 블록에서 처리하지 못하고 다음 블록으로 넘어올 거고. 이렇게 되면 첫 번째 블록 생산자는 유효한 것으로 트랜잭션을 본 것이고, 두 번째 블록 생산자는 유효하지 않은 것으로 본 것이 되지. 1 : 1이 된거지. 세 번째 BP의 선택에 따라 1 : 1 상황은 깨지게 되지.
허용 범위를 벗어난 트랜잭션을 포함하는 것은 큰 블록이 블록 전파를 지연시키는 원인이 되는 것과 같아. 커뮤니티는 이런 일이 생긴 걸 알 수 있기 때문에 투표를 통해 이런 불량 BP를 퇴출 시킬 수 있지. BP들이 저지를 수 있는 불량 사례들을 패턴화 하고, 그것들이 눈에 잘 띌 수 있게 하는 수단이 필요해 보이네. 토큰 보유자들이 얼마나 이러한 정보에 신경을 써서 투표에 반영할 지는 잘 모르겠고.

This subjective evaluation of computational cost frees the blockchain from having to precisely and deterministically measure how long something takes to run. With this design there is no need to precisely count instructions which dramatically increases opportunities for optimization without breaking consensus.

결국 트랜잭션에 포함할 것인가를 결정하는 것은 BP들의 주관이고, 주관적인 판단은 다른 BP들의 판단에 의해 옳고 그름을 판단하겠다는 것이네. 최적화에도 합의의 결과를 반영하겠다는 것.

Deferred Transactions

EOS.IO Software supports deferred transactions that are scheduled to execute in the future. This enables computation to move to different shards and/or the creation of long-running processes that continuously schedule a continuance transaction.

deferred 트랜잭션을 지원 해. deferred는 지금 실행하는 것이 아니라 나중에 실행하는 것으로 스케줄링 하겠다는 거지. *deferred 이것도 우리말로 표현하기 쉽지 않네. '지연된'이라고 하면 늘어진 것 같고. '미뤄진'이나 '연기된'이 의미적으로는 더 와 닿는데 어색하고.
deferred 트랜잭션으로 계산을 다른 샤드로 이동하거나 long-running process를 가능하게 해. long-running process는 이름 그대로 프로세스에 긴 시간이 필요한 거야. 긴 시간이 필요한 이유는 다수의 참여자가 다수의 행위를 통해 프로세스를 완료해야 하기 때문이지. 어떤 참여자의 행위는 요청했을 때 바로 수행되지 않을 수도 있어. 비동기라는 거지. deferred 트랜잭션은 비동기적으로 트랜잭션을 처리할 수 있는 방법을 제공하겠다는 거야.

Context Free Actions

이름 그대로 컨텍스트에 자유로운 액션. 컨텍스트를 고려할 필요가 없다는 것은 고려해야 할 상태(조건, 제약)이 없다는 것.
A Context Free Action involves computations that depend only on transaction data, but not upon the blockchain state. Signature verification, for example, is a computation that requires only the transaction data and a signature to determine the public key that signed the transaction. This is one of the most expensive individual computations a blockchain must perform, but because this computation is context free it can be performed in parallel.

context free 액션은 트랜잭션 데이터에만 의존해서 계산을 하겠지 - 블록체인 상태에 의존하지 않고. 예를 들어 서명을 검증하는 것은 서명한 공개 키를 결정하기 위한 트랜잭션 데이터와 서명 만 있으면 되지. 서명 검증은 블록체인 내에서 반드시 수행되어야만 하는 가장 비싼 개별 계산 중 하나인데 병렬 처리 못한다면 문제가 되겠지. context free한 액션이 필요해!

'context free' 이것도 우리말로 표현하기 쉽지 않아. '문맥 자유'이러한 용어를 쓰기는 싫어! '컨텍스트 독립' 이것도 그렇고.

Context Free Actions are like other user Actions, except they lack access to the blockchain state to perform validation. Not only does this enable EOS.IO to process all Context Free Actions such as signature verification in parallel, but more importantly, this enables generalized signature verification.

서명 검증을 일반화하고 병렬처리 할 길이 열렸다는 것.

With support for Context Free Actions, scalability techniques such as Sharding, Raiden, Plasma, State Channels, and others become much more parallelizable and practical. This development enables efficient inter-blockchain communication and potentially unlimited scalability.

병렬 처리를 위한 다양한 기술들을 사용하는 것도 쉬워졌다는 것. 블록체인 간 커뮤니케이션과 잠재적으로 제한 없는 확장성도 가능해 졌다는 것. 어떻게? context free 액션을 가지고.