Google Cloud True Time

Giriş

Dağıtık bir ağda zaman senkronizasyonunu sağlamak zor bir iş. Google bunu True Time ile sağlıyor. Google True Time, Google Spanner gibi veri tabanlarında kullanılıyor. Açıklaması şöyle

Google created a distributed SQL database called Spanner, it relies on something called True Time for very strong consistency of transactions across nodes. Google knows that time is uncertain, so True Time defines a bounded and small uncertainty of time window where transactions can not be ordered definitely. True Time works as a Global Time across Google datacenters.

True Time is expressed as a time interval [earliest, latest]. It exposes an API called now() whose value lies in this interval. The uncertainty interval varies between 1 ms to 7 ms — note that the maximum uncertainty has a tight upper bound.

The APIs TT.before(t) or TT.earliest() and TT.after(t) or TT.latest() take a timestamp as input and answers whether the given timestamp is before or after the current uncertainty interval.

The relation between TT.earliest(), TT.latest() and absolute time of an event is:

TT.earliest ≤ Absolute Time of current event ≤ TT.latest

Google bunu nasıl sağlıyor?

Açıklaması şöyle

Google does this magic by couple of tricks:

Optimized Infrastructure: Google infra runs on specially designed private network. They have optimized the network over time, it has a lot of redundancy of connections across datacenters and failure handling mechanisms built in. It does not mean network partition don’t happen or things don’t go wrong — however the possibility of such incidents and communication latency reduces a lot.

Using own clocks: True Time does not rely on external NTP pools or servers. Rather, Google datacenters are equipped with GPS receivers and Atomic clocks. See the below picture of such an installation:

AWS Time Sync Service

Açıklaması şöyle

Inspired from Google True Time, AWS also manages its own fleet of Atomic clocks and GPS clock receivers. Any EC2 server can connect to these time references via NTP using Chrony daemon for more accurate time rather than connecting to external NTP pools or time servers over NTP. More details can be found here. Leap second smearing is also handled by Amazon Time Sync Service.

Amazon Web Service (AWS) DynamoDB - Hem Key-value Hem de Document-Oriented Çalışabilir

Giriş

Bir NoSQL veri tabanıdır, ancak multi-model'i destekler yani key-value system ve document store olarak kullanılabilir.

1. Key-value store olarak Cassandra, HBase, Redis ile rakip

2. Document DB olarak MongoDB ile rakip.

Burada bir tane yazı var. Sorry, Amazon DynamoDB is not column-based, and it is not OLAP

DynamoDB ilk olarak 2012 yılında piyasaya çıktı

Özellikleri şöyle

Açıklaması şöyle

DynamoDB is Amazon's answer to MongoDB, a NoSQL database that works on JSON documents. These databases rely heavily on nested data and do not enforce any strict schema unless the developer turns that option on. That means that DynamoDB is great for high-volume sites like a CMS or mobile apps with a lot of traffic. For example, both Major League Baseball and Duolingo make use of DynamoDB.

Pricing Model

1. throughput model : Kullanım miktarı tahmin edilir ve bu aşılamaz.

2. on-demand pricing model : Kullanım miktarına göre fiyatlandırılır

Yanlış Kullanım

1. Normalizing Data

DynamoDB bir SQL veri tabanı değildir. Bu yüzden denormalized şekilde kullanılmalıdır

2. Single Table Design

Single Table Design (STD) için açıklaması şöyle

In DynamoDB, you are charged for the capacity throughput and indexes of each table.

The more tables you have the more you will end up paying (especially if each table has several secondary indexes).

The STD instead encourages grouping all of your (related) data entities in one table.

Replication

Açıklaması şöyle

Departing from the traditional SQL-based offerings, DynamoDB offers a persistence model where the information is spread into partitions with a dual consistency approach.

A write operation first saves the updated data to a persistence node. It is then synchronously copied to another persistence node. Only at this point, the operation is confirmed to the caller.

There is an asynchronous process that copies it from the second persistence node to a third one.

This means you have the redundancy of the data being persisted into 3 nodes, each located in a separate AZ. At the same time, you do not need to wait for all 3 nodes to save before returning the operation, which helps to maintain the latency at a lower level.

When retrieving data you have two choices: eventually consistent and strongly consistent.

If you opt for eventually consistent, your operation will be directed to any of the 3 nodes. If it happens to be the asynchronously copied one, there is a chance the information you will retrieve will be outdated when compared to the main node.

In contrast, the strongly consistent mode will only be directed to the main node.

MongoDB vs DynamoDB 

- MongoDB en büyük belge büyüklüğü olarak 16 MB'yi destekler. Bu DynamoDB'de 400 KB

- MongoDB C++ ile geliştirilmiştir. DynamoDB Java ile geliştirilmiştir

Primary Key 

Açıklaması şöyle

... it only allows three data types for primary keys: string, number, and binary. (It does support many different data types for other attributes within a table.)

Açıklaması şöyle

DynamoDB has a weird take on the concept of a primary key. You will have two keys to identify specific data:

Primary Key = Partition Key + Sort Key

Şeklen şöyle

Örnek

Tablo şöyle olabilir

      PRIMARY_KEY     SORT_KEY         OTHER_INFO

1.    ORDER#1234       PRODUCT#1      ProductName,Price etc

2.    ORDER#1234       INVOICE#1         InvoiceDate, PaymentInfo

3.    ORDER#1234       CUSTOMER#1   CustomerName, ShippingAddress

Value Type

Açıklaması şöyle

Dynamo DB stores the value in a JSON serialized format

Sütun Tipleri

Açıklaması şöyle

DynamoDB supports many different data types for attributes within a table. They can be categorized as follows:

1. Scalar Types – A scalar type can represent exactly one value. The scalar types are number, string, binary, Boolean, and null.

2. Document Types – A document type can represent a complex structure with nested attributes, such as you would find in a JSON document. The document types are list and map.

3. Set Types – A set type can represent multiple scalar values. The set types are string set, number set, and binary set.

Global Secondary Index

Eğer istediğimiz veri Primary Key dışındaysa bu index kullanılır. Tek problem her indeksin tek başına bir tablo olması

DynamoDB Disadvantages

Açıklaması şöyle

Size limit — item can only reach 400KB in size

Limited querying options (limited number of indices)

Throttling on burst throughput (and hot keys in certain situations)

create-table

Örnek

Şöyle yaparız

aws dynamodb --endpoint-url=http://localhost:4566 create-table \
    --table-name Music \
    --attribute-definitions \
        AttributeName=Artist,AttributeType=S \
        AttributeName=SongTitle,AttributeType=S \
    --key-schema \
        AttributeName=Artist,KeyType=HASH \
        AttributeName=SongTitle,KeyType=RANGE \
--provisioned-throughput \
        ReadCapacityUnits=10,WriteCapacityUnits=5

describe-table

Şöyle yaparız

aws --endpoint-url=http://localhost:4566 dynamodb describe-table 
  --table-name Music | grep TableStatus

put-item

Şöyle yaparız

aws --endpoint-url=http://localhost:4566 dynamodb put-item \
  --table-name Music  \
  --item \
  '{"Artist": {"S": "No One You Know"}, "SongTitle": {"S": "Call Me Today"},
    "AlbumTitle": {"S": "Somewhat Famous"}, "Awards": {"N": "1"}}'

scan

Şöyle yaparız

aws dynamodb scan --endpoint-url=http://localhost:4566 --table-name Music

Örnek

Açıklaması şöyle

Because DynamoDB is not relational and does not enforce ACID by default, it must use a modified version of standard SQL. Amazon has developed a query language called PartiQL which uses many SQL concepts but is built for highly nested data. The query below takes advantage of the key-value underpinnings of DynamoDB in a relatively SQL standard way.

Şöyle yaparız

UPDATE
    Music
SET
    AwardsWon = 1
SET
    AwardDetail = { 'Grammys': [ 2020, 2018 ] }
WHERE
    Artist = 'Acme Band'
    AND SongTitle = 'PartiQL Rocks'

Cache Stratejileri - Cache Access Patterns Refresh-ahead - Implemented by Cache Provider

Giriş

Şeklen şöyle

Açıklaması şöyle

.. it refreshes the cache data before its expiration time,it is done for hot-data, the data we expect to be requested in the near future.

Approach

1. Supposed the cached data’s expiration time is 60 seconds and the refresh-ahead factor is 0.5.

2. If the cached object is accessed after 60 seconds, Coherence will perform a synchronous read from the cache store to refresh its value.

3. If the cached data is accessed after 30 seconds, said 35th second, the cache returns the data and asynchronously refreshes the data.

AWS ElastiCache - Redis

Giriş

Açıklaması şöyle. Yani Memcached veya Redis olabilir. Memcached artık kaybolmaya başladığı için bunu Redis kabul etmek lazım

There are two types of in-memory caching engines:

1. Memcached — designed for simplicity, so used with you need the simplest model possible.

2. Redis — works for a wide range of use cases and have multi AZ. You can also complete backups/restores of redis.

Redis

Redis'in pahalı olduğu söyleniyor. ElastiCache kullanmadan önce Amazon Elastic Compute Cloud (EC2) üzerinde denenebilir. Açıklaması şöyle

Run a Docker redis in ec2 for a while first. Make sure it serves your purposes. Figure out how the sizing works for you. Remember redis is meant to hold ephemeral data in memory, so please don’t treat it as a DB. It’s best to design your system assuming that redis may or may not lose whatever is inside. Clustering or HA via Sentinel, can all come later when you know you need it!

Redis Kullanımı

İki şekilde kullanılabilir. Cluster mode enabled veya disabled olarak. Kısaca 

1 Redis-CME

2.Redis-CMD

Açıklaması şöyle

Elasticache provides two flavors of Redis, Cluster Mode Enabled (Redis-CME) and Cluster Mode Disabled(Redis-CMD). 

Redis-CMD

Açıklaması şöyle. Tek bir cluster ve tek bir shard var. Cluster'da primary ve replica düğümler var.

Broadly speaking, for Redis-CMD, there is only one shard. The shard comprises the primary node along with the read replicas. Read replicas maintain a copy of the data from the cluster’s primary node.

Redis-CME

Açıklaması şöyle. Tek bir cluster var ancal bu sefer 250 taneye kadar shard olabiliyor. Her bir shard için primary ve replica düğümler var.

For Redis-CME, Elasticache allows up to 250 shards for a Redis cluster. Each shard has a primary node and read replicas. Elasticache distributes the keyspace evenly across all the shards. When reading or writing data to the cluster, the client itself determines which shard to use based on the keyspace. This design pushes the work to the client and avoids any potential single points of failure.

Redis-CME Problemi

Açıklaması şöyle. Yani bir object graph gibi bir şeye ihtiyaç varsa, CME iyi olmayabilir

When we started using Redis, we soon realized use-cases where we wanted to fetch multiple Redis keys at once (think Friends of Friends) and to avoid multiple network round trips, we thought of using mget call in Redis which allows us to do so.

...

The caveat here was the sharded nature of our setup. This meant that essentially the keys that we were trying to fetch in one-go, could be distributed across multiple shards, i.e. across multiple nodes, defeating our fetch all-at-once requirement.

Bu problem için Redis Hashtags kullanılabilir. Açıklaması şöyle. Ancak bunu yapınca veri tüm shardlara eşit şekilde dağılmayabilir

To solve this, we started using Redis Hashtags which helped us localize all related data on a single Redis node. Redis Cluster provides the concept of hashtags, according to which, if there is a substring between {} brackets in a key, only what is inside the string is hashed. An example of this in our application would be {RELATED_STOCKS}_AAPL. By surrounding the RELATED_STOCKS section of each key in curly braces, we are effectively storing them in the same slot. This means that we can store an entire group by calling MSET once and fetch related stocks for multiple stocks at once using MGET. This usage pattern became more and more prevalent across our application. For example, all related stocks for all the stocks were now mapped to the same hash key in Redis because of {RELATED_STOCKS} hashtag, and hence same hash slot and shard on Redis, making keys distributed less evenly across nodes, which can cause certain nodes to use more memory than others.

Distributed Snapshot

Problem Tanımı

Açıklaması şöyle

Point in Time Snapshots is critical for capturing the “consistent” state of systems, which can be restored in case of any loss of system state, making your system fault tolerant.

Taking a snapshot of one particular server is easy. You define a cut-off time and at that time, the state of the server(local state) at that exact time can be captured for the snapshot.

However, Snapshot in distributed systems, i.e on all the nodes in a cluster, is a challenging problem because nodes in a cluster don’t have a common/global clock. Hence, it’s cannot be guaranteed that all the nodes in the cluster will capture their local state at the same “instant”.

In addition to the “local” state, there could be additional states associated with the distributed system, which are in transit i.e messages send from node 1 to node 2, but hasn’t arrived at node 2 yet.

The other constraint during snapshots is that it should not be a “stop the world” process and it should not alter the actual computations!!


In short, we need the distributed snapshot to create a “Consistent” snapshot of the global state of the distributed system, without impacting actual computations on that system.

Algoritma

Açıklaması şöyle

The algorithm used for capturing distributed snapshots is the Chandy-Lamport algorithm(Yes! Leslie Lamport is also behind Lamport Clocks).

Rate Limiting Algorithms Leaky/Leaking Bucket aka Spike Control Policy - Sabit Hızdadır

Giriş

Açıklaması şöyle. Bu yöntem de üst sınır aşılırsa istek es geçilmez ve sonra işlenmek üzere kuyruğa atılır. Bu yöntemi gerçekleştiren bir sınıf burada. Kuyruk ta artık dolarsa, yeni istekler dikkate alınmıyor

The Spike Control Policy is provided for smoothing API traffic. The policy ensures that within any given period of time, no more than the maximum configured requests are processed.
If there is no request quota in the current window, the policy allows requests to be queued for later reprocessing without closing the connection to the client.

Açıklaması şöyle

The leaky bucket limits the constant outflow rate, which is set to a fixed value. For example, if the outflow rate is set to one request per second, it cannot process two requests per second. This ensures the outflow rate is always stable, regardless of the inflow rate.

Şeklen şöyle

Bir başka şekil şöyle

Gerçekleştirim şöyle

In terms of algorithm implementation, a queue can be prepared to save requests, and a thread pool (ScheduledExecutorService) can be used to periodically obtain requests from the queue and execute them, and multiple concurrent executions can be obtained at one time.

This algorithm also has drawbacks after use: it cannot cope with short-term burst traffic.

Bu algoritmanın bir dezavantajı şöyle

This algorithm also has drawbacks after use: it cannot cope with short-term burst traffic.

Rate Limiting Algorithms - Token Bucket - Burst Destekler

Giriş

Açıklaması şöyle

The token-bucket algorithm is explained with the analogy of a bucket with finite capacity, into which tokens are added at a fixed rate. But it can’t fill up infinitely. If a token arrives when the bucket is complete, it’s discarded. On every request, some tokens are removed from the bucket. The request is rejected if there are fewer tokens in the bucket.

Belli bir süre örneğin 1 dakika içinde 100 tane istek işlenir. 100 istek arasındaki süre önemli değildir. 1 dakika geçince tekrar 100 tane token kovaya eklenir. Şeklen şöyle

Dolayısıyla token'lar bir anda tüketilebilir. Açıklaması şöyle

The token bucket allows for sudden increase in traffic to some extent, while the leaky bucket is mainly used to ensure the smooth outflow rate.

Bu algoritmanın bir problemi şöyle. Yani bir sonraki pencerenin tam bitiminde ve bir sonraki pencerenin tam başında kova tam dolarken iki tane 100'lük istek gelirse üst sınır aşma ihtimali var. Bir anda 200 istek işlerken bulabiliriz kendimizi. Böylece sistem aslında saniyede en fazla 100 istek işleyebilirlen aslında saniyede 200 istek işlemek zorunda kalıyor

I’ll show the problem with a perfect example to short explain the idea:

1. At some moments, our bucket contains 100 tokens.

2. At the same time, we consume 100 tokens.

3. After one second, the refiller again fills 100 tokens.

4. At the same time, we consume 100 tokens.

Açıklaması şöyle

Implementation idea: You can prepare a queue to save tokens, and periodically generate tokens through a thread pool and put them in the queue. Every time a request comes, get a token from the queue and continue to execute.