Additional info: I tried to remove the follow_owner component in the allay.json behavior file and the lag is gone. I think this follow_owner behavior needs to be improved in terms of performance especially when the can_teleport property is false. If I remember correctly, allay is the only mob that follows the owner without teleporting currently. If this doesn't get fixed, it might affect future incoming mobs as well imo.
This still affects 1.20.40. I'm quite sure this has something to do with allays following their owner behavior. Try this with 20 allays. Give them all items to hold and tie them to a fence. It doesn't matter if you give them all the same item. While you are nearby, try dropping an item and it should be just fine as allays don't start searching their owner when the owner is nearby. Now move approximately 20 blocks away from the allays and drop an item again. You'll notice the item being dropped very slowly. The issue seems to be gone if there is a dropped item nearby that the allays are looking for but can't reach it because they are tied to a fence. This might be caused by allays prioritizing to take items before following the player according to the allay.json behavior file, so the lag occurs again as soon as the item that they are trying to reach is gone. If you remove the items from all of the allays, the lag should be gone too. I hope this will be fixed soon.
This bug still occurs in 1.20.1
I know a free app from playstore to check celluler NAT type. The app name is STUNner. With that app help, i figured out that "symetric NAT" makes no one can join my world (not in the same LAN) and i also can't join anyone's world through xbox live service. However, when i use a VPN, it changes my NAT into "full cone". With this full cone NAT, i can join anyone's world that's not using symetric NAT but anyone that are trying to join my world will be stuck at locating server. Their names are shown on the pause menu but their character's locations are sometimes unknown and it's almost impossible to interact with them when they are actually still stuck at the locating server. Btw i get the symetric NAT type whenever i'm using my home wifi and my mom's hotspot.
Then i decided to use data celluler on my phone and my sister's phone using the 1.17.0.52 beta because my data celluler's NAT type is "port restricted cone" and my sister's data celluler is having the same NAT type because we were using the same ISP. I'm using this beta version because in this beta we can now host a multiplayer world using data celluler. And it WORKS properly. I can join my sister's world and she can join mine too without the need to use any vpn and there was no stuck at locating server.
My conclusion after doing these tests is it seems like symetrict NAT type is the culprit. I hope the devs will notice this and will be able to fix it because some ISP are using the symetrict NAT as their service including my wifi's ISP 😞
sorry if this comment is too long, messy and gramatically bad
This might be a separate bug, but i see a similar bug report being marked as duplicate to this report. If your screen freezes a bit for every 5 seconds, it might be due to your internal storage has no more than 500ish mb left. The issue seems to be gone when i give more empty space to my internal storage. There is also another bug that causes massive amount of lag (screen freezes for quite a long time and you can't do anything) if you put Minecraft application to an external storage such as SD Card. In my case, i'm using an old and pretty slow SD Card though. I recommend putting the Minecraft app in your internal storage as it solved the issue for me.