Case sharing of online real queuing system reconfiguration -- practical part

Write it at the front

The last article talked about << The way of system reconstruction —— How to design a reconfigurable solution that can be implemented >>, This article focuses on the recent online refactoring project —— The passenger Queuing service is reconstructed into a scenario , Introduce a complete reconfiguration technical scheme and its implementation —— Actual combat

Detailed technical proposal introduction

One 、 background

1、 present situation :

• At present, the performance bottleneck of online passenger queuing is obvious , Mainly adopts Redis List Storage structure . As the number of orders in the queue increases , Inquire about 、 Insert 、 Determine whether the order is operating in the queue RT Exponential growth .
• The current passenger queuing structure , Unable to meet business expansion requirements , To support the business after rapid iteration , Passenger queue reconstruction is imminent .

2、 Research items

• Use Mysql Feasibility analysis of storing queuing information ( Offline environmental pressure measurement )
• Sort out the external interface and scope of influence ( Currently, it is provided externally 20 Analysis of left and right interfaces ), Form the following :

The name of the interface	Interface path	The caller	QPS	RT(995)	Average RT	remarks
The team	/queue/enter	XXX	XXX	XXX	XXX

Two 、 The goal is

1、 The external interface remains unchanged , Transform from the underlying storage , Compatible with current online display scenarios , The passenger ranking display is decoupled from the queue .

The ranking shows that the normal queue is reserved 、 Channel queue 、 Priority queue ( Include absolute priority ), Sort by queue time

The out of queue sorting factor is calculated according to the fixed rules when entering the queue , Use more flexible strategy algorithm to calculate the team priority , When leaving the queue, you only need to sort according to the sorting factor , So as to indirectly determine the order of the team ,

2、 Data storage ranking adopts Redis Ordered set , Queue information is added mysql Storage , branch 128 A watch .

3、 Solve the current performance bottleneck , Support rapid iteration of subsequent businesses , And subsequent requirements expansion .

3、 ... and 、 The overall plan

1、 Comparison of new and old schemes

Storage architecture before refactoring : redis: list data structure , key： hive + models + Queue type

Storage architecture after refactoring : Rank the queue : redis Ordered set , key: Honeycomb center + models + Queue type ( In order to be compatible with the old ) ,

Queue information table (queue_info_xxx, mysql Storage , Press the center point of the honeycomb hash table , The order number + models Create a union unique index )

Comparison of some interfaces

Interface	View rankings	Is it in the queue	The team	Out of the team	Jump the queue
Before the refactoring	1. Loop all elements in all queues , Cycle to determine the calculation position ,2. Query the algorithm group to calculate the estimated time	Traverse and query all the elements of the queue , Cycle to determine if contain	First, determine whether there is in the queue , It will also be judged here that different queue types are hit , write in redis queue (list) in	According to the model cycle & Multi queue type loop out , And record log	Rights card cut in line
After refactoring	From... By order number ” Queue information table “ Query queue information in , There are queue records , Determine whether there is a ranking , If there is no ranking display M+( The ranking queue has online control ), Otherwise, query ” Rank the queue “ Direct return sequence . Query the algorithm group to calculate the estimated time	Direct inquiry " Queue information table " Determine whether there are records	Write... First " Queue information table ", If the row number threshold is not exceeded , Then write the corresponding " Rank the queue "	to update " Queue information table " state , If there is a ranking , Is removed from the ranking queue , And notify the candidate asynchronously , And record log	Directly update the queue information table ”order_by“ Field You can change the order of leaving the team

Bottleneck analysis before refactoring : Each request will take out all the elements in the queue and loop through ( When the number of queued orders increases ,RT Exponential growth , Fetch a imprison son , You can think about why ？)

Advantages of the reconstructed storage architecture : The original O(n) Time complexity , Turn into O(1) Complexity .

2、 Restructured architecture diagram

1. About queue size statistics :

Rank unrestricted queue : Directly through ZCARD obtain (O(1) Time complexity )

Rank the current limiting queue : Get the total length through the counter (O(1)), Downgrade passed ZCARD obtain

2） About the matching of new transport capacity —— Query list 【 Orange part 】 There may be a bottleneck problem —— The later optimization directions are 2 Kind of Can rank top N Pull out the buffer set Queue truncation —— Larger than N Convert to other table storage

3. Other flow charts : The team 、 Outgoing flow chart （ Omit here ）

4. Table structure design

   queue_info_[001 ~ 128] Queue information table , Press the center line of the honeycomb hash % 128 Rule table , Data is archived on a daily basis queue_manager Ranking queue management table It mainly controls whether the current is limited , And hive queue information queue_log_[001~128]: Order entry & Outgoing record sheet , Press the center line of the honeycomb hash % 128 Rule table , Consider archiving later .

Detailed table structure —— Omit

Four 、 Sort field (order_by) Design

For queuing scenarios , The less time , The more ahead . Time difference can be used to calculate in reverse order , The formula is as follows : ~(-1L << 39L) & (~( Millisecond time difference ))

Other rules are omitted here .

5、 ... and 、 Historical queue scenario compatibility problem

Ranking display : Normal queue 、 Channel queue 、 Priority queue

The order goes out of the queue : Different configurations by weight coefficient , Finally, the different sorting is calculated

6、 ... and 、 Grayscale scheme

By city grayscale , First select the cities with small flow .

7、 ... and 、 Rollback scheme

Turn off the city grayscale switch , Data already in the queue will affect , The migration tool is required to refresh the data

8、 ... and 、 Data archiving scheme & Bottom line plan

Data archiving : Passenger queuing information shall be filed on a daily basis

Out strategy : Long-term ( Configurable ) Queue status has not changed ( Possible exception ), Forced exit

Nine 、 Data monitoring & Call the police

Passengers line up Grafana monitor : Monitoring indicators : City 、 hive 、 models 、 Number of normal queues 、 Number of channel queues 、 Number of priority queues Call the police : The number of queues exceeds the threshold nail alarm

Ten 、 Time planning

Interface for scheme investigation (20 Interface ) Add transformation scheme 、 Those responsible , Progress item

The name of the interface	Interface path	The caller	QPS	RT(995)	Average RT	remarks	Retrofit scheme	Those responsible	speed of progress
The team	/queue/enter	XXX	XXX	XXX	XXX

Be careful : Interface self test and CR It is completed in the development phase , The monitoring alarm does not affect the development of the test , Can be developed during the test phase .

11、 ... and 、 Association Group

A little

Twelve 、 resource requirement

A little

summary

Refactoring requires consideration of many details , Every possible bottleneck needs to be considered , And subsequent optimization , Expansion problem .

All changes , Responsibility must be personal ( Avoid omission ), In addition, all self tests must pass before the test ( Develop and write unit tests ).

At present, the code development of this scheme has been basically completed , The next article continues with the scenario of queue system reconfiguration , We will talk about how to design the gray-scale pressure measurement scheme , Coming soon .

Welcome to your attention " On the structure " official account , Share original technical articles from time to time , We will have the opportunity to share the technical details of system reconfiguration live .

file