7. Transactions

The slippery Concept of a Transaction

ACID

• Atomicity

  • The transaction is aborted if some of writes in one grouped atomic transaction can not be completed.
  • main idea: what happens if a client wants to make several writes but what if some fails?

• Consistency

  • the data should always follow some rules.
    • ex. in accounting system, credit sum == debit sum
  • it is a property of application

• Isolation

  • concurrently executing transactions are isolated from each other
  • classic text describes isolation as serializability
  • (serializability): each transaction can pretend that it is the only transaction running on the entire database

• Durability

  • Once a transaction has committed successfully, data written will not be forgotten, despite of hardware fault or database crash
  • single-node DB : data has been written to nonvolatile storage
  • replicated DB : successfully copied to some number of nodes

Single-Object and Multi-Object Operations

• common philosophy: Abandon transaction entirely, rather than remain half-finished

• leaderless replication : best effort

• retry is good, though not perfect

  • transaction succeed, but network( DB → server ) failed

  • when failed due to overload → worse

  • only worth in transient errors

  • side effects

  • if client process fails while retrying, any data it was trying to write to the DB is lost

    Weak Isolation Levels

  • transaction isolation

    Rather than blindly relying on tools, we need to develop a good understanding of the kinds of concurrency problems that exist and how to prevent them.

    Read committed

  • no dirty read : read only committed

    • when updating multiple objects, keep sync/consistency
    • the same result even after rollback

  • no dirty write : overwrite only committed

    • with row-level locks
    • when transaction is ongoing, others see old value.

    Snapshot Isolation and Repeatable Read

  • Repeatable Read

    • Nonrepeatable read(read skew)
      • The data read at the end of the transaction is different with previous query

  • Snapshot Isolation

    • each transaction reads from a consistent snapshot of database

      (see only the old data)

    • Readers never block writers, writers never block readers

    • multi-version concurrency control(MVCC)

      • maintaining several version of an object side by side
      • data is tagged with its transaction id(txid)

    • visibility rules

      At the start of the transaction, make a list of proceeding transactions.

      1. Any write of above transactions are ignored
      2. Any writes made by aborted transactions are ignored.
      3. Any writes made by transactions with later transaction ID are ignored

      Preventing lost updates

    • client1: read → update

      client2: read - > update

      client1's update is lost

    • Prevent by locking

      • explicit lock
      • compare and set
      • conflict resolution and replication

      Write skews and Phantoms

    • write skew

      • Transactions update two different objects concurrently and there occurs conflict.

      • ex. at least 2 doctors should be on_call.

        • Bob changes to on_cal=false, Alice changes to on_cal=false, concurrently.
        • Now less than 2 doctors are on call.
        • Two different objects(record of Bob, record of Alice) are updated

      • restricted solution

        serialization, or explicit lock on rows

    • phantom

      • a write in one transaction changes the result of a search query in another tranascation

      • ex. select → condition → update

        between select and update, something changed.

      • SELECT FOR UPDATE may not help when SELECT returns 0 rows.

      • materializing conflict : create a table of all possible combinations, and put lock there.

        Serializability

      • the end result is the same as if they had executed one at a time, serially without any concurrency

        Two-phase Locking

      • read : shared lock

      • write : exclusive lock

      • first phase : when the locks are acquired,

        second phase : when all the locks are released

      • predicate lock

        • lock that belongs to all objects that match some search condition
        • applies even to objects that do not yet exist

      • index-range locking(next-key locking)

        • predicate lock has not good performance.
        • lock on index

        Serializable Snapshot Isolation

      • pessimistic concurrency control

        • if anything may go wrong, better wait

      • optimistic concurrency control

        • transaction continues. If anything goes wrong, abort
        • old idea
        • tend to be better than pessimistic control

      • Serializable Snapshot Isolation is promising.

        • optimistic approach
        • allows transactions without blocking

6. Partition

Partitioning of key-value data

• key-range partitioning
  • partitioned with range
  • good for range-search
  • rebalancing by spliting into two subranges.
• hash partitioning
  • apply hash function. might add additional random letters at the end/begining.
    • common to create fixed number of partition in advance

Partitioning and Secondary index

• Document-partitioned index(local index)

  • secondary index is stored at the same partition with primary key and value
  • one write requires write to one partition.
  • one read may require reads from multiple partitions

• Term-partitioned index(global index)

  • secondary indices are partitioned too. Based on term

  • one write may require write to multiple partitions

  • one read only require read from one partition.

    Rebalancing Partitions

    Strategies for rebalancing

  • fixed number of partitions

    • create more partitions than the number of nodes and spread it when node is added.
    • Number of partitions does not change. But the number of partition per nodes changes.

  • dynamic partitioning

    • Similar with the top level of B-tree
    • Suitable for key range partitioned data, but hash-partitioned can also use it.

  • Partitioning proportionally to nodes.

    • When new node joins the cluster, randomly choose the node to split and half of the data are moved.

    Automatic? Manual?

  • due to the overhead and risk of rebalancing, manual commit should join the process

    Request Routing

    3 ways

  • client contact any node → if it does not have right partition, forward.

  • client contact to routing tier like zookeeper

  • client be aware of the partitioning

    Common issue

  • how to make routing decisions?

  • hard problem.

  • in case of Zookeeper,

    • each node registers itself in Zookeeper.
    • Zookeeper maintains the authoritative mapping of partitions to nodes. Whenever t

• core concern(business logic)
• cross-cutting concern(system layer logic. 실제 business logic 이외)

을 분리하는 프로그래밍 패러다임.

로깅, data validation, DB transaction 처리 등은 여러 곳에서 이용되지만, 분명히 프로그램의 핵심 로직은 아니다.

그렇다보니 Object가 하나의 책임과 역할을 수행하는 OOP를 적용하기에는 불편하고,
프로그램 로직과는 별개로 관리하는 것이 편리하다.

간단한 예시를 생각하보자.
- 로깅을 하기 위해서 모든 함수의 parmater로 logger를 포함해야한다거나,
- 모든 함수에서 사용자의 권한을 확인하는 코드를 호출해야한다면,

중복 코드로 가독성이 떨어지고, 프로그램 로직과 부차적인 코드를 구별해서 관리하기가 어렵다.

로깅 형식을 바꾼다던가, type을 변경하려고만 해도 여기저기 흩어져있는 관련된 코드를 모두 수정해야한다.

AOP에서는 이처럼 여러 곳에 사용되는(흩어져서 존재하는) 기능을 모듈화하고,
이용되는 상황을 정의? 조건화?하여 반복 코드를 줄인다.

wikipedia의 아래 설명이 제일 믿을만하고 명료했다.

An aspect of a program is a feature linked to many other parts of the program, but which is not related to the program's primary function.
(https://en.wikipedia.org/wiki/Aspect_(computer_programming))

This allows behaviors that are not central to the business logic (such as logging) to be added to a program without cluttering the code, core to the functionality.
(https://en.wikipedia.org/wiki/Aspect-oriented_programming)

(한 페이지 설명: https://www.simplilearn.com/spring-aop-tutorial)

- 이해하기가 조금 어렵고,

- control flow를 관리하기 어려워 GOTO 보다 나쁘다는 평가도 있다.

- 여러 곳에 흩어져있는 코드를 하나로 관리하다보니, 하나를 수정했을 때 전체 영향을 미칠 수 있다.

* 비고

AOP의 개념보다도, 이 문제를 해결하기 위해서 AOP를 사용하는 것이 맞는가? 라는 판단을 내리는 게 더 어려운 것 같다.

Cross-cutting concerns의 예시

• Business rules
• Caching
• Code mobility
• Data validation
• Domain-specific optimizations
• Error detection and correction
• Internationalization and localization which includes Language localisation
• Information security
• Logging
• Memory management
• Monitoring
• Persistence
• Product features
• Real-time constraints
• Synchronization
• Transaction processing
• Context-sensitive help

https://martinfowler.com/bliki/InversionOfControl.html

https://martinfowler.com/articles/injection.html

• controlling the flow of program

  One important characteristic of a framework is that the methods defined by the user to tailor the framework will often be called from within the framework itself, rather than from the user's application code. The framework often plays the role of the main program in coordinating and sequencing application activity. This inversion of control gives frameworks the power to serve as extensible skeletons. The methods supplied by the user tailor the generic algorithms defined in the framework for a particular application.-- Ralph Johnson and Brian Foote

• user가 정의한 함수를 언제/어떻게 호출하는지를 user의 application code가 결정하는 것이 아니라, framework에서 제어하는 것.

• 어떤 것을 spring의 bean으로 등록할지 정의하는 것은 user가 하지만,

  언제, 어떻게 bean을 등록하고, 호출하는지는 framework에서 제어한다.

  user는 interface/형식에 맞추어서 작성하면, 내부 구현(?)/알고리즘에 의해 알아서 해준다.

• library와 다른 점은, framework는 main program의 역할을 한다는 것.

5. Replication

Leaders and Followers

• synchronous replication

• asynchronous replication

• setting up new followers

  • take consistent snapshot of leader → pass to follower
  • follower connects to the leader and requests the changes after the snapshot

• leader failure: failover

  • HOW-TO

    • declare leader has failed(usually with timeout)
    • choose new leader: best candidate - node with latest data changes.
    • configure system with new leader. Let previous leader know he is not the leader anymore

  • problems

    • loss of data from previous leader
    • synchronizing with different storage system
    • two leaders at the same time
    • appropriate timeout for the declaration of leader's death

  • Implementation of replication log

    • statement-based
    • WAL(Write Ahead Log)
      • PostgreSQL, Oracle
      • low level - storage engine dependent
    • Logical log replication(row-based)
      • sequence of records describing writes to DB in row-level
        • insert : new value of column
        • delete : unique identifier of row
        • update : unique identifier, and new value
    • trigger based
      • big overhead

  • Problems of replication log

    • Read After Write Consistency
    • Monotonic Read : Do not read older value than previous read
    • Consistent Prefix Read : data read should appear in the same sequence with writes
    MultiLeader replication

  • Usecases

    • multi-datacenter
    • clients with offline operation
    • collaborative editing ex. google docs

  • Handling write conflicts

    • avoiding conflict

      • certain user writes to certain datacenter → not always the case

    • converging toward a consistent state

      • apply already codede script
      • read both values
      • automatifc conflict resolution
        • conflict-free replicated datatype
        • mergeable persistent data structure: three-way merge like git
        • operational transformation : algorithm

    • topology

      • circular : each write has tag

      • star

        • circular and star may fail if only one node fails.

      • all-to-all : result may be over taken

        Leaderless Replication

      • with coordinator node / or client write to several nodes

      • writing to DB when a node is down

        • write to/read from several nodes
        • read repair : when stale response is found, client writes back
        • anti-entropy process : on background, compare with other nodes

      • quorums for reading and writing

        • w + r > n
        • sloppy quorum: w and r may have nodes that are not included in n home nodes
        • hinted handoff: any writes that was temporarily accepted on behalf of another node are sent to the appropriate home node

      • detecting concurrent writes

        • not so much in database level. application developer should understand DB and handle them.
        Issues

      • last write wins

        • ambiguity of "recent"
        • only safe way of LWW is to use immutable, unique key like uuid

      • happens-before relationship

        • server and clients hold version number for every key.
        • when client reads, compare the version number with the previous read.
        • when server writes, write with new version number

      • version vector : collection of version number from multiple nodes