Author: HelloGitHub- Lao Xun

Hello, here is HelloGitHub’s HelloZooKeeper series, free, open source, fun, entry-level ZooKeeper tutorials for beginners with basic programming skills.

This series of tutorials is to explain ZooKeeper from scratch, from the most basic installation and use to the principle and source code behind the explanation, the whole series hope to let ZK knowledge “drill” into your smart brain through interesting text, humorous atmosphere. This tutorial is open: open source and collaborative, so whether you’re a novice or veteran driver, we hope you can contribute to make this tutorial even better:

  • Novice: participate in the revision of the wrong words, sentences, spelling, typesetting and other problems in the article
  • Users: Participate in content discussions, answering questions, and helping others
  • Old driver: Get involved in writing the article and put your name in the author column

Project address: github.com/HelloGitHub…

Today let’s talk more about ZK’s memory model

First, memory model

ZKr: As usual, let’s see what happened in animal Village today.

Before the story we mentioned that all the data of the office is recorded in the red and yellow, after all, Ma Guoguo is the person in charge of the office, if lost, wushahat is afraid to keep, so Ma Guoguo now sleep to hold two books to sleep.

Before ma Guoguo small F recruit in, just to the small F asked Ma Guoguo: “Ma teacher, how to record this account ah, I am afraid I do not do well”, Ma Guoguo smiled slightly: “don’t be afraid, since you have been my home disciples, not pass inside, I will teach you”, “thank you Ma teacher! Quick teach me, how to do it “, so Ma Guoguo to small F on the lesson…

Let me take an earlier picture:

Chroot = chroot = chroot = chroot = chroot = chroot = chroot

But I’ve left the data out of the picture, but what you need to know is that there are two things to remember:

  • The parent of each path must exist, and the parent of the top-level path (for example, “/ chicken beauty”) is the root path
  • The path corresponds to the data one by one, which can be understood in the diagram as written on the right

But just recording the path and data you are too small ma Guo Guo, after all, it is ginger or old hot, Ma Guo guo is very forward-looking, let’s pick a record to zoom in to see the details

In addition to data, the nodes also record permissions, statistics, and child node lists. How’s that？ Ma Guo Guo is not very strong. ZKr ~

Let’s translate this memory model into ape language:

The ZK equivalent of the entire memory object is actually a DataTree

  • In fact, the entire ZK data ultimately exists in a hash table (ConcurrentHashMap), key is the path and value is the corresponding node
  • The node contains data, child node list, permissions, and statistics from the previous diagram
  • Paths and data are relatively simple
  • And then the other thing that we did at the beginning, we know that -1 means we don’t have to check permissions
  • List of child nodes, each node maintains a list of child nodes, recording only the child nodes. Grandson nodes and below are not recorded
  • The statistics are queried by the client, and the version in the statistics is used as the optimistic lock version number for deletion and update

ZK queries are fast because they use hash tables. The basic operation of add, delete, change and check is actually the hash table of the operation. I will not repeat the specific process of each operation here, because it is very simple, but it should be noted that:

  • The parent path must exist, otherwise an error is reported
  • An error is reported when a new path is created

Callback notification

In fact, the above content only says how the red book is saved, but Ma Guoguo also has another core ledger: the Yellow Book.

Shall we take a look at how Little Yellow Ben Ma Guo Guo plays?

2.1 Subscription (Office Perspective)

The atmosphere of the office is now in full swing, but also can not leave The subscription function set by Ma Guoguo at that time, so that the villagers need not come to the office again and again. Let’s take the villagers subscribing to the updates of the big star Chicken Taimei as an example.

First of all, assume that the number one fan Kun Kun ran to the office, put forward the need to subscribe to the chicken too beautiful updated video request, F first view the small red book must ensure that/chicken too beautiful/updated video exists, and then took out the Yellow Book, write down:

A subscription requires two records:

  • The specific transaction path corresponds to the villagers
  • Villagers correspond to specific business paths

If there are multiple villagers and multiple transactions it looks like this:

Then Kun Kun can safely go home and wait for the announcement.

Until Chicken taimei went to the office to upload the latest singing and dancing video, little F recorded in the little red book:

Then F will go to the Yellow Book to check if there is any subscription for/Ji Tai Mei/updated video, and find that three villagers: Kun Kun, Ma Xiaoyun and Dongdong have subscribed to this event, and will delete the records and corresponding transactions they subscribed to after remembering them:

And he would call them one by one and tell them,

  • You subscribe to/ Chicken too beautiful/updated videoSomething happened
  • This event is “data update”.

That’s the end of the office here.

2.2 Subscription (villager perspective)

Next, let’s cut the perspective to the villagers who subscribe. Let’s take Kun Kun as an example. After he went home from the office to subscribe, he was not idle and took out a small notebook to write it down:

After receiving a phone notice from the office, Kun Kun will again take out the small notebook, according to the current office notice of the event/chicken too beautiful/update video to find the small notebook need to do things: close the curtain, open the computer, put on headphones, prepare paper towels. After memorizing them, I deleted them from the little notebook:

And then strictly follow the contents of the records of the time to implement.

At this point, the whole subscription to notification process is over. Since records have been deleted on both sides, if Kun Kun wants to receive the notification of ji Tai Mei’s updated video again, he needs to go to the office to register again.

But you think this is the end of it?

Our Ma Guoguo is a lifelong learning martial arts master, since he learned the computer, IQ by leaps and bounds, is really a man of talent! Several problems were immediately identified in the process:

  1. Every time a villager comes to register the subscription transaction, F needs to record it one by one. If more than one villager registers at the same time, the villager at the back needs to queue up and wait for the villagers in front to register before F registers it
  2. When triggering the notification, F deleted the villagers to be notified from the minibook one by one after finding the subscription of the target event in the minibook. Moreover, the whole deletion operation was also in conflict with the previous registration operation, so they all needed to queue
  3. When recording the villagers’ registration data in the small Yellow Book, two records are needed for each subscription, which takes up a lot of space. Can we find a way to save some space

After careful thinking, Ma Guoguo found the optimization method, and ready to teach small F, let us and small F together with Ma Guoguo to learn what is the way ~

2.3 The improvement of the small Yellow Book

Front remind: the following explanation belongs to the advanced content, there are some hardcore! Please eat as appropriate

Suppose kun Kun, Ma Xiaoyun and Dongdong came to subscribe to the chicken Taimei event/Chicken Taimei in order. Xiao Huang originally recorded it like this:

Each villager will be assigned a unique increasing number starting from 0. The number and the villager will map each other, and then the relationship between the subscription path and the number will be recorded. So what’s the advantage of remembering this? Let’s start with the third point ma Guoguo mentioned before:

  • The subscribed path takes up a lot of space as the string itself and removes the originalVillagers correspond to the path mapping of specific transactions
  • The number itself is relatively small, and adoptedThe horse blendednewBitSetStorage mode (this will be explained later), each villager only takes 1 bit of storage, theoretically the same path subscription of less than 64 villagers, only need 8 bytes of storage

Both of these take care of the memory footprint problem, and with the storage problem out of the way, let’s talk about the two remaining problems:

  • 1. Now, if a villager comes to register and subscribe, let F check whether the villager’s corresponding number exists first. If not, increase the current number and add the mapping relationship between the number and the villager as shown in the figure. However, if the villager has been registered, you can directly add the number to the path and number mapping relationship by taking the number. The general process is as follows:

    Only the assigned new number will be locked. Other times, if multiple subscription requests are made at the same time, the read lock can be used concurrently.

  • 2. When the notification is triggered, it is only necessary to directly take out all the numbers corresponding to the path to be notified, and then take the numbers to check the corresponding notices of the villagers

    The village committee is very satisfied with the improvement, and Ma Guo Guo is very happy too! This improvement is only related to the office, and the villagers’ treatment is the same as before.

Chui finished the story, now translate in ape language.

Before 2.4 improvement

In the original version, the server uses two hash tables to record the mapping between the path and the client and the mapping between the client and the path respectively. The two hash tables are one-to-many relationship.

To subscribe to

When a client attempts to subscribe to a path, it simply tells the server in the request that the current path needs to be subscribed, which is essentially a Boolean value in the request. When the server gets the request and learns that the path needs to be subscribed, it stores the client and the path in the two hash tables mentioned above.

After the server returns successfully, the client will also make a local record, mapping the path and the specific callback to be executed, so the real callback is placed on the client, do not think that the server to call the client code.

The trigger

After processing some transaction methods, such as setData, create, delete, etc., the server will check to see if there are any callback notifications to be triggered. If so, it will fetch all the clients that need to be notified and initiate notifications to them one by one.

After receiving the notification, the client also retrieves the specific callback object from its own local record through the path and triggers the callback method of the object.

2.5 the improved

The improvements only concern the server side, so the client-side logic is not repeated.

And the main improvement does not involve logic, only involves the underlying data structure, so we focus on the new storage mode of data structure BitSet

The front really high energy, as appropriate under the rest, and then continue to read

The underlying BitSet is actually an array of type long, initialized to length 1 by default. Let’s zoom in on index 0 to see what it looks like.

The most important elements of this data type are the set and GET methods, and the ZK server ensures that the numbers added to the BitSet are incremented starting at 0, so we add them one by one starting at 0.

So 0 is just flipping the first digit from the right to 1

And then there is 1

And so on, 2 to 5

So, as you can see, bitsets are integers of 64 bits, each with a 0 or a 1, so an array of only one can record 64 digits, or, to be exact, 64 digits from 0 to 63. So you have to ask, what if I want to record 64? When recording 64, the array is expanded first (usually by a factor of 2)

Then turn the rightmost digit of the number in index 1 to 1

You can see why bitsets can store so much data, but the drawback is obvious: only numbers greater than or equal to 0 can be stored, so ZK needs to use two other hash tables to map the relationship between numbers and clients.

Now if you look back at the graph, it’s pretty clear:

Here I leave an assignment for you. Why does ZK maintain a number that increments from 0? What if it saves by skipping the number, such as 100, 200, etc.?

I haven’t told you how to use this improved version yet. Unfortunately, ZK still defaults to the improved method. If you want to change the server to the improved method, Need in a server-side environment variable Settings export zookeeper. WatchManagerName = org. Apache. The zookeeper. Server. Watch. WatchManagerOptimized

Do you think the chapter is over at this point?

2.6 A subscription benefits you for life

Magoguo is a person in charge of the pursuit of ultimate user experience! Because many villagers complained to him, upon receipt of the notice to come and subscription is too much trouble, they generally care about that, hope can you don’t have to repeatedly over subscription, horse blended, listen to the opinions of the masses of the people in the office on the subscription a new process, if the villagers want a subscription for life, please inform them in advance, We need to record more stuff in the little Yellow Book. If Kun Kun and Ma Xiaoyun come to subscribe/Chicken Too beautiful/update video, / Chicken too beautiful/dance:

What is different from before is that this extra record uses the villagers plus the path as the key, and then when triggering the notification, let F extra check this persistent subscription record, if the current villagers and path exist, the original record will not be deleted! This way, the subscription record will always exist, and the villagers will not have to come back to subscribe after each notification! After the villagers listen to applaud in succession! Ma Guoguo heart zizi, really do a practical matter ah!

But soon, the chicken is too big fan of beauty of the gentry and came to the horse blended, said he was such a beautiful feeling already fell in love with chicken, to subscribe to all transactions with chicken is beautiful, but the chicken too the United States is a big star now, a lot of affairs is very miscellaneous, if he is going to subscribe to the chicken too beautiful each transaction is impossible, and he also don’t know what a total of a transaction, So to ask Ma Guoguo if he can do another good thing, just subscribe to the top path of Jitaimei and receive notifications of all the other paths below him. Ma Guoguo is worthy of seeing the world, soon thought of a way, before the new persistent subscription record, do not distinguish between the line, now the record becomes this:

Then in the notification, check that the current path has a persistent recursive subscription, then check all the parent paths of the current path to see if there is a subscription, if there is a notification, so that Kun Kun can receive all/chicken tai mei below all events notification, Kun Kun satisfied to go back. Ma Guoguo shook his head: alas, young people chasing after stars to be rational! ZKr ~

Okay, back to the last of the new persistent subscriptions and persistent recursive subscriptions:

  • These two subscription schema names are rendered directly from enumerations in the source code:PERSISTENT 和 PERSISTENT_RECURSIVE
  • These two subscription modes are new features supported only in ZK 3.6.0 and later
  • The client must go through the new interfaceaddWatchTo add both types of subscriptions
  • Deleting persistent subscriptions also requires a separate call to the interfaceremoveWatchesFor those of you who are interested, spend some time on your own
  • A client can have only one type of subscription (one-time, persistent, and persistent recursion) in the same path. The category registered later overwrites the category registered earlier
  • Unfortunately, these two new subscription models are different from those mentioned in 2.5export zookeeper.watchManagerName=org.apache.zookeeper.server.watch.WatchManagerOptimizedConfigurations conflict and cannot be used together

Third, summary

This chapter introduces ZK memory model and Watcher notification callback mechanism and its principle, Watcher callback can be said to be ZK most commonly used function, we must often use in the usual business development, understand the principle is also very necessary.

The next chapter begins with the core and most characteristic knowledge point of ZK: cluster! Look forward to it!

As in the previous issue, if you have any questions about this article, either suggestions or questions about the principles of ZK, you can discuss them in the topics I created for easy recording and answering:

Address: www.yuque.com/kaixin1002/…

Give it a “like” before you go! ZKr ~