Redis personal summary concise version

Redis

Foundation and Application

5 Basic structure

• string

  • Dynamic string
  • The structure is similar to ArrayList
  • Maximum value - 512MB

• list

  • Double linked list
  • The structure is similar to LinkedList

• hash

  • Array + Linked list
  • The structure is similar to the old HashMap

• set

  • Array + Linked list
  • value All use null fill
  • The structure is similar to the old HashSet

• zset

  • Jump list

Distributed lock

• application

  • First step ：setnx
  • The second step ：expire

• set-expire Atomicity

  If setnx and expire Unexpected interruption occurs in the middle , cause expire Not implemented , Then the lock will never be released

  • set key value ex

    Instructions provided later
    It can ensure that the assignment process and the expiration setting are two operations, which are atomic

• Timeout problem

  • Blocking - Lock expired - Other threads get the lock

    hypothesis A Hold lock , The expiration time is 10s, however A Due to some kind of blockage , Self blocking exceeds 10s.
    At this time, the lock has expired ,B And got the lock , This will cause the lock not to be mutually exclusive .
    See solution ：Redlock

• Reentrant problem

  The above strategies do not support reentrant locks

  • Use hash Achieve reentrant locks

    have access to hash Structure implements a reentrant lock
    Realize the idea ：
    key ： Lock name
    field ： Threads id
    value： Lock count
    Every time you get a lock , Check whether the lock exists , Threads id Is it corresponding to
    When leaving the lock , Lock count -1

• RedLock

  Problems with common algorithms ：
  In the master-slave structure , If a thread A Just got the lock on the master node , There is no time to synchronize to the slave node , Then the master node hangs up , The lock will be lost .
  Next thread B You can still apply for this lock in the newly promoted master node

  • Premise ： More independent Redis Example

  • RedLock Algorithm

    Lock , Send to more than half of the nodes set key value nx ex Instructions
    As long as more than half of the nodes are considered successful , Then success
    Release the lock , Send... To all nodes del Instructions

  • cost

    • For multiple independent at the same time redis Reading and writing , Performance degradation
    • Introduced additional library
    • The cost of operation and maintenance has also risen

bitMap

• The bottom layer is still a string

• usage

  Be careful bitcount and bitpos Of [start,end] It's in bytes

  • setbit
  • getbit
  • bitcount
  • bitpos

HyperLogLog

GeoHash

• The bottom is zset

• GeoHash Algorithm

  Mapping two-dimensional coordinates to one-dimensional coordinates

• usage

  • geoadd
  • geodist
  • geopos
  • geohash
  • georadiusbymember

The bloon filter

• principle

  add to key When ： Enter a key, After many Hash Function gets multiple subscripts , Then set the subscript of the corresponding value to 1.
  Judge key While in existence ： Enter a key, After many Hash Function gets multiple subscripts .（1） If all subscripts are 1, So think there is （2） If one of the subscripts is not 1, Consider not to exist

  • advantage ： Complete the work in a small space
  • shortcoming ： There is a certain rate of miscalculation

• usage

  • bfadd
  • bfexists
  • bfmadd（ Batch ）
  • bfmexists（ Batch ）

• Miscalculation rate

  If the array is large , It's sparse , The misjudgment rate will be very low
  If the array is small , It's crowded , The misjudgment rate will rise
  In actual use , It should be noted that , Do not let the actual number of elements exceed the initialization capacity . Otherwise, it should be carried out more size Reconstruction of .

Current limiting

• Simple current limiting

  • Tail breaking and current limiting

    • effect

      A user can only perform a certain behavior within a specified time N Time

• Funnel restriction

  • The basic principle

    Some important parameters of funnel structure
    Funnel Capacity
    Leakage flow rate
    Funnel remaining space
    Last leak time

    Every time you apply to add water , First calculate the time from the last leakage to the current time , How much water has flowed , Update the remaining space in the funnel .
    If the remaining space is enough to add water this time , Allow to add water .
    If the remaining space is not enough, add water this time , Do not add water

  • RedisCell

    • cl.throttle Instructions

scan

• application

  Find the one that meets a certain rule key, with limit Options
  Cursor from 0 Start , Every time I look up , Will return the next cursor address
  When the cursor address is reset to zero , Represents the completion of a search

• Than keys More limit Options

• explain

  • limit It refers to the number of slots

  • traversal order

    The traversal order is not incremented according to the slot address

principle

Threads IO Model

• Non blocking IO
• Multiplexing
• Command queue
• The corresponding queue
• Timing task

Communication protocol

• RESP

  • Intuitive text protocols

Persistence

• snapshot

  • Binary serialized form

  • The files are compact

  • Realization principle

    • COW principle
    • fork Subprocesses
    • Data page COW Handle

• AOF

  • Instruction record text for modifying data

  • High readability

  • It will get bigger and bigger as it runs

    • Online loading AOF Time consuming

    • AOF rewrite （ Slimming ）

      • principle

        • Open up a sub process
        • Scan memory
        • Into operating instructions
        • Increment on splicing AOF

  • AOF Strategy

    • never
    • Per second
    • Each operation

• Mix persistence

  • snapshot
  • The incremental AOF

The Conduit

• Increase speed

• principle

  • Use a buffer , Temporarily store some instructions
  • Send together , Accept... Together
  • Reduce the number of network transfers

Business

• multi
• exec
• discard
• Compatible watch Use
• Using pipes to execute transactions can optimize

Subscription Publishing

With a few

Memory mechanism

• Memory recovery

  • Recycle in pages

    The operating system reclaims memory in pages , As long as there is one on this page key Also in the use of , It won't be recycled .
    So a lot of key, You can't immediately see the memory vacated .
    redis Will reuse the free memory that has not been reclaimed

• Memory allocation

  • jemalloc（facebook） Default , Better performance
  • tcmalloc（google）

colony

CAP

• Uniformity

  • Redis Does not satisfy consistency , But to meet the ultimate consistency

• Usability

  • Redis Meet availability

• Zone tolerance

Final consistency

• The slave node tries to catch up with the master node

Master slave synchronization

• Master slave synchronization

• From slave synchronization

  chain , Reduce the burden on the master node

• The incremental synchronization

  • Synchronous is the flow of instructions
  • Modified execution records are buffered locally
  • The buffer is sent asynchronously to the slave node
  • If the buffer ring array is overwritten , Snapshot synchronization is required

• Snapshot synchronization

  • First bgsave To local disk

  • Then send the snapshot file to the child node

  • The child node loads the snapshot file

  • Then perform incremental synchronization

  • If the snapshot section is too slow , Incremental buffer coverage will occur again , To form a dead cycle

    • solve ： Configure the right buffer size

• Copy without disk

  • Traverse the memory over and over , One pass serialization is sent to the slave node
  • Through socket

• wait Instructions

  • wait N time

    wait for N Slave nodes complete synchronization , Waiting for the most time second
    time by 0 To wait for
    If there's a network partition , It will cause permanent blockage , Loss of availability

  • Make asynchrony synchronous

sentry

• Monitor the health of the master node

• 3-5 Nodes , Guaranteed high availability

• Message loss issues

  • Because master-slave asynchronous replication （ buffer ）

• The basic principle

  • The client connection is from Sentinel Get the master node location
  • When the master node fails , The client will be informed of the new master node location
  • Monitor the failed original master node , After recovery, it becomes a slave node

• Basic usage

Cluster

• Slot position

  • 16384 individual （2 Of 14 Power ）
  • Slot information is stored in each node
  • The client connects to get slot information , Locate directly to the target node

• Slot location algorithm

  • CRC16 Algorithm , Then on 16384 modulus

• Jump

• transfer

• The network jitter

• Maybe offline - Confirm to go offline

  • Consultation mechanism
  • If the number of nodes that may lose contact with a node reaches the majority, the node is considered to be offline

Expand

Info Instructions

• Server
• Clients
• Memory
• Persistence
• Stats
• Replication

Expiration strategy

• Master node

  • Delete regularly

    • Greedy strategy

      Choose at random from expired dictionaries 20 individual key
      Delete the expired key
      If it's overdue key More than the 1/4, Re execution 1 step

    • There is a maximum time limit , Default 25ms

    • Avoid a lot of key At the same time , Add a little random time

  • Lazy deletion

• From the node

  • The master node sends del To the slave node
  • Or asynchrony will be inconsistent

Elimination strategy

• noeviction

  • Do not continue to write Services - Default

• volatile-lru

  • Set the expiration time of key,lru

• volatile-ttl

  • Set the expiration time of key,ttl The smallest elimination

• volatile-random

  • Set the expiration time of key Random

• allkeys-lru

  • All key-lru

• allkeys-random

  • All key- Random

Lazy delete

• introduce

  Delete a large key When , Will cause visible Caton

• principle

  To delete key The data structure of is disconnected from the original data structure
  Wrap the subsequent memory reclamation operation into a task and put it into the asynchronous queue
  Leave it to the background thread
  Not all key It's the same as above
  Small key Direct deletion
  Big key Disconnect before deleting

• flushdb and flushall Back plus async It will become an asynchronous task

• AOF Of Sync Very slow, too , There is also an independent task team and asynchronous thread processing

Source code

character string

• embstr（ short ）
• raw（ Long ）
• threshold ： The length exceeds 44 byte （64-1-16-3）

Dictionaries

• Contains two Hashtable

• Gradual relocation

• Capacity expansion condition

  The number of elements exceeds the length
  If you're doing bgsave, In order to reduce the COW, I won't expand the capacity
  If the number of elements reaches 5 times , No matter bgsave Forced expansion

• Reduction conditions

  The number of elements is less than the length of the array 10%

Compressed list

Quick list

Skip list

Compact list

XMind - Trial Version