Sorted out some Java architecture, interview materials (micro services, clusters, distributed, middleware, etc.), partners in need can pay attention to the public number [programmer internal point], no routine to get

Highlights:

  • Reeling off nine distributed ID generation methods, the interviewer gets a little confused
  • Backend programmers have to follow Nginx forward matching rules
  • Face recognition function based on Java
  • Rattle off six @Transactional annotation failure scenarios
  • Dry goods recommended! 13 free technical ebook sites for Programmers

The introduction

Also served as an interviewer, interviewed a lot of applicants, because IT is my own recruitment of their own, so I will not see the applicant to build rocket technology more than cattle, only see the screws of the craft porcelain porcelain solid. After all, it’s gonna be a whole, and it’s gonna be hard for the team to drag everyone down. Interview questions are usually not too difficult, like with Redis. I just want to make sure he has really used it. Redis 5 kinds of basic data structure and easy to operate, to know the most basic request, this time if he would say every roughly application scenario for the data structure, so it must be a points, than those who only speak several data structures, such as the blank stare I asked a lot of strong next question, don’t be silence.

Want to exchange technology or interview experience can add me VX: xinzhiFU521, must know all words, good chat so much into the topic!

What are the basic data structures of Redis?

String (String)

In any programming language, the String String is the most basic data structure. Have you ever wondered what Redis does to store a String?

A String can be modified in Redis. It’s called a Simple Dynamic String (SDS). It’s a String, but its internal structure is more like an ArrayList, which maintains an array of bytes. A certain amount of space is pre-allocated within it to reduce the frequent allocation of memory.

Redis allocates memory like this:

  • When the string length is less than 1MB, each expansion doubles the existing space.

  • If the length of the character string exceeds 1MB, the space is expanded by 1MB each time.

The maximum length of a string is 512MB. This ensures sufficient memory space without wasting memory.

The above pictures originated from the network, if there is infringement contact delete

The figure above shows the basic structure of a string, where content holds the string content and 0x\0 as the closing character is not counted in Len.

Examine the data structure of the string

struct SDS{
  T capacity;       // Array capacity
  T len;            // The actual length
  byte flages;  // Flag bit. The lower three bits indicate the type
  byte[] content;   // The contents of the array
}

Copy the code

Capacity and len are both generic, so why not just int? In order to make more reasonable use of memory, Redis uses different data types for strings of different lengths, and len will be the same size as capacity when creating strings, so there is no redundant space. So a String value can be a String, a number (integer, floating point), or binary.

1. Application Scenarios:

Store key-value pairs, which I won’t go into too much detail about

2, String (String)

set   [key]  [value] to the specifiedkeySet values (setOverwrite old values)get  [key] get specifiedkeyThe value of the del [key] Delete specifiedkey

exists  [key] Checks whether a specified existskeymset [key1] [value1] [key2] [value2] ...... Mget [key1] [key2]...... Batch takekey

expire [key]  [time] to the specifiedkeySet expiration time in seconds setex [key]  [time]  [value] is equivalent toset + expireCommand combination setnx [key]  [value] ifkeyThere is no,setCreate, otherwise return0

incr   [key] ifvalueAn integer can be incremented by the incr command each time1

incrby  [key] [number] Increments the integer value using the incrby commandnumber
Copy the code

A. list B. list C. list

The list in Redis is similar to the LinkedList in Java in that the underlying structure is a LinkedList structure. The insertion and deletion operations of list are very fast and the time complexity is 0(1). Unlike the insertion and deletion operations of array structure, data need to be moved.

But the bottom of the list in Redis is not a two-way list.

When the amount of data is small, its underlying storage structure is a piece of continuous memory, called ziplist(compressed list), it will be next to all the elements stored together, allocation is a piece of continuous memory; When there is a large amount of data, the structure will be quickList.

However, a simple linked list has its drawbacks. The front and back Pointers of the linked list, prev and Next, take up more memory, waste more space, and increase memory fragmentation. After Redis 3.2, we changed to ziplist+ linked list hybrid structure, called QuickList.

Here are two types of linked lists

Ziplist (Compressed list)

Take a look at ziplist’s data structure,

struct ziplist<T>{
    int32 zlbytes;            // The number of bytes used to compress the list
    int32 zltail_offset;    // The offset from the starting position of the last element, used to quickly locate the last node
    int16 zllength;            // Number of elements
    T[] entries;            // Element content
    int8 zlend;                // End bit 0xFF
}
Copy the code

Int32 zlbytes: number of bytes used in the compressed list int32 zltail_offset: offset from the start position of the last element, used to quickly locate the last node int16 zlLength: number of elements T[] entries: Element content int8 zlend: End bit 0xFF

The ztail_offset field is used to quickly locate the last element and traverse backwards in order to support bidirectional traversal

The above pictures originated from the network, if there is infringement contact delete

Entry data structure:

struct entry{
    int<var> prevlen;            // The length of the previous entry
    int<var> encoding;            // Element type encoding
    optional byte[] content;    // Element content
}
Copy the code

Entry Its Prevlen field indicates the length of the previous entry in bytes. When the compressed list is traversed backwards, this field is used to quickly locate the next element.

1. Application Scenarios:

Since list is a list sorted by insertion order, there are more application scenarios, such as:

  • Message queues: LPOP and RPUSH (or vice versa, LPUSH and RPOP) fulfill the function of queues

  • The likes list, comments list, leaderboards of moments: lpush and lrange commands can implement the function of the latest list. Each time, lpush commands can insert new elements into the list, and then lrange commands can read the latest list of elements.

2. Common names for list operations:

rpush [key] [value1] [value2] ...... Insert rPOP [key] to the right of the list to remove the right of the list header element, and return the element lPOP [key] to remove the left of the list header element, Llen [key] Returns the number of elements in the list. Lrem [key] [count] [value] Deletes the elements equal to value in the list. Count is the number of deleted elements. If count<0, delete the same elements from the right. If count=0, delete all the same elements. Index indicates the index of the element. Index can be negative. Index = indicates the penultimate element, and index=-2 indicates the penultimate element. Lindex [key] [index] retrieves the element with the specified index in list. Time complexity: O(n)) lrange [key] [start_index] [end_index] Obtain all elements in the list (time complexity: O(n)) Ltrim [key] [start_index] [end_index] Retain elements within the interval and delete other elements (time complexity is O (n))Copy the code

3. Hash (dictionary)

Hash in Redis is more similar to Java HashMap in that it is an array + linked list structure. When a Hash collision occurs, an element will be appended to the linked list. It is worth noting that the value in Redis Hash can only be a string.

hset books java "Effective java" (integer) 1 hset books golang "concurrency in go" (integer) 1 hget books java "Effective Java "hset user age 17 (integer) 1 hincrby user age 1 # A single key can be countedCopy the code

Both Hash and String can be used to store user information, but the difference is that Hash can store each field of user information separately. String stores all the user information as a serialized String. If you want to modify a user field, you must query all the user information strings, parse them into the corresponding user information object, and store them as a serialized String after modification. Hash can save network traffic by modifying only one field, but the memory footprint of a hash is larger than that of a String, which is a disadvantage of hash.

1. Application Scenarios:

 

  • Shopping cart:hset [key] [field] [value]Command, can be implemented toThe user Id.Product Idforfield, the quantity of goods isvalue, make up exactly three elements of a shopping cart.
  • Store objects:hashThe type of(key, field, value)Structure and object(Object ID, attribute, value)Is similar in structure and can also be used to store objects.

2. Common hash operation commands:

Hset [key] [field] [value] New field information hget [key] [field] Obtain field information hdel [key] [field] Delete field hlen [key] Number of fields saved hgetall [key] Hmset [key] [field1] [value1] [field2] [value2]...... obtain all the fields and values in the specified key dictionary Batch creation Hincr [key] [field] Pair Value increment Hincrby [key] [field] [number] Number increment of field valueCopy the code

A set of

A set in Redis is similar to a HashSet in Java in that its internal key-value pairs are unordered and unique. Its internal implementation is equivalent to a special dictionary in which all values are a single value, NULL. When the last element in the collection is removed, the data structure is automatically deleted and the memory is reclaimed.

1. Application Scenarios:

  • Friends, followers, fans, and interested people:
    1. sinterCommand to obtain the common friends of users A and B.
    2. sismemberThe command is used to check whether A is A friend of B.
    3. scardCommand to obtain the number of friends.
    4. Pay attention to,smoveThe command moves B from A’s fan set to A’s friends set
  • Home page display random: There are many recommended merchants on the home page of Meituan, but not all of them can be displayed. The set type is suitable for storing all the contents that need to be displayed, andsrandmemberCommand to get a random number of them.
  • Store the user ID that wins a prize in an activity, because have to repeat function, can guarantee the same user won’t win a prize twice.

2, set common command:

Sadd [key] [value] Specifies the keysetAdd element smembers [key] get specifiedkeyAll elements in the set sismember [key] [value] Determines whether a certain type exists in the setvalue

scard [key] get the length of the set spop [key] Pop up an element srem [key] [value] Deletes the specified elementCopy the code

V. Zset (Ordered Set)

Zset is also called SortedSet. On the one hand, it is a set, which ensures the uniqueness of the internal value. On the other hand, it can assign a score to each value, representing the sorting weight of the value. Its internal implementation uses a data structure called a skip list.

1. Application Scenarios:

Zset can be used as a leaderboard, but different from list, zset can realize dynamic sorting. For example, it can be used to store the list of fans. Value is the user ID of fans, score is the attention time, we can sort the list of fans by attention time.

Zset can also be used to store a student’s scores, with value being the student’s ID and score being his test scores. We can get his ranking by ranking his scores.

2, zset ordered set common operation commands:

Zadd [key] [score] [value] add element to set with specified key zrange [key] [start_index] [end_index] Zrevrange [key] [start_index] [end_index] Zrank [key] [value] Get the rank of the elements in the set zrangebyScore [key] [score1] [score2] Zrem [key] [value] Delete element zscore [key] [value] Obtain element scoreCopy the code

conclusion

In this paper, many concepts have been skimped over, just to give you a rough description of Redis five basic data structures and application scenarios, aiming to give partners a direction for preparing questions for the interview, the subsequent output of Redis articles will continue, welcome to pay attention to, let’s learn to get offers together.

So much for today, if this article is a little help to you, I hope you can get a thumbs up 👍 oh

Your approval is my motivation to write!

Small benefits:

Hundreds of technical e-books, SHH ~, free for your friends. Please reply to the official account [666] for self-collection

Sorted out some Java architecture, interview materials, partners in need can pay attention to the public number [programmer internal points]